leerho opened a new pull request, #576: URL: https://github.com/apache/datasketches-cpp/pull/576
This implements version 2 of the Count-Min format, as specified in [docs/count-min-format.md](https://github.com/apache/datasketches-tck/blob/main/docs/count-min-format.md) in datasketches-tck. The spec was adopted by lazy consensus in apache/datasketches-tck#18 and merged in apache/datasketches-tck#21. Closes #555. ## Changes - **Row seeds:** `rowSeed[i] = XXH64(LE64(i), seed)` (§3). Version 1 drew the row seeds from `std::default_random_engine` and `std::uniform_int_distribution`, whose results differ between libstdc++, libc++ and the MSVC STL. Version 1 images were therefore read with the wrong buckets on another standard library, with no error (#555). - **Hashing:** items are hashed with XXH64, and `bucket = (hash >> 1) mod numBuckets` (§5). Integers are hashed as 8 little-endian bytes, and strings as their bytes, as before (§4). - **Versions:** - New sketches write serial version 2. - Version 1 images are still read. A sketch read from one keeps the version 1 hashing and is written back as version 1 (§6). - Sketches of different versions can't be merged. - Any other serial version is rejected. - The new `get_serial_version()` reports the version. - **`numHashes`:** must be in [1, 127] (§1). Before, 0 was accepted, and estimates then returned the maximum value of `W`. Version 1 images written by C++ may have up to 255 rows, so they are still read. `suggest_num_hashes()` now returns at most 127. - **Empty items:** ignored (§4.4). An update with a size of 0, including `(nullptr, 0)`, does nothing. Every query (estimate, lower bound and upper bound) returns 0 for an empty item. The `std::string` overloads already behaved this way. - **Docs:** the class documentation describes the two versions, notes that only `W = int64_t` images are readable in other languages, and states the empty-item rule. New sketches hash items differently from before. Estimates from the same inputs can therefore change, within the usual error bounds. Version 1 images keep their behavior. ## Tests - **`count_min_v2_test.cpp`:** - the spec's test vectors: XXH64 (§7.1), row seeds (§7.2), buckets for seeds 9001 and 42 (§7.3), and both images, byte for byte (§7.4); - the empty-item rule, checked on a non-empty sketch so that the upper bound is covered; - the `numHashes` range, in the constructor and in version 2 images; - version 1 images: read, written back unchanged, still usable, and not mergeable with version 2. This uses a version 1 image written by the current code; - rejection of other serial versions; - copies keeping their version. - **Cross-language files (§8):** - with `GENERATE`, `count_min_serialize_for_java.cpp` writes the seven `count_min_v2_<case>_cpp.sk` files; - with `SERDE_COMPAT`, `count_min_deserialize_from_java_test.cpp` runs the §8.2 checks on the Java files and requires each one to be byte-identical to the C++ sketch for the same case. All seven cases are byte-identical to the files generated by datasketches-java main. - **`CM frequency cancellation`:** this test assumed that `"x"` and `"y"` land in different buckets of a 1 × 5 sketch. Under version 2 hashing they share a bucket, so the test now uses 6 buckets. - **Old file names:** the tests no longer write `count_min_empty_cpp.sk` and `count_min_non_empty_cpp.sk`. §8.3 reserves those names for version 1 images, and C++ no longer writes version 1. The next TCK snapshot update will show them removed. The Count-Min tests pass under ASan and UBSan, with and without `SERDE_COMPAT`. The integration test and the Count-Min benchmark build. This PR touches only `count/`, and it merges cleanly with all open PRs. 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- 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]
