fyi the article layout is a bit wanky in chrome and mozilla. However, Safari doesn't have this problem
Building an efficient hash table in Java
11–20 of 22 posts
Re: Building an efficient hash table in Java
#12Not an different algorithm, but around 15 years ago I looked at the JDK’s hashmap implementation and saw it was doing a loop to calculate the next highest power of two (after some multiplier) to determine the table capacity.
For fun, I swapped it for a bitwise calculation from Hacker’s Delight. It benchmarked surprisingly well, multiple percent improvement at various map sizes (even after JIT warmup). Swapping a 3 line loop for a one line bit twiddle wasn’t the most beautiful change, but I was surprised I could beat the original with such a trivial change. It also made me wonder why it hadn’t already been done.
I didn’t have any interest in trying to push it back upstream, but it was a fun to do.
Re: Building an efficient hash table in Java
#13Heheh a bit tangential, but a long time ago, I had a similar thought: how much performance could we gain if we just compared hash values (typically integers) and avoided comparing actual keys -- and the pointer-chasing that entails -- as far as possible?
The problem is that for a regular hash table, eventually keys must be compared because two keys could have the same hash value. So maybe we relegate key comparisons only in cases when we encounter a collision.
The only case where this can work is when the set of keys that could ever be looked up is static. Otherwise we could always get a lookup for a new, non-existent key that creates a new collision and return the wrong value. Still, there are cases where this could be useful, e.g. looking up enum values, or a frozendict implementation. Something like minimal perfect hashing, but simpler.
So I came up with this silly project and benchmarked it in Java, C# and a hacky CPython "extension": https://github.com/kunalkandekar/Picadillo
A very micro optimization, but turned out there was a 5% - 30% speedup on a PC of that era.
Re: Building an efficient hash table in Java
#14Really cool, excited to see how the rest of the library pans out. @dang perhaps auto-flagged as was top of front-page for a few minutes then disappeared, shame as a fun read.
Thanks! Appreciate it
Re: Building an efficient hash table in Java
#15fyi the article layout is a bit wanky in chrome and mozilla. However, Safari doesn't have this problem
Thanks for the heads-up!
I'm still figuring out Hugo, so I'm not sure I can fix it right away, but I'll take a look.
Re: Building an efficient hash table in Java
#16In a concurrent environment, I wonder if the overhead of wrapping every API call with a synchronized would make this significantly slower than using ConcurrentHashMap.
Thanks. This is actually one of the topics I really want to tackle next.
If we just wrap every API call with synchronized, I'd expect heavy contention (some adaptive spinning and then OS-level park/unpark), so it'll likely bottleneck pretty quickly.
Doing something closer to ConcurrentHashMap (locking per bin rather than globally) could mitigate that.
For the open-addressing table itself, I'm also considering adding lightweight locking at the group level (e.g., a small spinlock per group) so reads stay cheap and writes only lock a narrow region along the probe path.
Re: Building an efficient hash table in Java
#17Heheh a bit tangential, but a long time ago, I had a similar thought: how much performance could we gain if we just compared hash values (typically integers) and avoided comparing actual keys -- and the pointer-chasing that entails -- as far as possible? The problem is that for a regular hash table, eventually keys must be compared because two keys could have the same hash value. So maybe we relegate key comparisons…
This is a really fun project!
In SwissTable, the main difference is that you only get a probabilistic signal of presence (kind of like a Bloom filter), but the core idea feels very similar.
Re: Building an efficient hash table in Java
#18Not an different algorithm, but around 15 years ago I looked at the JDK’s hashmap implementation and saw it was doing a loop to calculate the next highest power of two (after some multiplier) to determine the table capacity. For fun, I swapped it for a bitwise calculation from Hacker’s Delight. It benchmarked surprisingly well, multiple percent improvement at various map sizes (even after JIT warmup). Swapping a 3 li…
Ohhh, I went digging after your comment and I think this is exactly what you were referring to: JDK-7192942 ("Inefficient calculation of power of two in HashMap").
I honestly love hearing about these hidden gem micro-optimizations.
Thanks a lot for sharing!
Re: Building an efficient hash table in Java
#19In a concurrent environment, I wonder if the overhead of wrapping every API call with a synchronized would make this significantly slower than using ConcurrentHashMap.
Thanks. This is actually one of the topics I really want to tackle next. If we just wrap every API call with synchronized, I'd expect heavy contention (some adaptive spinning and then OS-level park/unpark), so it'll likely bottleneck pretty quickly. Doing something closer to ConcurrentHashMap (locking per bin rather than globally) could mitigate that. For the open-addressing table itself, I'm also considering adding…
I think that's a great idea! I just checked one of my larger projects and it 55% ConcurrentHashMap and 45% HashMap so I'd personally benefit from this plan.