Waterpine opened a new pull request, #330:
URL: https://github.com/apache/datasketches-rust/pull/330
## Summary
`BloomFilter` computed each bit index as `hash % capacity`, a 64-bit
hardware division per hash function. It now uses Lemire's remainder by direct
computation ("Faster Remainder by Direct Computation", 2019) with a 128-bit
multiplier cached in the filter. The capacity is always a positive multiple of
64, so the multiplier cannot overflow and the result equals `hash % capacity`
for every `u64` hash.
On the benchmark machine this makes inserting integers and 32-byte items
about 1.8x to 1.9x faster (time ratio 0.52 to 0.55), and the additional
insertion and membership workloads below 1.3x to 2.3x faster. The gain depends
on the CPU; see "Scope of the results".
The multiplier is derived from the bit array length when a filter is built
or deserialized, so bit placement and serialization are unchanged.
`BloomFilter` grows by 16 bytes; heap use is unchanged.
## Results
Main benchmark suite, 6 rounds. The ratio is the time after this change
divided by the time before; below 1 is faster.
| benchmark | time ratio |
| --- | --- |
| `bloom::update::u64` | 0.52 |
| `bloom::update::bytes_32` | 0.55 |
| `bloom::update::contains_and_insert_present_u64` | 0.55 |
Additional workloads that are not in the repository's suite (10 rounds):
`contains` of present items 0.43 to 0.72, of absent items 0.75 to 0.78,
`insert` of a large filter 0.79. Peak and retained heap are unchanged.
## Scope of the results
The gain comes from removing a 64-bit hardware division per hash function.
That division is slow on the benchmark CPU (Xeon E5-2660 v3, Haswell), so the
ratios above are probably close to the best case: CPUs with faster dividers
should gain less, and I have not measured any. On 64-bit targets such as x86-64
and aarch64 the new code is plain integer multiplication, with no `unsafe`,
intrinsics, or target features. I have not measured 32-bit targets such as
wasm32: there the original remainder was a 32-bit operation and the 128-bit
arithmetic compiles to several instructions, so they might not benefit.
## Checks
`cargo x check`, `cargo x lint`, `cargo x test`, and `cargo +1.86.0 check -p
datasketches --all-features` pass.
Measured with Divan on one machine (2x Xeon E5-2660 v3, Linux 6.8) against
`bb6ba57`, using paired rounds that alternate sockets; ratios are the geometric
mean of per-round median ratios (below 1 is faster). The branch is based on
upstream `main` at `4ba130e`; the numbers were not repeated there, because the
commits in between change HLL and XOR code, benchmark timing units, and two
variable renames in KLL and t-digest.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
