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]

Reply via email to