3 ms·

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 t

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.)
    - nomemory 5y ago
      I've assumed they were inline initially, until I profiled and found out one of the swap methods was not. I believe there's also a limit on the amount of bytecode to inline, so no matter how hot a method, if the associated bytecode reaches a certain threshold it won't be. I need to double check though.
      - JanecekPetr 5y ago
        Indeed, max bytecode count (FreqInlineSize and MaxInlineSize) and inlining depth (MaxInlineLevel). Your GC choice will also slightly modify the inlining decisions, and then obviously GraalVM will be completely different.
        kaba0 5y ago
        But inlining will not cause better performance in every case, will it?
        JanecekPetr 5y ago
        Correct! Inlining obviously costs CPU, code cache space, and makes the receiver method bigger so that it's less likely it will be inlined itself. If there ever is a decompilation occuring, the inlining efforts were pretty much wasted.
        masklinn 5y ago
        However it must be pointed out that inlining enables further optimisations. The tradeoffs are more complicated for a jit, but for an aot compiler it’s one of the most important optimisations in the pipeline.
        vips7L 5y ago
        Is there a full list of the differences between the graal jit and C2? I was only aware of graal having better partial escape analysis over C2's conservative EA.
  - tsimionescu 5y ago
    Out of curiosity, weren't your objects ending up neatly compacted after a GC cycle?
    - nomemory 5y ago
      I didn't perform any deletes, and I've tried to keep everything clean without allocating intermediary objects. But one the pitfalls is that I cannot play easily on the memory lane with Java. For example in the entries and bins implementation I had to have two separate arrays. In C I would've kept a single array, with a compact zone, and another sparse zone, iterating through it using an offset.
vips7L 5y ago
https://cr.openjdk.java.net/~skuksenko/valhalla/hashmaps/hash.html https://cr.openjdk.java.net/~skuksenko/valhalla/hashmaps/has... Might be what you're looking for?

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.)
  - nomemory 5y ago
    I've assumed they were inline initially, until I profiled and found out one of the swap methods was not. I believe there's also a limit on the amount of bytecode to inline, so no matter how hot a method, if the associated bytecode reaches a certain threshold it won't be. I need to double check though.
    - JanecekPetr 5y ago
      Indeed, max bytecode count (FreqInlineSize and MaxInlineSize) and inlining depth (MaxInlineLevel). Your GC choice will also slightly modify the inlining decisions, and then obviously GraalVM will be completely different.
      - kaba0 5y ago
        But inlining will not cause better performance in every case, will it?
        JanecekPetr 5y ago
        Correct! Inlining obviously costs CPU, code cache space, and makes the receiver method bigger so that it's less likely it will be inlined itself. If there ever is a decompilation occuring, the inlining efforts were pretty much wasted.
        masklinn 5y ago
        However it must be pointed out that inlining enables further optimisations. The tradeoffs are more complicated for a jit, but for an aot compiler it’s one of the most important optimisations in the pipeline.
      - vips7L 5y ago
        Is there a full list of the differences between the graal jit and C2? I was only aware of graal having better partial escape analysis over C2's conservative EA.
- tsimionescu 5y ago
  Out of curiosity, weren't your objects ending up neatly compacted after a GC cycle?
  - nomemory 5y ago
    I didn't perform any deletes, and I've tried to keep everything clean without allocating intermediary objects. But one the pitfalls is that I cannot play easily on the memory lane with Java. For example in the entries and bins implementation I had to have two separate arrays. In C I would've kept a single array, with a compact zone, and another sparse zone, iterating through it using an offset.

vips7L 5y ago

https://cr.openjdk.java.net/~skuksenko/valhalla/hashmaps/hash.html https://cr.openjdk.java.net/~skuksenko/valhalla/hashmaps/has... Might be what you're looking for?