InString Speed Test!

[hutch--]

I have rewritten the scanloop part of finstr using a different technique to determine if the 4 bytes being tested contain a null termniator or not. i have been testing against Lingo's latest which is a very fast algo but it does have some anomolies in terms of what is pointed at it and these make it inconsistent in its speed. The match loop is a lot faster in his latest version but for some reason it has problems with text that starts with a blank space " word " etc ...

I have not added the final part of finstr which is to test up to the last 3 bytes so in its current form it will miss a search pattern up to 3 bytes long if it is at the end of the source being searched. It does not effect any of the examples in the test piece.

These are the results on my dev PIV.

Code Select Expand


Source length = 185
Mismatch length = 290

280 finstr mismatch recovery
21 finstr short
81 finstr medium
128 finstr long
175 finstr end
----------------------
Short Search
----------------------
74 average finstr
114 average InStringL
----------------------
----------------------
Medium Search
----------------------
195 average finstr
173 average InStringL
----------------------
----------------------
Long Search
----------------------
385 average finstr
467 average InStringL
----------------------
------------------------------------------
Full Length search on high ANSI characters
------------------------------------------
353 average finstr
505 average InStringL
----------------------
----------------------
Mismatch Recovery Test
----------------------
1186 average finstr
1365 average InStringL
----------------------
Press any key to continue ...



[attachment deleted by admin]

[UlliN]

Hi,

that's my results on an AMD FX57

Code Select Expand


Source length = 185
Mismatch length = 290

280 finstr mismatch recovery
21 finstr short
81 finstr medium
128 finstr long
175 finstr end
----------------------
Short Search
----------------------
86 average finstr
86 average InStringL
----------------------
----------------------
Medium Search
----------------------
240 average finstr
111 average InStringL
----------------------
----------------------
Long Search
----------------------
464 average finstr
355 average InStringL
----------------------
------------------------------------------
Full Length search on high ANSI characters
------------------------------------------
426 average finstr
306 average InStringL
----------------------
----------------------
Mismatch Recovery Test
----------------------
1416 average finstr
928 average InStringL
----------------------
Press any key to continue ...

Ulli

[Jimg]

Good job Hutch.

Can you explain how this part works?

Code Select Expand

  ; ----------------------------------------------
  ; test if the next 4 bytes contain an ascii zero
  ; ----------------------------------------------
    add esi, 4
    mov edx, [esi]
    lea ecx, [edx-01010101h]
    not edx
    and ecx, esp        ; modify ECX
    test ecx, edx       ; test with no modify
    jnz no_match



The old method of doing one load of a double into edx and testing dl and dh  for example-

Code Select Expand


  ; ----------------------------------------
  ; test each byte for a patn 1st char match
  ; ----------------------------------------
    mov ebx,[esi]
    mov edx,[esi+2]
    sub bl,al
    jz si0
    sub bh,al
    jz si1
    sub dl,al
    jz si2
    sub dh,al
    jz si3

is faster on an AMD, but slower on the celeron.

One problem-

Try

    Mainstr db "The time has come the walrus said to speak of many things,"
            db " of birds and bugs and ceiling wax, of cabbages and kings."
            db " And if the sea is boiling hot and whether pigs have wings «¤»¼µþ®§© z",0

    Substr1  db "z",0
   
   
It never finds the "z"



Timing results:

Code Select Expand


your latest on AMD     latest code with old  your latest on        Old method on
Athlon XP 3000+         method of match as    Celeron 2.0 Ghz        Celeron
at 2.16 Ghz              above on AMD

Source length = 185    Source length = 185   Source length = 185   Source length = 185                                                 
Mismatch length = 290  Mismatch length = 290 Mismatch length = 290 Mismatch length = 290                                               
                                                                                                                                       
280 finstr mismatch r  280 finstr mismatch r 280 finstr mismatch r 280 finstr mismatch r                                               
21 finstr short        21 finstr short       21 finstr short       21 finstr short                                                     
81 finstr medium       81 finstr medium      81 finstr medium      81 finstr medium                                                     
128 finstr long        128 finstr long       128 finstr long       128 finstr long                                                     
175 finstr end         175 finstr end        175 finstr end        175 finstr end                                                       
---------------------  --------------------- --------------------- ---------------------                                               
Short Search           Short Search          Short Search          Short Search                                                         
---------------------  --------------------- --------------------- ---------------------                                               
110 average finstr     105 average finstr    70 average finstr     88 average finstr                                                   
113 average InStringL  113 average InStringL 112 average InStringL 116 average InStringL                                               
---------------------  --------------------- --------------------- ---------------------                                               
---------------------  --------------------- --------------------- ---------------------                                               
Medium Search          Medium Search         Medium Search         Medium Search                                                       
---------------------  --------------------- --------------------- ---------------------                                               
304 average finstr     255 average finstr    190 average finstr    239 average finstr                                                   
142 average InStringL  141 average InStringL 169 average InStringL 173 average InStringL                                               
---------------------  --------------------- --------------------- ---------------------                                               
---------------------  --------------------- --------------------- ---------------------                                               
Long Search            Long Search           Long Search           Long Search                                                         
---------------------  --------------------- --------------------- ---------------------                                               
478 average finstr     421 average finstr    388 average finstr    444 average finstr                                                   
377 average InStringL  377 average InStringL 461 average InStringL 453 average InStringL                                               
---------------------  --------------------- --------------------- ---------------------                                               
---------------------  --------------------- --------------------- ---------------------                                               
Full Length search on  Full Length search on Full Length search on Full Length search on                                               
---------------------  --------------------- --------------------- ---------------------                                               
557 average finstr     419 average finstr    345 average finstr    425 average finstr                                                   
539 average InStringL  539 average InStringL 502 average InStringL 492 average InStringL                                               
---------------------  --------------------- --------------------- ---------------------                                               
---------------------  --------------------- --------------------- ---------------------                                               
Mismatch Recovery Tes  Mismatch Recovery Tes Mismatch Recovery Tes Mismatch Recovery Tes                                               
---------------------  --------------------- --------------------- ---------------------                                               
1676 average finstr    1710 average finstr   1151 average finstr   1245 average finstr                                                 
1166 average InString  1168 average InString 1322 average InString 1309 average InString                                               
---------------------  --------------------- --------------------- ---------------------                                               
Press any key to cont  Press any key to cont Press any key to cont Press any key to cont                                               

So looking at the numbers, I would say your new method is the best overall if you fix the problem with finding the last character.

[hutch--]

Jim,

Thanks for doing all of the tests.

I posted the reason why above.

I have not added the final part of finstr which is to test up to the last 3 bytes so in its current form it will miss a search pattern up to 3 bytes long if it is at the end of the source being searched. It does not effect any of the examples in the test piece.

The block of code that determines if a null is within the 4 bytes read in is AND masking. Agner Fog used it in his classic StrLen algo. I used the preset value in ESP because its a normal speedup for Agner's algo.

[Jimg]

I posted the reason why above.

opps  :red

[MichaelW]

P3:

Code Select Expand


Source length = 185
Mismatch length = 290

280 finstr mismatch recovery
21 finstr short
81 finstr medium
128 finstr long
175 finstr end
----------------------
Short Search
----------------------
107 average finstr
114 average InStringL
----------------------
----------------------
Medium Search
----------------------
295 average finstr
191 average InStringL
----------------------
----------------------
Long Search
----------------------
503 average finstr
491 average InStringL
----------------------
------------------------------------------
Full Length search on high ANSI characters
------------------------------------------
561 average finstr
493 average InStringL
----------------------
----------------------
Mismatch Recovery Test
----------------------
1647 average finstr
1343 average InStringL
----------------------

Pentium D (family 15, model 4, stepping 7):

Code Select Expand


Source length = 185
Mismatch length = 290

280 finstr mismatch recovery
21 finstr short
81 finstr medium
128 finstr long
175 finstr end
----------------------
Short Search
----------------------
98 average finstr
96 average InStringL
----------------------
----------------------
Medium Search
----------------------
256 average finstr
180 average InStringL
----------------------
----------------------
Long Search
----------------------
434 average finstr
416 average InStringL
----------------------
------------------------------------------
Full Length search on high ANSI characters
------------------------------------------
518 average finstr
524 average InStringL
----------------------
----------------------
Mismatch Recovery Test
----------------------
1416 average finstr
1358 average InStringL
----------------------