I have a performance-critical framework that went from Java’s Map to Trove (http://trove4j.sourceforge.net/html/overview.html) and now uses FastUtil (https://fastutil.di.unimi.it/).

For my use cases, these massively outperform the built-in java Maps and Sets.

It would be interesting to include these in the benchmark. A quick googling finds plenty of comparisons that are a few years old now but I can’t find a current up to date java map/set benchmark.

Or was this for Object/boxed primitives, too?

There are two areas that are important in my use case:

* the performance of normal get/computeIfAbsent/forEach etc. FastUtil has for example fast iterators avoid allocating Map.Entry etc.

* the memory usage. The total footprint is important because I actually dimension VMs based on stuff. But garbage collection minimization is also really important.

To be fair, unlike std::unordered_map, the open addressing implementations don't come with a guarantee that they won't move the items in the hash table. But in practice that doesn't really matter anyway, since you could always use unordered_map<unique_ptr<T>> instead of unordered_map<T>. But, I digress..

* Memory footprint and GC load

* Write performance (especially characterizing fast-path vs. rebalance times)

* Loading vs. performance tradeoffs (can the table perform well with 80% occupancy? 99%?)

* Small-table utilization.

If some of the implementations consume substantially less memory and/or GC churn while having largely indistinguishable lookup performance, then they're a win for value. This is one place that open addressing can win.

For the libraries we were writing, we didn't know if consumers would be stuffing in one element (the most common case) or millions of elements (uncommon but important), so we ended up implementing a clever abstraction that would start with a pointer to the single object, then replace it with a hash table when the second element was added. Since we used hash tables like country doctors prescribe aspirin, it reduced the heap footprint of the server by ~30%. Of course, Hansen's Law states "Clever is the opposite of maintainable," and that definitely applied here.

I think with regards to C++ using separate chaining is a legacy decision made in the late 1990's. I think back then, the CPU vs memory speed difference was not as big, so pointer chasing wasn't considered that big of a deal. In addition, this was the days of 32-bit systems with MB's or RAM so having separate, smaller allocations was seen as better than having one large one (see for example deque).

Nowadays, with a much bigger relative performance penalty for accessing memory as well as 64-bit systems with GB's or RAM, I think people are moving to open addressing (for example Rust, as well as Google and Facebook's hash table implementations) unless you need pointer stability.

The fact that std::unordered_map more or less mandated separate chaining is seen as something that holds the standard library back in terms of performance, hence the competing implementations from Google and Facebook.

[0]: https://youtube.com/watch?v=ncHmEUmJZf4

Think about how vector would be implemented under the hood. What happens if you delete an element? Does it shift down all of the elements after it? If you do that, the objects have literally moved in memory. Any pointer that points into those memory locations is now invalid. That's a problem if you wanted to hold onto pointer to elements. But if you declare that your interface has certain pointer stability guarantees then suddenly your implementation is massively constrained. Now your vector implementation will have big gaps that you need to deal with and will waste a ton of memory if you add and remove many elements.

Pointer instability means that it is undefined behaviour to:

1) store (both on stack and heap) the pointer address to a value element outside of its respective container

2) then modify the container's content

3) then thereafter use the stored pointer address

This implies that:

- containers without pointer stability require pass-by-value (or a pointer to a temp copy) to be used for its values after accessing them OR

- containers without pointer stability require absolute immutibility of the container to guarantee runtime safety OR

- containers without pointer stability require "relative" immutability during the existence of a pointer to a value element to guarantee runtime safety. Note that I think this last option is a bad idea, because it requires multithreaded blocking/synchronization of the container and is also easy to encapsulate wrongly, leading to UB.

... with a specific set of mutating operations that (may) alter the container's structure (eg, element insertions and removals).

Altering the value of one element of the container doesn't invalidate iterators or references to any element. You can make as many mutating passes over a std::vector as you like without invalidating anything.

Things only start to get dicey when you push_back(), insert(), erase(), etc.

Allocating every object separately in its own node as used in chaining implementations guarantee that the object location is stable (i.e doesn't change), but in addition to making iteration slower it requires separate allocation for each object.

Looking at some discussions the open-jdk team had, they decided to continue with Separate Chaining. I don't have the link, but then I got interested to see how some Open Addressing (nothing fancy) will behave in Java, so this is the reason I've written this "article".

Unfortunately I coudln't beat HashMap with the "classic" approach, but I got close. I am curious to see a better implementation that brings more engineering tricks on the table.

I think one of the big advantages of using open addressing is memory locality. Since it is harder to control memory layout in Java (and relies on the optimizer/JIT to optimize common patterns) I wonder if you are getting the full benefit of open addressing in Java.

In addition HashMap is standard and the Java compiler/optimzer/JIT can make certain assumptions about how it is used which may enable certain optimizations. Also, a lot of the heuristics for optimization likely used a lot of profiling over the years, and because HashMap is so widely used, it is likely that common usages of HashMap are reflected in the profile data and thus the optimization heuristics.

You could, manually :). Either way if they're hot, they're inlined.

One common trick for open-addressing maps in Java I don't see in your implementations is to have an array of keys zipped with values (or two arrays, one for keys, one for values) instead of array of Entries. This improves locality and indirection a bit. Obviously more is needed for even more speed.

(Mandatory "in the future it will be better": Valhalla is coming in a few years, that's when we'll have much more control over the memory layout.)

The tradeoffs are more complicated for a jit, but for an aot compiler it’s one of the most important optimisations in the pipeline.

Might be what you're looking for?

Also maybe there are some tricks that can be done, to have a faster Open Addressing implementation in Java.

PS: I've also tried Cuckoo Hashing and Hopscotch and they were also slower, but haven't managed to document my findings.

That is why you shouldn't use hash tables in code that might (even potentially) become a target for DoS attacks.

You can use a family of hash functions and seed the hash table instance with a key.

The attacker won't be able to do make assumptions regarding collisions because he doesn't have access to the initial key.

The optimizations are cache friendly open-addressing with linear probing, storing the hash, and power of 2 sizes. Another usual optimization would be a sorted array instead of the linked list.

Linked list buckets are terrible for cache locality anyway.

[1] https://cr.openjdk.java.net/~skuksenko/valhalla/hashmaps/has...

How much do you want to bet on that?

Also fun read: https://eev.ee/blog/2012/04/09/php-a-fractal-of-bad-design/

Isn't it a rather safe bet since most people won't roll their own hash functions anyway.

  This is done by initializing a (unsigned) vrbl "perturb"

The premise is that probing consecutive memory addresses is cheap because of cache locality and because the address computation is a simple increment. This should be cheaper than resolving hash collisions with additional random probes or by chasing linked list references to random memory locations for each link.

https://github.com/python/cpython/blob/f840398a5fd8741653c26...

The article contains also a Robin Hood implementation that overall works worse than HashMap. If you can give something recommendation on how to improve it I would forever in debt.

Here's the code I tested with.

php:

  #!/usr/bin/env php
  <?
  $ret=[];
  for($i=0; $i<5000000; $i++){
   $ret["id.".($i%500000)]="val.".$i;
  }
  print(count($ret))."\n";
  print $ret["id.10000"]."\n";

  #include <iostream> 
  #include <map> 
  using namespace std; 
  
  int main(){ 
   map<string, string> ret; 
   for(int i=0; i<5000000; i++){
    ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i); 
   }
   cout << ret.size() << endl;
   cout << ret["id.10000"] << endl;
   return 0;
  }

  use std::collections::HashMap;
  fn main(){
    let mut ret = HashMap::new();
    for i in 0..5000000 {
        ret.insert(format!("id.{}", i%500000), format!("val.{}",i));
    }
    println!("{}", ret.len());
    match ret.get("id.10000") {
        Some(val) => println!("{}", val),
        None => println!("ERROR")
      }
  }

unordered_map is the hashmap.

map is a red-black tree, which keeps the data sorted. You should use map<> if you need to visit the data in-order with a for-each loop. Hashmaps can't visit the data in order.

unordered_map is actually known to have relatively bad performance on GCC and some other open-source implementations. I don't know if there's a spec-problem that favors a slower-hash table (rather than the modern open-addressing scheme, which is faster on modern computers), but I can believe unordered_map has an issue on common standard libraries today.

------------

> ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i);

Lets count the mallocs.

> string("id.")

One

> to_string(i%500000)

Two

> string("id.")+to_string(i%500000)

Three, then two frees() as the previous two strings are deallocated.

> ret[string("id.")+to_string(i%500000)]

Four. The ret[] operator searches for the string. Since it doesn't exist, it now has to malloc the key and insert the value in there. std::move() might solve that issue and cut this one out easily?

> string("val.")

Five

> to_string(i)

Six

> string("val.")+to_string(i)

Seven + 2x frees.

> ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i);

Eight, to place the value in there. Again, probably solved with std::move. +1 more free.

So eight mallocs and 6 frees?

---------

Yeah, C++ strings shoot yourself in the foot performance-wise. But they're easy to use and free of stupid malloc/free bugs, but it means that they will malloc/free a LOT more than you might guess with the untrained eye.

I know that Perl / PHP / etc. etc. were explicitly designed to be more favorable towards string manipulation. And I'd bet that there's some old C++98 stuff that might lock in the performance of string to this older, less performant model.

EDIT: I see you managed to avoid the problem of excessive mallocs/frees in the Rust code with "format". The C++ equivalent might be snprintf, though that dips down into C-style strings.

Yes. std::unordered_map requires that pointers to stored values will always be valid (except if the value is erased). This makes open adressing effectively impossible. If you need max. performance, std::unordered_map is indeed not a good choice.

> The ret[] operator searches for the string. Since it doesn't exist, it now has to malloc the key and insert the value in there.

The optimal method would be https://en.cppreference.com/w/cpp/container/unordered_map/em...

> So eight mallocs and 6 frees? > Yeah, C++ strings shoot yourself in the foot performance-wise.

Most implementations of std::string use short string optimization. Typically, you can save up to 12 chars (32-bit) or 24 chars (64-bit) inside the actual string container without any memory allocation.

Looking at the code example, I would say that there won't be any mallocs at all for std::string.

I think the performance difference just comes from the suboptimal design of std::unordered_map, where each node has to be allocated on the heap. In open addressing hash tables, as used by PHP (and I guess also by Rust), the nodes live in a single large array. The only memory allocation you see is when the array has to be resized due to a rehash - which happens very rarely!

> Yes. std::unordered_map requires that pointers to stored values will always be valid (except if the value is erased).

Hmm, that requirement also prevents Cuckoo-hashing.

The general pattern here (and this is problematic in a lot of languages), is the idea of having a "shortcut" into an object in a data-structure. For example, C++ and Java's "iterator-invalidation" rules are absolutely arcane, even if we removed the pointer-requirements.

Many data-structures want to move things around (cuckoo-hashing, open-addressing, robin-hood hashing... look 3 different, high-performance strategies and we're still just talking about hash tables!!). But those moves "invalidate" the shortcuts (be it a pointer or an iterator).

Some data-structures can have those pointers just fine (Red-and-black trees), others cannot. Representing all these possibilities with a fixed, easily understood interface that generalizes among all of these data-structures / decisions seems impossible.

------

Well, I guess that's why I keep rolling my own data-structures when I need performance guarantees... standard-library just has to make decisions that may or may not match my cases.

Yes, this is what many companies do. std containers are good enough for the general case, but are certainly situations where you need something more fancy. However, before you roll your own, first check if there's a good library you can use. The world's best hashtable has already been written by other people :-)

Iterators can be invalidated (e.g. after a rehash). The requirement is rather that the address of the value itself must not change (so that pointers will remain valid).

> If you really need that property, you could get most of the benefits by using unordered_map<unique_ptr<T>> instead of unordered_map<T>.

I agree. I don't know why they have decided for the current design. They even expose the bucket interface (https://en.cppreference.com/w/cpp/container/unordered_map/bu...) which should really be an implementation detail...

And determining if a cell is full or empty in a hash-map isn't exactly efficient either (You pretty much have to visit those locations and see if a tombstone or empty symbol is there).

-------

I recognize that people want to foreach() over a HashMap, but I'm just not convinced its an efficient operation, nor a good fit for the iterator interface (especially with all this discussion of invalidations and movement...)

Iteration doesn't necessarily imply a specified order.

> but I'm just not convinced its an efficient operation

Why does iteration have to be efficient?

> nor a good fit for the iterator interface

What would you use instead?

Iterator invalidation only comes into play when you erase elements. If you just iterate over a hashtable and, say, print the elements, you wouldn't have to worry about it at all.

So a foreach(cuckoo_table) operation may not in fact visit all elements if the table has an insert somewhere in the loop.

BTW, inserting elements can invalidate iterators with any hashtable if it might cause a rehash.

    foreach(datastructure){
        datastructure.what-functions-are-legal() ??
    }

List: All operations allowed, except for reading from an erased element.

map: All operations allowed, except for reading from an erased element.

unordered_map: ??? Under debate right now.

-------

So even if you had assurances that unordered_map.insert would work (ex: Robinhood hash, you check size() and compare to capacity(), much like a vector), the movement of data means that your iterator is basically invalidated on any insert.

So unordered_map(Robin-hood): Nothing. No erases, no insertions allowed during the foreach loop at all.

-------

This comes up in practice. The minute you have 2 threads, and a 2nd thread _might_ insert while the 1st thread _might_ be in a foreach loop, you suddenly have to have assurances for what is or isn't legal from an iterator-invalidation perspective.

I guess you could just have the entire for-each loop inside of a lock, but that seems a bit inefficient?

Yes, but this applies to any hashtable that might rehash on inseration (= most). In practice this is not a big problem. For example, you can just put the new elements / to be deleted keys on a std::vector and only insert/erase after the for-loop.

I don't see how this makes iteration itself problematic. You can still iterate over a std::unordered_map perfectly fine. Just don't erase/insert elements while iterating.

> I guess you could just have the entire for-each loop inside of a lock, but that seems a bit inefficient?

Yes, you would have to lock the whole for-loop. It's the same with any other data structures where the iterators can get invalidated on inseration/deletion, e.g. std::vector.

Even for containers where iterators are not invalidated, you have to be careful with fain-grained locks. For example, you can only increment the iterator while holding the lock!

There's std::format from C++20 too[1]. One can use std::ostringstream instead, I suppose, but at that point I'd probably use snprintf too.

[1] https://en.cppreference.com/w/cpp/utility/format/format

Note that std::format still returns a std::string (which might allocate memory, depending on the size of the string), but that doesn't matter if it is going to be moved anyways.

If you want to write into an existing buffer, you can use std::format_to_n as a modern replacement for snprintf.

  std::format("id.{}", i) // is fine

  std::format("{}-{}", oops) // You need two parameters, compiler knows this

of course one can always find faster, drop-in replacement libraries: https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-o...

e.g. replacing std::unordered_map with robin_hood::hash_map makes the above C++ code go from 1.2 seconds to 0.5 seconds on my machine (std::map is around 1.3/1.4 seconds for libstdc++).

(though as others said, this test is in big part a test of std::string performance... replacing strings by int make times go down to ~0.1s here)

You’re using the default hash function, which is SipHash 1-3, which is known to be quite slow. Not horrendously so but it was picked for attack resistance.

If you need high hashmap performances and control input (or have a rather safe type) it’s pretty common knowledge that you should replace the hash function with something like fnv or fx.

You’re also allocating a ton in a hot loop, also a known mispattern. I’d expect C++ to also be greatly affected there.

This can be much slower than just having a slightly slower hash function, because the equality function will be called against many more candidates, potentially with each requiring one or more uncached fetches from main memory.

I now recommend wyhash more often than not, and sometimes fnv can beat that. wyhash has the substantial advantage that it can also be made attack-resistant with a seed given to the builder, with much less overhead than sip.

My most recent problematic use cases for fx were all to do with hashing just one or two scalar integers per key. Its few per-word instructions weren't nearly enough to get a good distribution when there were only 1-2 words (on a usize=u64 target). Even hacking in fmix64 from Murmur3 helped a ton, but made it no faster than wyhash in the end, and harder to reason about. I ended up using wyhash for some keys and fnv for others.

In any case, nobody should switch hash functions without evaluating performance on full-sized realistic production data. You can easily end up with bad overall hash table performance because of poor distribution with your real keys.

Microbenchmarks tend to miss this, especially if they do not create real-sized and real-shaped key sets. Then all you see is the hash function performance, which is misleading if it results in poor overall table performance, which is what happened to me with fx in particular. I think a lot of people choose fx based on such microbenchmarks and assume its distribution is good enough to scale out, but this should not be assumed, only tested.

You might also see surprising effects from cache locality when testing tables big enough that they don't fit in cache, and if this matters for your workload then you definitely want to account for that in your choice of hash table data structure.

Even with all that, the php version was still 2x faster. And it truly is due to the hashtable implementation itself.

7.0 is when php switched to open addressing: https://www.npopov.com/2014/12/22/PHPs-new-hashtable-impleme...

Chaining was from php 5.