From 86c052e5cb1096cb282b78b72e4df8fa9d76b4c6 Mon Sep 17 00:00:00 2001 From: =?utf8?q?=E5=BF=97=E5=AE=87?= Date: Thu, 23 Apr 2026 16:19:24 +0000 Subject: [PATCH] test(core): add random-access skiplist benchmark Addresses review feedback from @nymius: existing benches use fixed targets, which can land favorably or unfavorably relative to skip pointer positions and don't reflect real query patterns. The new bench draws 256 targets from a deterministic xorshift sequence and runs both a skiplist-enhanced get() and a plain linear walk over a 100k-node chain, so the same query stream exercises both paths. Also changed benchmarks to reflect checkpoint full chains and removed unhelpful benchmarks. --- crates/core/benches/checkpoint_skiplist.rs | 148 +++++++-------------- 1 file changed, 47 insertions(+), 101 deletions(-) diff --git a/crates/core/benches/checkpoint_skiplist.rs b/crates/core/benches/checkpoint_skiplist.rs index 2b9ea29c..268f85d8 100644 --- a/crates/core/benches/checkpoint_skiplist.rs +++ b/crates/core/benches/checkpoint_skiplist.rs @@ -16,15 +16,6 @@ fn create_checkpoint_chain(length: u32) -> CheckPoint { /// Benchmark get() operations at various depths fn bench_checkpoint_get(c: &mut Criterion) { - // Small chain - get near start - c.bench_function("get_100_near_start", |b: &mut Bencher| { - let cp = create_checkpoint_chain(100); - let target = 10; - b.iter(|| { - black_box(cp.get(target)); - }); - }); - // Medium chain - get middle c.bench_function("get_1000_middle", |b: &mut Bencher| { let cp = create_checkpoint_chain(1000); @@ -34,10 +25,12 @@ fn bench_checkpoint_get(c: &mut Criterion) { }); }); - // Large chain - get near end + // Large chain - get near end. Target is deliberately not a power of two or a multiple of + // common skiplist intervals (e.g. 1000), so neither pskip nor a fixed-stride scheme gets a + // free 1-hop hit on a "lucky" alignment. c.bench_function("get_10000_near_end", |b: &mut Bencher| { let cp = create_checkpoint_chain(10000); - let target = 9000; + let target = 9123; b.iter(|| { black_box(cp.get(target)); }); @@ -100,24 +93,6 @@ fn bench_checkpoint_range(c: &mut Criterion) { black_box(range); }); }); - - // Range near tip (minimal skip pointer usage) - c.bench_function("range_10000_near_tip", |b: &mut Bencher| { - let cp = create_checkpoint_chain(10000); - b.iter(|| { - let range: Vec<_> = cp.range(9900..).collect(); - black_box(range); - }); - }); - - // Single element range (edge case) - c.bench_function("range_single_element", |b: &mut Bencher| { - let cp = create_checkpoint_chain(10000); - b.iter(|| { - let range: Vec<_> = cp.range(5000..=5000).collect(); - black_box(range); - }); - }); } /// Benchmark insert() operations @@ -141,84 +116,56 @@ fn bench_checkpoint_insert(c: &mut Criterion) { }); } -/// Compare linear traversal vs skiplist-enhanced get() -fn bench_traversal_comparison(c: &mut Criterion) { - // Linear traversal benchmark - c.bench_function("linear_traversal_10000", |b: &mut Bencher| { - let cp = create_checkpoint_chain(10000); - let target = 100; // Near the beginning - - b.iter(|| { - let mut current = cp.clone(); - while current.height() > target { - if let Some(prev) = current.prev() { - current = prev; - } else { - break; - } - } - black_box(current); +/// Random-access lookups over a realistic-size chain, comparing skiplist-enhanced +/// `get()` against a plain linear walk. Targets are drawn from a deterministic +/// xorshift sequence so the same query stream is used for both benches. +/// +/// Chain length is sized to the order of a full Bitcoin chain (~1M blocks) so the log-scale +/// advantage of pskip is visible. +fn bench_random_access(c: &mut Criterion) { + const CHAIN_LEN: u32 = 1_000_000; + const QUERIES: usize = 256; + + let cp = create_checkpoint_chain(CHAIN_LEN); + + // Deterministic xorshift64* over the height range. + let mut state: u64 = 0x9E37_79B9_7F4A_7C15; + let targets: Vec = (0..QUERIES) + .map(|_| { + state ^= state << 13; + state ^= state >> 7; + state ^= state << 17; + (state % (CHAIN_LEN as u64 + 1)) as u32 + }) + .collect(); + + { + let cp = cp.clone(); + let targets = targets.clone(); + c.bench_function("random_access_skiplist_1m", move |b: &mut Bencher| { + let mut i = 0usize; + b.iter(|| { + let target = targets[i % QUERIES]; + i = i.wrapping_add(1); + black_box(cp.get(target)); + }); }); - }); - - // Skiplist-enhanced get() for comparison - c.bench_function("skiplist_get_10000", |b: &mut Bencher| { - let cp = create_checkpoint_chain(10000); - let target = 100; // Same target + } + c.bench_function("random_access_linear_1m", move |b: &mut Bencher| { + let mut i = 0usize; b.iter(|| { - black_box(cp.get(target)); - }); - }); -} + let target = targets[i % QUERIES]; + i = i.wrapping_add(1); -/// Analyze skip pointer distribution and usage -fn bench_skip_pointer_analysis(c: &mut Criterion) { - c.bench_function("count_skip_pointers_10000", |b: &mut Bencher| { - let cp = create_checkpoint_chain(10000); - - b.iter(|| { - let mut count = 0; let mut current = cp.clone(); - loop { - if current.skip().is_some() { - count += 1; - } - if let Some(prev) = current.prev() { - current = prev; - } else { - break; - } - } - black_box(count); - }); - }); - - // Measure actual skip pointer usage during traversal - c.bench_function("skip_usage_in_traversal", |b: &mut Bencher| { - let cp = create_checkpoint_chain(10000); - let target = 100; - - b.iter(|| { - let mut current = cp.clone(); - let mut skips_used = 0; - while current.height() > target { - if let Some(skip_cp) = current.skip() { - if skip_cp.height() >= target { - current = skip_cp; - skips_used += 1; - continue; - } - } - - if let Some(prev) = current.prev() { - current = prev; - } else { - break; + match current.prev() { + Some(prev) => current = prev, + None => break, } } - black_box((current, skips_used)); + black_box(current); }); }); } @@ -229,8 +176,7 @@ criterion_group!( bench_checkpoint_floor_at, bench_checkpoint_range, bench_checkpoint_insert, - bench_traversal_comparison, - bench_skip_pointer_analysis + bench_random_access ); criterion_main!(benches); -- 2.49.0