1
\$\begingroup\$

Can the following function be improved in terms of performance?

I am calculating millions of such hashes. The long array represents a record from data table where all values are encoded as long values. Usually in one calculation stream all arrays are of the same length but in some rare cases this rule does not apply. Typical length of the array vary from 300 to 1 elements.

I was wondering whether using SIMD (SSE / AVX) instructions in System.Numerics.Vectors library of .NET 4.6 could help?

public static int GetHashCode(long[] array)
{
    if (array == null) return 0;
    unchecked
    {
        int hash = 17;
        for(int i = 0; i < array.Length; i++)
            hash = 31 * hash + array[i].GetHashCode();
        return hash;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Is this a 32-bit process or a 64-bit process? \$\endgroup\$ – CodesInChaos Aug 23 '16 at 9:15
  • \$\begingroup\$ Do rows sometimes only differ is small parts? If not, you could simply leave out some of the inputs. \$\endgroup\$ – CodesInChaos Aug 23 '16 at 9:18
  • \$\begingroup\$ @CodesInChaos this is 64-bit process. Yes rows often differ only in small parts. \$\endgroup\$ – Sebastian Widz Aug 23 '16 at 15:18
  • \$\begingroup\$ A common approach is to only hash the first x (like 6-20) rows. \$\endgroup\$ – paparazzo Aug 23 '16 at 17:46
  • 1
    \$\begingroup\$ More important is how is it going to be used? Hash is only Int 32. You are using multiple long just to find a bucket. Right now this imperfect hash is more expensive than a comparison (equals). Equal would check length and then element by element compare and stop once it finds an inequality. In real life I bet you would be better with length and the first 6 values. With different primes so order matters. Sorry but to use up to 300 long to create an Int 32 is silly. \$\endgroup\$ – paparazzo Aug 23 '16 at 18:20
4
\$\begingroup\$

You could use XOR to combine hashes which is much faster than your calculation:

int hash = 0;
for(int i = 0; i < array.Length; i++)
    hash ^= array[i].GetHashCode();
return hash;
\$\endgroup\$
  • 1
    \$\begingroup\$ Doing nothing but XOR has issues with hash collisions, both because XOR is commutative (e.g., abc hashes to the same value as cba) and because it biases to zero values (a XOR b = 0 for any a = b, which happens frequently in real-world data). You could toss in a multiplication with a prime number before or after the XOR function to resolve that, though. \$\endgroup\$ – Dan Lyons Aug 23 '16 at 17:49
  • \$\begingroup\$ @DanLyons Multiplication is also commutative. \$\endgroup\$ – paparazzo Aug 23 '16 at 17:51
  • 1
    \$\begingroup\$ @Paparazzi: Whether multiplication is commutative is irrelevant; it is not commutative with xor. (A * B) ^ C and A * (B ^ C) can have completely different values; consider A, B, C all equal to 2, for example. \$\endgroup\$ – Eric Lippert Aug 23 '16 at 17:59
  • \$\begingroup\$ @DanLyons: Can you briefly explain why prime numbers have a desirable property as a multiplicand? \$\endgroup\$ – Eric Lippert Aug 23 '16 at 18:00
  • 1
    \$\begingroup\$ @Paparazzi: The proposal for mixing them is the comment you replied to. It is in the sentence "... toss in a multiplication ... before or after the XOR". \$\endgroup\$ – Eric Lippert Aug 23 '16 at 18:08
0
\$\begingroup\$

After discussion in comments of my other answer I did some investigation and found this interesting 5 years old article form Eric Lippert. It says

[...] In particular, be careful of “xor”. It is very common to combine hash codes together by xoring them, but that is not necessarily a good thing. Suppose you have a data structure that contains strings for shipping address and home address. Even if the hash algorithm on the individual strings is really good, if the two strings are frequently the same then xoring their hashes together is frequently going to produce zero. “xor” can create or exacerbate distribution problems when there is redundancy in data structures. [..]

Therefore XOR seems not to be the best solution for combining hash codes in general. Not sure if that is true in your case because the quality of the hash functions depends on the distribution of the data.

However, if XOR is still to slow, you could try to simplify the hash function. Of course, that will increases the number of collisions, but probably it performs better than a GetHashCode method that is much slower than Equals.

You could try something like that for example:

public static int GetHashCode(long[] array)
{
    if (array == null) return 0;
    if (array.Length == 0) return -1;
    unchecked
    {
        int hash = 17;
        hash = 31 * hash + array[0].GetHashCode();
        hash = 31 * hash + array[array.Length/2].GetHashCode();
        hash = 31 * hash + array[array.Length-1].GetHashCode();
        hash = 31 * hash + array.Length;
        return hash;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.