pmcgleenon opened a new issue, #298: URL: https://github.com/apache/datasketches-rust/issues/298
The [asap_sketchlib announcement post](https://projectasap.github.io/blog/2026/sketchlib-announcement/) compares Count-Min Sketch throughput across Rust crates (5 rows x 32768 columns, 10M Zipf-distributed i64 items). It reports datasketches as the slowest: ``` ┌────────────────┬────────────────────┬───────────────────┐ │ implementation │ insert (M items/s) │ query (M items/s) │ ├────────────────┼────────────────────┼───────────────────┤ │ asap_sketchlib │ 93.8 │ 65.2 │ ├────────────────┼────────────────────┼───────────────────┤ │ sketch_oxide │ 15.5 │ 9.8 │ ├────────────────┼────────────────────┼───────────────────┤ │ datasketches │ 8.2 │ 5.9 │ └────────────────┴────────────────────┴───────────────────┘ ``` I reproduced the setup on an different machine from the one used in the blog: ``` ┌──────────────────────────────┬────────────────────┬───────────────────┐ │ implementation │ insert (M items/s) │ query (M items/s) │ ├──────────────────────────────┼────────────────────┼───────────────────┤ │ asap_sketchlib (FastPath) │ 48.0 │ 45.6 │ ├──────────────────────────────┼────────────────────┼───────────────────┤ │ asap_sketchlib (RegularPath) │ 17.1 │ 16.5 │ ├──────────────────────────────┼────────────────────┼───────────────────┤ │ datasketches 0.5.0 │ 17.8 │ 16.7 │ ├──────────────────────────────┼────────────────────┼───────────────────┤ │ sketch_oxide │ 18.8 │ 19.4 │ └──────────────────────────────┴────────────────────┴───────────────────┘ ``` **Where the time goes** bucket_index hashes each row with its seeded MurmurHash3 and then [computes h1 % num_buckets](https://github.com/apache/datasketches-rust/blob/cc614c2a4e59b3a062c5fa4aecd371327a654629/datasketches/src/countmin/sketch.rs#L510) . It is called once per row from the update and estimate loops, so every operation does a 64-bit hardware division per row. On the CPU above it costs about as much as the hash itself. **Proposed change** Keep the hash and seeds exactly as they are, and replace only the reduction: - if num_buckets is a power of two, use h1 & (num_buckets - 1); - otherwise, use Lemire's direct remainder ("Faster Remainder by Direct Computation", 2019), with a multiplier u128::MAX / num_buckets + 1 computed once at construction. **Results** ``` ┌────────────────────────┬──────┬─────────┐ │ bench │ main │ patched │ ├────────────────────────┼──────┼─────────┤ │ update, u64 │ 24.4 │ 44.6 │ ├────────────────────────┼──────┼─────────┤ │ estimate, u64 │ 23.5 │ 44.8 │ ├────────────────────────┼──────┼─────────┤ │ update, 32-byte keys │ 11.2 │ 16.4 │ ├────────────────────────┼──────┼─────────┤ │ estimate, 32-byte keys │ 11.5 │ 16.0 │ └────────────────────────┴──────┴─────────┘ ``` asap has a FastPath configuration that reuses a single hash across all rows. This would change the bucket placement so it is not compatible with datasketches. Potentially we could introduce a new configuration mode to cater for it. @tisonkun FYI what do you think about this proposed changed above which will maintain compatibility? -- 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]
