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 3d8b664 perf: reduce sketch hashing overhead (#265)
3d8b664 is described below
commit 3d8b6640085ce87198325d5ba76fd5dc7217709f
Author: tison <[email protected]>
AuthorDate: Wed Sep 2 20:46:49 2026 +0800
perf: reduce sketch hashing overhead (#265)
---
CHANGELOG.md | 1 +
benchmarks/Cargo.toml | 13 ++++-
benchmarks/{cpc => bloom}/mod.rs | 2 +-
benchmarks/bloom/update.rs | 53 +++++++++++++++++++
benchmarks/{cpc => countmin}/mod.rs | 2 +-
benchmarks/countmin/update.rs | 49 ++++++++++++++++++
benchmarks/cpc/mod.rs | 1 +
benchmarks/cpc/update.rs | 49 ++++++++++++++++++
benchmarks/{cpc => frequencies}/mod.rs | 2 +-
benchmarks/frequencies/update.rs | 50 ++++++++++++++++++
benchmarks/{main.rs => hash_inputs.rs} | 20 ++++----
benchmarks/{cpc => hll}/mod.rs | 2 +-
benchmarks/hll/update.rs | 50 ++++++++++++++++++
benchmarks/main.rs | 7 +++
benchmarks/{cpc => theta}/mod.rs | 2 +-
benchmarks/theta/update.rs | 49 ++++++++++++++++++
benchmarks/{cpc => tuple}/mod.rs | 2 +-
benchmarks/tuple/update.rs | 52 +++++++++++++++++++
datasketches/src/hash/mod.rs | 16 +++---
datasketches/src/hash/murmurhash.rs | 70 +++++++++++++-------------
datasketches/src/hash/value/canonical_float.rs | 2 +
datasketches/src/hash/value/mod.rs | 1 +
datasketches/src/hash/value/natural_extend.rs | 1 +
datasketches/src/hash/value/raw_bytes.rs | 1 +
datasketches/src/hash/value/sign_extend.rs | 1 +
datasketches/src/hash/xxhash.rs | 18 ++++---
26 files changed, 448 insertions(+), 68 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index f65b267..427ec34 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -15,6 +15,7 @@ All significant changes to this project will be documented in
this file.
### Improvements
* Improve truncated-input diagnostics across sketch deserializers.
+* Improve hash-backed sketch update performance for integer and raw-byte
inputs.
### Bug fixes
diff --git a/benchmarks/Cargo.toml b/benchmarks/Cargo.toml
index 3bbbda5..25af32a 100644
--- a/benchmarks/Cargo.toml
+++ b/benchmarks/Cargo.toml
@@ -23,7 +23,18 @@ edition.workspace = true
rust-version.workspace = true
[dev-dependencies]
-datasketches = { workspace = true, features = ["cpc", "kll", "req", "tdigest"]
}
+datasketches = { workspace = true, features = [
+ "bloom",
+ "countmin",
+ "cpc",
+ "frequencies",
+ "hll",
+ "kll",
+ "req",
+ "tdigest",
+ "theta",
+ "tuple",
+] }
divan = { workspace = true }
rand = { workspace = true }
diff --git a/benchmarks/cpc/mod.rs b/benchmarks/bloom/mod.rs
similarity index 98%
copy from benchmarks/cpc/mod.rs
copy to benchmarks/bloom/mod.rs
index 431ad1f..1dea33b 100644
--- a/benchmarks/cpc/mod.rs
+++ b/benchmarks/bloom/mod.rs
@@ -15,4 +15,4 @@
// specific language governing permissions and limitations
// under the License.
-mod serde;
+mod update;
diff --git a/benchmarks/bloom/update.rs b/benchmarks/bloom/update.rs
new file mode 100644
index 0000000..2aa6b81
--- /dev/null
+++ b/benchmarks/bloom/update.rs
@@ -0,0 +1,53 @@
+// 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.
+
+use datasketches::bloom::BloomFilterBuilder;
+use datasketches::hash::value::raw_bytes;
+use divan::Bencher;
+use divan::black_box;
+use divan::counter::ItemsCount;
+
+use crate::hash_inputs::ITEMS;
+use crate::hash_inputs::bytes_32_values;
+
+#[divan::bench]
+fn u64(bencher: Bencher) {
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut filter = BloomFilterBuilder::with_accuracy(ITEMS as u64, 0.01)
+ .build()
+ .unwrap();
+ for value in 0..ITEMS as u64 {
+ filter.insert(black_box(value));
+ }
+ black_box(filter)
+ });
+}
+
+#[divan::bench]
+fn bytes_32(bencher: Bencher) {
+ let values = bytes_32_values();
+
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut filter = BloomFilterBuilder::with_accuracy(ITEMS as u64, 0.01)
+ .build()
+ .unwrap();
+ for value in &values {
+ filter.insert(raw_bytes::from_slice(black_box(value)));
+ }
+ black_box(filter)
+ });
+}
diff --git a/benchmarks/cpc/mod.rs b/benchmarks/countmin/mod.rs
similarity index 98%
copy from benchmarks/cpc/mod.rs
copy to benchmarks/countmin/mod.rs
index 431ad1f..1dea33b 100644
--- a/benchmarks/cpc/mod.rs
+++ b/benchmarks/countmin/mod.rs
@@ -15,4 +15,4 @@
// specific language governing permissions and limitations
// under the License.
-mod serde;
+mod update;
diff --git a/benchmarks/countmin/update.rs b/benchmarks/countmin/update.rs
new file mode 100644
index 0000000..f25af1e
--- /dev/null
+++ b/benchmarks/countmin/update.rs
@@ -0,0 +1,49 @@
+// 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.
+
+use datasketches::countmin::CountMinSketch;
+use datasketches::hash::value::raw_bytes;
+use divan::Bencher;
+use divan::black_box;
+use divan::counter::ItemsCount;
+
+use crate::hash_inputs::ITEMS;
+use crate::hash_inputs::bytes_32_values;
+
+#[divan::bench]
+fn u64(bencher: Bencher) {
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut sketch = CountMinSketch::<u64>::new(4, 16_384).unwrap();
+ for value in 0..ITEMS as u64 {
+ sketch.update(black_box(value));
+ }
+ black_box(sketch)
+ });
+}
+
+#[divan::bench]
+fn bytes_32(bencher: Bencher) {
+ let values = bytes_32_values();
+
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut sketch = CountMinSketch::<u64>::new(4, 16_384).unwrap();
+ for value in &values {
+ sketch.update(raw_bytes::from_slice(black_box(value)));
+ }
+ black_box(sketch)
+ });
+}
diff --git a/benchmarks/cpc/mod.rs b/benchmarks/cpc/mod.rs
index 431ad1f..13c2486 100644
--- a/benchmarks/cpc/mod.rs
+++ b/benchmarks/cpc/mod.rs
@@ -16,3 +16,4 @@
// under the License.
mod serde;
+mod update;
diff --git a/benchmarks/cpc/update.rs b/benchmarks/cpc/update.rs
new file mode 100644
index 0000000..ba532b8
--- /dev/null
+++ b/benchmarks/cpc/update.rs
@@ -0,0 +1,49 @@
+// 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.
+
+use datasketches::cpc::CpcSketch;
+use datasketches::hash::value::raw_bytes;
+use divan::Bencher;
+use divan::black_box;
+use divan::counter::ItemsCount;
+
+use crate::hash_inputs::ITEMS;
+use crate::hash_inputs::bytes_32_values;
+
+#[divan::bench]
+fn u64(bencher: Bencher) {
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut sketch = CpcSketch::new(11).unwrap();
+ for value in 0..ITEMS as u64 {
+ sketch.update(black_box(value));
+ }
+ black_box(sketch)
+ });
+}
+
+#[divan::bench]
+fn bytes_32(bencher: Bencher) {
+ let values = bytes_32_values();
+
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut sketch = CpcSketch::new(11).unwrap();
+ for value in &values {
+ sketch.update(raw_bytes::from_slice(black_box(value)));
+ }
+ black_box(sketch)
+ });
+}
diff --git a/benchmarks/cpc/mod.rs b/benchmarks/frequencies/mod.rs
similarity index 98%
copy from benchmarks/cpc/mod.rs
copy to benchmarks/frequencies/mod.rs
index 431ad1f..1dea33b 100644
--- a/benchmarks/cpc/mod.rs
+++ b/benchmarks/frequencies/mod.rs
@@ -15,4 +15,4 @@
// specific language governing permissions and limitations
// under the License.
-mod serde;
+mod update;
diff --git a/benchmarks/frequencies/update.rs b/benchmarks/frequencies/update.rs
new file mode 100644
index 0000000..9026b29
--- /dev/null
+++ b/benchmarks/frequencies/update.rs
@@ -0,0 +1,50 @@
+// 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.
+
+use datasketches::frequencies::FrequentItemsSketch;
+use datasketches::hash::value::raw_bytes;
+use datasketches::hash::value::raw_bytes::RawBytes;
+use divan::Bencher;
+use divan::black_box;
+use divan::counter::ItemsCount;
+
+use crate::hash_inputs::ITEMS;
+use crate::hash_inputs::bytes_32_values;
+
+#[divan::bench]
+fn u64(bencher: Bencher) {
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut sketch = FrequentItemsSketch::<u64>::new(16_384).unwrap();
+ for value in 0..ITEMS as u64 {
+ sketch.update(black_box(value));
+ }
+ black_box(sketch)
+ });
+}
+
+#[divan::bench]
+fn bytes_32(bencher: Bencher) {
+ let values = bytes_32_values();
+
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut sketch =
FrequentItemsSketch::<RawBytes<&[u8]>>::new(16_384).unwrap();
+ for value in &values {
+ sketch.update(raw_bytes::from_slice(black_box(value)));
+ }
+ black_box(sketch)
+ });
+}
diff --git a/benchmarks/main.rs b/benchmarks/hash_inputs.rs
similarity index 74%
copy from benchmarks/main.rs
copy to benchmarks/hash_inputs.rs
index 11c9962..073edf4 100644
--- a/benchmarks/main.rs
+++ b/benchmarks/hash_inputs.rs
@@ -15,16 +15,14 @@
// specific language governing permissions and limitations
// under the License.
-use divan::AllocProfiler;
+pub const ITEMS: usize = 10_000;
-#[global_allocator]
-static ALLOC: AllocProfiler = AllocProfiler::system();
-
-mod cpc;
-mod kll;
-mod req;
-mod tdigest;
-
-fn main() {
- divan::main();
+pub fn bytes_32_values() -> Vec<[u8; 32]> {
+ (0..ITEMS)
+ .map(|value| {
+ let mut bytes = [0; 32];
+ bytes[..8].copy_from_slice(&(value as u64).to_le_bytes());
+ bytes
+ })
+ .collect()
}
diff --git a/benchmarks/cpc/mod.rs b/benchmarks/hll/mod.rs
similarity index 98%
copy from benchmarks/cpc/mod.rs
copy to benchmarks/hll/mod.rs
index 431ad1f..1dea33b 100644
--- a/benchmarks/cpc/mod.rs
+++ b/benchmarks/hll/mod.rs
@@ -15,4 +15,4 @@
// specific language governing permissions and limitations
// under the License.
-mod serde;
+mod update;
diff --git a/benchmarks/hll/update.rs b/benchmarks/hll/update.rs
new file mode 100644
index 0000000..88a335c
--- /dev/null
+++ b/benchmarks/hll/update.rs
@@ -0,0 +1,50 @@
+// 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.
+
+use datasketches::hash::value::raw_bytes;
+use datasketches::hll::HllSketch;
+use datasketches::hll::HllType;
+use divan::Bencher;
+use divan::black_box;
+use divan::counter::ItemsCount;
+
+use crate::hash_inputs::ITEMS;
+use crate::hash_inputs::bytes_32_values;
+
+#[divan::bench]
+fn u64(bencher: Bencher) {
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut sketch = HllSketch::new(12, HllType::Hll8).unwrap();
+ for value in 0..ITEMS as u64 {
+ sketch.update(black_box(value));
+ }
+ black_box(sketch)
+ });
+}
+
+#[divan::bench]
+fn bytes_32(bencher: Bencher) {
+ let values = bytes_32_values();
+
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut sketch = HllSketch::new(12, HllType::Hll8).unwrap();
+ for value in &values {
+ sketch.update(raw_bytes::from_slice(black_box(value)));
+ }
+ black_box(sketch)
+ });
+}
diff --git a/benchmarks/main.rs b/benchmarks/main.rs
index 11c9962..ee28803 100644
--- a/benchmarks/main.rs
+++ b/benchmarks/main.rs
@@ -20,10 +20,17 @@ use divan::AllocProfiler;
#[global_allocator]
static ALLOC: AllocProfiler = AllocProfiler::system();
+mod bloom;
+mod countmin;
mod cpc;
+mod frequencies;
+mod hash_inputs;
+mod hll;
mod kll;
mod req;
mod tdigest;
+mod theta;
+mod tuple;
fn main() {
divan::main();
diff --git a/benchmarks/cpc/mod.rs b/benchmarks/theta/mod.rs
similarity index 98%
copy from benchmarks/cpc/mod.rs
copy to benchmarks/theta/mod.rs
index 431ad1f..1dea33b 100644
--- a/benchmarks/cpc/mod.rs
+++ b/benchmarks/theta/mod.rs
@@ -15,4 +15,4 @@
// specific language governing permissions and limitations
// under the License.
-mod serde;
+mod update;
diff --git a/benchmarks/theta/update.rs b/benchmarks/theta/update.rs
new file mode 100644
index 0000000..ca9b94f
--- /dev/null
+++ b/benchmarks/theta/update.rs
@@ -0,0 +1,49 @@
+// 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.
+
+use datasketches::hash::value::raw_bytes;
+use datasketches::theta::ThetaSketchBuilder;
+use divan::Bencher;
+use divan::black_box;
+use divan::counter::ItemsCount;
+
+use crate::hash_inputs::ITEMS;
+use crate::hash_inputs::bytes_32_values;
+
+#[divan::bench]
+fn u64(bencher: Bencher) {
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut sketch =
ThetaSketchBuilder::default().lg_k(14).build().unwrap();
+ for value in 0..ITEMS as u64 {
+ sketch.update(black_box(value));
+ }
+ black_box(sketch)
+ });
+}
+
+#[divan::bench]
+fn bytes_32(bencher: Bencher) {
+ let values = bytes_32_values();
+
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let mut sketch =
ThetaSketchBuilder::default().lg_k(14).build().unwrap();
+ for value in &values {
+ sketch.update(raw_bytes::from_slice(black_box(value)));
+ }
+ black_box(sketch)
+ });
+}
diff --git a/benchmarks/cpc/mod.rs b/benchmarks/tuple/mod.rs
similarity index 98%
copy from benchmarks/cpc/mod.rs
copy to benchmarks/tuple/mod.rs
index 431ad1f..1dea33b 100644
--- a/benchmarks/cpc/mod.rs
+++ b/benchmarks/tuple/mod.rs
@@ -15,4 +15,4 @@
// specific language governing permissions and limitations
// under the License.
-mod serde;
+mod update;
diff --git a/benchmarks/tuple/update.rs b/benchmarks/tuple/update.rs
new file mode 100644
index 0000000..9041fed
--- /dev/null
+++ b/benchmarks/tuple/update.rs
@@ -0,0 +1,52 @@
+// 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.
+
+use datasketches::hash::value::raw_bytes;
+use datasketches::tuple::DefaultUpdatePolicy;
+use datasketches::tuple::TupleSketchBuilder;
+use divan::Bencher;
+use divan::black_box;
+use divan::counter::ItemsCount;
+
+use crate::hash_inputs::ITEMS;
+use crate::hash_inputs::bytes_32_values;
+
+#[divan::bench]
+fn u64(bencher: Bencher) {
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let policy = DefaultUpdatePolicy::<u64>::default();
+ let mut sketch =
TupleSketchBuilder::new(policy).lg_k(14).build().unwrap();
+ for value in 0..ITEMS as u64 {
+ sketch.update(black_box(value), 1);
+ }
+ black_box(sketch)
+ });
+}
+
+#[divan::bench]
+fn bytes_32(bencher: Bencher) {
+ let values = bytes_32_values();
+
+ bencher.counter(ItemsCount::new(ITEMS)).bench_local(|| {
+ let policy = DefaultUpdatePolicy::<u64>::default();
+ let mut sketch =
TupleSketchBuilder::new(policy).lg_k(14).build().unwrap();
+ for value in &values {
+ sketch.update(raw_bytes::from_slice(black_box(value)), 1);
+ }
+ black_box(sketch)
+ });
+}
diff --git a/datasketches/src/hash/mod.rs b/datasketches/src/hash/mod.rs
index c5c26c4..2084902 100644
--- a/datasketches/src/hash/mod.rs
+++ b/datasketches/src/hash/mod.rs
@@ -82,11 +82,12 @@ pub(crate) use self::seed::*;
))]
pub(crate) const DEFAULT_UPDATE_SEED: u64 = 9001;
-/// Reads an u64 from a byte slice in little-endian order.
-///
-/// # Panics
-///
-/// Panics if `bytes.len()` is greater than 8.
+#[cfg(feature = "bloom")]
+#[inline(always)]
+fn read_u32_le(bytes: &[u8]) -> u32 {
+ u32::from_le_bytes(bytes.try_into().expect("four-byte hash input"))
+}
+
#[cfg(any(
feature = "bloom",
feature = "countmin",
@@ -96,8 +97,7 @@ pub(crate) const DEFAULT_UPDATE_SEED: u64 = 9001;
feature = "theta",
feature = "tuple",
))]
+#[inline(always)]
fn read_u64_le(bytes: &[u8]) -> u64 {
- let mut buf = [0u8; 8];
- buf[..bytes.len()].copy_from_slice(bytes);
- u64::from_le_bytes(buf)
+ u64::from_le_bytes(bytes.try_into().expect("eight-byte hash input"))
}
diff --git a/datasketches/src/hash/murmurhash.rs
b/datasketches/src/hash/murmurhash.rs
index 1e0a383..5f62a40 100644
--- a/datasketches/src/hash/murmurhash.rs
+++ b/datasketches/src/hash/murmurhash.rs
@@ -35,6 +35,7 @@ pub struct MurmurHash3X64128 {
}
impl MurmurHash3X64128 {
+ #[inline(always)]
pub fn with_seed(seed: u64) -> Self {
MurmurHash3X64128 {
h1: seed,
@@ -45,18 +46,18 @@ impl MurmurHash3X64128 {
}
}
+ #[inline(always)]
pub fn finish128(&self) -> (u64, u64) {
let mut h1 = self.h1;
let mut h2 = self.h2;
- let total = self.total + self.buf_len as u64;
let rem = self.buf_len;
// tail
if rem > 0 {
if rem > 8 {
// read k2 little endian
- let mut k2 = read_u64_le(&self.buf[8..rem]);
+ let mut k2 = read_u64_le_partial(&self.buf[8..rem]);
// mix k2
k2 = k2.wrapping_mul(C2);
k2 = k2.rotate_left(33);
@@ -66,7 +67,7 @@ impl MurmurHash3X64128 {
// read k1 little endian
let k1_len = rem.min(8);
- let mut k1 = read_u64_le(&self.buf[..k1_len]);
+ let mut k1 = read_u64_le_partial(&self.buf[..k1_len]);
// mix k1
k1 = k1.wrapping_mul(C1);
k1 = k1.rotate_left(31);
@@ -74,8 +75,8 @@ impl MurmurHash3X64128 {
h1 ^= k1;
}
- h1 ^= total;
- h2 ^= total;
+ h1 ^= self.total;
+ h2 ^= self.total;
h1 = h1.wrapping_add(h2);
h2 = h2.wrapping_add(h1);
h1 = fmix64(h1);
@@ -85,7 +86,7 @@ impl MurmurHash3X64128 {
(h1, h2)
}
- #[inline]
+ #[inline(always)]
fn update(&mut self, mut k1: u64, mut k2: u64) {
// k1 *= c1; k1 = MURMUR3_ROTL64(k1, 31); k1 *= c2; out.h1 ^= k1;
k1 = k1.wrapping_mul(C1);
@@ -108,9 +109,6 @@ impl MurmurHash3X64128 {
self.h2 = self.h2.rotate_left(31);
self.h2 = self.h2.wrapping_add(self.h1);
self.h2 = self.h2.wrapping_mul(5).wrapping_add(0x38495ab5);
-
- // accumulate total length
- self.total += 16;
}
}
@@ -121,54 +119,54 @@ impl Default for MurmurHash3X64128 {
}
impl Hasher for MurmurHash3X64128 {
+ #[inline(always)]
fn finish(&self) -> u64 {
self.finish128().0
}
+ #[inline(always)]
fn write(&mut self, mut bytes: &[u8]) {
- if self.buf_len + bytes.len() < 16 {
- self.buf[self.buf_len..self.buf_len +
bytes.len()].copy_from_slice(bytes);
- self.buf_len += bytes.len();
- return;
- }
+ self.total = self.total.wrapping_add(bytes.len() as u64);
if self.buf_len != 0 {
- let wanted = 16 - self.buf_len;
- self.buf[self.buf_len..].copy_from_slice(&bytes[..wanted]);
+ let copied = (16 - self.buf_len).min(bytes.len());
+ self.buf[self.buf_len..self.buf_len +
copied].copy_from_slice(&bytes[..copied]);
+ self.buf_len += copied;
+ bytes = &bytes[copied..];
+
+ if self.buf_len < 16 {
+ return;
+ }
let k1 = read_u64_le(&self.buf[0..8]);
let k2 = read_u64_le(&self.buf[8..16]);
self.update(k1, k2);
-
- bytes = &bytes[wanted..];
self.buf_len = 0;
}
- // Number of full 128-bit blocks of 16 bytes.
- // Possible exclusion of a remainder of up to 15 bytes.
- let blocks = bytes.len() >> 4; // bytes / 16
-
- // Process the 128-bit blocks (the body) into the hash
- for i in 0..blocks {
- let lo = i << 4;
- let mi = lo + 8;
- let hi = mi + 8;
- let k1 = read_u64_le(&bytes[lo..mi]);
- let k2 = read_u64_le(&bytes[mi..hi]);
+ while bytes.len() >= 16 {
+ let k1 = read_u64_le(&bytes[..8]);
+ let k2 = read_u64_le(&bytes[8..16]);
self.update(k1, k2);
+ bytes = &bytes[16..];
}
- // remain bytes
- let len = bytes.len() % 16;
- if len > 0 {
- self.buf[0..len].copy_from_slice(&bytes[blocks << 4..]);
- self.buf_len = len;
- }
+ self.buf[..bytes.len()].copy_from_slice(bytes);
+ self.buf_len = bytes.len();
+ }
+}
+
+#[inline(always)]
+fn read_u64_le_partial(bytes: &[u8]) -> u64 {
+ let mut value = 0;
+ for (index, &byte) in bytes.iter().enumerate() {
+ value |= u64::from(byte) << (index * 8);
}
+ value
}
/// Finalization mix: force all bits of a hash block to avalanche.
-#[inline]
+#[inline(always)]
fn fmix64(mut k: u64) -> u64 {
k ^= k >> 33;
k = k.wrapping_mul(0xff51afd7ed558ccd);
diff --git a/datasketches/src/hash/value/canonical_float.rs
b/datasketches/src/hash/value/canonical_float.rs
index 4c29b5b..06edd98 100644
--- a/datasketches/src/hash/value/canonical_float.rs
+++ b/datasketches/src/hash/value/canonical_float.rs
@@ -97,6 +97,7 @@ pub fn from_f64(v: f64) -> CanonicalFloat<f64> {
}
impl HashStrategy<f32> for CanonicalFloatStrategy {
+ #[inline(always)]
fn hash<H: Hasher>(value: &f32, state: &mut H) {
let value = *value as f64;
let canonical_value = from_f64(value);
@@ -105,6 +106,7 @@ impl HashStrategy<f32> for CanonicalFloatStrategy {
}
impl HashStrategy<f64> for CanonicalFloatStrategy {
+ #[inline(always)]
fn hash<H: Hasher>(value: &f64, state: &mut H) {
let canonical = if value.is_nan() {
// Java's Double.doubleToLongBits() NaN value.
diff --git a/datasketches/src/hash/value/mod.rs
b/datasketches/src/hash/value/mod.rs
index ee42e19..88d87e7 100644
--- a/datasketches/src/hash/value/mod.rs
+++ b/datasketches/src/hash/value/mod.rs
@@ -166,6 +166,7 @@ impl<T: fmt::Display, S> fmt::Display for Value<T, S> {
}
impl<T, S: HashStrategy<T>> Hash for Value<T, S> {
+ #[inline(always)]
fn hash<H: Hasher>(&self, state: &mut H) {
S::hash(&self.value, state);
}
diff --git a/datasketches/src/hash/value/natural_extend.rs
b/datasketches/src/hash/value/natural_extend.rs
index 1b2ec4d..981c8b1 100644
--- a/datasketches/src/hash/value/natural_extend.rs
+++ b/datasketches/src/hash/value/natural_extend.rs
@@ -133,6 +133,7 @@ pub fn from_u32(v: u32) -> NaturalExtend<u32> {
macro_rules! impl_natural_extend {
($t:ty, |$v:ident| $extended:expr) => {
impl HashStrategy<$t> for NaturalExtendStrategy {
+ #[inline(always)]
fn hash<H: Hasher>(value: &$t, state: &mut H) {
let $v = *value;
let extended = $extended;
diff --git a/datasketches/src/hash/value/raw_bytes.rs
b/datasketches/src/hash/value/raw_bytes.rs
index 2b41735..0c48139 100644
--- a/datasketches/src/hash/value/raw_bytes.rs
+++ b/datasketches/src/hash/value/raw_bytes.rs
@@ -129,6 +129,7 @@ pub fn from_str(v: &str) -> RawBytes<&str> {
macro_rules! impl_raw_bytes {
($t:ty, |$v:ident| $as_slice:expr) => {
impl HashStrategy<$t> for RawBytesStrategy {
+ #[inline(always)]
fn hash<H: Hasher>(value: &$t, state: &mut H) {
let $v = value;
let slice = $as_slice;
diff --git a/datasketches/src/hash/value/sign_extend.rs
b/datasketches/src/hash/value/sign_extend.rs
index 561fbd1..cefcafe 100644
--- a/datasketches/src/hash/value/sign_extend.rs
+++ b/datasketches/src/hash/value/sign_extend.rs
@@ -160,6 +160,7 @@ pub fn from_u32(v: u32) -> SignExtend<u32> {
macro_rules! impl_sign_extend {
($t:ty, |$v:ident| $extended:expr) => {
impl HashStrategy<$t> for SignExtendStrategy {
+ #[inline(always)]
fn hash<H: Hasher>(value: &$t, state: &mut H) {
let $v = *value;
let extended = $extended as u64;
diff --git a/datasketches/src/hash/xxhash.rs b/datasketches/src/hash/xxhash.rs
index 04c3e47..1ea5503 100644
--- a/datasketches/src/hash/xxhash.rs
+++ b/datasketches/src/hash/xxhash.rs
@@ -17,6 +17,7 @@
use std::hash::Hasher;
+use crate::hash::read_u32_le;
use crate::hash::read_u64_le;
const DEFAULT_SEED: u64 = 0;
@@ -43,6 +44,7 @@ pub struct XxHash64 {
}
impl XxHash64 {
+ #[inline(always)]
pub fn with_seed(seed: u64) -> Self {
XxHash64 {
seed,
@@ -56,6 +58,7 @@ impl XxHash64 {
}
}
+ #[inline(always)]
pub fn finish64(&self) -> u64 {
let mut hash = if self.total_len >= 32 {
let mut acc = self
@@ -88,8 +91,8 @@ impl XxHash64 {
}
if idx + 4 <= buf.len() {
- let k1 = read_u64_le(&buf[idx..idx + 4]);
- hash ^= k1.wrapping_mul(P1);
+ let k1 = read_u32_le(&buf[idx..idx + 4]);
+ hash ^= u64::from(k1).wrapping_mul(P1);
hash = hash.rotate_left(23).wrapping_mul(P2).wrapping_add(P3);
idx += 4;
}
@@ -105,6 +108,7 @@ impl XxHash64 {
}
#[allow(dead_code)]
+ #[inline(always)]
pub fn hash_u64(input: u64, seed: u64) -> u64 {
let mut hash = seed.wrapping_add(P5).wrapping_add(8);
let mut k1 = input;
@@ -116,7 +120,7 @@ impl XxHash64 {
finalize(hash)
}
- #[inline]
+ #[inline(always)]
fn update(&mut self, chunk: &[u8]) {
self.v1 = round(self.v1, read_u64_le(&chunk[0..8]));
self.v2 = round(self.v2, read_u64_le(&chunk[8..16]));
@@ -132,10 +136,12 @@ impl Default for XxHash64 {
}
impl Hasher for XxHash64 {
+ #[inline(always)]
fn finish(&self) -> u64 {
self.finish64()
}
+ #[inline(always)]
fn write(&mut self, bytes: &[u8]) {
self.total_len = self.total_len.wrapping_add(bytes.len() as u64);
@@ -169,14 +175,14 @@ impl Hasher for XxHash64 {
}
}
-#[inline]
+#[inline(always)]
fn round(mut acc: u64, input: u64) -> u64 {
acc = acc.wrapping_add(input.wrapping_mul(P2));
acc = acc.rotate_left(31);
acc.wrapping_mul(P1)
}
-#[inline]
+#[inline(always)]
fn merge_round(mut acc: u64, val: u64) -> u64 {
let mut v = val;
v = v.wrapping_mul(P2);
@@ -186,7 +192,7 @@ fn merge_round(mut acc: u64, val: u64) -> u64 {
acc.wrapping_mul(P1).wrapping_add(P4)
}
-#[inline]
+#[inline(always)]
fn finalize(mut hash: u64) -> u64 {
hash ^= hash >> 33;
hash = hash.wrapping_mul(P2);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
