Skip to content

Commit 23f3080

Browse files
committed
add benchmark
1 parent 496f539 commit 23f3080

File tree

5 files changed

+99
-4
lines changed

5 files changed

+99
-4
lines changed

Cargo.toml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@ members = [
44
"crates/*",
55
"crates/bpe/benchmarks",
66
"crates/bpe/tests",
7+
"crates/consistent-hashing/benchmarks",
78
]
89
resolver = "2"
910

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
[package]
2+
name = "consistent-hashing-benchmarks"
3+
edition = "2021"
4+
5+
[[bench]]
6+
name = "performance"
7+
path = "performance.rs"
8+
harness = false
9+
test = false
10+
11+
[dependencies]
12+
consistent-hashing = { path = "../" }
13+
14+
criterion = { version = "0.7", features = ["csv_output"] }
15+
rand = "0.9"
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
# save report in this directory, even if a custom target directory is set
2+
criterion_home = "./target/criterion"
3+
4+
# The colors table allows users to configure the colors used by the charts
5+
# cargo-criterion generates.
6+
[colors]
7+
# Color-blind friendly color scheme from https://personal.sron.nl/~pault/.
8+
comparison_colors = [
9+
{r = 51, g = 34, b = 136 }, # indigo
10+
{r = 136, g = 204, b = 238 }, # cyan
11+
{r = 68, g = 170, b = 153 }, # teal
12+
{r = 17, g = 119, b = 51 }, # green
13+
{r = 153, g = 153, b = 51 }, # olive
14+
{r = 221, g = 204, b = 119 }, # sand
15+
{r = 204, g = 102, b = 119 }, # rose
16+
{r = 136, g = 34, b = 85 }, # wine
17+
{r = 170, g = 68, b = 153 }, # purple
18+
]
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
use std::{
2+
hash::{DefaultHasher, Hash},
3+
hint::black_box,
4+
time::Duration,
5+
};
6+
7+
use consistent_hashing::{ConsistentChooseKHasher, ConsistentHasher};
8+
use criterion::{
9+
criterion_group, criterion_main, AxisScale, Bencher, BenchmarkId, Criterion, PlotConfiguration,
10+
Throughput,
11+
};
12+
use rand::{rng, Rng};
13+
14+
fn throughput_benchmark(c: &mut Criterion) {
15+
let keys: Vec<u64> = rng().random_iter().take(1000).collect();
16+
17+
let mut group = c.benchmark_group(format!("choose"));
18+
group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));
19+
for n in [1usize, 10, 100, 1000, 10000] {
20+
group.throughput(Throughput::Elements(keys.len() as u64));
21+
group.bench_with_input(BenchmarkId::new(format!("1"), n), &n, |b, n| {
22+
b.iter_batched(
23+
|| &keys,
24+
|keys| {
25+
for key in keys {
26+
let mut h = DefaultHasher::new();
27+
key.hash(&mut h);
28+
black_box(ConsistentHasher::new(h).prev(*n + 1));
29+
}
30+
},
31+
criterion::BatchSize::SmallInput,
32+
)
33+
});
34+
for k in [1, 2, 3, 10, 100] {
35+
group.bench_with_input(BenchmarkId::new(format!("k_{k}"), n), &n, |b, n| {
36+
b.iter_batched(
37+
|| &keys,
38+
|keys| {
39+
let mut res = Vec::with_capacity(k);
40+
for key in keys {
41+
let mut h = DefaultHasher::new();
42+
key.hash(&mut h);
43+
black_box(ConsistentChooseKHasher::new(h, k).prev(*n + k, &mut res));
44+
}
45+
},
46+
criterion::BatchSize::SmallInput,
47+
)
48+
});
49+
}
50+
}
51+
group.finish();
52+
}
53+
54+
criterion_group!(
55+
name = benches;
56+
config = Criterion::default()
57+
.warm_up_time(Duration::from_millis(500))
58+
.measurement_time(Duration::from_millis(4000))
59+
.nresamples(1000);
60+
61+
targets = throughput_benchmark,
62+
);
63+
criterion_main!(benches);

crates/consistent-hashing/src/lib.rs

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -232,11 +232,11 @@ impl<H: ManySeqBuilder> ConsistentChooseKHasher<H> {
232232
}
233233

234234
// TODO: Implement this as an iterator!
235-
pub fn prev(&self, mut n: usize) -> Vec<usize> {
236-
let mut samples = Vec::with_capacity(self.k);
235+
pub fn prev(&self, mut n: usize, samples: &mut Vec<usize>) {
237236
let mut samplers: Vec<_> = (0..self.k)
238237
.map(|i| ConsistentHashRevIterator::new(n - i, self.builder.seq_builder(i)).peekable())
239238
.collect();
239+
samples.clear();
240240
for i in (0..self.k).rev() {
241241
let mut max = 0;
242242
for k in 0..=i {
@@ -248,8 +248,6 @@ impl<H: ManySeqBuilder> ConsistentChooseKHasher<H> {
248248
samples.push(max);
249249
n = max;
250250
}
251-
samples.sort();
252-
samples
253251
}
254252
}
255253

0 commit comments

Comments
 (0)