Author Topic: Python & fast Instr()  (Read 1792 times)

jj2007

  • Moderator
  • Member
  • *****
  • Posts: 9782
  • Assembler is fun ;-)
    • MasmBasic
Python & fast Instr()
« on: January 24, 2019, 08:03:02 PM »
Quora:
Quote
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]
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

  • Member
  • ****
  • Posts: 610
Re: Python & fast Instr()
« Reply #1 on: January 24, 2019, 08:17:14 PM »
8 GB ram installed

Code: [Select]
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

  • Member
  • *****
  • Posts: 1185
Re: Python & fast Instr()
« Reply #2 on: January 24, 2019, 08:25:10 PM »
Code: [Select]
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)
I can walk on water but stagger on beer bourbon.

zedd151

  • Member
  • ****
  • Posts: 870
Re: Python & fast Instr()
« Reply #3 on: January 25, 2019, 06:25:40 AM »
OK, I'll weigh in..

Code: [Select]
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.
I'm not always the sharpest knife in the drawer, but I have my moments.  :P

zedd151

  • Member
  • ****
  • Posts: 870
Re: Python & fast Instr()
« Reply #4 on: January 25, 2019, 06:26:59 AM »
These AMD's seem to be really slow.   :(
I'm not always the sharpest knife in the drawer, but I have my moments.  :P

LiaoMi

  • Member
  • ****
  • Posts: 593
Re: Python & fast Instr()
« Reply #5 on: January 26, 2019, 10:17:36 PM »
32 GB ram installed
Code: [Select]
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

  • Moderator
  • Member
  • *****
  • Posts: 9782
  • Assembler is fun ;-)
    • MasmBasic
Re: Python & fast Instr()
« Reply #6 on: January 27, 2019, 12:11:01 AM »
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

  • Member
  • ****
  • Posts: 593
Re: Python & fast Instr()
« Reply #7 on: January 27, 2019, 12:39:43 AM »
 :biggrin:

Quote
from a DOS prompt as PythonSearch.exe 2.0

Code: [Select]
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

  • Moderator
  • Member
  • *****
  • Posts: 9782
  • Assembler is fun ;-)
    • MasmBasic
Re: Python & fast Instr()
« Reply #8 on: January 27, 2019, 12:41:50 AM »
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]
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

  • Member
  • ****
  • Posts: 593
Re: Python & fast Instr()
« Reply #9 on: January 27, 2019, 12:49:45 AM »
1.99 -  :( Fatal Error - HeapAlloc

PythonSearch 1.52 -  is the max

Code: [Select]
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

  • Moderator
  • Member
  • *****
  • Posts: 9782
  • Assembler is fun ;-)
    • MasmBasic
Re: Python & fast Instr()
« Reply #10 on: January 27, 2019, 12:57:22 AM »
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

  • Member
  • ***
  • Posts: 476
Re: Python & fast Instr()
« Reply #11 on: January 27, 2019, 01:28:19 AM »
Windows 7 x64 8 GB
Code: [Select]
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)
May the source be with you

jj2007

  • Moderator
  • Member
  • *****
  • Posts: 9782
  • Assembler is fun ;-)
    • MasmBasic
Re: Python & fast Instr()
« Reply #12 on: January 27, 2019, 02:27:19 AM »
Wow! What you get with 2.01?

TimoVJL

  • Member
  • ***
  • Posts: 476
Re: Python & fast Instr()
« Reply #13 on: January 27, 2019, 02:52:07 AM »
After 1.99 it fallback to 1 GB.
Forgot to mention of using a editbin.exe /LARGEADDRESSAWARE PythonSearch2.exe
without it 1.78 GB
May the source be with you

LiaoMi

  • Member
  • ****
  • Posts: 593
Re: Python & fast Instr()
« Reply #14 on: January 27, 2019, 04:52:20 AM »
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]
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   
---------------------------