davecromberge commented on PR #141:
URL:
https://github.com/apache/datasketches-characterization/pull/141#issuecomment-6739381015
## Findings so far
Alongside this suite I ran a small benchmark that does the same work in all
four libraries. Each library used the same keys, lg_k 12, 16 input pairs where
B overlaps A by half, a 1 s warm-up and the median of 11 samples. I ran 5
rounds in shuffled order. Every library passed the same exact-mode checks first
(union 3000, intersection 1000, A-not-B 1000, Jaccard 1/3).
Setup:
- Apple M3 Pro, rustc 1.99
- datasketches-rust 0.6.0, datasketches-cpp master (clang -O3),
datasketches-java 9.0.0 on JDK 25, datasketches-go 0.2.0
**Theta, 100k items per sketch** (time per operation; lower is better):
| Operation | Rust 0.6.0 | C++ | Java | Go |
|---|---|---|---|---|
| update (per key) | 7.4 ns | 8.4 ns | 10.4 ns | 13.4 ns |
| union | 155 µs | 228 µs | 313 µs | 339 µs |
| intersection | 130 µs | 149 µs | 168 µs | 223 µs |
| A-not-B (unordered inputs) | 93 µs | 2,127 µs¹ | 53 µs | 2,818 µs¹ |
| Jaccard | 270 µs | 312 µs | 421 µs | 455 µs |
| compact, ordered | 44 µs | 74 µs | 136 µs | 180 µs |
| compact, unordered | 18 µs | 19 µs | 11 µs | 26 µs |
| serialize | 1.9 µs | 0.77 µs | 1.0 µs | 4.0 µs |
| deserialize | 3.1 µs | 0.61 µs | 1.1 µs | 3.4 µs |
| deserialize, compressed (v4) | 15.2 µs | 6.3 µs | 7.6 µs | 8.2 µs |
¹ In C++ and Go, A-not-B appears to take quadratic time when the inputs are
unordered. I'll follow up separately.
What 0.6.0 shows:
- Rust already leads on updates, union, intersection, Jaccard and ordered
compaction.
- It trails on:
- unordered compaction and A-not-B, behind Java;
- serialize and deserialize, plain and compressed, behind C++ and Java.
- Rust validates every entry on deserialize. C++ copies the entries without
checking them, which explains part of the gap.
- CPC update is level with Java (10.3 vs 9.5 ns) and faster than C++ and Go.
- Tuple follows the same pattern as theta. 0.6.0 trails C++ on tuple
serialize (14.1 vs 4.7 µs) and deserialize (18.5 vs 7.4 µs).
## Planned datasketches-rust optimisations
I have a set of datasketches-rust changes locally that are not yet submitted:
- **Compaction:** gather the entries without a hash-table walk per entry.
- **Set operations:** faster inner loops for union, intersection and
A-not-B, plus a cheaper hasher for A-not-B.
- **Compressed format:** faster encode and decode for serial version 4.
- **Inlining:** fixes to a few hot functions.
Updates and accuracy are unchanged. The accuracy profiles in this PR give
identical deterministic output. The KLL quantile columns are randomised, so
they are excluded from that comparison.
**How the numbers change** at 100k items (2k in brackets):
| Operation | Rust 0.6.0 | Rust with changes | Best other |
|---|---|---|---|
| theta union | 155 µs (84) | 95 µs (37) | 228 µs, C++ (135) |
| theta intersection | 130 µs (59) | 82 µs (33) | 149 µs, C++ (65) |
| theta A-not-B, unordered | 93 µs (42) | 28 µs (10) | 53 µs, Java (13) |
| theta Jaccard | 270 µs (128) | 143 µs (54) | 312 µs, C++ (144) |
| theta compact, ordered | 44 µs (19) | 16 µs (7.9) | 74 µs, C++ (32) |
| theta compact, unordered | 18 µs (9.3) | 3.4 µs (2.7) | 11 µs, Java (4.3) |
| theta deserialize, compressed | 15.2 µs (7.5) | 4.2 µs (1.8) | 6.3 µs, C++
(3.0) |
| tuple serialize | 14.1 µs (6.5) | 3.9 µs (1.8) | 4.7 µs, C++ (2.2) |
| tuple deserialize | 18.5 µs (8.3) | 7.5 µs (3.4) | 7.4 µs, C++ (3.3) |
| tuple A-not-B | 117 µs (50) | 36 µs (18) | 82 µs, Java (30) |
With these changes:
- Rust is fastest on every set operation and compaction case above.
- Rust is fastest on compressed deserialize.
- Tuple serialize and deserialize are level with C++.
- Plain (v3) serialize and deserialize improve only slightly, to 1.8 µs and
2.7 µs. They are still 2–4× slower than C++, and I'm looking at that separately.
Once the library changes land, this suite will show these numbers with no
changes on the characterization side. Bumping the `datasketches` version in
`rust/Cargo.toml` is enough.
--
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]