Reimplementation a Hash using open addressing

[akzhan]

Crystal Hash(K, V) should be reimplemented using open addressing and powers of two.

To be read:

• http://www.idryman.org/blog/2017/05/03/writing-a-damn-fast-hash-table-with-tiny-memory-footprints/.
• https://github.com/konovod/testhash
• https://github.com/yxhuvud/crystal-hash
• https://developers.redhat.com/blog/2017/02/27/towards-faster-ruby-hash-tables/
• (sometimes 508) http://blog.redpanthers.co/behind-scenes-hash-table-performance-ruby-2-4

Thanks to @RX14, @konovod, @yxhuvud for links.

Refs #2817, #3932, #2331 and #4033 (comment) to continue discussion and implementation.

[funny-falcon]

Questions to be cleared:

• current Hash implementation preserves order of insertion. Should new implementation do the same?

If so, then single valuable design is that is adopted by PHP, Python and Ruby: "open-addressing hash array" consists indexes to entries array.
With this design there is no much profit from clever alhorithms like "robin-hood hashing". Correctly implemented double hashing looks to be enough.

• should Hash be able to contain more than 2^31 entries? It will cost additional memory and/or complexity.

• should index array be compressed for small hashes? Or is it ok to alqays store indices as uint32?

• which Key types could live without saved hash value? Obviously, integer types. Is it ok to always store hash for non-integer keys?
  But even integer keys have to have bitmap for deleted entries.

[akzhan]

• We usually follow Ruby behavior in these cases:

"Hashes enumerate their values in the order that the corresponding keys were inserted."

• 2^31 seems like reasonable limit (but you can propose 2^62 or something else).

• Small hashes are common just like a Ruby.

• Every object has the hash method that responds to get a hash value. It's OK to use it only. Just to explain: LLVM usually inline Int32.hash etc. calls in release mode because Hash(K, V) is statically typed generic class.

/cc @asterite

[RX14]

With this design there is no much profit from clever alhorithms like "robin-hood hashing". Correctly implemented double hashing looks to be enough.

Why is this and are there benchmarks to back it up?

[funny-falcon]

Every object has the hash method that responds to get a hash value. It's OK to use it only. Just to explain: LLVM usually inline Int32.hash etc. calls in release mode because Hash(K, V) is statically typed generic class.

@akzhan , but Crystal's current hash functions are just awful for hash table with "power of two". Especially awful Float "identity" functions:

$ crystal eval 'puts 1.0.hash.to_s(16)'
3ff0000000000000
yura@dell:~/Project/postgresql/build$ crystal eval 'puts 2.0.hash.to_s(16)'
4000000000000000

Every hash function is 'ok' if hash table is by prime numbers. But for "power of two" more work should be done.

And, by the way, looks like Crystal is the only contemporary language of "application level" that doesn't fear of HashDos:

• neither hash seeded in any way (with global or per-table seed),
• nor "strong" hash algorithms used.

Is it intentionally? Is Crystal recommended for public interface, or is it for private tools only?

[funny-falcon]

Why is this and are there benchmarks to back it up?

@RX14 , what cool algorithms (like "robin-hood" hashing) for?
RR is for:

• cache-locality on lookup
• high-density - big load factor
• and short lookup chain with two previous property preserved.

With ordered hash table implemented as "indices array + entries array" both first two properties are not preserved:

• cache-locality is destroyed by lookup to entries array with index.
  It could be fixed if hash value is stored alongside with index. But it will cost memory footprint then.
• load-factor is dictated by "entries array" reallocation strategy, and doesn't depends much on cleverness of "indices hash" algorithm. (Exception from the is Hash(Int32,Int32) - entries array comparable with indices hash array. But it whould be pity to introduce additional algorithmic complexity just cause of this case).
• with low load factor (0.33-0.66) , lookup chain is usually short regardless of algorithm cleverness. And since indices array usually smaller than entries array, it is better to simply reduce maximum load factor.
  With clever trick, first two lookup are could be made into consecutive cells of indices array even if "double-hashing" is used.
• deletion is already have to be handled within entries array (for correct iteration). And rehashing have to be done when entries array is full. So no need in clever deletion algorithm.

I agree that clever algorithms are useful. But it will be useful for UnorderedHash, if some will add it to Crystal. Ordered Hash table destroys much of gain from cleverness.

[RX14]

I was sure we further hashed the #hash return value with a hash with better distribution. I must be going crazy.

@funny-falcon Why do we need an entries array instead of simply using a doubly linked list inside an Entry struct as we do now? Doesn't this solve most of the problems you listed.

[akzhan]

@funny-falcon

• Thanks for deep into FloatXX.hash implementations. It's yet another reason to reimplement Float64.hash using something like _Py_HashDouble. Yes, WIP (introducing of frexp was first step Introduce Math.frexp method. #4560). There is related Problem with Hash's hash codes truncation #3932 issue. Anyway XXX.hash reimplementation is related, but another task.

• Hash value must be seeded by Hash class itself. It is not implemented yet, but we have Problem with Hash's hash codes truncation #3932.

[akzhan]

OK, @funny-falcon - just to clarify, what do you recommend to implement following #4557 (comment)?

Anyway object hash functions will be adjusted.

[akzhan]

Powers of two is not a dogma. It's just faster in some scenarios.

Open addressing looks like just fit to modern processors.

[asterite]

@funny-falcon Crystal is a work in progress, totally not production ready. Not a lot of thought (in fact I would say "none") has been given to hash functions, they "just work". Pull requests and discussions are welcome to discuss and enhance this, though I personally know nothing about the subject.