4 ms·

> But, as described here, the decision to use Separate Chaining vs. Open Addressing is not unanimously accepted by programming languages designers. For example,

> But, as described here, the decision to use Separate Chaining vs. Open Addressing is not unanimously accepted by programming languages designers. For example, in python, ruby, and rust, the standard hash tables are implemented using Open Addressing, while Java, go, C#, C++ are all more conservatory and use Separate Chaining. 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.

dpratt 5y ago
Granted, it’s a micro benchmark without a lot of context, but wouldn’t the conclusion that the default HashMap implementation is, on average, faster than all the open addressing implementations contradict this conclusion?
- nomemory 5y ago
  For me it was faster on average and with less variance. But the micro-benchmarks are flawed by default, so I believe it's room to improve them. 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.
  - dpratt 5y ago
    FYI, if you're the author of the article, you deserve some recognition. It's extremely well written, concise and detailed. I've sent it out to my entire team as recommended reading.
nomemory 5y ago
Exactly. 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.
- RcouF1uZ4gsC 5y ago
  > 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.
  - nomemory 5y ago
    Exactly, in Java i couldn't even inline my functions, and had zero control over the underlying memory layout.
    - JanecekPetr 5y ago
      > i couldn't even inline my functions 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.)
Koffiepoeder 5y ago
Could someone explain to me in a clear and high level fashion what exactly pointer stability (or pointer instability for that regards) entails? I've watched some of the cppcon talks on the google hashtable implementation [0] and in that talk Matt Kulukundis also mentioned it affecting the adoption rate, but I always failed to really grasp the concept and its implications. Google searches also ended up rather fruitless to be honest. [0]: https://youtube.com/watch?v=ncHmEUmJZf4 https://youtube.com/watch?v=ncHmEUmJZf4
- gpderetta 5y ago
  If you allocate your objects inline in your internal table, rehashing will invalidate existing references to those objects as they will need to be copied into the new, larger, table. 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.
- UncleMeat 5y ago
  An operation maintains Pointer Stability means if you take a pointer to an element in a data structure and then execute that operation, the pointer is still valid and pointing to the same data. 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.
  - Koffiepoeder 5y ago
    So, am I correct if I then put it as following? 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.

dpratt 5y ago

Granted, it’s a micro benchmark without a lot of context, but wouldn’t the conclusion that the default HashMap implementation is, on average, faster than all the open addressing implementations contradict this conclusion?

nomemory 5y ago
For me it was faster on average and with less variance. But the micro-benchmarks are flawed by default, so I believe it's room to improve them. 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.
- dpratt 5y ago
  FYI, if you're the author of the article, you deserve some recognition. It's extremely well written, concise and detailed. I've sent it out to my entire team as recommended reading.

nomemory 5y ago

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

RcouF1uZ4gsC 5y ago
> 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.
- nomemory 5y ago
  Exactly, in Java i couldn't even inline my functions, and had zero control over the underlying memory layout.
  - JanecekPetr 5y ago
    > i couldn't even inline my functions 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.)

Koffiepoeder 5y ago

Could someone explain to me in a clear and high level fashion what exactly pointer stability (or pointer instability for that regards) entails? I've watched some of the cppcon talks on the google hashtable implementation [0] and in that talk Matt Kulukundis also mentioned it affecting the adoption rate, but I always failed to really grasp the concept and its implications. Google searches also ended up rather fruitless to be honest. [0]: https://youtube.com/watch?v=ncHmEUmJZf4 https://youtube.com/watch?v=ncHmEUmJZf4

gpderetta 5y ago
If you allocate your objects inline in your internal table, rehashing will invalidate existing references to those objects as they will need to be copied into the new, larger, table. 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.
UncleMeat 5y ago
An operation maintains Pointer Stability means if you take a pointer to an element in a data structure and then execute that operation, the pointer is still valid and pointing to the same data. 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.
- Koffiepoeder 5y ago
  So, am I correct if I then put it as following? 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.