Last active
March 2, 2026 10:05
-
-
Save hsqStephenZhang/3f0989fe371ccc44426e9a4c327fbe2a to your computer and use it in GitHub Desktop.
benchmark code for binary search code
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Intel(R) Core(TM) i5-14600KF, 64G mem | |
| ❯ perf stat -e branches,branch-misses $BENCH_BIN --bench --profile-time 5 "Binary Search/Traditional" | |
| Gnuplot not found, using plotters backend | |
| Benchmarking Binary Search/Traditional: Complete (Analysis Disabled) | |
| Performance counter stats for 'target/release/deps/bs_bench-df11742845ad013f --bench --profile-time 5 Binary Search/Traditional': | |
| 4,660,266,661 cpu_atom/branches/ (0.12%) | |
| 9,251,408,708 cpu_core/branches/ (99.88%) | |
| 433,443,172 cpu_atom/branch-misses/ # 9.30% of all branches (0.12%) | |
| 671,665,652 cpu_core/branch-misses/ # 7.26% of all branches (99.88%) | |
| 4.986636359 seconds time elapsed | |
| ❯ perf stat -e branches,branch-misses $BENCH_BIN --bench --profile-time 5 "Binary Search/Branchless" | |
| Gnuplot not found, using plotters backend | |
| Benchmarking Binary Search/Branchless: Complete (Analysis Disabled) | |
| Performance counter stats for 'target/release/deps/bs_bench-df11742845ad013f --bench --profile-time 5 Binary Search/Branchless': | |
| 5,578,659,613 cpu_atom/branches/ (0.25%) | |
| 11,924,327,834 cpu_core/branches/ (99.75%) | |
| 10,214,866 cpu_atom/branch-misses/ # 0.18% of all branches (0.25%) | |
| 2,562,955 cpu_core/branch-misses/ # 0.02% of all branches (99.75%) | |
| */ | |
| use criterion::{Criterion, black_box, criterion_group, criterion_main}; | |
| use rand::distributions::{Alphanumeric, DistString}; | |
| use rand::{Rng, thread_rng}; | |
| #[inline(always)] | |
| pub fn binary_search_traditional<T: Ord>(arr: &[T], target: &T) -> Result<usize, usize> { | |
| let mut left = 0; | |
| let mut right = arr.len(); | |
| while left < right { | |
| let mid = left + (right - left) / 2; | |
| match arr[mid].cmp(target) { | |
| std::cmp::Ordering::Less => left = mid + 1, | |
| std::cmp::Ordering::Equal => return Ok(mid), | |
| std::cmp::Ordering::Greater => right = mid, | |
| } | |
| } | |
| Err(left) | |
| } | |
| #[inline(always)] | |
| pub fn binary_search_branchless<T: Ord>(arr: &[T], target: &T) -> Result<usize, usize> { | |
| arr.binary_search(target) | |
| } | |
| fn bench_binary_search_i32(c: &mut Criterion) { | |
| let mut rng = thread_rng(); | |
| let size = 10_000; | |
| let arr: Vec<i32> = (0..size).collect(); | |
| let queries: Vec<i32> = (0..1000).map(|_| rng.gen_range(-10..size + 10)).collect(); | |
| let mut group = c.benchmark_group("Binary Search (i32)"); | |
| group.bench_function("Traditional", |b| { | |
| b.iter(|| { | |
| for q in &queries { | |
| let _ = black_box(binary_search_traditional(black_box(&arr), black_box(q))); | |
| } | |
| }) | |
| }); | |
| group.bench_function("Branchless (std)", |b| { | |
| b.iter(|| { | |
| for q in &queries { | |
| let _ = black_box(binary_search_branchless(black_box(&arr), black_box(q))); | |
| } | |
| }) | |
| }); | |
| group.finish(); | |
| } | |
| fn bench_binary_search_strings(c: &mut Criterion) { | |
| let mut rng = thread_rng(); | |
| let size = 10_000; | |
| let string_len = 100; // Define what "large" means here | |
| // Generate a sorted array of large random strings | |
| let mut arr: Vec<String> = (0..size) | |
| .map(|_| Alphanumeric.sample_string(&mut rng, string_len)) | |
| .collect(); | |
| arr.sort(); | |
| // Generate queries: mix of hits (in the array) and misses (random strings) | |
| let queries: Vec<String> = (0..1000) | |
| .map(|i| { | |
| if i % 2 == 0 { | |
| // 50% chance to search for an existing element | |
| arr[rng.gen_range(0..size)].clone() | |
| } else { | |
| // 50% chance to search for a new element (likely a miss) | |
| Alphanumeric.sample_string(&mut rng, string_len) | |
| } | |
| }) | |
| .collect(); | |
| let mut group = c.benchmark_group("Binary Search (Large Strings)"); | |
| group.bench_function("Traditional", |b| { | |
| b.iter(|| { | |
| for q in &queries { | |
| let _ = black_box(binary_search_traditional(black_box(&arr), black_box(q))); | |
| } | |
| }) | |
| }); | |
| group.bench_function("Branchless (std)", |b| { | |
| b.iter(|| { | |
| for q in &queries { | |
| let _ = black_box(binary_search_branchless(black_box(&arr), black_box(q))); | |
| } | |
| }) | |
| }); | |
| group.finish(); | |
| } | |
| criterion_group!( | |
| benches, | |
| bench_binary_search_i32, | |
| bench_binary_search_strings | |
| ); | |
| criterion_main!(benches); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment