Skip to content

Commit 24bb4d1

Browse files
borsbors
committed
Auto merge of #45333 - alkis:master, r=bluss
Improve SliceExt::binary_search performance Improve the performance of binary_search by reducing the number of unpredictable conditional branches in the loop. In addition improve the benchmarks to test performance in l1, l2 and l3 caches on sorted arrays with or without dups. Before: ``` test slice::binary_search_l1 ... bench: 48 ns/iter (+/- 1) test slice::binary_search_l2 ... bench: 63 ns/iter (+/- 0) test slice::binary_search_l3 ... bench: 152 ns/iter (+/- 12) test slice::binary_search_l1_with_dups ... bench: 36 ns/iter (+/- 0) test slice::binary_search_l2_with_dups ... bench: 64 ns/iter (+/- 1) test slice::binary_search_l3_with_dups ... bench: 153 ns/iter (+/- 6) ``` After: ``` test slice::binary_search_l1 ... bench: 15 ns/iter (+/- 0) test slice::binary_search_l2 ... bench: 23 ns/iter (+/- 0) test slice::binary_search_l3 ... bench: 100 ns/iter (+/- 17) test slice::binary_search_l1_with_dups ... bench: 15 ns/iter (+/- 0) test slice::binary_search_l2_with_dups ... bench: 23 ns/iter (+/- 0) test slice::binary_search_l3_with_dups ... bench: 98 ns/iter (+/- 14) ```
2 parents b226793 + 2ca111b commit 24bb4d1

File tree

4 files changed

+136
-30
lines changed

4 files changed

+136
-30
lines changed

‎src/libcore/benches/lib.rs

+1-1
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,6 @@ extern crate test;
2020
mod any;
2121
mod hash;
2222
mod iter;
23-
mod mem;
2423
mod num;
2524
mod ops;
25+
mod slice;

‎src/libcore/benches/slice.rs

+67
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
2+
// file at the top-level directory of this distribution and at
3+
// http://rust-lang.org/COPYRIGHT.
4+
//
5+
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6+
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7+
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8+
// option. This file may not be copied, modified, or distributed
9+
// except according to those terms.
10+
11+
use test::black_box;
12+
use test::Bencher;
13+
14+
enum Cache {
15+
L1,
16+
L2,
17+
L3,
18+
}
19+
20+
fn binary_search<F>(b: &mut Bencher, cache: Cache, mapper: F)
21+
where F: Fn(usize) -> usize
22+
{
23+
let size = match cache {
24+
Cache::L1 => 1000, // 8kb
25+
Cache::L2 => 10_000, // 80kb
26+
Cache::L3 => 1_000_000, // 8Mb
27+
};
28+
let v = (0..size).map(&mapper).collect::<Vec<_>>();
29+
let mut r = 0usize;
30+
b.iter(move || {
31+
// LCG constants from https://en.wikipedia.org/wiki/Numerical_Recipes.
32+
r = r.wrapping_mul(1664525).wrapping_add(1013904223);
33+
// Lookup the whole range to get 50% hits and 50% misses.
34+
let i = mapper(r % size);
35+
black_box(v.binary_search(&i).is_ok());
36+
})
37+
}
38+
39+
#[bench]
40+
fn binary_search_l1(b: &mut Bencher) {
41+
binary_search(b, Cache::L1, |i| i * 2);
42+
}
43+
44+
#[bench]
45+
fn binary_search_l2(b: &mut Bencher) {
46+
binary_search(b, Cache::L2, |i| i * 2);
47+
}
48+
49+
#[bench]
50+
fn binary_search_l3(b: &mut Bencher) {
51+
binary_search(b, Cache::L3, |i| i * 2);
52+
}
53+
54+
#[bench]
55+
fn binary_search_l1_with_dups(b: &mut Bencher) {
56+
binary_search(b, Cache::L1, |i| i / 16 * 16);
57+
}
58+
59+
#[bench]
60+
fn binary_search_l2_with_dups(b: &mut Bencher) {
61+
binary_search(b, Cache::L2, |i| i / 16 * 16);
62+
}
63+
64+
#[bench]
65+
fn binary_search_l3_with_dups(b: &mut Bencher) {
66+
binary_search(b, Cache::L3, |i| i / 16 * 16);
67+
}

‎src/libcore/slice/mod.rs

+18-16
Original file line numberDiff line numberDiff line change
@@ -391,23 +391,25 @@ impl<T> SliceExt for [T] {
391391
fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
392392
where F: FnMut(&'a T) -> Ordering
393393
{
394-
let mut base = 0usize;
395-
let mut s = self;
396-
397-
loop {
398-
let (head, tail) = s.split_at(s.len() >> 1);
399-
if tail.is_empty() {
400-
return Err(base)
401-
}
402-
match f(&tail[0]) {
403-
Less => {
404-
base += head.len() + 1;
405-
s = &tail[1..];
406-
}
407-
Greater => s = head,
408-
Equal => return Ok(base + head.len()),
409-
}
394+
let s = self;
395+
let mut size = s.len();
396+
if size == 0 {
397+
return Err(0);
410398
}
399+
let mut base = 0usize;
400+
while size > 1 {
401+
let half = size / 2;
402+
let mid = base + half;
403+
// mid is always in [0, size).
404+
// mid >= 0: by definition
405+
// mid < size: mid = size / 2 + size / 4 + size / 8 ...
406+
let cmp = f(unsafe { s.get_unchecked(mid) });
407+
base = if cmp == Greater { base } else { mid };
408+
size -= half;
409+
}
410+
// base is always in [0, size) because base <= mid.
411+
let cmp = f(unsafe { s.get_unchecked(base) });
412+
if cmp == Equal { Ok(base) } else { Err(base + (cmp == Less) as usize) }
411413
}
412414

413415
#[inline]

‎src/libcore/tests/slice.rs

+50-13
Original file line numberDiff line numberDiff line change
@@ -15,22 +15,59 @@ use rand::{Rng, XorShiftRng};
1515

1616
#[test]
1717
fn test_binary_search() {
18+
let b: [i32; 0] = [];
19+
assert_eq!(b.binary_search(&5), Err(0));
20+
21+
let b = [4];
22+
assert_eq!(b.binary_search(&3), Err(0));
23+
assert_eq!(b.binary_search(&4), Ok(0));
24+
assert_eq!(b.binary_search(&5), Err(1));
25+
1826
let b = [1, 2, 4, 6, 8, 9];
19-
assert!(b.binary_search_by(|v| v.cmp(&6)) == Ok(3));
20-
assert!(b.binary_search_by(|v| v.cmp(&5)) == Err(3));
21-
let b = [1, 2, 4, 6, 7, 8, 9];
22-
assert!(b.binary_search_by(|v| v.cmp(&6)) == Ok(3));
23-
assert!(b.binary_search_by(|v| v.cmp(&5)) == Err(3));
24-
let b = [1, 2, 4, 6, 8, 9];
25-
assert!(b.binary_search_by(|v| v.cmp(&8)) == Ok(4));
26-
assert!(b.binary_search_by(|v| v.cmp(&7)) == Err(4));
27+
assert_eq!(b.binary_search(&5), Err(3));
28+
assert_eq!(b.binary_search(&6), Ok(3));
29+
assert_eq!(b.binary_search(&7), Err(4));
30+
assert_eq!(b.binary_search(&8), Ok(4));
31+
32+
let b = [1, 2, 4, 5, 6, 8];
33+
assert_eq!(b.binary_search(&9), Err(6));
34+
2735
let b = [1, 2, 4, 6, 7, 8, 9];
28-
assert!(b.binary_search_by(|v| v.cmp(&8)) == Ok(5));
36+
assert_eq!(b.binary_search(&6), Ok(3));
37+
assert_eq!(b.binary_search(&5), Err(3));
38+
assert_eq!(b.binary_search(&8), Ok(5));
39+
2940
let b = [1, 2, 4, 5, 6, 8, 9];
30-
assert!(b.binary_search_by(|v| v.cmp(&7)) == Err(5));
31-
assert!(b.binary_search_by(|v| v.cmp(&0)) == Err(0));
32-
let b = [1, 2, 4, 5, 6, 8];
33-
assert!(b.binary_search_by(|v| v.cmp(&9)) == Err(6));
41+
assert_eq!(b.binary_search(&7), Err(5));
42+
assert_eq!(b.binary_search(&0), Err(0));
43+
44+
let b = [1, 3, 3, 3, 7];
45+
assert_eq!(b.binary_search(&0), Err(0));
46+
assert_eq!(b.binary_search(&1), Ok(0));
47+
assert_eq!(b.binary_search(&2), Err(1));
48+
assert!(match b.binary_search(&3) { Ok(1...3) => true, _ => false });
49+
assert!(match b.binary_search(&3) { Ok(1...3) => true, _ => false });
50+
assert_eq!(b.binary_search(&4), Err(4));
51+
assert_eq!(b.binary_search(&5), Err(4));
52+
assert_eq!(b.binary_search(&6), Err(4));
53+
assert_eq!(b.binary_search(&7), Ok(4));
54+
assert_eq!(b.binary_search(&8), Err(5));
55+
}
56+
57+
#[test]
58+
// Test implementation specific behavior when finding equivalent elements.
59+
// It is ok to break this test but when you do a crater run is highly advisable.
60+
fn test_binary_search_implementation_details() {
61+
let b = [1, 1, 2, 2, 3, 3, 3];
62+
assert_eq!(b.binary_search(&1), Ok(1));
63+
assert_eq!(b.binary_search(&2), Ok(3));
64+
assert_eq!(b.binary_search(&3), Ok(6));
65+
let b = [1, 1, 1, 1, 1, 3, 3, 3, 3];
66+
assert_eq!(b.binary_search(&1), Ok(4));
67+
assert_eq!(b.binary_search(&3), Ok(8));
68+
let b = [1, 1, 1, 1, 3, 3, 3, 3, 3];
69+
assert_eq!(b.binary_search(&1), Ok(3));
70+
assert_eq!(b.binary_search(&3), Ok(8));
3471
}
3572

3673
#[test]

0 commit comments

Comments
 (0)