comparison_of_binary_search_logics.rs

#![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 |


*/