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/tests/slice.rs | 63 ++++++++++++++++++++++++++++++++++++---------- 1 file changed, 50 insertions(+), 13 deletions(-) (limited to 'src/libcore/tests') diff --git a/src/libcore/tests/slice.rs b/src/libcore/tests/slice.rs index 8c31d2e83d3..7835080db1d 100644 --- a/src/libcore/tests/slice.rs +++ b/src/libcore/tests/slice.rs @@ -15,22 +15,59 @@ use rand::{Rng, XorShiftRng}; #[test] fn test_binary_search() { + let b: [i32; 0] = []; + assert_eq!(b.binary_search(&5), Err(0)); + + let b = [4]; + assert_eq!(b.binary_search(&3), Err(0)); + assert_eq!(b.binary_search(&4), Ok(0)); + assert_eq!(b.binary_search(&5), Err(1)); + let b = [1, 2, 4, 6, 8, 9]; - assert!(b.binary_search_by(|v| v.cmp(&6)) == Ok(3)); - assert!(b.binary_search_by(|v| v.cmp(&5)) == Err(3)); - let b = [1, 2, 4, 6, 7, 8, 9]; - assert!(b.binary_search_by(|v| v.cmp(&6)) == Ok(3)); - assert!(b.binary_search_by(|v| v.cmp(&5)) == Err(3)); - let b = [1, 2, 4, 6, 8, 9]; - assert!(b.binary_search_by(|v| v.cmp(&8)) == Ok(4)); - assert!(b.binary_search_by(|v| v.cmp(&7)) == Err(4)); + assert_eq!(b.binary_search(&5), Err(3)); + assert_eq!(b.binary_search(&6), Ok(3)); + assert_eq!(b.binary_search(&7), Err(4)); + assert_eq!(b.binary_search(&8), Ok(4)); + + let b = [1, 2, 4, 5, 6, 8]; + assert_eq!(b.binary_search(&9), Err(6)); + let b = [1, 2, 4, 6, 7, 8, 9]; - assert!(b.binary_search_by(|v| v.cmp(&8)) == Ok(5)); + assert_eq!(b.binary_search(&6), Ok(3)); + assert_eq!(b.binary_search(&5), Err(3)); + assert_eq!(b.binary_search(&8), Ok(5)); + let b = [1, 2, 4, 5, 6, 8, 9]; - assert!(b.binary_search_by(|v| v.cmp(&7)) == Err(5)); - assert!(b.binary_search_by(|v| v.cmp(&0)) == Err(0)); - let b = [1, 2, 4, 5, 6, 8]; - assert!(b.binary_search_by(|v| v.cmp(&9)) == Err(6)); + assert_eq!(b.binary_search(&7), Err(5)); + assert_eq!(b.binary_search(&0), Err(0)); + + let b = [1, 3, 3, 3, 7]; + assert_eq!(b.binary_search(&0), Err(0)); + assert_eq!(b.binary_search(&1), Ok(0)); + assert_eq!(b.binary_search(&2), Err(1)); + assert!(match b.binary_search(&3) { Ok(1...3) => true, _ => false }); + assert!(match b.binary_search(&3) { Ok(1...3) => true, _ => false }); + assert_eq!(b.binary_search(&4), Err(4)); + assert_eq!(b.binary_search(&5), Err(4)); + assert_eq!(b.binary_search(&6), Err(4)); + assert_eq!(b.binary_search(&7), Ok(4)); + assert_eq!(b.binary_search(&8), Err(5)); +} + +#[test] +// Test implementation specific behavior when finding equivalent elements. +// It is ok to break this test but when you do a crater run is highly advisable. +fn test_binary_search_implementation_details() { + let b = [1, 1, 2, 2, 3, 3, 3]; + assert_eq!(b.binary_search(&1), Ok(1)); + assert_eq!(b.binary_search(&2), Ok(3)); + assert_eq!(b.binary_search(&3), Ok(6)); + let b = [1, 1, 1, 1, 1, 3, 3, 3, 3]; + assert_eq!(b.binary_search(&1), Ok(4)); + assert_eq!(b.binary_search(&3), Ok(8)); + let b = [1, 1, 1, 1, 3, 3, 3, 3, 3]; + assert_eq!(b.binary_search(&1), Ok(3)); + assert_eq!(b.binary_search(&3), Ok(8)); } #[test] -- cgit 1.4.1-3-g733a5