Faster ByteArray search/loop

[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?

[Eduardo-]

InStr works with byte arrays::

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

[some1uk03]

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

[Eduardo-]

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?

[some1uk03]

Ok, it seems to be an ENCODING issue.

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

[Arnoutdv]

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

[jpbro]

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:

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

[Eduardo-]

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.

[Elroy]

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

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).

[Elroy]

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.

[Arnoutdv]

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

[Elroy]

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.

[The trick]

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

[Elroy]

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.

[Eduardo-]

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?

[baka]

----

[couttsj]

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

J.A. Coutts

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

[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)

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

this Doesn't work either.

[The trick]

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.

[dilettante]

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.

[Elroy]

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.

[jpbro]

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?

[Eduardo-]

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:

[Niya]

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.

[jpbro]

Sure, here it is:

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.

[jj2007]

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.

[wqweto]

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:

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

    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>

[Eduardo-]

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

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

[wqweto]

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

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>

[Schmidt]

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

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

[couttsj]

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

[SmUX2k]

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)

[wqweto]

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>

[Schmidt]

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:

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

[The trick]

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:

Yes, of course.

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:

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:

[The trick]

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

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.

[Eduardo-]

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).

[couttsj]

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

[The trick]

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

[Eduardo-]

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.