InstrCi - case-insensitive string search

[jj2007]

I'm wondering why the last version of InString-JJ  is so slow
for my  Test 13 --Find 'Duplicate inc' in 'windows.inc' -
clocks: 844498 against clocs: 679641 of previous version

Latest version is a byte scanner again, so it runs an ultrafast inner SSE2 loop with D instead of Du - at the expense of many false hits that forces it to run slow code in the bsf loop (there are more than 18,000 uppercase D in windows.inc). Try replacing Duplicate with WARNING...

The new package (the one that produces the table) has both versions. InStringJJw is the word scanner explained here, while the first example of the more recent byte scanner version is at the bottom of that page. As the tables show, they are roughly equivalent. If the search string starts with a rare character, the byte scanner rocks, of course.

The version attached contains the file test. Try playing with the WindInc patterns :wink

Code Select Expand

Intel(R) Celeron(R) M CPU        420  @ 1.60GHz (SSE3)
Type        Short   Medium HighAnsi MisMatch MisMatch     File  Overall
Source    Mainstr  Mainstr  Mainstr mismatch mismatch  fbuffer  sum of
Pattern   Substr1  Substr2  Substr4  mmStr_b  mmStr_x  WindInc  cycles*
======== ======== ======== ======== ======== ======== ======== ========
OVH           264        0        0        0        0        0      264
InStrL         36       36      264       12      120  1558560      468
InstrM32      192      240      408      168      384  3035448     1392
finstr         48       84      300       24      300  2806320      756
finstr2        48       60      204       24      204  2342100      540
finstr3        48       60      204       24      192  2353740      528
finstr4        36       72      312       24      312  3027360      756
finstr5        36       96      372       24      348  3315468      876
finstr6        48       60      204       24      204  2342112      540
InstrJJ        48       72       96       60      108   815556      384
InstrJJw       36       60      108       48      120   667620      372

* not including file test
[attachment deleted by admin]

[UtillMasm]

Code Select Expand

c:\china>"C:\Program Files\Microsoft SDKs\Windows\v6.0\VC\Bin\ml.exe" /c /coff
instrnew.asm
Microsoft (R) Macro Assembler Version 8.00.50727.762
Copyright (C) Microsoft Corporation.  All rights reserved.

Assembling: instrnew.asm

c:\china>\masm32\bin\link.exe /subsystem:console instrnew.obj
Microsoft (R) Incremental Linker Version 5.12.8078
Copyright (C) Microsoft Corp 1992-1998. All rights reserved.


c:\china>instrnew.exe
Genuine Intel(R) CPU           T2400  @ 1.83GHz (SSE3)
Type        Short   Medium HighAnsi MisMatch MisMatch     File  Overall
Source    Mainstr  Mainstr  Mainstr mismatch mismatch  fbuffer  sum of
Pattern   Substr1  Substr2  Substr4  mmStr_b  mmStr_x  WindInc  cycles*
======== ======== ======== ======== ======== ======== ======== ========
OVH           264        0        0        0        0        0      264
InStrL         33       33      264       11      110  1577950      451
InstrM32      253      275      495      187      407  3063731     1617
finstr         44       88      297       22      297  2874828      748
finstr2        55       66      209       33      198  2409429      561
finstr3        44       66      198       33      187  2414093      528
finstr4        44       77      319       22      308  3129148      770
finstr5        44       77      330       22      330  3298768      803
finstr6        55       66      209       33      198  2410782      561
InstrJJ        44       66       99       55      110   808071      374
InstrJJw       33       55       99       44      121   687203      352

* not including file test

Sizes:
Mainstr         100
Substr1         4
Substr2         7
Substr4         9

mismatch        100
mmStr_b         5
mmStr_x         5

File            874032
WindInc         13 = Duplicate inc

Press any key to exit...
c:\china>

[lingo]

I can't start included exe from  InstrNewSSE_FileTest.zip (see attachment)

Code Select Expand


Intel(R) Core(TM)2 Duo CPU     E8500  @ 3.16GHz (SSE4)

Search Test 1 - value expected 37; lenSrchPattern ->22
InString - JJb:                         38 ; clocks: 86
InString - JJw:                         38 ; clocks: 92
SrchBytes -  Lingo:                     37 ; clocks: 49

Search Test 2 - value expected 1007; lenSrchPattern ->17
InString - JJb:                         1008 ; clocks: 13628
InString - JJw:                         1008 ; clocks: 11236
SrchBytes -  Lingo:                     1007 ; clocks: 11592

Search Test 3 - value expected 1008 ;lenSrchPattern ->16
InString - JJb:                         1009 ; clocks: 303
InString - JJw:                         1009 ; clocks: 658
SrchBytes -  Lingo:                     1008 ; clocks: 135

Search Test 4 - value expected 1008 ;lenSrchPattern ->16
InString - JJb:                         1009 ; clocks: 3108
InString - JJw:                         1009 ; clocks: 3634
SrchBytes -  Lingo:                     1008 ; clocks: 1544

Search Test 5 - value expected 1008 ;lenSrchPattern ->16
InString - JJb:                         1009 ; clocks: 1822
InString - JJw:                         1009 ; clocks: 2470
SrchBytes -  Lingo:                     1008 ; clocks: 1273

Search Test 6 - value expected 1008 ;lenSrchPattern ->16
InString - JJb:                         1009 ; clocks: 303
InString - JJw:                         1009 ; clocks: 640
SrchBytes -  Lingo:                     1008 ; clocks: 130

Search Test 7 - value expected 1009 ;lenSrchPattern ->14
InString - JJb:                         1010 ; clocks: 567
InString - JJw:                         1010 ; clocks: 597
SrchBytes -  Lingo:                     1009 ; clocks: 523

Search Test 8 - value expected 1001 ;lenSrchPattern ->1
InString - JJb:                         1002 ; clocks: 265
InString - JJw:                         1002 ; clocks: 326
SrchBytes -  Lingo:                     1001 ; clocks: 93

Search Test 9 - value expected 1001 ;lenSrchPattern ->2
InString - JJb:                         1002 ; clocks: 256
InString - JJw:                         1002 ; clocks: 611
SrchBytes -  Lingo:                     1001 ; clocks: 96

Search Test 10 - value expected 1001 ;lenSrchPattern ->3
InString - JJb:                         1002 ; clocks: 257
InString - JJw:                         1002 ; clocks: 609
SrchBytes -  Lingo:                     1001 ; clocks: 97

Search Test 11 - value expected 1001 ;lenSrchPattern ->4
InString - JJb:                         1002 ; clocks: 257
InString - JJw:                         1002 ; clocks: 613
SrchBytes -  Lingo:                     1001 ; clocks: 96

Search Test 12 - value expected 1001 ;lenSrchPattern ->5
InString - JJb:                         1002 ; clocks: 265
InString - JJw:                         1002 ; clocks: 771
SrchBytes -  Lingo:                     1001 ; clocks: 97

Search Test 13 --Find 'Duplicate inc' in 'windows.inc' ;lenSrchPattern ->13
InString - JJb:                         1127625 ; clocks: 845967
InString - JJw:                         1127625 ; clocks: 665849
SrchBytes -  Lingo:                     1127624 ; clocks: 510086

Search Test 14 --Find 'warning or' in 'windows.inc' ;lenSrchPattern ->10
InString - JJb:                         1127404 ; clocks: 362831
InString - JJw:                         1127404 ; clocks: 665390
SrchBytes -  Lingo:                     1127403 ; clocks: 207779

Press ENTER to exit...
[attachment deleted by admin]

[jj2007]

I can't start included exe from  InstrNewSSE_FileTest.zip (see attachment)

Strange. It's your own algo - I swear I didn't modify a single byte. Maybe a problem with Vista?

Your timings look good. When will you post code? I guess I can speak for everybody when I say we are curious :bg

[UtillMasm]

on my 'Microsoft Windows Vista Ultimate 32bit english with Service Pack 1' is ok.

[lingo]

"Strange. It's your own algo - I swear I didn't modify a single byte."

I'm not a newbie to talk with me this way...
Your "old" instrings work for me OK (see the results.txt in every subdir)
Your last two tests do not work for me and I have no time to dig in
your macros.


UtillMasm,

I am with Vista Ultimate 64 bit with SP 1



[attachment deleted by admin]

[UtillMasm]

oh my fo!

i have assume you with 32bit. :lol

[jj2007]

"Strange. It's your own algo - I swear I didn't modify a single byte."

I have no time to dig in your macros.

Just to avoid embarrassing copyright battles: the macros are JimG (TM). And they work on almost all PCs... :bg

[Jimg]

Just to remove any misunderstanding, they are not trademarked, they are free for any use whatsoever, and the printing macros were mods of some code originally written by Phil.  (wonder what ever happen to Phil?)

[dedndave]

we don't support 64 bit OS's here at MASM32
MS doesn't support us - we don't have to support them  :P

[jj2007]

It was a bit tricky, but I managed to get Lingo's byte shift Boyer-Moore algo on board:

Code Select Expand

Intel(R) Celeron(R) M CPU        420  @ 1.60GHz (SSE3)
Type        Short   Medium HighAnsi MisMatch MisMatch     File  Overall
Source    Mainstr  Mainstr  Mainstr mismatch mismatch  fbuffer  sum of
Pattern   Substr1  Substr2  Substr4  mmStr_b  mmStr_x  WindInc  cycles*
======== ======== ======== ======== ======== ======== ======== ========
OVH           264        0        0        0        0        0      264
InstrM32      192      240      408      168      384  3034608     1392
finstr2        48       60      204       24      216  2342292      552
finstr3        48       60      204       24      216  2355540      552
finstr6        48       60      204       24      204  2342484      540
InStrL         36       36      264       12      120  1557576      468
InstrJJ        48       72      108       60       96   815124      384
InstrJJw       36       60      108       48      120   665688      372
BMLinDB         0        0      168        0        0   941484      168

Note:
a) 0 cycles means the pattern was too short for Lingo's algo - minimum is 8 bytes.
b) Lingo's code had to be modified for purely technical reasons - the macros supplied by JimG/Phil require 2 args instead of 3.

Warning: The executable has no idea on which drive your \masm32\include\windows.inc sits. Therefore extract the exe's to the same drive as your Masm32 installation, and run it from there.

EDIT: Error check added. Watch out for e after the cycle count.

[attachment deleted by admin]

[fearless]

Code Select Expand

Intel(R) Core(TM)2 Quad  CPU   Q9550  @ 2.83GHz (SSE4)
Type        Short   Medium HighAnsi MisMatch MisMatch     File  Overall
Source    Mainstr  Mainstr  Mainstr mismatch mismatch  fbuffer  sum of
Pattern   Substr1  Substr2  Substr4  mmStr_b  mmStr_x  WindInc  cycles*
======== ======== ======== ======== ======== ======== ======== ========
OVH           229        0        0        0        0        0      229
InstrM32      128      162      324      111      306  2664793     1031
finstr2        26       43      187       18      136  1876070      410
finstr3        34       43      128       17      128  1918850      350
finstr6        26       43      145       17      128  1873902      359
InStrL         17       26      179        9       68  1328491      299
InstrJJ        26       34       51       34       43   651534      188
InstrJJw       17       43       68       26       85   498678      239
BMLinDB         0        0      102        0        0   847875      102

* not including file test

Sizes:
Mainstr         100
Substr1         4
Substr2         7
Substr4         9

mismatch        100
mmStr_b         5
mmStr_x         5

File            851328
WindInc         13 = Duplicate inc

[UtillMasm]

Code Select Expand

c:\china>"\Program Files\Microsoft SDKs\Windows\v6.0\VC\Bin\ml.exe" /c /coff instrnew.asm
Microsoft (R) Macro Assembler Version 8.00.50727.762
Copyright (C) Microsoft Corporation.  All rights reserved.

Assembling: instrnew.asm

c:\china>\masm32\bin\link.exe /subsystem:console instrnew.obj
Microsoft (R) Incremental Linker Version 5.12.8078
Copyright (C) Microsoft Corp 1992-1998. All rights reserved.


c:\china>instrnew.exe
Genuine Intel(R) CPU           T2400  @ 1.83GHz (SSE3)
Type        Short   Medium HighAnsi MisMatch MisMatch     File  Overall
Source    Mainstr  Mainstr  Mainstr mismatch mismatch  fbuffer  sum of
Pattern   Substr1  Substr2  Substr4  mmStr_b  mmStr_x  WindInc  cycles*
======== ======== ======== ======== ======== ======== ======== ========
OVH           264        0        0        0        0        0      264
InstrM32      209      242      429      187      407  3089163     1474
finstr2        55       66      242       33      209  2425984      605
finstr3        44       66      198       33      187  2434069      528
finstr6        55       66      198       33      198  2423784      550
InStrL         44       33      253       11      121  1559305      462
InstrJJ        44       66       99       55      110   812658      374
InstrJJw       33       55       99       44      110   697653      341
BMLinDB       -11        0      165        0        0   660748      154

* not including file test

Sizes:
Mainstr         100
Substr1         4
Substr2         7
Substr4         9

mismatch        100
mmStr_b         5
mmStr_x         5

File            874031
WindInc         13 = Duplicate inc

Press any key to exit...
c:\china>

[jj2007]

Error check added, see attachment above. Watch out for e after the cycle count:

Code Select Expand


Intel(R) Celeron(R) M CPU        420  @ 1.60GHz (SSE3)
Type        Short   Medium HighAnsi MisMatch MisMatch     File  Overall
Source    Mainstr  Mainstr  Mainstr mismatch mismatch  fbuffer  sum of
Pattern   Substr1  Substr2  Substr4  mmStr_b  mmStr_x  WindInc  cycles*
======== ======== ======== ======== ======== ======== ======== ========
OVH           264        0        0        0        0        0      264
InstrM32      192      216      408      168      384  3034320     1368
finstr2        48       72      204       24      204  2343300      552
finstr3        48       72      204       24      192  2350572      540
finstr6        48       72      204       24      204  2342664      552
InStrL         36       48      264       12      120 1558824e      480
InstrJJ        48       96      120       48       84   813828      396
InstrJJw       36       60      108       36      108   667296      348
BMLinDB        0e      132      168        0       0e   947220      300

* not including file test

Sizes:
Mainstr         100
Substr1         4
Substr2         9
Substr4         9

mismatch        100
mmStr_b         5
mmStr_x         5

File            849788
WindInc         13 = Duplicate inc

Note 0e is not an error - this algo was not designed for simple string searches and needs at least an 8-byte pattern. The overall cycle count is not valid in this case, of course.

[UtillMasm]

Code Select Expand

c:\china>instrnew.exe
Genuine Intel(R) CPU           T2400  @ 1.83GHz (SSE3)
Type        Short   Medium HighAnsi MisMatch MisMatch     File  Overall
Source    Mainstr  Mainstr  Mainstr mismatch mismatch  fbuffer  sum of
Pattern   Substr1  Substr2  Substr4  mmStr_b  mmStr_x  WindInc  cycles*
======== ======== ======== ======== ======== ======== ======== ========
OVH           264      -11      -11        0        0        0      242
InstrM32      198      253      429      187      396  3053754     1463
finstr2        55       66      209       33      198  2415127      561
finstr3        44       66      198       22      187  2429416      517
finstr6        55       66      198       33      198  2424917      550
InStrL         33       44      253       11      121  1577477      462
InstrJJ        44       66       99       44       77   808027      330
InstrJJw       33       66       99       33       99   683859      330
BMLinDB        0e      121      165      -11       0e   649583      275

* not including file test

Sizes:
Mainstr         100
Substr1         4
Substr2         9
Substr4         9

mismatch        100
mmStr_b         5
mmStr_x         5

File            874029
WindInc         13 = Duplicate inc

Press any key to exit...
c:\china>