Python & fast Instr()

[jj2007]

Quora:

In Python, how do you search for a substring in a giant string?
...
I made a 1GB+ string and timed searching for a substring which appears at the very end of the string:
Under 1 second on my MacBook Pro

Obviously, that tempted me ;-)

include \masm32\MasmBasic\MasmBasic.inc         ; download
bytes=160000000         ; adapt to your HeapAlloc limits
uselib ShlWapi
  Init
  PrintCpu 0
  Let esi=New$(bytes)           ; create a fat buffer
  Let edi=String$(20000,"x")    ; and a small one with xxx
  mov ebx, esi
  For_ ecx=1 To bytes/20000-1
        invoke MbCopy, ebx, edi, 20000  ; fill the buffer
        xchg eax, ebx
  Next
  invoke MbCopyz, ebx, Chr$("There it is")      ; add the string to search for

  NanoTimer()                           ; time it
  mov edx, bytes                ; pass total length of string in edx
  Print Str$("fast Instr_ at\t%i: ", Instr_(FAST, esi, "it is", 64))
  PrintLine NanoTimer$()

  NanoTimer()
  Print Str$("slow Instr_ at\t%i: ", Instr_(esi, "it is"))      ; slow Instr_()
  PrintLine NanoTimer$()

  NanoTimer()
  Print Str$("Masm32 find$ at\t%i: ", find$(1, esi, "it is"))   ; slow
  PrintLine NanoTimer$()

  NanoTimer()
  invoke crt_strstr, esi, Chr$("it is")
  sub eax, esi
  Print Str$("CRT strstr at\t%i: ", eax)        ; slow
  PrintLine NanoTimer$(), CrLf$, CrLf$, "case-insensitive:"

  NanoTimer()                           ; time it
  mov edx, bytes                ; pass total length of string in edx
  Print Str$("fast Instr_ at\t%i: ", Instr_(FAST, esi, "there it is", 64+2))
  PrintLine NanoTimer$(), " (only first character case-insensitive)"

  NanoTimer()
  Print Str$("slow Instr_ at\t%i: ", Instr_(esi, "there it is", 1))     ; slow Instr_()
  PrintLine NanoTimer$(), " (full case-insensitive search)"

;   NanoTimer()
;   Print Str$("Masm32 match at\t%i: ", find$(1, esi, "there it is"))   ; no such function
;   PrintLine NanoTimer$()

  NanoTimer()
  lea edx, [esi+bytes-1000000]
  push edx
  invoke StrStrIA, edx, Chr$("there it is")
  pop edx
  sub eax, edx
  Print Str$("StrStrIA at\t%i: ", eax)
  Print NanoTimer$(), " (shortened because it's utterly slow)"
EndOfCode

Output:

Code Select Expand

Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
fast Instr_ at  1599980007: 171 ms
slow Instr_ at  1599980007: 1504 ms
Masm32 find$ at 1599980007: 1748 ms
CRT strstr at   1599980006: 1331 ms

case-insensitive:
fast Instr_ at  1599980001: 164 ms (only first character case-insensitive)
slow Instr_ at  1599980001: 1492 ms (full case-insensitive search)
StrStrIA at     980000: 223 ms (shortened because it's utterly slow)

P.S.: Recently, I upgraded my RAM from 4 to 6 GB. Before, I could HeapAlloc about 800MB, not it's about 1.6GB, sometimes even 1.8 :t

[ragdog]

8 GB ram installed

Code Select Expand

AMD A4-7210 APU with AMD Radeon R3 Graphics
fast Instr_ at  1599980007: 290 ms
slow Instr_ at  1599980007: 2817 ms
Masm32 find$ at 1599980007: 2277 ms
CRT strstr at   1599980006: 2625 ms

case-insensitive:
fast Instr_ at  1599980001: 291 ms (only first character case-insensitive)
slow Instr_ at  1599980001: 2823 ms (full case-insensitive search)
StrStrIA at     980000: 377 ms (shortened because it's utterly slow)


[sinsi]

Code Select Expand

Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
fast Instr_ at  1599980007: 110 ms
slow Instr_ at  1599980007: 677 ms
Masm32 find$ at 1599980007: 674 ms
CRT strstr at   1599980006: 710 ms

case-insensitive:
fast Instr_ at  1599980001: 107 ms (only first character case-insensitive)
slow Instr_ at  1599980001: 678 ms (full case-insensitive search)
StrStrIA at     980000: 98 ms (shortened because it's utterly slow)

[zedd151]

OK, I'll weigh in..

Code Select Expand


AMD A6-9220e RADEON R4, 5 COMPUTE CORES 2C+3G
fast Instr_ at  1599980007: 288 ms
slow Instr_ at  1599980007: 1856 ms
Masm32 find$ at 1599980007: 1864 ms
CRT strstr at   1599980006: 1948 ms

case-insensitive:
fast Instr_ at  1599980001: 289 ms (only first character case-insensitive)
slow Instr_ at  1599980001: 1851 ms (full case-insensitive search)
StrStrIA at     980000: 266 ms (shortened because it's utterly slow)

Windows 7 Pro, 32 bit btw.

[zedd151]

These AMD's seem to be really slow.   :(

[LiaoMi]

32 GB ram installed

Code Select Expand


Intel(R) Core(TM) i7-4810MQ CPU @ 2.80GHz
fast Instr_ at  1599980007: 136 ms
slow Instr_ at  1599980007: 795 ms
Masm32 find$ at 1599980007: 788 ms
CRT strstr at   1599980006: 822 ms

case-insensitive:
fast Instr_ at  1599980001: 114 ms (only first character case-insensitive)
slow Instr_ at  1599980001: 798 ms (full case-insensitive search)
StrStrIA at     980000: 121 ms (shortened because it's utterly slow)

[jj2007]

32 GB ram installed

That's quite a lot! Can you test where is the limit? Run the exe from a DOS prompt as PythonSearch.exe 2.0 meaning "try to allocate 2GB". Without a commandline arg, 1GB is assumed.

[LiaoMi]

 

from a DOS prompt as PythonSearch.exe 2.0

Code Select Expand

Intel(R) Core(TM) i7-4810MQ CPU @ 2.80GHz
trying with 1.00 GB
fast Instr_ at  1073720007: 109 ms
slow Instr_ at  1073720007: 1038 ms
Masm32 find$ at 1073720007: 805 ms
CRT strstr at   1073720006: 842 ms

case-insensitive:
fast Instr_ at  1073720001: 105 ms (only first character case-insensitive)
slow Instr_ at  1073720001: 908 ms (full case-insensitive search)
StrStrIA at     978176: 187 ms (shortened because it's utterly slow)

no matter how I enter, always displays a message "trying with 1.00 GB"

[jj2007]

You are running it with the default 1GB. Can you go higher, e.g. *.exe 1.99? I wonder if HeapAlloc can accept values >2.0 GB (it's 32-bit code) (see also Raymond Chen on A 32-bit application can allocate more than 4GB of memory, and you don't need 64-bit Windows to do it)

On my 12GB machine, 1.67 GB is the max:

Code Select Expand

Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
trying with 1.67 GB
fast Instr_ at  1793120007: 199 ms
slow Instr_ at  1793120007: 1688 ms
Masm32 find$ at 1793120007: 1937 ms
CRT strstr at   1793120006: 1508 ms

case-insensitive:
fast Instr_ at  1793120001: 185 ms (only first character case-insensitive)
slow Instr_ at  1793120001: 1665 ms (full case-insensitive search)
StrStrIA at     971154: 220 ms (shortened because it's utterly slow)

[LiaoMi]

1.99 -  :( Fatal Error - HeapAlloc

PythonSearch 1.52 -  is the max

Code Select Expand

Intel(R) Core(TM) i7-4810MQ CPU @ 2.80GHz
trying with 1.52 GB
fast Instr_ at  1632060007: 117 ms
slow Instr_ at  1632060007: 819 ms
Masm32 find$ at 1632060007: 791 ms
CRT strstr at   1632060006: 833 ms

case-insensitive:
fast Instr_ at  1632060001: 122 ms (only first character case-insensitive)
slow Instr_ at  1632060001: 825 ms (full case-insensitive search)
StrStrIA at     972428: 132 ms (shortened because it's utterly slow)

[jj2007]

Hutch will be happy to see that even with 32GB of RAM, you can allocate only 1.5GB in a 32-bit process :P

[TimoVJL]

Windows 7 x64 8 GB

Code Select Expand

PythonSearch2.exe 1.99
AMD Athlon(tm) II X2 220 Processor
trying with 1.99 GB
fast Instr_ at  2136720007: 396 ms
slow Instr_ at  2136720007: 2712 ms
Masm32 find$ at 2136720007: 2949 ms
CRT strstr at   2136720006: 2370 ms

case-insensitive:
fast Instr_ at  2136720001: 398 ms (only first character case-insensitive)
slow Instr_ at  2136720001: 2720 ms (full case-insensitive search)
StrStrIA at     973770: 227 ms (shortened because it's utterly slow)


[jj2007]

Wow! What you get with 2.01?

[TimoVJL]

After 1.99 it fallback to 1 GB.
Forgot to mention of using a editbin.exe /LARGEADDRESSAWARE PythonSearch2.exe
without it 1.78 GB

[LiaoMi]

After 1.99 it fallback to 1 GB.
Forgot to mention of using a editbin.exe /LARGEADDRESSAWARE PythonSearch2.exe
without it 1.78 GB

Sorry, forgot to allow >2GB :icon_redface:

This one allows >2GB and is linked with /LARGEADDRESSAWARE

Code Select Expand

Intel(R) Core(TM) i7-4810MQ CPU @ 2.80GHz
trying with 1.99 GB
fast Instr_ at  2136720007: 154 ms
slow Instr_ at  2136720007: 1093 ms
Masm32 find$ at 2136720007: 1053 ms
CRT strstr at   2136720006: 1091 ms

case-insensitive:
fast Instr_ at  2136720001: 171 ms (only first character case-insensitive)
slow Instr_ at  2136720001: 1062 ms (full case-insensitive search)
StrStrIA at     973770: 122 ms (shortened because it's utterly slow)

> 2 Gb
---------------------------
Fatal error:
---------------------------
Insufficient buffer or New$(<=0)
---------------------------
OK   
---------------------------