ben-manes / caffeine / #4634

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 block 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 differences are very hardware and compiler dependent, as there are
wide variations when running on Intel, Arm, Java versions, and JVMs
(Graal vs C2). The user effect will be noise since this was not a
performance bottleneck due to the cache's overall design.

Run Details

21 of 0 new or added lines in 0 files covered. (NaN%)

1 existing line in 1 file now uncovered.

7634 of 7707 relevant lines covered (99.05%)

0.99 hits per line