ben-manes / caffeine / #4633

100%

master: 100%

Build Type

push

github

Committed by ben-manes

Commit Message

optimize the frequency sketch

In an earlier analysis the block-based sketch was significantly faster
than the flat (uniform) one. This was independently confirmed by a C#
and Go port, who also observed a 2x speed up. However, when recently
adding this benchmark to the CI it showed it as a regression. Therefore
some implicit compiler optimizations are now explicit, which allows the
block-based sketch to match or exceed the flat-based performance.

- We no longer rely on escape analysis to optimize away the method
scoped arrays (count, index). These should have been stack allocated
and broken into their components.
- The arrays were meant to break a loop data dependency, but it is now
faster to keep that. `Math.min` is a single cycle, branch-free
instruction that the OOO pipeline seems to prefer.
- `increment` is manually loop unrolled like the flat version, which
shows a simiar speed up.
- Previously, the flat benchmark version implemented the scaffolding
interface directly, was pre-allocated, and the init guard was removed.
This gave it a large advantage as it improved inlining, branch
prediction, etc. The benchmark is now fair.
- For jdk11 the black is always faster by at least 10M ops/s. In jdk23
the speedup only occurs as the table size increases, matching the
expected gains from better cache effects. It is marginally slower on
the small table size due to indexing differences.

The net user effect will be noise since this was not a performance
bottleneck due to the cache's overall design.

Run Details

25 of 25 new or added lines in 1 file covered. (100.0%)

2 existing lines in 2 files now uncovered.

7637 of 7711 relevant lines covered (99.04%)

0.99 hits per line