The MASM Forum Archive 2004 to 2012
Welcome, Guest. Please login or register.
November 28, 2021, 11:23:05 PM

Login with username, password and session length
Search:     Advanced search
128553 Posts in 15254 Topics by 684 Members
Latest Member: mottt
* Home Help Search Login Register
+  The MASM Forum Archive 2004 to 2012
|-+  General Forums
| |-+  The Laboratory (Moderator: Mark_Larson)
| | |-+  Compare two strings
« previous next »
Pages: 1 [2] 3 4 ... 10 Print
Author Topic: Compare two strings  (Read 75634 times)
jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Compare two strings
« Reply #15 on: March 30, 2010, 11:21:51 PM »

Ok, misunderstanding ThumbsUp
Logged

qWord
Member
*****
Posts: 1425



Re: Compare two strings
« Reply #16 on: March 30, 2010, 11:27:37 PM »

Ok, misunderstanding ThumbsUp
yep ..  - maybe caused by my bad english  BigGrin
Logged

FPU in a trice: SmplMath
It's that simple!
jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Compare two strings
« Reply #17 on: March 30, 2010, 11:29:55 PM »

For Yvan TheHolyMan: These are the correct invokes for the standard Windows and CRT functions:

   invoke lstrcmp, esi, edi
   invoke crt_strcmp, esi, edi
Logged

qWord
Member
*****
Posts: 1425



Re: Compare two strings
« Reply #18 on: March 30, 2010, 11:44:27 PM »

just for addition: an version without string instructions (as hutch suggest):
Code:
    lea esi,sz1
    lea edi,sz2
    movzx eax,BYTE ptr [esi]
    movzx ebx,BYTE ptr [edi]
    .while eax == ebx
@@:     or eax,ebx
        jz @F
        inc esi
        inc edi
        movzx eax,BYTE ptr [esi]
        movzx ebx,BYTE ptr [edi]
    .endw
    .if 0
@@:     ; equal
    .else
        ; not equal     
    .endif
Logged

FPU in a trice: SmplMath
It's that simple!
jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Compare two strings
« Reply #19 on: March 31, 2010, 08:56:02 AM »

just for fun:
Code:
Intel(R) Pentium(R) 4 CPU 3.40GHz (SSE3)
4842    cycles for qWord, 1000 bytes
3746    cycles for movzx, 1000 bytes
6685    cycles for movzx check null, 1000 bytes
4192    cycles for repe cmpsb, 1000 bytes
31225   cycles for lstrcmp, 1000 bytes
3119    cycles for crt_strcmp, 1000 bytes

43      cycles for qWord, 10 bytes
32      cycles for movzx, 10 bytes
141     cycles for movzx check null, 10 bytes
123     cycles for repe cmpsb, 10 bytes
831     cycles for lstrcmp, 10 bytes
40      cycles for crt_strcmp, 10 bytes

As so often, the CRT function is damn fast, also taking into account that they check for nullbytes why "our" algos don't (with the exception of the movzx check null version).

* StrComp.zip (4.25 KB - downloaded 309 times.)
Logged

lingo
Member
*****
Posts: 625



Re: Compare two strings
« Reply #20 on: March 31, 2010, 02:25:06 PM »

Code:
Intel(R) Core(TM)2 Duo CPU     E8500  @ 3.16GHz (SSE4)
2542    cycles for qWord, 1000 bytes
2049    cycles for movzx, 1000 bytes
2032    cycles for LingoCMP, 1000 bytes
4036    cycles for movzx check null, 1000 bytes
4075    cycles for repe cmpsb, 1000 bytes
13431   cycles for lstrcmp, 1000 bytes
2807    cycles for crt_strcmp, 1000 bytes

15      cycles for LingoCMP, 10 bytes
25      cycles for qWord, 10 bytes
18      cycles for movzx, 10 bytes
33      cycles for movzx check null, 10 bytes
93      cycles for repe cmpsb, 10 bytes
836     cycles for lstrcmp, 10 bytes
27      cycles for crt_strcmp, 10 bytes

2524    cycles for qWord, 1000 bytes
2047    cycles for movzx, 1000 bytes
2026    cycles for LingoCMP, 1000 bytes
4039    cycles for movzx check null, 1000 bytes
4089    cycles for repe cmpsb, 1000 bytes
13416   cycles for lstrcmp, 1000 bytes
2789    cycles for crt_strcmp, 1000 bytes

15      cycles for LingoCMP, 10 bytes
25      cycles for qWord, 10 bytes
17      cycles for movzx, 10 bytes
34      cycles for movzx check null, 10 bytes
92      cycles for repe cmpsb, 10 bytes
846     cycles for lstrcmp, 10 bytes
27      cycles for crt_strcmp, 10 bytes

2530    cycles for qWord, 1000 bytes
2038    cycles for movzx, 1000 bytes
2032    cycles for LingoCMP, 1000 bytes
4039    cycles for movzx check null, 1000 bytes
4081    cycles for repe cmpsb, 1000 bytes
13491   cycles for lstrcmp, 1000 bytes
2798    cycles for crt_strcmp, 1000 bytes

15      cycles for LingoCMP, 10 bytes
25      cycles for qWord, 10 bytes
17      cycles for movzx, 10 bytes
33      cycles for movzx check null, 10 bytes
94      cycles for repe cmpsb, 10 bytes
843     cycles for lstrcmp, 10 bytes
28      cycles for crt_strcmp, 10 bytes


--- ok ---

* StrCompLingo.zip (4.71 KB - downloaded 320 times.)
Logged
hutch--
Administrator
Member
*****
Posts: 12013


Mnemonic Driven API Grinder


Re: Compare two strings
« Reply #21 on: March 31, 2010, 02:40:35 PM »

My only comment so far is why are these tests being done on such small samples, 10 bytes is "who cares" and 1k is very small, tests should also be run only much longer compares, a meg or larger. All you are testing with such short samples is the attack rate, not the sustain rate.
Logged

Regards,



Download site for MASM32
http://www.masm32.com
hutch--
Administrator
Member
*****
Posts: 12013


Mnemonic Driven API Grinder


Re: Compare two strings
« Reply #22 on: March 31, 2010, 03:34:58 PM »

Here is a quick dabble with an unroll of movzx.

Code:
Intel(R) Core(TM)2 Quad CPU    Q9650  @ 3.00GHz (SSE4)
2516    cycles for qWord, 1000 bytes
2023    cycles for movzx, 1000 bytes
2022    cycles for LingoCMP, 1000 bytes
2019    cycles for movzx unrolled, 1000 bytes xxxxxxxx
4059    cycles for repe cmpsb, 1000 bytes
13379   cycles for lstrcmp, 1000 bytes
2773    cycles for crt_strcmp, 1000 bytes

15      cycles for LingoCMP, 10 bytes
22      cycles for qWord, 10 bytes
26      cycles for movzx, 10 bytes
15      cycles for movzx unrolled, 10 bytes  zzzzzzzzzzzz
92      cycles for repe cmpsb, 10 bytes
393     cycles for lstrcmp, 10 bytes
27      cycles for crt_strcmp, 10 bytes

2359    cycles for qWord, 1000 bytes
2023    cycles for movzx, 1000 bytes
2019    cycles for LingoCMP, 1000 bytes
2018    cycles for movzx unrolled, 1000 bytes xxxxxxxx
4059    cycles for repe cmpsb, 1000 bytes
13401   cycles for lstrcmp, 1000 bytes
2776    cycles for crt_strcmp, 1000 bytes

15      cycles for LingoCMP, 10 bytes
25      cycles for qWord, 10 bytes
17      cycles for movzx, 10 bytes
15      cycles for movzx unrolled, 10 bytes  zzzzzzzzzzzz
92      cycles for repe cmpsb, 10 bytes
393     cycles for lstrcmp, 10 bytes
27      cycles for crt_strcmp, 10 bytes

2523    cycles for qWord, 1000 bytes
2026    cycles for movzx, 1000 bytes
2024    cycles for LingoCMP, 1000 bytes
2019    cycles for movzx unrolled, 1000 bytes xxxxxxxx
4053    cycles for repe cmpsb, 1000 bytes
13295   cycles for lstrcmp, 1000 bytes
2773    cycles for crt_strcmp, 1000 bytes

15      cycles for LingoCMP, 10 bytes
22      cycles for qWord, 10 bytes
26      cycles for movzx, 10 bytes
15      cycles for movzx unrolled, 10 bytes  zzzzzzzzzzzz
92      cycles for repe cmpsb, 10 bytes
393     cycles for lstrcmp, 10 bytes
27      cycles for crt_strcmp, 10 bytes


--- ok ---

* strcmp2.zip (10.14 KB - downloaded 318 times.)
Logged

Regards,



Download site for MASM32
http://www.masm32.com
lingo
Member
*****
Posts: 625



Re: Compare two strings
« Reply #23 on: March 31, 2010, 04:57:32 PM »

 wink
Code:
Intel(R) Core(TM)2 Duo CPU     E8500  @ 3.16GHz (SSE4)
2514    cycles for qWord, 1000 bytes
2033    cycles for movzx, 1000 bytes
1265    cycles for LingoCMP, 1000 bytes
2022    cycles for LingoCMP with check null, 1000 bytes
2019    cycles for movzx unrolled, 1000 bytes xxxxxxxx
4059    cycles for repe cmpsb, 1000 bytes
13251   cycles for lstrcmp, 1000 bytes
2776    cycles for crt_strcmp, 1000 bytes

8       cycles for LingoCMP, 10 bytes
15      cycles for LingoCMP with check null, 10 bytes
22      cycles for qWord, 10 bytes
26      cycles for movzx, 10 bytes
15      cycles for movzx unrolled, 10 bytes  zzzzzzzzzzzz
93      cycles for repe cmpsb, 10 bytes
825     cycles for lstrcmp, 10 bytes
27      cycles for crt_strcmp, 10 bytes

2358    cycles for qWord, 1000 bytes
2023    cycles for movzx, 1000 bytes
1266    cycles for LingoCMP, 1000 bytes
2021    cycles for LingoCMP with check null, 1000 bytes
2018    cycles for movzx unrolled, 1000 bytes xxxxxxxx
4058    cycles for repe cmpsb, 1000 bytes
13228   cycles for lstrcmp, 1000 bytes
2775    cycles for crt_strcmp, 1000 bytes

8       cycles for LingoCMP, 10 bytes
15      cycles for LingoCMP with check null, 10 bytes
25      cycles for qWord, 10 bytes
17      cycles for movzx, 10 bytes
15      cycles for movzx unrolled, 10 bytes  zzzzzzzzzzzz
92      cycles for repe cmpsb, 10 bytes
850     cycles for lstrcmp, 10 bytes
27      cycles for crt_strcmp, 10 bytes

2519    cycles for qWord, 1000 bytes
2026    cycles for movzx, 1000 bytes
1267    cycles for LingoCMP, 1000 bytes
2022    cycles for LingoCMP with check null, 1000 bytes
2019    cycles for movzx unrolled, 1000 bytes xxxxxxxx
4059    cycles for repe cmpsb, 1000 bytes
13223   cycles for lstrcmp, 1000 bytes
2785    cycles for crt_strcmp, 1000 bytes

8       cycles for LingoCMP, 10 bytes
15      cycles for LingoCMP with check null, 10 bytes
22      cycles for qWord, 10 bytes
26      cycles for movzx, 10 bytes
15      cycles for movzx unrolled, 10 bytes  zzzzzzzzzzzz
92      cycles for repe cmpsb, 10 bytes
843     cycles for lstrcmp, 10 bytes
27      cycles for crt_strcmp, 10 bytes


--- ok ---

* StrCmp3.zip (5.28 KB - downloaded 323 times.)
Logged
jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Compare two strings
« Reply #24 on: March 31, 2010, 06:42:39 PM »

Lingo, what about your old algo here?
Logged

jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Compare two strings
« Reply #25 on: March 31, 2010, 06:43:57 PM »

why are these tests being done on such small samples, 10 bytes is "who cares"

Pretty relevant for a string sort, though, don't you think?
Logged

clive
Hardcore x86, ARM and MIPS toolsmith
Member
*****
Posts: 1230


Project Looking Glass. Following the white rabbit.


Re: Compare two strings
« Reply #26 on: March 31, 2010, 07:55:09 PM »

Quote from: jj2007
Pretty relevant for a string sort, though, don't you think?

Well if you're doing sorts then perhaps we should move beyond a simple inequity test, and consider whether the string is actually greater,equal,smaller which is what strcmp() does.

-Clive
Logged

It could be a random act of randomness. Those happen a lot as well.
clive
Hardcore x86, ARM and MIPS toolsmith
Member
*****
Posts: 1230


Project Looking Glass. Following the white rabbit.


Re: Compare two strings
« Reply #27 on: March 31, 2010, 08:13:44 PM »

Quote from: jj2007
As so often, the CRT function is damn fast, also taking into account that they check for nullbytes why "our" algos don't (with the exception of the movzx check null version).

I'll note that the CRT algorithm has code to get string1 to be DWORD aligned during the bulk of the comparison. The key branch targets are also DWORD aligned, with the primary loop fitting within a single cache line.

-Clive
Logged

It could be a random act of randomness. Those happen a lot as well.
jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Compare two strings
« Reply #28 on: March 31, 2010, 11:08:13 PM »

Well if you're doing sorts then perhaps we should move beyond a simple inequity test, and consider whether the string is actually greater,equal,smaller which is what strcmp() does.
Good idea. Here is a new version, the StrCmpSSE proc returns in edx the position of the first mismatch, and in eax the difference of the mismatching bytes. It still needs some polishing (still no check for end of string as yet), but the timings look promising.

Code:
Intel(R) Celeron(R) M CPU        420  @ 1.60GHz (SSE3)
String comparison: short string 10 bytes, long string 4000
1070    cycles for SSE, long string
13702   cycles for qWord, long string
3266    cycles for Lingo, long string
12030   cycles for movzx, long string
24007   cycles for movzx check null, long string
16089   cycles for repe cmpsb, long string
72240   cycles for lstrcmp, long string
11139   cycles for crt_strcmp, long string

15      cycles for SSE, 10 bytes
43      cycles for qWord, 10 bytes
27      cycles for movzx, 10 bytes
51      cycles for movzx check null, 10 bytes
88      cycles for repe cmpsb, 10 bytes
456     cycles for lstrcmp, 10 bytes
47      cycles for crt_strcmp, 10 bytes

Codesizes:
Lingo:  365
SSE:    164

* StrCompSSE.zip (6.55 KB - downloaded 294 times.)
Logged

jj2007
Member
*****
Gender: Male
Posts: 6011



Re: Compare two strings
« Reply #29 on: April 01, 2010, 08:55:05 AM »

Here is the version with check for end of string. The timings suffer a bit, of course, but it is still a bit faster than Lingo's old algo, and a factor 5 faster than the CRT version.

Note that lstrcmp is slow because it performs additional tasks (MSDN, remarks section):
Quote
The lstrcmp function uses a word sort, rather than a string sort. A word sort treats hyphens and apostrophes differently than it treats other symbols that are not alphanumeric, in order to ensure that words such as "coop" and "co-op" stay together within a sorted list.
Code:
Intel(R) Pentium(R) 4 CPU 3.40GHz (SSE3)
String comparison: short string 10 bytes, long string 5050
3061    cycles for SSE with null check, long string
4977    cycles for Lingo, long string
15422   cycles for crt_strcmp, long string
34880   cycles for movzx check null, long string
20329   cycles for repe cmpsb, long string
174637  cycles for lstrcmp, long string

37      cycles for SSE with null check, 10 bytes
23      cycles for Lingo, 10 bytes
41      cycles for crt_strcmp, 10 bytes
98      cycles for movzx check null, 10 bytes
123     cycles for repe cmpsb, 10 bytes
679     cycles for lstrcmp, 10 bytes

Codesizes:
Lingo:  365
SSE:    190

* StrCompSSE.zip (6.31 KB - downloaded 323 times.)
Logged

Pages: 1 [2] 3 4 ... 10 Print 
« previous next »
Jump to:  

Powered by MySQL Powered by PHP The MASM Forum Archive 2004 to 2012 | Powered by SMF 1.0.12.
© 2001-2005, Lewis Media. All Rights Reserved.
Valid XHTML 1.0! Valid CSS!