From 2ca111b6b91c578c8a2b8e610471e582b6cf2c6b Mon Sep 17 00:00:00 2001 From: Alkis Evlogimenos Date: Mon, 16 Oct 2017 14:05:16 +0200 Subject: 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) ``` --- src/libcore/slice/mod.rs | 34 ++++++++++++++++++---------------- 1 file changed, 18 insertions(+), 16 deletions(-) (limited to 'src/libcore/slice') diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs index 5039bef631e..e5b4df96845 100644 --- a/src/libcore/slice/mod.rs +++ b/src/libcore/slice/mod.rs @@ -394,23 +394,25 @@ impl SliceExt for [T] { fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result where F: FnMut(&'a T) -> Ordering { - let mut base = 0usize; - let mut s = self; - - loop { - let (head, tail) = s.split_at(s.len() >> 1); - if tail.is_empty() { - return Err(base) - } - match f(&tail[0]) { - Less => { - base += head.len() + 1; - s = &tail[1..]; - } - Greater => s = head, - Equal => return Ok(base + head.len()), - } + let s = self; + let mut size = s.len(); + if size == 0 { + return Err(0); } + let mut base = 0usize; + while size > 1 { + let half = size / 2; + let mid = base + half; + // mid is always in [0, size). + // mid >= 0: by definition + // mid < size: mid = size / 2 + size / 4 + size / 8 ... + let cmp = f(unsafe { s.get_unchecked(mid) }); + base = if cmp == Greater { base } else { mid }; + size -= half; + } + // base is always in [0, size) because base <= mid. + let cmp = f(unsafe { s.get_unchecked(base) }); + if cmp == Equal { Ok(base) } else { Err(base + (cmp == Less) as usize) } } #[inline] -- cgit 1.4.1-3-g733a5