6

I am trying to compare two long bytearrays in VB.NET and have run into a snag. Comparing two 50 megabyte files takes almost two minutes, so I'm clearly doing something wrong. I'm on an x64 machine with tons of memory so there are no issues there. Here is the code that I'm using at the moment and would like to change.

_Bytes and item.Bytes are the two different arrays to compare and are already the same length.

For Each B In item.Bytes If B <> _Bytes(I) Then Mismatch = True Exit For End If I += 1 Next

I need to be able to compare as fast as possible files that are potentially hundreds of megabytes and even possibly a gigabyte or two. Any suggests or algorithms that would be able to do this faster?

Item.bytes is an object taken from the database/filesystem that is returned to compare, because its byte length matches the item that the user wants to add. By comparing the two arrays I can then determine if the user has added something new to the DB and if not then I can just map them to the other file and not waste hard disk drive space.

[Update]

I converted the arrays to local variables of Byte() and then did the same comparison, same code and it ran in like one second (I have to benchmark it still and compare it to others), but if you do the same thing with local variables and use a generic array it becomes massively slower. I’m not sure why, but it raises a lot more questions for me about the use of arrays.

Improve this question
2
  • Comparing two 50MB arrays take less than a second for me using the naive approach. You should have another issue. Commented Mar 9, 2009 at 20:02
  • 1
    Check stackoverflow.com/q/43289/276648 which is the same question for C#. Lots of answers. I like the unsafe version stackoverflow.com/a/8808245/276648 as it will also run on Mono Linux. Commented Jan 10, 2013 at 3:58

6 Answers 6

Reset to default
17

What is the _Bytes(I) call doing? It's not loading the file each time, is it? Even with buffering, that would be bad news!

There will be plenty of ways to micro-optimise this in terms of looking at longs at a time, potentially using unsafe code etc - but I'd just concentrate on getting reasonable performance first. Clearly there's something very odd going on.

I suggest you extract the comparison code into a separate function which takes two byte arrays. That way you know you won't be doing anything odd. I'd also use a simple For loop rather than For Each in this case - it'll be simpler. Oh, and check whether the lengths are correct first :)

EDIT: Here's the code (untested, but simple enough) that I'd use. It's in C# for the minute - I'll convert it in a sec:

public static bool Equals(byte[] first, byte[] second) { if (first == second) { return true; } if (first == null || second == null) { return false; } if (first.Length != second.Length) { return false; } for (int i=0; i < first.Length; i++) { if (first[i] != second[i]) { return false; } } return true; }

EDIT: And here's the VB:

Public Shared Function ArraysEqual(ByVal first As Byte(), _ ByVal second As Byte()) As Boolean If (first Is second) Then Return True End If If (first Is Nothing OrElse second Is Nothing) Then Return False End If If (first.Length <> second.Length) Then Return False End If For i as Integer = 0 To first.Length - 1 If (first(i) <> second(i)) Then Return False End If Next i Return True End Function
Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

the _Bytes(I) is an array of bytes that is already in memory.
i is just an index to find the byte
Amazing Jon, I'm thrilled to have the Stack Celeb helping out on this!
Try the code I've just provided - but I'm really surprised it was taking two minutes. The above code takes about 140ms on my laptop (built with optimisation, and not running under a debugger, admittedly).
Hi Jon, your first condition in the VB code has a Not too many. The parens aren't needed either but they don't do any harm (Is == object.ReferenceEquals == roughly == for references when no operator == is defined).
|
4

The fastest way to compare two byte arrays of equal size is to use interop. Run the following code on a console application:

using System; using System.Runtime.InteropServices; using System.Security; namespace CompareByteArray { class Program { static void Main(string[] args) { const int SIZE = 100000; const int TEST_COUNT = 100; byte[] arrayA = new byte[SIZE]; byte[] arrayB = new byte[SIZE]; for (int i = 0; i < SIZE; i++) { arrayA[i] = 0x22; arrayB[i] = 0x22; } { DateTime before = DateTime.Now; for (int i = 0; i < TEST_COUNT; i++) { int result = MemCmp_Safe(arrayA, arrayB, (UIntPtr)SIZE); if (result != 0) throw new Exception(); } DateTime after = DateTime.Now; Console.WriteLine("MemCmp_Safe: {0}", after - before); } { DateTime before = DateTime.Now; for (int i = 0; i < TEST_COUNT; i++) { int result = MemCmp_Unsafe(arrayA, arrayB, (UIntPtr)SIZE); if (result != 0) throw new Exception(); } DateTime after = DateTime.Now; Console.WriteLine("MemCmp_Unsafe: {0}", after - before); } { DateTime before = DateTime.Now; for (int i = 0; i < TEST_COUNT; i++) { int result = MemCmp_Pure(arrayA, arrayB, SIZE); if (result != 0) throw new Exception(); } DateTime after = DateTime.Now; Console.WriteLine("MemCmp_Pure: {0}", after - before); } return; } [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl, EntryPoint="memcmp", ExactSpelling=true)] [SuppressUnmanagedCodeSecurity] static extern int memcmp_1(byte[] b1, byte[] b2, UIntPtr count); [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl, EntryPoint = "memcmp", ExactSpelling = true)] [SuppressUnmanagedCodeSecurity] static extern unsafe int memcmp_2(byte* b1, byte* b2, UIntPtr count); public static int MemCmp_Safe(byte[] a, byte[] b, UIntPtr count) { return memcmp_1(a, b, count); } public unsafe static int MemCmp_Unsafe(byte[] a, byte[] b, UIntPtr count) { fixed(byte* p_a = a) { fixed (byte* p_b = b) { return memcmp_2(p_a, p_b, count); } } } public static int MemCmp_Pure(byte[] a, byte[] b, int count) { int result = 0; for (int i = 0; i < count && result == 0; i += 1) { result = a[0] - b[0]; } return result; } } }
Improve this answer

2 Comments

Which one was fastest in your tests? Timings?
MemCmp_Safe: 00:00:00.0060003 MemCmp_Unsafe: 00:00:00.0020002 MemCmp_Pure: 00:00:00.0270015
3

If you don't need to know the byte, use 64-bit ints that gives you 8 at once. Actually, you can figure out the wrong byte, once you've isolated it to a set of 8.

Use BinaryReader:

saveTime = binReader.ReadInt32()

Or for arrays of ints:

Dim count As Integer = binReader.Read(testArray, 0, 3)
Improve this answer

5 Comments

Can you explain that further please?
use arrays of int instead or arrays of bytes.
So given that these are byte arrays from a file how do I get them into this blocked format that you speak of?
Either read the file as binary one 64-bit int at a time, or after reading 8 bytes, place them into a 64-bit int, using bit-shifts and bitwise-or.
@Middletone: check the link, and use the BinaryReader.
0

Better approach... If you are just trying to see if the two are different then save some time by not having to go through the entire byte array and generate a hash of each byte array as strings and compare the strings. MD5 should work fine and is pretty efficient.

Improve this answer

1 Comment

It is very ridiculous thing. Any cryptographic function should scan each of array and calculate hash value for both... So it costs much more than simply perform per byte comparison.
0

I see two things that might help:

First, rather than always accessing the second array as item.Bytes, use a local variable to point directly at the array. That is, before starting the loop, do something like this:

 array2 = item.Bytes

That will save the overhead of dereferencing from the object each time you want a byte. That could be expensive in Visual Basic, especially if there's a Getter method on that property.

Also, use a "definite loop" instead of "for each". You already know the length of the arrays, so just code the loop using that value. This will avoid the overhead of treating the array as a collection. The loop would look something like this:

For i = 1 to max Step 1 If (array1(i) <> array2(i)) Exit For EndIf Next
Improve this answer

Comments

0

Not strictly related to the comparison algorithm:

Are you sure your bottleneck is not related to the memory available and the time used to load the byte arrays? Loading two 2 GB byte arrays just to compare them could bring most machines to their knees. If the program design allows, try using streams to read smaller chunks instead.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.