1

I've got a speed critical piece of code which involves the comparison of 2 4 byte arrays. I've been trying to work out the fastest way to achieve this, and have looked at this.

Doing 100,000,000 comparisons using pinvoke and memcmp takes ~9.5 seconds, using the UnsafeCompare method posted in the above link takes ~3.5 seconds.

If set 2 4 character strings and compare those using s1 == s2 it takes ~0.5 seconds. If I use string.Compare(s1, s2) it takes about ~12 seconds.

Is there some way I can get my byte array comparisons to compare is speed to doing s1 == s2? And if not, could there be any problems with me doing something like below, basically storing my byte arrays as strings?

        string s1 = Convert.ToChar(1).ToString() + Convert.ToChar(2).ToString() + Convert.ToChar(3).ToString() + Convert.ToChar(4).ToString();
        string s2 = Convert.ToChar(1).ToString() + Convert.ToChar(2).ToString() + Convert.ToChar(3).ToString() + Convert.ToChar(4).ToString();

        if (s1 == s2)
            .....

Hoping someone can help me out with this. Thanks!

Community
  • 1
  • 1
Will Calderwood
  • 4,393
  • 3
  • 39
  • 64

2 Answers2

3

I'd recommend these steps:

  1. Compare the two 4-byte arrays byte-by-byte, i.e. a[0] == b[1] && … && a[3] == b[3]. This will be much faster than any calls to memcmp and alikes. Most likely, the JIT compiler will compile this into an efficient (and inline) sequence of instructions. You are comparing only four bytes, you cannot expect an algorithm designed for comparing arbitrarily long memory chunks to perform better.

  2. Think about storing the data as 32-bit integers instead of 4-byte arrays. That will provide another performance gain, because the comparison (a == b) will be translated into a single 32-bit comparison instruction.

  3. Try to rethink your algorithm — is it really necessary to perform 100 million comparisons? Aren't there any options to reduce the time complexity of the algorithm? That would yield a considerable performance boost.

However, without knowing a broader context it's hard to recommend any better and specific optimizations.

Ondrej Tucny
  • 27,626
  • 6
  • 70
  • 90
  • I tried what you suggested in 1. This took about ~8s. 2 I think is a good option, the int32 comparison takes ~0.33s, so that's the fastest of the bunch. The 100m comparisons was just for the test, the actual app wont be hitting it quite so hard. – Will Calderwood Apr 10 '11 at 21:01
1

Haven't tried out this for speed, but what about hard-coding the length and doing a comparison like this:

byte[] one = new byte[] { 0, 1, 2, 3 };
byte[] two = new byte[] { 0, 1, 2, 4 };

bool isEqual = ((one[0] == two[0]) && (one[1] == two[1]) && (one[2] == two[2]) && (one[3] == two[3]));
David Paxson
  • 553
  • 1
  • 3
  • 8