INSTR performance

[David Roberts]

Is this OK?

to

! mov ebx, LenMainString              'Length of long string
! Sub ebx, LenSubString               'Calculate last location to look at for start of a match,
[COLOR="Blue"]! js xit                              'If LenSubString > LenMainString[/COLOR]
! Add ebx, esi                        'after this point the short string can't match because there aren't enough characters

[Pierre Bellisle]

Nice!
Look's good to me...


[Added]
Does anybody knows where to find a really good assembler reference ?

I mean all recents Intel/AMD opcodes with CPU restriction
and concise explanation of what the opcode does.
For example, many I found on the net do not have JS.

[David Roberts]

The following is a link to a pdf download

OpCode of Intel Assembly 80x86 Mnemonics

Found a bug in your version of Instr2, Pierre.

! mov edi, pSubString                 'Pointer to start of short string
! mov esi, pMainString                'Pointer to start of long string
! Add esi, StartPos                   'Add starting position

! mov ebx, LenMainString              'Length of long string
! Sub ebx, LenSubString               'Calculate last location to look at for start of a match,
! js xit                              'If LenSubString > LenMainString
! Add ebx, esi                        'after this point the short string can't match because there aren't enough characters

StartPos is added to esi prematurely. Ebx can end up past the end of MainString.

Ebx should be the same for any value of StartPos.

Change to

! mov edi, pSubString                 'Pointer to start of short string
! mov esi, pMainString                'Pointer to start of long string
 
! mov ebx, LenMainString              'Length of long string
! Sub ebx, LenSubString               'Calculate last location to look at for start of a match,
! js xit                              'If LenSubString > LenMainString
! Add ebx, esi                        'after this point the short string can't match because there aren't enough characters
! Add esi, StartPos                   'Add starting position

Added: The 'overun' in some cases was sufficient to effect speed. Instr2 is now faster than Boyer-Moore when SubString is less than 6.

[Paul Dixon]

Pierre,
not concise at all but explains all the instructions in detail, the Intel IA-32 Software Developer's Manual. It comes in about 5 volumes, you need Volumes 2A and 2B.

http://www.intel.com/products/processor/manuals/

Volume 2A:

http://download.intel.com/design/processor/manuals/253666.pdf

Volume 2B

http://download.intel.com/design/processor/manuals/253667.pdf

David,
I haven't followed this whole thread, I've been too busy recently, but I'm sure I can knock 30% off the original INSTR2 I posted, (at least for short search strings). I hope to get some code done in the next day or 2 or maybe 3.. .
It'll still be a straight forward "Search from the start" algorithm, nothing fancy like Boyer-Moore, but just more efficient than my original code.

From the little I've read about Boyer-Moore, almost any INSTR should beat it with small search strings. Boyer-Moore is only of real use when the string to be searched for is long, and has certain other characteristics, as it's only then that the algorithm can reliably skip forward and not need to read the whole of the string to be searched.

Paul.

[Pierre Bellisle]

David,
Thank for the link and the bug report.
I guess that 6 reveal Paul's excellent work.

Paul,
Thank for the links also.
I see Boyer-Moore the same way you do.
For me, since the size of both the Boyer-Moore and Instr2,
is insignificant compared to the final size of an exe,
I will keep a routine that have both of them and
programally switch accordingly to the substring lenght.
Best of both world.

I will stay around, I don't want to miss your next version,
great work...

[David Roberts]

Sounds good, Paul.

I don't know if you are considering a rewrite or a tweak but if the latter it is worth mentioning the 'lock up' encountered a little while back.

I've revised the test case to

SubString = String$(10000,0)
MainString = String$(10000-16, 0) + String$(16,1)

Both InStr and Boyer-Moore return almost immediately whereas, on my machine, INSTR2 returns in 16ms.

Changing the 10,000 to 100,000 both InStr and Boyer-Moore again return almost immediately with INSTR2 returning after 1188ms.

With 1,000,000 INSTR2 is clearly not 'locking-up' as thought and will probably return if we waited long enough but seems to get 'bogged down' with redundant calculation.

Added: Just for the hell of it I tried

SubString = String$(100000000,0)
MainString = String$(16,1) + String$(100000000, 0)

Boyer-Moore came back in 438ms, InStr in 234ms and INSTR2 in 109ms.

I've just deleted an 'oops'. I had StartPos for InStr as 60 so it didn't find SubString.

[David Roberts]

GOT IT!

With this test case I figured that we should only go past NoFind: twice - the first time by falling through and the second time after a jump but NoFind: was passed an enormous amount of times.

If we insert as follows

! dec esi 'Compensate for the following INC
NoFind:
! inc esi 'Point to next charater in string to restart the search from
! cmp esi, ebx
! jg xit ' not enough characters though, so not found

we pull out without further ado.

With

SubString = String$(100000000,0)
MainString = String$(100000000-16, 0) + String$(16,1)

InStr pulls out after 234ms, Boyer-Moore after 157ms and INSTR2 after 140ms.

So, Paul's code now reckons no match the fastest.

Added: However, , with MainString extended

SubString = String$(100000000,0)
MainString = String$(100000000-16,0) + String$(30,1)

InStr pulls out after 3266ms, Boyer-Moore after 172ms and INSTR after 1875ms.

Boyer-Moore likes big strings here too.

Short ones?

SubString = String$(5,5)
MainString = String$(100000000-16,0) + String$(30,1)

InStr at 219ms, Boyer-Moore at 62ms and INSTR2 at 47ms.

Here we have the less than 6 rule coming into play again.

[Pierre Bellisle]

Oups! Wrong thread....