rustyconover opened a new issue, #555:
URL: https://github.com/apache/datasketches-cpp/issues/555
`count_min_sketch` draws its per-row hash seeds in its constructor
(`count/include/count_min_impl.hpp`) like this:
```cpp
std::default_random_engine rng(_seed);
std::uniform_int_distribution<uint64_t> extra_hash_seeds(0,
std::numeric_limits<uint64_t>::max());
...
hash_seeds.push_back(extra_hash_seeds(rng) + _seed);
```
Both `std::default_random_engine` and the algorithm behind
`std::uniform_int_distribution` are implementation-defined. So libstdc++,
libc++ and the MSVC STL each produce **different hash seeds for the same seed**.
The serialized form stores only the seed, not the derived hash seeds. If a
sketch is serialized on one platform and deserialized on another, the receiver
hashes items into different buckets than the sender used. No error is raised,
and `get_estimate()` silently returns wrong answers.
### Reproduction
This uses the same derivation as the constructor, with the default seed 9001
and 3 hashes:
```cpp
#include <cstdint>
#include <cstdio>
#include <limits>
#include <random>
int main() {
const uint64_t seed = 9001;
std::default_random_engine rng(seed);
std::uniform_int_distribution<uint64_t> extra_hash_seeds(0,
std::numeric_limits<uint64_t>::max());
for (int i = 0; i < 3; ++i) printf("%llu\n", (unsigned long
long)(extra_hash_seeds(rng) + seed));
}
```
| Linux, GCC 14 / libstdc++ | macOS, Apple clang / libc++ |
|---|---|
| 4480857443237086988 | 3314421722738642050 |
| 6631161516192699342 | 9951529646378312046 |
| 11350819014790094519 | 9791000334130093217 |
We hit this in a DuckDB extension that wraps the library, where sketches are
stored as BLOBs. A Count-Min sketch built on Linux returned wrong estimates
when it was queried on Windows. Our CI caught it because the Windows build
produced different serialized bytes for the same input.
### Suggested fix
Derive the hash seeds with a fully specified algorithm instead of the
standard-library distributions. Two options:
- Use a fixed generator and scaling (`std::minstd_rand0` and the 64-bit
generators are fully specified; the distributions are not), or a simple hash of
`(seed, i)`.
- To stay compatible with sketches already serialized on Linux, reproduce
libstdc++'s output exactly. libstdc++'s `default_random_engine` is
`minstd_rand0`, and its `uniform_int_distribution` upscaling algorithm is short.
We took the second option in a vcpkg overlay patch, and checked it against
libstdc++ over 360k draws:
https://github.com/Query-farm/datasketches/blob/v2.0/vcpkg-overlay/apache-datasketches/count-min-portable-hash-seeds.patch
I'm happy to open a PR with that approach, or with whichever approach you
prefer. Storing the hash seeds in the serialized form would also work, but it
changes the format.
Version: 5.3.0 (`5b5524f`).
--
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]
