Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#![feature(test)]
//#![feature(partition_point)]
#![feature(duration_extras)]
#![feature(i128_type)]
extern crate test;
use std::cmp::Ord;
use std::cmp::Ordering::Greater;
use std::cmp::Ordering::Less;
use std::collections::HashMap;
use std::convert::Into;
use std::result::Result;
use std::result::Result::Err;
use std::result::Result::Ok;
use std::time::{Duration, Instant};
use test::black_box;
use logics::*;
mod logics {
use std::cmp::Ordering;
use std::cmp::Ordering::Equal;
use std::cmp::Ordering::Greater;
use std::cmp::Ordering::Less;
// logic1: Previous binary_earcy_by code
// logic2: Current binary_earcy_by code
// logic5: The logic of current partition_point and use early return to exit
// logic6: The logic of current partition_point and use flag to exit
// logic7: https://github.com/rust-lang/rust/pull/74024
#[inline]
pub fn logic1<T, F>(slice: &[T], mut f: F) -> Result<usize, usize>
where
F: FnMut(&T) -> Ordering,
{
let mut base = 0usize;
let mut s = slice;
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()),
}
}
}
#[inline]
pub fn logic2<T, F>(slice: &[T], mut f: F) -> Result<usize, usize>
where
F: FnMut(&T) -> Ordering,
{
let s = slice;
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;
let cmp = f(unsafe { s.get_unchecked(mid) });
base = if cmp == Greater { base } else { mid };
size -= half;
}
let cmp = f(unsafe { s.get_unchecked(base) });
if cmp == Equal {
Ok(base)
} else {
Err(base + (cmp == Less) as usize)
}
}
#[inline]
pub fn logic5<T, F>(slice: &[T], mut f: F) -> Result<usize, usize>
where
F: FnMut(&T) -> Ordering,
{
let mut left = 0;
let mut right = slice.len();
while left < right {
let mid = left + (right - left) / 2;
let cmp = f(unsafe { slice.get_unchecked(mid) });
if cmp == Less {
left = mid + 1;
} else {
right = mid;
if cmp == Equal {
return Ok(left);
}
}
}
Err(left)
}
#[inline]
pub fn logic6<T, F>(slice: &[T], mut f: F) -> Result<usize, usize>
where
F: FnMut(&T) -> Ordering,
{
let mut left = 0;
let mut right = slice.len();
let mut any_equal = false;
while left < right {
let mid = left + (right - left) / 2;
let cmp = f(unsafe { slice.get_unchecked(mid) });
if cmp == Less {
left = mid + 1;
}
if cmp != Less {
right = mid;
}
if cmp == Equal {
left = mid;
}
if cmp == Equal {
any_equal = true;
}
}
if any_equal {
Ok(left)
} else {
Err(left)
}
}
#[inline]
pub fn logic7<T, F>(slice: &[T], mut f: F) -> Result<usize, usize>
where
F: FnMut(&T) -> Ordering,
{
let s = slice;
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;
// SAFETY: the call is made safe by the following inconstants:
// - `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 };
if cmp == Equal {
return Ok(mid);
} else if cmp == Less {
base = mid
}
size -= half;
}
// SAFETY: 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)
}
}
}
macro_rules! define_binary_search_1 {
($name:ident, $logic:ident) => {
fn $name<T: Ord>(slice: &[T], value: &T) -> Result<usize, usize> {
$logic(slice, |x| x.cmp(value))
}
};
}
macro_rules! define_partition_point_1 {
($name:ident, $logic:ident) => {
fn $name<T: Ord, F>(slice: &[T], mut pred: F) -> usize
where
F: FnMut(&T) -> bool,
{
match $logic(slice, |x| if pred(x) { Less } else { Greater }) {
Ok(n) => n,
Err(n) => n,
}
}
};
}
define_binary_search_1!(binary_search_logic_1, logic1);
define_binary_search_1!(binary_search_logic_2, logic2);
define_binary_search_1!(binary_search_logic_5, logic5);
define_binary_search_1!(binary_search_logic_6, logic6);
define_binary_search_1!(binary_search_logic_7, logic7);
define_partition_point_1!(partition_point_logic_1, logic1);
define_partition_point_1!(partition_point_logic_2, logic2);
define_partition_point_1!(partition_point_logic_5, logic5);
define_partition_point_1!(partition_point_logic_6, logic6);
define_partition_point_1!(partition_point_logic_7, logic7);
const SPOOL_UP: usize = 10000;
const SAMPLE_SIZE: usize = 10000;
const NUMBER_OF_SAMPLES: usize = 100;
fn main() {
#[cfg(debug_assertions)]
eprintln!("!!! DEBUG MODE !!!");
let sizes = &[1_000, 10_000, 1_000_000];
let dups = &[1, 16, 1_000, 1_000_000];
let mut stats = HashMap::<(String, usize, usize), (Duration, Duration)>::new();
let cases = sizes
.into_iter()
.cloned()
.flat_map(|size| {
dups.into_iter()
.cloned()
.filter(|dup| dup <= &size)
.map(|dup| (size, dup))
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();
for &(size, dup) in &cases {
stats.insert(
("B.S. Logic 1".into(), size, dup),
my_bench::<_, usize, _>(binary_search_logic_1, size, dup),
);
stats.insert(
("B.S. Logic 2".into(), size, dup),
my_bench::<_, usize, _>(binary_search_logic_2, size, dup),
);
stats.insert(
("B.S. Logic 5".into(), size, dup),
my_bench::<_, usize, _>(binary_search_logic_5, size, dup),
);
stats.insert(
("B.S. Logic 6".into(), size, dup),
my_bench::<_, usize, _>(binary_search_logic_6, size, dup),
);
stats.insert(
("B.S. Logic 7".into(), size, dup),
my_bench::<_, usize, _>(binary_search_logic_7, size, dup),
);
stats.insert(
("corelib B.S.".into(), size, dup),
my_bench::<_, usize, _>(|s, v| s.binary_search(v), size, dup),
);
stats.insert(
("P.P. Logic 1".into(), size, dup),
my_bench::<_, usize, _>(|s, v| partition_point_logic_1(s, |x| x < v), size, dup),
);
stats.insert(
("P.P. Logic 2".into(), size, dup),
my_bench::<_, usize, _>(|s, v| partition_point_logic_2(s, |x| x < v), size, dup),
);
stats.insert(
("P.P. Logic 5".into(), size, dup),
my_bench::<_, usize, _>(|s, v| partition_point_logic_5(s, |x| x < v), size, dup),
);
stats.insert(
("P.P. Logic 6".into(), size, dup),
my_bench::<_, usize, _>(|s, v| partition_point_logic_6(s, |x| x < v), size, dup),
);
stats.insert(
("P.P. Logic 7".into(), size, dup),
my_bench::<_, usize, _>(|s, v| partition_point_logic_7(s, |x| x < v), size, dup),
);
// stats.insert(
// ("corelib P.P.".into(), size, dup),
// my_bench::<_, usize, _>(|s, v| s.partition_point(|x| x < v), size, dup),
// );
}
let show_table = |logics: &[&str]| {
write_header(&cases);
for &logic in logics {
print!("| {:13} |", logic);
for &(size, dup) in &cases {
if let Some(&(mean, sd)) = stats.get(&(logic.into(), size, dup)) {
print!(" {:3} ({:3}) |", as_nanos(mean), as_nanos(sd))
} else {
print!(" not found |");
}
}
println!();
}
};
show_table(&[
"B.S. Logic 1",
"B.S. Logic 2",
"B.S. Logic 5",
"B.S. Logic 6",
"B.S. Logic 7",
"corelib B.S.",
]);
println!();
show_table(&[
"P.P. Logic 1",
"P.P. Logic 2",
"P.P. Logic 5",
"P.P. Logic 6",
"P.P. Logic 7",
"corelib P.P.",
]);
println!();
}
fn write_header(cases: &[(usize, usize)]) {
print!("| {:13} |", "size");
for &(size, _) in cases {
print!(" {:9} |", size);
}
println!();
print!("| {:13} |", "dup");
for &(_, dup) in cases {
print!(" {:9} |", dup);
}
println!();
print!("+{}+", "-".repeat(15));
for _ in cases {
print!("{}+", "-".repeat(11));
}
println!();
}
fn my_bench<F, T, R>(f: F, size: usize, dup: usize) -> (Duration, Duration)
where
F: Fn(&[T], &T) -> R,
usize: Into<T>,
{
let slice: Vec<T> = (0..size).map(|x| x / dup * dup).map(|x| x.into()).collect();
let mut lcg = 0usize;
let mut next_value = || {
lcg = lcg.wrapping_mul(1664525).wrapping_add(1013904223);
(lcg % size / dup * dup).into()
};
let spoolup_values: Vec<T> = (0..SPOOL_UP).map(|_| next_value()).collect();
let samples_values: Vec<Vec<T>> = (0..NUMBER_OF_SAMPLES)
.map(|_| (0..SAMPLE_SIZE).map(|_| next_value()).collect())
.collect();
for x in spoolup_values {
black_box(f(&slice, &x));
}
let mut elapses = Vec::new();
for values in samples_values {
let started_at = Instant::now();
for value in values {
black_box(f(&slice, &value));
}
let ended_at = Instant::now();
elapses.push(as_secs_f64(ended_at - started_at) / SAMPLE_SIZE as f64);
}
let mean = elapses.iter().sum::<f64>() / NUMBER_OF_SAMPLES as f64;
let sd_sum = elapses.iter().map(|x| x - mean).map(|x| x * x).sum::<f64>();
let sd = (sd_sum / NUMBER_OF_SAMPLES as f64).sqrt();
let err = 1.96 * sd;
(from_secs_f64(mean), from_secs_f64(err))
}
const NANOS_PER_SEC: u32 = 1_000_000_000;
fn as_secs_f64(dur: Duration) -> f64 {
dur.as_secs() as f64 + dur.subsec_nanos() as f64 / NANOS_PER_SEC as f64
}
fn as_nanos(dur: Duration) -> u128 {
dur.as_secs() as u128 * NANOS_PER_SEC as u128 + dur.subsec_nanos() as u128
}
#[inline]
pub fn from_secs_f64(secs: f64) -> Duration {
const MAX_NANOS_F64: f64 = ((std::u64::MAX as u128 + 1) * (NANOS_PER_SEC as u128)) as f64;
let nanos = secs * (NANOS_PER_SEC as f64);
if !nanos.is_finite() {
panic!("got non-finite value when converting float to duration");
}
if nanos >= MAX_NANOS_F64 {
panic!("overflow when converting float to duration");
}
if nanos < 0.0 {
panic!("underflow when converting float to duration");
}
let nanos = nanos as u128;
Duration::new(
(nanos / (NANOS_PER_SEC as u128)) as u64,
(nanos % (NANOS_PER_SEC as u128)) as u32,
)
}
/*
# results
## 1.46 (nightly-2020-08-27)
| size | 1000 | 1000 | 1000 | 10000 | 10000 | 10000 | 1000000 | 1000000 | 1000000 | 1000000 |
| dup | 1 | 16 | 1000 | 1 | 16 | 1000 | 1 | 16 | 1000 | 1000000 |
+---------------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
| B.S. Logic 1 | 44 ( 12) | 23 ( 4) | 2 ( 2) | 56 ( 3) | 39 ( 2) | 13 ( 3) | 198 (162) | 139 ( 98) | 50 ( 3) | 2 ( 2) |
| B.S. Logic 2 | 36 ( 2) | 36 ( 4) | 7 ( 2) | 49 ( 2) | 52 ( 11) | 58 ( 29) | 129 ( 19) | 130 ( 14) | 145 (106) | 12 ( 2) |
| B.S. Logic 5 | 39 ( 2) | 23 ( 4) | 2 ( 2) | 52 ( 3) | 37 ( 3) | 12 ( 2) | 171 (142) | 164 (110) | 48 ( 3) | 4 ( 5) |
| B.S. Logic 6 | 23 ( 2) | 13 ( 3) | 2 ( 2) | 35 ( 2) | 23 ( 2) | 10 ( 3) | 165 ( 33) | 110 ( 46) | 47 ( 34) | 3 ( 3) |
| B.S. Logic 7 | 46 ( 3) | 25 ( 3) | 2 ( 2) | 65 ( 4) | 48 ( 34) | 14 ( 2) | 233 ( 66) | 186 (115) | 57 ( 8) | 2 ( 2) |
| corelib B.S. | 36 ( 2) | 37 ( 5) | 7 ( 2) | 50 ( 5) | 73 ( 56) | 44 ( 3) | 149 ( 91) | 158 (109) | 118 ( 5) | 12 ( 2) |
| size | 1000 | 1000 | 1000 | 10000 | 10000 | 10000 | 1000000 | 1000000 | 1000000 | 1000000 |
| dup | 1 | 16 | 1000 | 1 | 16 | 1000 | 1 | 16 | 1000 | 1000000 |
+---------------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
| P.P. Logic 1 | 20 ( 3) | 21 ( 3) | 20 ( 2) | 36 ( 2) | 36 ( 4) | 52 ( 50) | 195 (116) | 170 ( 31) | 141 (100) | 55 ( 41) |
| P.P. Logic 2 | 41 ( 2) | 34 ( 3) | 15 ( 7) | 56 ( 2) | 73 ( 55) | 21 ( 2) | 164 (115) | 142 ( 20) | 127 ( 89) | 13 ( 3) |
| P.P. Logic 5 | 40 ( 2) | 27 ( 2) | 8 ( 3) | 54 ( 3) | 53 ( 13) | 19 ( 2) | 174 (129) | 145 ( 22) | 89 ( 3) | 11 ( 4) |
| P.P. Logic 6 | 41 ( 3) | 28 ( 3) | 8 ( 3) | 55 ( 8) | 53 ( 2) | 22 ( 18) | 142 ( 16) | 149 ( 32) | 124 ( 93) | 11 ( 4) |
| P.P. Logic 7 | 42 ( 3) | 35 ( 2) | 7 ( 2) | 56 ( 4) | 55 ( 4) | 21 ( 2) | 167 (113) | 144 ( 25) | 102 ( 5) | 13 ( 3) |
| corelib P.P. | not found | not found | not found | not found | not found | not found | not found | not found | not found | not found |
## 1.23 (nightly-2018-01-04)
| size | 1000 | 1000 | 1000 | 10000 | 10000 | 10000 | 1000000 | 1000000 | 1000000 | 1000000 |
| dup | 1 | 16 | 1000 | 1 | 16 | 1000 | 1 | 16 | 1000 | 1000000 |
+---------------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
| B.S. Logic 1 | 46 ( 11) | 23 ( 5) | 2 ( 2) | 55 ( 3) | 37 ( 5) | 12 ( 2) | 178 ( 39) | 136 ( 84) | 48 ( 4) | 2 ( 2) |
| B.S. Logic 2 | 11 ( 3) | 10 ( 2) | 10 ( 2) | 17 ( 5) | 17 ( 3) | 15 ( 2) | 103 ( 42) | 153 (146) | 106 (102) | 25 ( 3) |
| B.S. Logic 5 | 44 ( 9) | 21 ( 2) | 2 ( 2) | 52 ( 2) | 36 ( 2) | 12 ( 2) | 137 ( 19) | 117 ( 15) | 47 ( 4) | 2 ( 3) |
| B.S. Logic 6 | 58 ( 19) | 26 ( 2) | 2 ( 2) | 69 ( 3) | 46 ( 3) | 15 ( 2) | 248 (121) | 272 (175) | 59 ( 3) | 2 ( 2) |
| B.S. Logic 7 | 44 ( 10) | 23 ( 3) | 2 ( 2) | 60 ( 3) | 39 ( 5) | 13 ( 2) | 171 ( 94) | 170 ( 54) | 47 ( 3) | 2 ( 2) |
| corelib B.S. | 9 ( 2) | 9 ( 2) | 21 ( 10) | 15 ( 3) | 15 ( 5) | 14 ( 4) | 90 ( 21) | 106 ( 52) | 95 ( 64) | 22 ( 3) |
| size | 1000 | 1000 | 1000 | 10000 | 10000 | 10000 | 1000000 | 1000000 | 1000000 | 1000000 |
| dup | 1 | 16 | 1000 | 1 | 16 | 1000 | 1 | 16 | 1000 | 1000000 |
+---------------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
| P.P. Logic 1 | 39 ( 2) | 25 ( 2) | 8 ( 3) | 70 ( 59) | 51 ( 7) | 20 ( 3) | 138 ( 18) | 182 (151) | 82 ( 4) | 11 ( 3) |
| P.P. Logic 2 | 10 ( 3) | 10 ( 2) | 13 ( 4) | 20 ( 9) | 17 ( 6) | 15 ( 2) | 112 ( 75) | 99 ( 47) | 88 ( 71) | 25 ( 3) |
| P.P. Logic 5 | 18 ( 2) | 18 ( 2) | 21 ( 2) | 36 ( 5) | 36 ( 7) | 35 ( 4) | 163 ( 99) | 147 ( 31) | 113 ( 16) | 46 ( 5) |
| P.P. Logic 6 | 29 ( 22) | 18 ( 2) | 17 ( 2) | 37 ( 3) | 37 ( 3) | 36 ( 4) | 148 ( 25) | 183 ( 96) | 117 ( 20) | 46 ( 5) |
| P.P. Logic 7 | 17 ( 10) | 10 ( 2) | 10 ( 2) | 17 ( 6) | 35 ( 5) | 15 ( 4) | 95 ( 28) | 110 ( 63) | 64 ( 4) | 25 ( 3) |
| corelib P.P. | not found | not found | not found | not found | not found | not found | not found | not found | not found | not found |
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment