This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 3db8a5f refactor: remove the rand runtime dependency and add common
random bit function (#264)
3db8a5f is described below
commit 3db8a5f1ebbb2df7ebe98c491b315341ab6643f6
Author: Jeff Chung <[email protected]>
AuthorDate: Wed Sep 2 21:59:21 2026 +0800
refactor: remove the rand runtime dependency and add common random bit
function (#264)
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 1 +
Cargo.lock | 1 -
datasketches/Cargo.toml | 7 +-
datasketches/src/common/mod.rs | 2 +
datasketches/src/common/random.rs | 142 ++++++++++++++++++++++++++++++++++++++
datasketches/src/kll/sketch.rs | 5 +-
datasketches/src/req/compactor.rs | 3 +-
7 files changed, 152 insertions(+), 9 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index e043ec0..3e8c86b 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -14,6 +14,7 @@ All significant changes to this project will be documented in
this file.
### Improvements
+* The crate no longer has any runtime dependencies. The `kll` and `req`
features previously pulled in `rand`; compaction now draws its coin from an
in-tree generator.
* Improve truncated-input diagnostics across sketch deserializers.
* Improve hash-backed sketch update performance for integer and raw-byte
inputs.
* Improve Bloom filter membership-and-insert performance and simplify
Theta-family hash table thresholds.
diff --git a/Cargo.lock b/Cargo.lock
index 106a663..ab02dc6 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -244,7 +244,6 @@ version = "0.5.0"
dependencies = [
"googletest",
"insta",
- "rand",
]
[[package]]
diff --git a/datasketches/Cargo.toml b/datasketches/Cargo.toml
index 1033540..1a31d98 100644
--- a/datasketches/Cargo.toml
+++ b/datasketches/Cargo.toml
@@ -43,15 +43,12 @@ countmin = []
cpc = []
frequencies = []
hll = []
-kll = ["dep:rand"]
-req = ["dep:rand"]
+kll = []
+req = []
tdigest = []
theta = []
tuple = []
-[dependencies]
-rand = { workspace = true, optional = true }
-
[dev-dependencies]
googletest = { workspace = true }
insta = { workspace = true }
diff --git a/datasketches/src/common/mod.rs b/datasketches/src/common/mod.rs
index 918c57b..c9c1cf7 100644
--- a/datasketches/src/common/mod.rs
+++ b/datasketches/src/common/mod.rs
@@ -26,3 +26,5 @@ pub use self::search_criteria::SearchCriteria;
#[cfg(any(feature = "cpc", feature = "hll"))]
pub(crate) mod inv_pow2;
+#[cfg(any(feature = "kll", feature = "req"))]
+pub(crate) mod random;
diff --git a/datasketches/src/common/random.rs
b/datasketches/src/common/random.rs
new file mode 100644
index 0000000..9959b58
--- /dev/null
+++ b/datasketches/src/common/random.rs
@@ -0,0 +1,142 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A thread-local source of uniform random bits.
+//!
+//! The generator is SplitMix64, the fixed-increment form of the splittable
+//! generator introduced in <https://doi.org/10.1145/2714064.2660195> and
shipped
+//! in the JDK as `java.util.SplittableRandom`. The constants and shift amounts
+//! used here match Sebastiano Vigna's public-domain reference
+//! implementation, <https://prng.di.unimi.it/splitmix64.c>.
+
+use std::cell::Cell;
+use std::collections::hash_map::RandomState;
+use std::hash::BuildHasher;
+
+/// Advances a SplitMix64 state by one step, returning `(next_state, output)`.
+///
+/// The state advances by the fixed odd increment `0x9E37_79B9_7F4A_7C15`, the
+/// 64-bit approximation of 2^64/φ, which makes the state a Weyl sequence of
+/// full period 2^64. The output is that new state run through Stafford's
+/// variant-13 mixer, a bijection, so the outputs inherit both the period and
+/// the equidistribution of the state.
+///
+/// The step is bit-for-bit identical to `next()` in the reference
+/// `splitmix64.c`, so a given seed yields the same stream as that
+/// implementation.
+fn next_u64(state: u64) -> (u64, u64) {
+ let state = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
+ let mut z = state;
+ z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
+ z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
+ (state, z ^ (z >> 31))
+}
+
+/// Returns the seed for the calling thread's stream.
+///
+/// The seed is derived from `RandomState`'s randomized hash keys and the
current
+/// thread's id so that threads in one process start at unrelated points of the
+/// cycle.
+fn random_seed() -> u64 {
+ RandomState::new().hash_one(std::thread::current().id())
+}
+
+thread_local! {
+ /// The calling thread's SplitMix64 state, seeded on first use.
+ static STATE: Cell<u64> = Cell::new(random_seed());
+}
+
+/// Returns `true` or `false`, each with probability 1/2.
+///
+/// The bit is the low bit of the next output of the calling thread's stream.
+/// The call is a handful of arithmetic operations on thread-local state: it
+/// never allocates, locks, or blocks. The first call on a thread seeds that
+/// thread's state.
+pub fn random_bit() -> bool {
+ STATE.with(|state| {
+ let (next, value) = next_u64(state.get());
+ state.set(next);
+ value & 1 == 1
+ })
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ #[test]
+ fn assert_split_mix64_matches_the_reference_output() {
+ // Expected outputs for seed 0, taken from the reference splitmix64.c.
+ let expected = [
+ 0xe220_a839_7b1d_cdaf,
+ 0x6e78_9e6a_a1b9_65f4,
+ 0x06c4_5d18_8009_454f,
+ 0xf88b_b8a8_724c_81ec,
+ ];
+ let mut state = 0;
+ for want in expected {
+ let (next, got) = next_u64(state);
+ state = next;
+ assert_eq!(got, want);
+ }
+ }
+
+ /// A coin that stops moving is the failure this module is most exposed to:
+ /// dropping the write-back in `random_bit` pins every flip to one value,
and
+ /// the sketches keep compacting and keep passing their own tests while
+ /// always promoting the same half.
+ #[test]
+ fn assert_random_bit_yields_both_values() {
+ let mut seen = [false; 2];
+ for _ in 0..64 {
+ seen[usize::from(random_bit())] = true;
+ }
+ assert_eq!(seen, [true, true], "the stream stopped advancing");
+ }
+
+ /// The KLL and REQ error bounds hold only for a fair coin, so pin the
+ /// balance. One million draws have a standard deviation of 500 heads; the
+ /// bound below is six of them, which a correct generator exceeds about
twice
+ /// in a billion runs.
+ #[test]
+ fn assert_random_bit_is_unbiased() {
+ const DRAWS: u32 = 1_000_000;
+ const TOLERANCE: u32 = 3_000;
+
+ let mut heads = 0;
+ for _ in 0..DRAWS {
+ heads += u32::from(random_bit());
+ }
+ assert!(heads.abs_diff(DRAWS / 2) <= TOLERANCE, "heads = {heads}");
+ }
+
+ /// Threads must not share a starting point, otherwise sketches filled on
+ /// different threads make identical compaction choices and their errors
+ /// correlate. Two independent streams agree on 64 consecutive bits with
+ /// probability 2^-64.
+ #[test]
+ fn assert_each_thread_draws_its_own_stream() {
+ fn draw_word() -> u64 {
+ (0..64).fold(0, |word, _| (word << 1) | u64::from(random_bit()))
+ }
+
+ let other = std::thread::spawn(draw_word)
+ .join()
+ .expect("the drawing thread should not panic");
+ assert_ne!(draw_word(), other, "two threads shared one stream");
+ }
+}
diff --git a/datasketches/src/kll/sketch.rs b/datasketches/src/kll/sketch.rs
index 82399cd..38b9245 100644
--- a/datasketches/src/kll/sketch.rs
+++ b/datasketches/src/kll/sketch.rs
@@ -43,6 +43,7 @@ use crate::codec::assert::ensure_serial_version_is;
use crate::codec::assert::insufficient_data;
use crate::codec::family::Family;
use crate::common::SearchCriteria;
+use crate::common::random::random_bit;
use crate::error::Error;
/// KLL sketch for estimating quantiles and ranks.
@@ -732,7 +733,7 @@ impl<T: Clone + Ord> KllSketch<T> {
current,
level,
self.is_level_zero_sorted,
- rand::random::<bool>(),
+ random_bit(),
use_up,
);
if above.is_empty() {
@@ -985,7 +986,7 @@ fn general_compress<T: Clone + Ord>(
current,
current_level,
is_level_zero_sorted,
- rand::random::<bool>(),
+ random_bit(),
use_up,
);
let promoted_len = promoted.len();
diff --git a/datasketches/src/req/compactor.rs
b/datasketches/src/req/compactor.rs
index 8f9cc92..a56c0fa 100644
--- a/datasketches/src/req/compactor.rs
+++ b/datasketches/src/req/compactor.rs
@@ -20,6 +20,7 @@
//! Each level in the REQ sketch uses a compactor to maintain a bounded set of
items
//! with deterministic compaction when capacity is exceeded.
+use crate::common::random::random_bit;
use crate::error::Error;
use crate::req::INITIAL_SECTIONS_PER_COMPACTOR;
use crate::req::MIN_K;
@@ -244,7 +245,7 @@ where
if (self.state & 1) == 1 {
self.coin = !self.coin; // flip coin for odd states
} else {
- self.coin = rand::random::<bool>(); // random coin flip for even
states
+ self.coin = random_bit(); // random coin flip for even states
}
let odds = self.coin;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
