Faster ByteArray search/loop

[Niya]

Sure, here it is:....

Thanks. Was a little busy over the weekend but I finally had time to dive into this today.

I've just tested looping a byte array to find a series of bytes, and it is slower than InStr but certainly "close". Some things to note:

1) It's dramatically slower in the IDE (~25x slower).
2) It's noticeably slower when compiled with no optimizations (~5x)
3) It's still slower when compiled with the "Remove Array Bounds Checks" optimization is selected (~2x - so yes, still slower but maybe OK?)

Are you running compiled with the "Remove Array Bounds Checks" optimization selected when you test the performance?

This didn't surprise me that much. I'm willing to bet that most people aren't aware that modern x86 processors have string instructions, however you cannot access them directly from a high level language like VB6. This was what actually prompted me to ask for your implementation, so I could test it against not only the native Instr function but a handwritten assembly version.

I took some time today to write a byte array version of Instr in pure assembly and these were the results:-

IDE

ASM Instr : 1.042
Runtime Instr : 1.417
VB6 Instr : 14.549

Runtime/ASM : 1.3599
VB6/ASM : 13.9626

EXE with all optimizations enabled

ASM Instr : 0.88
Runtime Instr : 1.17
VB6 Instr : 1.893

Runtime/ASM : 1.3295
VB6/ASM : 2.1511

The runtime Instr is the normal Instr we all know and love, the VB6 Instr is a VB6 version based on the code you posted and the ASM Instr is my own handwritten assembly version. As you have already discovered, a pure VB6 version is horribly slow, at best it's twice as slow as the normal Instr function. The assembly version performs only slightly better than normal Instr. It performed roughly 30% better.

This is the benchmark code:-

Private Sub Form_Load()
    
    Const MAX As Long = (10 ^ 7)
    Dim sText As String
    Dim sSrch As String
    
    Dim arText() As Byte
    Dim arSrch() As Byte
    Dim l As Long
    Dim i As Long
    Dim T As Double, RuntimeTime As Double, VBTime As Double, ASMTime As Double
    
    sText = "Hello there. Do you like kittens?"
    sSrch = "like"
    
    arText = sText 'StrConv(sText, vbFromUnicode)
    arSrch = sSrch 'StrConv(sSrch, vbFromUnicode)
    
    T = Timer
    For i = 1 To MAX
        l = ASMInstrByteArray(1, arText, arSrch)
    Next
    ASMTime = Timer - T
    Prn "ASM Instr : " & Fo(ASMTime)
   
    
    T = Timer
    For i = 1 To MAX
        l = InStr(1, sText, sSrch, vbBinaryCompare)
    Next
    RuntimeTime = Timer - T
    Prn "Runtime Instr : " & Fo(RuntimeTime)
      
   
    T = Timer
    For i = 1 To MAX
        l = VBInstrByteArray(1, arText, arSrch)
    Next
    VBTime = Timer - T
    Prn "VB6 Instr : " & Fo(VBTime)
       
    '****************************************
    
    Prn ""
    Prn "Runtime/ASM : " & Fo(RuntimeTime / ASMTime)
    Prn "VB6/ASM : " & Fo(VBTime / ASMTime)

End Sub

This is the pure VB6 version that's based on yours:-

Private Function VBInstrByteArray(ByVal start As Long, ByRef data() As Byte, ByRef srch() As Byte) As Long
    
    Dim a As Long, b As Long
    Dim i As Long
    Dim x As Long
        
    a = (LBound(data) + start) - 1
    b = LBound(srch)
    
    For i = a To UBound(data)
        If data(i) = srch(b) Then
            b = b + 1
            If b > UBound(srch) Then
                VBInstrByteArray = i - (UBound(srch) - LBound(srch)) + 1
                Exit For
            End If
        Else
            b = LBound(srch)
        End If
    Next

End Function

And this is the assembly version:-

use32

push ebp							
mov ebp, esp	

push esi
push edi
push ebx
;----------------------------------

mov edi, [ebp + 12]	;Copy SAFEARRAY** from 1st arg into EDI
mov edi, [edi]		;Get SAFEARRAY* from SAFEARRAY**

mov ecx, [edi + 16]	;Number of elements in array in 2nd arg goes in
			;ECX

mov edi, [edi + 12]	;Get pvData pointer from SAFEARRAY and put that
			;into EDI. EDI now points to the first element
			;in the byte array passed in the 2nd argument

mov ebx, edi		;Keep a copy of the pointer to the start
			;of the data in the 1st array in EBX

add edi, [ebp + 8]	;Move pointer of the array being searched
			;to the offset specified in the 1st argument

dec edi			;Our function is one-based like VB6's Instr
			;so we decrement the pointer by 1

mov esi, [ebp + 16]	;Copy SAFEARRAY** from 3rd arg into ESI
mov esi, [esi]		;Get SAFEARRAY* from SAFEARRAY**

mov edx, [esi + 16]	;Number of elements in array in 3rd arg goes in
			;EDX

mov esi, [esi + 12]	;Get pvData pointer from SAFEARRAY and put that
			;into ESI. ESI now points to the first element
			;in the byte array passed in the 3rd argument



mov al, [esi]		;Move the value of the first byte of the second
			;array into AL register.

dec edx			;Subtract one from the length of the second
			;array. We always start
			;the CMBSB from the 
			;second byte in the second array since
			;SCASB will match the 1st byte

inc esi			;Move to the second byte of the
			;second array

scanAgain:

repne scasb 		;Scan each byte of the 1st array
			;until a match is found to the
			;byte value in AL.


jne returnZero		;If the end of the string was reached without
			;a match then return 0

cmp edx, 0		

je matchFound		;If the length of the second array is 1
			;(Remember EDX is the length of second array -1)
			;then we don't need any further matching


cmp edx, ecx		;Compare the length of the second array(-1) to
			;the number of bytes remaining to be scanned in 
			;the first array

jg returnZero		;If the remainer to be scanned in the 1st array
			;is less than the size of the second array, then
			;there no match is possible so return 0

push ecx		;Preseve counter of the remaining bytes
			;to be scanned in the 1st array.

push esi		;Preserve pointer to second byte
			;in the second array

mov ecx, edx		;Put the length of the second byte array
			;into ECX for the REP prefix counter


repe cmpsb		;Compare the two byte arrays until
			;either ECX is 0 or a match was not found

pop esi			;Restore pointer to second array
pop ecx			;Restore SCASB counter

jne scanAgain		;If the result of the last comparison
			;was not a match then continue searching the
			;the array for a match

matchFound:
mov eax, edi		;EDI should be pointed to
			;end the of match found

sub eax, ebx		;Subtract it from the address at the start
			;of the array to get an offset

sub eax, edx		;Subtract the length of the second array
			;to get an offset to the start of the match
			;Note: EDX actually stores the length of the
			;second array -1. 
			;Also note that the value returned in EAX here
			;is 1 based like the VB6 Instr function

jmp exitFunc

returnZero:

xor eax, eax


exitFunc:
;----------------------------------
pop ebx
pop edi
pop esi

mov esp, ebp
pop ebp

ret 12

What makes the assembly version special is that uses processor's native string instructions via these two lines:-

repne scasb

repe cmpsb

Those two instructions are actually looping instructions where the loops are implemented at a very low level in the processor and as such they are extremely fast. They are about as fast as you can possibly get.

I've attached the entire project to this post.

IMPORANT!

In order to run the project you must install the trick's assembly add-in. You can find a link to it in this post. It's quick to install and "dog" easy to use.