4
\$\begingroup\$

I implemented open-indexing sparse 2D spatial HashMap, and I'm quite satisified with performance ( ~30-70 CPU cycles to get object at particular location for size ~16 Milion objects ).

However, I don't understand behaviour of hashFunction. Just by trial and error I found out that best performing for my case is slightly modified Knuth's hash function:

return i * 2654435761 >> 8;
( original Knuth's hash function is return i * 2654435761 >> 16; )

with this hash function I get no more than 1-2 buckets maped to the same hash (when capacity is sufficient) ... the histogram looks like: 689780 without collision (buckets mapped to same hash) 358791 with 1 colision 5 with 3 collisions

but I have no idea why, and why it is performing better with >>8 than >>16), and if this behaviour is general or somehow specific for my settings

I also tried other hash functions which are used as pseudo random generators .. some are here:

inline ULONG hashFunc( ULONG i ) {
// see http://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key
//return  ( ( 2166136261UL ^ i ) * 16777619 );              // VERY BAD
//return  ( 2166136261UL ^ (i * 16777619) );                // VERY BAD
//return ((i >> 16)^i);                                     // NOT WORKING
//return ( i * 2654435761 >> 16 );                          // Knuth's multiplicative method // GOOD
return ( i * 2654435761 >> 8 );                             // GOOD, even better than Knuth for map size 2^16 ( 65536 fields )
//return ( i * 2654435761 >> 16 ) ^ i;                      // REASONABLY GOOD but worse than pure Knuth
//i = ((i >> 16) ^ i) * 0x45d9f3b; i = ((i >> 16) ^ i) * 0x45d9f3b; return  ((i >> 16) ^ i);                                        // REASONABLY GOOD but worse than pure Knuth
//i = ((i >> 16) ^ i) * 0x45d9f3b; return  ((i >> 16) ^ i); // LESS GOOD
//i = ((i >> 16) ^ i) * 0x3335b369; i = ((i >> 16) ^ i) * 0x3335b369; return  ((i >> 16) ^ i);                                        // LESS GOOD
};

all are performing worse than Knuth or modified Knuth. ( Just empirical observation, no idea why )

The questions:

  1. Do you have experience that some other hash function performs better for such job ?
  2. Do you understand the behaviour?
  3. Do you know how to properly make analogy to Knuth 32bit for 64bit integer ( because if I understand it correctly, the 32bit golden ratio multiplicator is prime number, I'm not sure If it is easy to get multiplicator with such property for 64bit )

some details for explanation:

I have to say that I use the hash function somewhat differently than is common:

  1. First I discretize double x,y to uint16 ix,iy
  2. Then I compute bucket index as uint32 bucket = (iy<<16)+ix;
  3. Then I compute the uint hash = hashFunc()&mask where mask = capacity -1 and capacity is power of 2 ( &mask is basically modulo capacity ). I know that many people recommend use prime-number capacity for hashmap, but I find it tricky to find proper prime number during resize-ing, and also & is faster than modulo.

My hashmap is open-indexing, and it is able to realize if the object is in particular particular grid tile (ix,iy = bucket ) without actually dereferencing the object pointer, which I think gives it speed advantage.

each memory field of the hashmap stores not only pointer to the object TYPE* object but also the bucket index uint32 bucket to which the object belong and number of objects uint n with the same hash. The bucket index is used to check if object belong to particular (ix,iy) position or if it was mapped to that hash by chance (when there are collisions). I do not store hash since I think it is faster compute it on the fly than use more memory.

( you can see code here ( HashMap | HashMap2D | test_HashMap2D) If you are interested

\$\endgroup\$
5
\$\begingroup\$

First of all, for uniformly distributed data, Knuth’s function i * 2654435761 >> 16 is definitely better than i * 2654435761 >> 8 because it shuffles more bits. An explanation follows.

Consider the multiplication of numbers WXYZ and PQRS (all these letters representing arbitrary digits in any base) and see how the digits get added together in the end:

WXYZ * PQRS =    WP WQ WR WS
            +       XP XQ XR XS
            +          YP YQ YR YS
            +             ZP ZQ ZR ZS
            —————————————————————————
            =  A  B  C  D  E  F  G  H

You can see that the last digit of the result, H, only depends on Z and S. Whereas the digit in the middle, E, depends on all digits of the initial numbers. A good hash function of this form will therefore try to pick digits in the middle of the multiplication result, for better shuffling, hence the >> 16 for a 32-bit hash.

Now what does it mean if your test results are not what the theory predicted? The theory may be wrong, but we’re talking about Knuth, so I’d be more tempted to say that the test is wrong. And indeed TestApp creates points with coordinates between -150.f and 150.f, but your map object is set up to store values between -16384.f and 16384.f. In other words, in the end you are hashing a series of numbers WXYZ where W hardly ever changes, making the higher bit values useless to the final result. I hope this makes it also clear to you why the >> 8 shift is giving you better hashes.

I’m not sure how you’d want to fix the test, but you could for instance insert points in this way instead:

points[i].set((ix + randf()) * map.step * 0x7fff / nside,
              (iy + randf()) * map.step * 0x7fff / nside);
\$\endgroup\$
  • \$\begingroup\$ thanks, this makes sense. But I would like some hash scheme which would work well for any size of the map. One reason why I want to use HashMap instead of some GridMap od OctTree is that the map can be modified at runtime (during the game) ... grow and shrink by actions of users. I want to have possibility to make map up to +/-16384 tiles large, even thought I would usually use just few hundreds tiles in the centre. \$\endgroup\$ – Prokop Hapala Jan 20 '16 at 15:23
0
\$\begingroup\$

For MLCG constants you want an odd number that's a multiple of five (assuming no explicit modulo). That'll be a weak PRNG. For Weyl like generators in integer you want an irrational scaled and rounded to odd...golden ratio and sqrt of two are good choices. That will give you a weak low discrepancy sequence. Neither of these tend to work well for hashing.

Starting from the point where you have quantized and packed the coordinate what I would suggest is to pass that through a bit finalizer that performs well with low entropy inputs (keys). One or two xorshift multiple sequence as an example.

A method to improve the current scheme would be to change the shift and mask N bits to shift off all but the top N bits as per Sam's answer.

\$\endgroup\$
  • \$\begingroup\$ I feel your answer is very knowledgeable, but since I'm not an expert I'm not familiar with many things you say. What means MLCG and PRNG? To the second part - It would be helpfull if you write is by few lines of code. Also I was considering to use other hashing schemes described e.g. here cybertron.cg.tu-berlin.de/eitz/pdf/2007_hsh.pdf but I found that since Knuth gives just few collision, I'm not sure if computational cost of more complex hash is worth it. \$\endgroup\$ – Prokop Hapala Jan 20 '16 at 15:35
  • \$\begingroup\$ I am stuck with cell only for the next week or so...I'll clean up my answer later. MLCG=multiplicative linear congruent generator. prng=pseudo random number generator. Taking the top N bits should work reasonably well \$\endgroup\$ – MB Reynolds Jan 20 '16 at 16:03
  • 1
    \$\begingroup\$ I typed up a post with the theory \$\endgroup\$ – MB Reynolds Mar 4 '16 at 12:52

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.