Faster ByteArray search/loop

I'm ditching string usage and replacing with ByteArrays, however, i do miss the instr() for strings which was/is super fast.

I have now written my own function to loop though the bytearray but this takes a very long time. Nothing close to instr().

Are there any API's or faster methods of replacing the instr() for byteArrays?

InStr works with byte arrays::

Code:

---

    Dim s As String
    Dim b() As Byte
   
    s = "this is a string aaa 123 bbb"
    b = s
    Debug.Print InStr(b, "aaa")

---

On the example provided, (small arrays) yh it seems to.
But not on larger byteArrays. Always returns 0.

Quote:

---

Originally Posted by some1uk03

On the example provided, (small arrays) yh it seems to.
But not on larger byteArrays. Always returns 0.

---

What can have to do the size of the array, if the function treats strings as byte arrays? (or byte arrays as strings)

Do you have an example where you see it fails?

Ok, it seems to be an ENCODING issue.

b = s '//works
---
b = StrConv(s, vbFromUnicode) '// doesn't work

Quote:

---

Originally Posted by some1uk03

I'm ditching string usage and replacing with ByteArrays, however, i do miss the instr() for strings which was/is super fast.

I have now written my own function to loop though the bytearray but this takes a very long time. Nothing close to instr().

Are there any API's or faster methods of replacing the instr() for byteArrays?

---

Can you show the function you created?
Is the byte array actually a string array?

vbSpeed has an alternative InStr() function which under the hood use a byte array.
Maybe you can modify it to suit your needs:
http://www.xbeat.net/vbspeed/c_InStr.htm

The code:
http://www.xbeat.net/vbspeed/cod_InStrMarzo.htm

Quote:

---

Originally Posted by some1uk03

Ok, it seems to be an ENCODING issue.

b = s '//works
---
b = StrConv(s, vbFromUnicode) '// doesn't work

---

After converting from unicode, InStr will no longer match Unicode strings against your byte array. You have to convert your search string from Unicode as well:

Code:

---

Sub Test()
  Dim x As String
  Dim b() As Byte
 
  x = "ABCDEFG"
 
  b = x
 
  Debug.Print InStr(1, b, "ABC")  ' Prints 1
  Debug.Print InStr(1, b, StrConv("ABC", vbFromUnicode))  ' Prints 0
 
  b = StrConv(x, vbFromUnicode)
 
  Debug.Print InStr(1, b, "ABC")  ' Prints 0
  Debug.Print InStr(1, b, StrConv("ABC", vbFromUnicode))    ' Prints 1
End Sub

---

Quote:

---

Originally Posted by some1uk03

Ok, it seems to be an ENCODING issue.

b = s '//works
---
b = StrConv(s, vbFromUnicode) '// doesn't work

---

If you are converting the string from Unicode to ANSI, the byte array is totally changed.
You are basically cutting half of the bytes.

Convert your search string (the needle) the same way you convert the string being searched (the hay), and it'll always work:

Code:

---


Option Explicit

Private Sub Form_Load()
    Dim sHay As String
    Dim sNeedle As String

    sHay = "asdfasdfzzzqwerqwer"
    sNeedle = "zzz"

    Debug.Print InStr(StrConv(sHay, vbFromUnicode), StrConv(sNeedle, vbFromUnicode))

End Sub



---

And yeah, you're converting to ANSI, so of course searching an ANSI string with a UNICODE search criteria will never work. They've both either got to be ANSI or UNICODE (not a mixture).

Now, you might be puzzled as to why the answer in the above was 5, and not 9. That's because your byte arrays are still being treated as Unicode, even though they're ANSI.

Interestingly, the Instr still works even if there are an odd number of characters before the searched text. Apparently, Instr does do a byte-by-byte search, and then divides by two (with rounding) when it finds the desired text.

Probably best to just always feed Unicode strings into Instr, unless you're very careful with what you're doing, and have a good understanding of it.

There is also the InstrB function, which the returns the index as if it was a byte search

Quote:

---

Originally Posted by Arnoutdv

There is also the InstrB function, which the returns the index as if it was a byte search

---

That'd probably be better for ANSI strings, or byte arrays with ANSI data in them.

Use InStrB but it's very slow because you have two byte-array string conversions.

Quote:

---

Originally Posted by The trick

Use InStrB but it's very slow because you have two byte-array string conversions.

---

I thought his "hay" was already an ANSI byte array, but some1uk03 isn't clear about that, so IDK.

My first question is: why to convert to ANSI (at all)?

Unless you are already having the string in ANSI (to save space or some other valid reason -or semi-valid-), keep them in Unicode. Why to convert to ANSI before the search?

----

This returns the correct answer. Don't know about the speed though.

J.A. Coutts

Code:

---

Option Explicit

Private Const CP_UTF8 = 65001

Private Declare Function WideCharToMultiByte Lib "kernel32" (ByVal CodePage As Long, ByVal dwFlags As Long, ByVal lpWideCharStr As Long, ByVal cchWideChar As Long, ByVal lpMultiByteStr As Long, ByVal cbMultiByte As Long, ByVal lpDefaultChar As Long, ByVal lpUsedDefaultChar As Long) As Long
Private Declare Function MultiByteToWideChar Lib "kernel32" (ByVal CodePage As Long, ByVal dwFlags As Long, ByVal lpMultiByteStr As Long, ByVal cchMultiByte As Long, ByVal lpWideCharStr As Long, ByVal cchWideChar As Long) As Long

Private Function GetbSize(bArray() As Byte) As Long
    On Error GoTo GetSizeErr
    GetbSize = UBound(bArray) + 1
    Exit Function
GetSizeErr:
    GetbSize = 0
End Function

Private Function StrToUtf8(strInput As String) As Byte()
    Dim nBytes As Long
    Dim abBuffer() As Byte
    If Len(strInput) < 1 Then Exit Function
    ' Get length in bytes *including* terminating null
    nBytes = WideCharToMultiByte(CP_UTF8, 0&, ByVal StrPtr(strInput), -1, 0&, 0&, 0&, 0&)
    ' We don't want the terminating null in our byte array, so ask for `nBytes-1` bytes
    ReDim abBuffer(nBytes - 2)  ' NB ReDim with one less byte than you need
    nBytes = WideCharToMultiByte(CP_UTF8, 0&, ByVal StrPtr(strInput), -1, ByVal VarPtr(abBuffer(0)), nBytes - 1, 0&, 0&)
    StrToUtf8 = abBuffer
End Function

Private Function Utf8ToStr(abUtf8Array() As Byte) As String
    Dim nBytes As Long
    Dim nChars As Long
    Dim strOut As String
    ' Catch uninitialized input array
    nBytes = GetbSize(abUtf8Array)
    If nBytes <= 0 Then Exit Function
    ' Get number of characters in output string
    nChars = MultiByteToWideChar(CP_UTF8, 0&, VarPtr(abUtf8Array(0)), nBytes, 0&, 0&)
    ' Dimension output buffer to receive string
    strOut = String(nChars, 0)
    nChars = MultiByteToWideChar(CP_UTF8, 0&, VarPtr(abUtf8Array(0)), nBytes, StrPtr(strOut), nChars)
    Utf8ToStr = Replace(strOut, Chr$(0), "") 'Remove Null terminating characters
End Function

Private Sub Command1_Click()
    Dim bHay() As Byte
    Dim bNeedle() As Byte
    bHay = StrToUtf8("asdfasdfzzzqwerqwer")
    bNeedle = StrToUtf8("zzz")
    Debug.Print InStr(bHay, bNeedle), InStrB(bHay, bNeedle)
End Sub

---

Just to clarify. I'm not converting a STRING in to a ByteArray.

The byteArray loads a File in to the array. i/e bArray = sFile.ReadyByteArray(filepath)

Quote:

---

@jpBro: Debug.Print InStr(1, b, StrConv("ABC", vbFromUnicode)) ' Prints 1

---

this Doesn't work either.

Quote:

---

Originally Posted by Elroy

I thought his "hay" was already an ANSI byte array, but some1uk03 isn't clear about that, so IDK.

---

InStr and InStrB accept strings. So each time you pass a byte array it's converted to a string.

Perhaps look into StrStrA()/StrStrW() in shlwapi.dll?

These are easy to use if you don't link with /LARGEADDRESSAWARE. But if you do then you'd need to be more careful, doing unsigned pointer arithmetic to convert results from pointers back to offset indices.

Quote:

---

Originally Posted by The trick

InStr and InStrB accept strings. So each time you pass a byte array it's converted to a string.

---

Ahh, I didn't realize that, but it makes sense. That would definitely cause some slowdown.

Quote:

---

Originally Posted by some1uk03

I have now written my own function to loop though the bytearray but this takes a very long time. Nothing close to instr().

---

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?

Quote:

---

Originally Posted by The trick

InStr and InStrB accept strings. So each time you pass a byte array it's converted to a string.

---

Are you sure Trick about that? It does not make sense to me, since Strings and byte arrays are basically already the same thing.

And the definition of InStr is Variant:

Attachment 184634

Quote:

---

Originally Posted by jpbro

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?

---

Can you post your byte compare function? I wanna do some testing of my own.

Sure, here it is:

Code:

---

Option Explicit

Private Sub Form_Click()
  Const c_FindString As String = "Find Me"
 
  Dim ii As Long
  Dim jj As Long
  Dim kk As Long
  Dim l_FindPos As Long
  Dim l_String As String
  Dim la_String() As Byte
  Dim la_Find() As Byte
  Dim l_UboundFind As Long
  Dim l_UboundString As Long
 
  Randomize Timer
 
  l_String = String$(Rnd * 100000, "A")
  l_String = l_String & c_FindString
  l_String = l_String & String$(Rnd * 100000, "A")
 
  New_c.Timing True
  For ii = 1 To 10000
      l_FindPos = InStr(1, l_String, c_FindString)
  Next ii
  Me.Print "InStr: " & New_c.Timing, "Find Pos: " & l_FindPos

  la_String = StrConv(l_String, vbFromUnicode)
  la_Find = StrConv(c_FindString, vbFromUnicode)
  l_UboundString = UBound(la_String)
  l_UboundFind = UBound(la_Find)
  l_FindPos = 0
     
  New_c.Timing True
  For ii = 1 To 10000
      kk = 0
      For jj = 0 To l_UboundString
        If la_String(jj) = la_Find(kk) Then
            kk = kk + 1
            If kk > l_UboundFind Then
              l_FindPos = jj - l_UboundFind + 1
              Exit For
            End If
        Else
            kk = 0
        End If
      Next jj
  Next ii
 
  Me.Print "LoopFind: " & New_c.Timing, "Find Pos: " & l_FindPos
End Sub

---

Notes:

Click the form to get a comparison of Instr/FindLoop timings. You can click multiple times.
I just whipped it up - there may be bugs, and I doubt it's the most efficient approach.
I use RC6 for the Timing, but you can easily swap in your own timing class/APIs.
Try it in the IDE, compiled without optimizations, and compiled with the Remove Array Bounds Checks optimization to see the differences in timings.

Quote:

---

Originally Posted by some1uk03

Just to clarify. I'm not converting a STRING in to a ByteArray.

The byteArray loads a File in to the array. i/e bArray = sFile.ReadyByteArray(filepath)

---

Technically speaking, there is no difference between a pointer to an ANSI string and a pointer to a byte array. But you need to convince VB to refrain from any conversions under the hood.

If speed is really an issue, I would write a routine in Assembly, link to it and just pass a pointer to the byte array.

Quote:

---

Originally Posted by Eduardo-

Are you sure Trick about that? It does not make sense to me, since Strings and byte arrays are basically already the same thing.

And the definition of InStr is Variant:

Attachment 184634

---

InStr is an intrinsic and it does not compile to a call to VBA.InStr (unless you explicitly use VBA.InStr in your code). InStr calls __vbaInStr export of MSVBVM60.DLL directly.

Here is some disassembly

Code:

---

    MsgBox InStrB(1, baHay, baNeedle)
00401B20 C7 45 9C 04 00 02 80 mov        dword ptr [ebp-64h],80020004h 
00401B27 C7 45 94 0A 00 00 00 mov        dword ptr [unnamed_var1],0Ah 
00401B2E C7 45 AC 04 00 02 80 mov        dword ptr [ebp-54h],80020004h 
00401B35 C7 45 A4 0A 00 00 00 mov        dword ptr [unnamed_var1],0Ah 
00401B3C C7 45 BC 04 00 02 80 mov        dword ptr [ebp-44h],80020004h 
00401B43 C7 45 B4 0A 00 00 00 mov        dword ptr [unnamed_var1],0Ah 
00401B4A 8B 45 DC            mov        eax,dword ptr [baHay] 
00401B4D 89 85 78 FF FF FF    mov        dword ptr [ebp-88h],eax 
00401B53 C7 85 70 FF FF FF 11 20 00 00 mov        dword ptr [unnamed_var1],2011h 
00401B5D 8B 45 E0            mov        eax,dword ptr [baNeedle] 
00401B60 89 45 88            mov        dword ptr [ebp-78h],eax 
00401B63 C7 45 80 11 20 00 00 mov        dword ptr [unnamed_var1],2011h 
00401B6A 6A 01                push        1 
00401B6C 8D 85 70 FF FF FF    lea        eax,[unnamed_var1] 
00401B72 50                  push        eax 
00401B73 E8 10 F6 FF FF      call        ___vbaStrVarCopy (401188h) 
00401B78 8B D0                mov        edx,eax 
00401B7A 8D 4D D4            lea        ecx,[unnamed_var1] 
00401B7D E8 0C F6 FF FF      call        @__vbaStrMove (40118Eh) 
00401B82 50                  push        eax 
00401B83 8D 45 80            lea        eax,[unnamed_var1] 
00401B86 50                  push        eax 
00401B87 E8 FC F5 FF FF      call        ___vbaStrVarCopy (401188h) 
00401B8C 8B D0                mov        edx,eax 
00401B8E 8D 4D D8            lea        ecx,[unnamed_var1] 
00401B91 E8 F8 F5 FF FF      call        @__vbaStrMove (40118Eh) 
00401B96 50                  push        eax 
00401B97 6A 00                push        0 
00401B99 E8 F6 F5 FF FF      call        @__vbaInStrB (401194h) 
00401B9E 89 45 CC            mov        dword ptr [ebp-34h],eax 
00401BA1 C7 45 C4 03 00 00 00 mov        dword ptr [unnamed_var1],3 
00401BA8 8D 45 94            lea        eax,[unnamed_var1] 
00401BAB 50                  push        eax 
00401BAC 8D 45 A4            lea        eax,[unnamed_var1] 
00401BAF 50                  push        eax 
00401BB0 8D 45 B4            lea        eax,[unnamed_var1] 
00401BB3 50                  push        eax 
00401BB4 6A 00                push        0 
00401BB6 8D 45 C4            lea        eax,[unnamed_var1] 
00401BB9 50                  push        eax 
00401BBA E8 DB F5 FF FF      call        @__vba@07FBF5D4 (40119Ah) 
00401BBF 8D 45 D4            lea        eax,[unnamed_var1] 
00401BC2 50                  push        eax 
00401BC3 8D 45 D8            lea        eax,[unnamed_var1] 
00401BC6 50                  push        eax 
00401BC7 6A 02                push        2 
00401BC9 E8 B4 F5 FF FF      call        ___vbaFreeStrList (401182h) 
00401BCE 83 C4 0C            add        esp,0Ch 
00401BD1 8D 45 94            lea        eax,[unnamed_var1] 
00401BD4 50                  push        eax 
00401BD5 8D 45 A4            lea        eax,[unnamed_var1] 
00401BD8 50                  push        eax 
00401BD9 8D 45 B4            lea        eax,[unnamed_var1] 
00401BDC 50                  push        eax 
00401BDD 8D 45 C4            lea        eax,[unnamed_var1] 
00401BE0 50                  push        eax 
00401BE1 6A 04                push        4 
00401BE3 E8 94 F5 FF FF      call        ___vbaFreeVarList (40117Ch) 
00401BE8 83 C4 14            add        esp,14h

---

As you can see there are a lot of conversions from byte-arrays to strings going on.

cheers,
</wqw>

In this test code I see very little, to almost no difference between InStr speed with String versus Byte arrays:

Code:

---

Private Sub Form_Load()
    Dim iT1
    Const t As String = "This is a text to repeat many times "
    Dim c As Long
    Dim s As String
    Dim b() As Byte
   
    Me.AutoRedraw = True
   
    For c = 1 To 1000
        s = s & t
    Next
   
    s = s & " some other text to find in the middle" & s
   
    iT1 = Timer
    For c = 1 To 30000
        Call InStr(s, "text to find")
    Next
    Me.Print "String: " & Round(Timer - iT1, 2)
   
    b = s
   
    iT1 = Timer
    For c = 1 To 30000
        Call InStr(b, "text to find")
    Next
    Me.Print "Byte array: " & Round(Timer - iT1, 2)
End Sub

---

Yes, in practice the performance is not so abysmal. For instance I use InStrB for byte-arrays equality comparison like this

Code:

---

Private Function pvArrayEqual(baFirst() As Byte, baSecond() As Byte) As Boolean
    If pvArraySize(baFirst) = pvArraySize(baSecond) Then
        pvArrayEqual = (InStrB(baFirst, baSecond) = 1)
    End If
End Function

---

cheers,
</wqw>

Quote:

---

Originally Posted by wqweto

Yes, in practice the performance is not so abysmal. For instance I use InStrB for byte-arrays equality comparison like this

Code:

---

Private Function pvArrayEqual(baFirst() As Byte, baSecond() As Byte) As Boolean
    If pvArraySize(baFirst) = pvArraySize(baSecond) Then
        pvArrayEqual = (InStrB(baFirst, baSecond) = 1)
    End If
End Function

---

cheers,
</wqw>

---

IMO, faster should be a direct expression (avoiding the call-overhead to your Private Function):
If CStr(baFirst) = CStr(baSecond) Then ...

instead of:
If pvArrayEqual(baFirst, baSecond) Then ...

Olaf

I did some tests using a large text file (2,167,737 bytes), and comparing a string InStr to a byte InStrB.
----------------------------------
String Search for 'Formulate'
File Length: 2167737
175277.3564288 175277.3576243
Found at: 2148904 in 1.19549999362789 ms

Byte Search for 'Formulate'
File Length: 2167737
175280.0588472 175280.0598327
Found at: 2148904 in 0.985499995294958 ms
----------------------------------
Summarizing the results, it can be seen that the byte search is slightly faster than the string search. I assume that is because the string occupies twice as much memory.

String Search
Found at: 2148904 in 1.19549 ms
Found at: 2148904 in 1.17450 ms
Found at: 2148904 in 1.13419 ms
Found at: 2148904 in 1.17599 ms

Byte Search
Found at: 2148904 in 0.98549 ms
Found at: 2148904 in 1.05680 ms
Found at: 2148904 in 1.00329 ms
Found at: 2148904 in 1.04049 ms

J.A. Coutts

Would it be quicker to "fake" a byte array using a function and within that function using mid() to paste the byte array values directly into a pre-set string of pre-determined length? Essentially the data would be stored as a string in memory (allowing for a quick instr to be done without any conversion taking place, useful if you plan to search regularly) but you would reference the positions like you would with a byte array when adding data. With some (not particularly) clever coding you could probably speed up multi-byte replacements within the string so you can fill the byte array with data quickly (the one thing that might slow it down if it had to be done one byte at a time).

I mean, I know what I am talking about...I'm used to other people not understanding what I am trying to explain (and I'm often not that good at explaining)...I can explain further if that helps, or even write an example.

Down side is that storing it as a unicode string is going to use double the memory that the byte array would take up, but that wouldn't be a major issue unless you're working with gigabytes of data :-)

Edit: I mention "within that function" above...there would probably need to be multiple functions...one function returns the byte value at a specific point, another is used for adding data to the string, another would be used for searching the string (unless you directly searched the string it used)

Quote:

---

Originally Posted by Schmidt

IMO, faster should be a direct expression (avoiding the call-overhead to your Private Function):
If CStr(baFirst) = CStr(baSecond) Then ...

---

I'm always wary of casting byte-arrays to strings after all those couttsj horror threads with byte-arrays-in-strings gone wrong :-))

What if these byte-arrays being compared are odd sized? Will it blend? :-))

cheers,
</wqw>

Quote:

---

Originally Posted by wqweto

I'm always wary of casting byte-arrays to strings
after all those couttsj horror threads with byte-arrays-in-strings gone wrong :-))

What if these byte-arrays being compared are odd sized? Will it blend? :-))

---

No reason to be wary - and odd sizes blend quite nicely:

Code:

---

Private Sub Form_Load()
  'create a byte-array of lenght 3
  Dim B1() As Byte: B1 = StrConv("abc", vbFromUnicode)
  Debug.Print UBound(B1) + 1, LenB(CStr(B1))
 
  'make a copy of B1 (in B2) ... and compare in two ways
  Dim B2() As Byte: B2 = B1
  Debug.Print "Direct comparison", CStr(B1) = CStr(B2) '<- gives True
  Debug.Print "StrComp-comparison", StrComp(B1, B2) = 0 '<- gives True
End Sub

---

Olaf

Quote:

---

Originally Posted by Eduardo-

Are you sure Trick about that? It does not make sense to me, since Strings and byte arrays are basically already the same thing.

And the definition of InStr is Variant:

Attachment 184634

---

Yes, of course.

Quote:

---

In this test code I see very little, to almost no difference between InStr speed with String versus Byte arrays:

---

Check the parameters ;) Also you forget about the VB6 optimizations. The more correct test is:

Code:

---

Private Sub Form_Load()
    Dim iT1
    Const t As String = "This is a text to repeat many times "
    Dim c As Long
    Dim s As String
    Dim b() As Byte
    Dim q As Long
   
    Me.AutoRedraw = True
   
    For c = 1 To 1000
        s = s & t
    Next
   
    s = s & " some other text to find in the middle" & s

    iT1 = Timer
    For c = 1 To 30000
        q = InStr(1, s, "text to find")
    Next
    Me.Print "String: " & Round(Timer - iT1, 2)
   
    b = s

    iT1 = Timer
    For c = 1 To 30000
        q = InStr(1, b, "text to find")
    Next
    Me.Print "Byte array: " & Round(Timer - iT1, 2)

End Sub

---

Just see the difference:

https://www.vbforums.com/images/ieimages/2022/04/5.png

Quote:

---

Originally Posted by wqweto

Yes, in practice the performance is not so abysmal. For instance I use InStrB for byte-arrays equality comparison like this

Code:

---

Private Function pvArrayEqual(baFirst() As Byte, baSecond() As Byte) As Boolean
    If pvArraySize(baFirst) = pvArraySize(baSecond) Then
        pvArrayEqual = (InStrB(baFirst, baSecond) = 1)
    End If
End Function

---

cheers,
</wqw>

---

RtlCompareMemory is more faster.

Quote:

---

Originally Posted by wqweto

after all those couttsj horror threads with byte-arrays-in-strings gone wrong

---

I would like to know about that, because I sometimes exchange byte arrays with strings, forth and back (and found no problems so far).

Quote:

---

Originally Posted by Eduardo-

I would like to know about that, because I sometimes exchange byte arrays with strings, forth and back (and found no problems so far).

---

When I first started working with encryption, I used strings as much as possible because the tools to work with them were built into VB. I ran into numerous problems, not the least of which was issues with extended Latin characters (above &H7F) using StrConv. In the end I gave up and developed my own set of tools to use with byte arrays, and hence my interest in this thread. After I started working with JavaScript, I have standardized on WideCharToMultiByte and MultiByteToWideChar for doing conversions.

J.A. Coutts

There is no any problem with converting a BSTR to a byte array and vice versa.

Quote:

---

Originally Posted by couttsj

When I first started working with encryption, I used strings as much as possible because the tools to work with them were built into VB. I ran into numerous problems, not the least of which was issues with extended Latin characters (above &H7F) using StrConv. In the end I gave up and developed my own set of tools to use with byte arrays, and hence my interest in this thread. After I started working with JavaScript, I have standardized on WideCharToMultiByte and MultiByteToWideChar for doing conversions.

J.A. Coutts

---

Ah, yes. StrConv, ChrW, AscW can cause problems.
But as I see it, that's an issue that has very little to do with exchanging byte arrays with strings.
It has more to do with if you can rely that the numbers stored on the bytes won't be changed in any conversion.

I mean, to exchange byte arrays with Strings directly apparently work with no issues.

I remember that some time ago I also had the idea that converting byte array to string and vice-versa could corrupt the data, I don't find that thread now but I remember that the actual problem is when using those other conversion functions.

Quote:

---

Originally Posted by jpbro

Sure, here it is:....

---

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

Quote:

---

Originally Posted by jpbro

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

Code:

---

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

Code:

---

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:-

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:-

Code:

---

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:-

Code:

---

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:-

Code:

---

repne scasb

---

Code:

---

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.

Quote:

---

Originally Posted by jpbro

.
I just whipped it up - there may be bugs, and I doubt it's the most efficient approach.

---

I'd also like to point out that it may be very possible to optimize the pure VB6 version to perform at least as well as the normal Instr function. Like you, I also get the feeling that it may be possible to optimize it further. Despite performing twice as bad as both the ASM and normal Instr, I was still very surprised at how well it did with all optimizations enabled. Someone like Olaf could probably make it faster.

I'm also pretty sure that my ASM version could also be optimized further. Though I love playing around with assembly, I'm far from an assembly language expert.

Quote:

---

Originally Posted by Niya

I'd also like to point out that it may be very possible to optimize the pure VB6 version to perform at least as well as the normal Instr function. Like you, I also get the feeling that it may be possible to optimize it further. Despite performing twice as bad as both the ASM and normal Instr, I was still very surprised at how well it did with all optimizations enabled. Someone like Olaf could probably make it faster.

I'm also pretty sure that my ASM version could also be optimized further. Though I love playing around with assembly, I'm far from an assembly language expert.

---

You could put your VBInstrByteArray into a standard module and precalculate the Ubound/LBound values to increase the performance.

Quote:

---

Originally Posted by The trick

You could put your VBInstrByteArray into a standard module and precalculate the Ubound/LBound values to increase the performance.

---

You were absolutely right! I refactored it a bit here and put it in a module:-

Code:

---

Public Function VBInstrByteArray2(ByVal start As Long, ByRef data() As Byte, ByRef srch() As Byte) As Long
   
    Dim b As Long
    Dim i As Long
    Dim x As Long
    Dim lbSrch As Long, ubSrch As Long, lenSrch As Long
   
    lbSrch = LBound(srch)
    ubSrch = UBound(srch)
    lenSrch = (ubSrch - lbSrch) + 1
    b = lbSrch
   
    For i = (LBound(data) + start) - 1 To UBound(data)
        If data(i) = srch(b) Then
            b = b + 1
            If b > ubSrch Then
                VBInstrByteArray2 = i - lenSrch
                Exit For
            End If
        Else
            b = lbSrch
        End If
    Next

End Function

---

And these were the results from an EXE with all optimizations enabled:-

Code:

---

ASM Instr : 0.931
Runtime Instr : 1.249
VB6 Instr : 1.883
VB6 Instr v2 : 0.704

Runtime/ASM : 1.3416
VB6/ASM : 2.0226
VB6 v2/ASM : 0.7562

---

It performed the best, outperforming my ASM version by 30%.

Of course we should obligatory mention Boyer–Moore string-search algorithm which has the potential to obliterate any naive loop approach be it in ASM or not.

cheers,
</wqw>

Good job, Niya! Note that repne scasb is not the fastest option, especially if the first byte to search is a common character like "e". With SIMD instructions, it can be a factor 2-3 faster. The bigger problem, in any case, are the conversions done under the hood.

Quote:

---

Originally Posted by wqweto

Of course we should obligatory mention Boyer–Moore string-search algorithm which has the potential to obliterate any naive loop approach be it in ASM or not.

---

We tested BM ad nauseam, and never found an advantage.