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.

[luislavena]

@asterite can we assume Hash(T) to should not honor ordering? (aka: recent Ruby behavior vs legacy 1.8.x one).

Working with that assumption, several changes can be recommended for Hash(T) without introducing yet another base class.

Thank you.

[funny-falcon]

@RX14

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

You are not crazy. Just with "prime numbers" it was not strictly necessary. But both "power of two" and trick with multiplying instead of modulo requires that step, if original hash function is such dumb.

@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.

But it introduce new problems: how reliably and efficiently combine double-linked list and moving semantic of Robin-Hood hashing? At least it will demand additional memory for list. Should it be compressed for small hashes? If so, then you will have a lot of branches to deal with. And you will ruin insertion performance.

Consider that most hashes in applications are "delete-less" ie they are only filled and (rarer) updated. Especially web applications (that selects a lot of db records, and only shows them). For such hashes, "indices hash + entries array" is most efficient data structure (if order of insertion should be preserved).

[funny-falcon]

@akzhan

OK, @funny-falcon - just to clarify, what do you recommend to implement following #4557 (comment)?
Anyway object hash functions will be adjusted.

First, I believe it is better to have:

  def hash_inc(state : HashState)
    state = state.mix(v1)
    state = state.mix(v2)
    state
  end
  # default implementation inherited from Object
  def hash
     state = HashState.new
     state = hash_inc(state)
     state.finalize
  end

For backward compatibility, it could be reverted:

   def hash
     ...
   end
   # also inserited from Object. Is it possible to inherit both default hash and hash_inc?
   def hash_inc(state : HashState)
      state.mix(hash)
   end

(If HashState is a struct. I believe, optimizer has more freedom with such design. But it is not dogma.)

And then, Hash will initialize HashState with global or per-table random seed.

Float's hash then could be implemented as:

struct Float64
   def hash_inc(state)
      state.mix(unsafe_as(Int64))
   end
end

Second, (a bit of self promoting) I "recommend" to use my hash function:
https://github.com/funny-falcon/funny_hash/blob/master/funny_hash.h
It is simple, fast enough, has state of just two variables, and has fast and simple incremental mode.
Probably it is not "bullet proof" as SipHash, but I believe it is just enough for hash-table hash-function.

I'd be happy to implementation all above if you like the design.

Powers of two is not a dogma. It's just faster in some scenarios.
Open addressing looks like just fit to modern processors.

With sane hash functions, "power of two" becomes sane choice.

[RX14]

@funny-falcon yeah it didn't hit me that Entry wouldn't be in the heap any more (if we wanted cache locality at least), you're right.

I think we should implement an ordered and unordered hash and see how fast we can make each one. Once we have data on how much of a performance difference it makes for insertion and deletion, we can decide. I'd like to see it kept ordered but if it's going to be 2x slower I don't think it's worth it.

[RX14]

Also power of 2 means that the hash table can have a load factor as low as 0.5 right? I'd prefer if our hash implementation was memory efficient.

[funny-falcon]

@luislavena

@asterite can we assume Hash(T) to should not honor ordering? (aka: recent Ruby behavior vs legacy 1.8.x one).
Working with that assumption, several changes can be recommended for Hash(T) without introducing yet another base class.

@RX14

I think we should implement an ordered and unordered hash and see how fast we can make each one. Once we have data on how much of a performance difference it makes for insertion and deletion, we can decide. I'd like to see it kept ordered but if it's going to be 2x slower I don't think it's worth it.

Back in the time, I thought it was huge mistake to introduce ordered hash for default Hash in Ruby 1.9 , cause double linked list eats a lot of memory. But then PHP adopted this new design, and then Python, and now Ruby. Now I'm not sure.

Now I believe, two base classes is "righter" way to go. Question is: should OrderedHash or UnorderedHash be default Hash?

[funny-falcon]

@RX14

Also power of 2 means that the hash table can have a load factor as low as 0.5 right? I'd prefer if our hash implementation was memory efficient.

In fact, prime numbers are less flexible in terms of memory/performance efficiency. Yes, you may have more prime numbers, but then you will pay for rehashing.

Power of two allows Linear Hashing. It is straight forward to implement with chaining. I implemented it once with Cuckoo Hashing. And I know implementation with Coalesce Chaining.

In any way, when we talk about OrderedHash implemented as "indices array + entries array", hash load factor affects only "indices array", and so doesn't matter that much.

And another point: memory efficiency is almost always result of tradeoff - you pay raw performance for memory efficiency. Cuckoo Hashing and Robin Hood hashing trades insertion performance for lookup performance and memory efficiency. I doubt usual application will win from this tradeoff.

I believe, there should not be "Ultimate Swiss Knife" Hash for every kind of usage. It should be convenient enough, fast enough and memory efficient enough for regular usage. It should not be "super convenient", nor "super fast", nor "super memory efficient", cause either "super" trades off from other.
And don't forget about code complexity: it should be simple enough to be confident in.

Those rare men, who need particular "super" should implement it by them-self, because they knows better what they want.

[funny-falcon]

Ahh, I talk too much. Lets go to work.

[RX14]

I didn't mean to accept both ordered and unordered implementations into the stdlib, just to benchmark both and use that to decide which to accept later.

[funny-falcon]

Then bechmark should a real application, not "microbenchmark".

Unordered open-addressing will beat ordered hash in almost every micro-benchmark, except, probably, iteration (and maybe insertion).

But will real application gain from this "victory"? It is a good question.

And OrderedHash-es are prooved to be useful, otherwise there weren't such hash in many standard libraries (Python had inefficient implementation for a while; before Ruby 1.9 became wildly adopted, ActiveSuport implemented ordered hash by itself).

So, certainly OrderedHash should be in stdlib. If it will perform at 90% of UnorderedHash performance, shouldn't it be default Hash? (imho, it should) 80%? 70%? (then choice is not so obvious to me :-) )

[RX14]

@funny-falcon that's what I was getting at, of course unordered will beat ordered in the benchmarks the question is how much.

I'm not entirely sure how much the compiler uses hashes but it might be a decent candidate for benchmarking (if you disable the LLVM parts and just dump the bc). Otherwise a web application uses hashes for http headers (and params but they're lazily parsed so you'll have to actually access those). Ideally we'd have both micro benchmarks and real applications being benchmarked with changes.

[akzhan]

@sdogruyol, @Eliasjp, @elorest, @drujensen and others: can You help to choose Hash implementation? There is good question to be cleared:

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

Please read discussion (there are many questions).

[funny-falcon]

Rust tries to be system language, and tries to be as efficient as possible. And then it adopted strange choses as SipHash24 and 92% load factor. I proud I convinced them to switch to SipHash13 (but I'm sure, simpler hash function will be enough). And they are ready to reduce load factor (not my proud :-) ).

What is Crystal's intention? Is it application language, or system language? Is it "convinient C/C++" or "fast Ruby"?

While Crystal certainly could be used for both,
I believe that intention dictates defaults and stdlib.

(But yeah, C++ std:vunordered_hash is awful :-) )

System language doesn't need bullet-proof super-convinient Hash as default. It needs fast Hash (and hash functions).

Application language should not demand programmer to think about such issue: Hash should be convinient and safe.

[akzhan]

@funny-falcon

Just my opinion:

Default - Crystal is not system language. It's application/framework one (Crystal may be embeddable into Ruby applications later, as I have seen on Roadmap - "DSL for writing Ruby extensions").

Also looks like 50-75% load factor is OK. Anyway we can implement OrderedMap and BusyMap, for example, as additional classes. But it is just my opinion, Crystal compiler itself will explode with these assumptions :)

[RX14]

@funny-falcon what are the tradeoffs between Rust's hash map and what you're proposing for crystal. I'm not sure what you mean by " strange choices".

[funny-falcon]

New key during iteration could be forbidden just as documentation.

It is quite easy to check during iteration, than no rehashing occured due to new keys (as Ruby's st_tables does now).

But check for concurrent iteration during each insert (like Ruby's Hash does) could be inefficient a bit. Though, it will be friendlier for unexperienced programmers.

[funny-falcon]

Found during investigation, that 64bit Crystal has serious issue for serious programming: #4589
I will just ignore presence of this issue at the moment.

[akzhan]

just links to #4946, #5000, #5104 and #5146 (i prefer latest, of course).

[akzhan]

Now it's time to develop new hashes!

[yxhuvud]

Hmm, maybe I should get mine to compile again. Not because I think it is very fast (I don't - f-f simply have more experience in building hash tables), but because it gives something to benchmark against.

And I am quite certain I benched using numbers, and as ysbaddaden showed the hash function for those where abysmal.

[funny-falcon]

Here is a draft: https://gist.github.com/funny-falcon/084f7ebc159401dfd56bf33241a2ebd6
It certainly contains unknown bugs, but it could be benchmarked with simple scenarios.

[akzhan]

@funny-falcon it should be better in form of [WIP]Pull Request.

[akzhan]

Looks like Hash should be adopted for two different sizes (small (<=6?) and others).

[asterite]

It would be so cool if someone would retake this issue. Maybe copying in parts the algorithm used by Ruby. Or I think just anything that uses open addressing while retaining insertion order somehow should be a good start and a good improvement because it will avoid having to allocate memory on each hash insertion.

[asterite]

I'm experimenting with this a bit. I did something really simple (open addressing, linear probing, two arrays: one for indices, another for ordered entries). So far the results are promising, it works faster than the existing Hash and allocates less memory (and should also have better cache locality). I still need to take care of deleting hash entries in a smart way, though...