Lexicographic comparison of integers

cmp_dec.rs

#![cfg_attr(test, feature(test))]
#![cfg_attr(feature = "int_log", feature(int_log))]

use std::cmp::Ordering;

macro_rules! imp {
    ($lhs:expr, $rhs:expr, |$min:ident, $max:ident| $divisor:expr) => {{
        // Because `'0' < '9' < 'A' < 'Z' (< 'a' < 'z')` holds, we don't need to special-case
        // radixes greater than 10.

        let (lhs, rhs) = ($lhs, $rhs);

        if lhs == rhs {
            return Ordering::Equal;
        }

        let (lhs, rhs, reversed) = if lhs < rhs {
            (rhs, lhs, true)
        } else {
            (lhs, rhs, false)
        };

        if rhs == 0 {
            return if reversed {
                Ordering::Less
            } else {
                Ordering::Greater
            };
        }

        let divisor = match (lhs, rhs) {
            ($max, $min) => $divisor,
        };
        // Align the number of digits to make numerical comparison equivalent to lexical comparison.
        let lhs = lhs / divisor;

        if (lhs < rhs) ^ reversed {
            Ordering::Less
        } else {
            // We've ruled out the case of the input `rhs` equals the input `lhs`, so if `lhs` here
            // equals `rhs`, it has been truncated and thus has been greater originally.
            Ordering::Greater
        }
    }};
}

/// Lexicographically compares two integers.
///
/// ## Examples
///
/// ```
/// # use playground::cmp_int;
/// #
/// assert!(cmp_int(42, 3, 10).is_gt());
/// assert!(cmp_int(24, 3, 10).is_lt());
///
/// assert!(cmp_int(0x2a, 0x9, 16).is_lt());
/// assert!(cmp_int(0xa2, 0x9, 16).is_gt());
/// ```
pub const fn cmp_int(lhs: u64, rhs: u64, radix: u64) -> Ordering {
    if radix <= 1 {
        panic!("`radix` must be greater than 1");
    }

    imp!(lhs, rhs, |min, max| radix
        .pow(log(max, radix) - log(min, radix)))
}

pub const fn cmp_dec(lhs: u64, rhs: u64) -> Ordering {
    imp!(lhs, rhs, |min, max| 10_u64.pow(log10(max) - log10(min)))
}

pub const fn cmp_bin(lhs: u64, rhs: u64) -> Ordering {
    imp!(lhs, rhs, |min, max| 1 << (log2(max) - log2(min)))
}

#[cfg(not(feature = "int_log"))]
const fn log(mut n: u64, base: u64) -> u32 {
    if n == 0 || base <= 1 {
        unreachable!();
    }

    let mut x = 0;

    while n >= base {
        n /= base;
        x += 1;
    }

    x
}

#[cfg(not(feature = "int_log"))]
const fn log10(n: u64) -> u32 {
    log(n, 10)
}

const fn log2(n: u64) -> u32 {
    u64::BITS - 1 - n.leading_zeros()
}

#[cfg(test)]
mod benches {
    extern crate test;

    use test::Bencher;

    use super::*;

    #[bench]
    fn native_01_digit(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1_u64, 9_u64));
            lhs.cmp(&rhs)
        });
    }

    #[bench]
    fn native_04_digits(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1234_u64, 4321_u64));
            lhs.cmp(&rhs)
        });
    }

    #[bench]
    fn native_16_digits(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1234567812345678_u64, 8765432187654321_u64));
            lhs.cmp(&rhs)
        });
    }

    #[bench]
    fn to_string_01_digit(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1_u64, 9_u64));
            (*lhs.to_string()).cmp(&*rhs.to_string())
        });
    }

    #[bench]
    fn to_string_04_digits(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1234_u64, 4321_u64));
            (*lhs.to_string()).cmp(&*rhs.to_string())
        });
    }

    #[bench]
    fn to_string_16_digits(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1234567812345678_u64, 8765432187654321_u64));
            (*lhs.to_string()).cmp(&*rhs.to_string())
        });
    }

    #[bench]
    fn itoa_01_digit(b: &mut Bencher) {
        let (lhs, rhs) = (1_u64, 9_u64);
        b.iter(|| {
            let (lhs, rhs) = test::black_box((lhs, rhs));
            let (mut lbuf, mut rbuf) = (itoa::Buffer::new(), itoa::Buffer::new());
            let (lhs, rhs) = (lbuf.format(lhs), rbuf.format(rhs));
            lhs.cmp(&rhs)
        });
    }

    #[bench]
    fn itoa_04_digits(b: &mut Bencher) {
        let (lhs, rhs) = (1234_u64, 4321_u64);
        b.iter(|| {
            let (lhs, rhs) = test::black_box((lhs, rhs));
            let (mut lbuf, mut rbuf) = (itoa::Buffer::new(), itoa::Buffer::new());
            let (lhs, rhs) = (lbuf.format(lhs), rbuf.format(rhs));
            lhs.cmp(&rhs)
        });
    }

    #[bench]
    fn itoa_16_digits(b: &mut Bencher) {
        let (lhs, rhs) = (1234567812345678_u64, 8765432187654321_u64);
        b.iter(|| {
            let (lhs, rhs) = test::black_box((lhs, rhs));
            let (mut lbuf, mut rbuf) = (itoa::Buffer::new(), itoa::Buffer::new());
            let (lhs, rhs) = (lbuf.format(lhs), rbuf.format(rhs));
            lhs.cmp(&rhs)
        });
    }

    #[bench]
    fn cmp_int_01_digit(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1_u64, 9_u64));
            cmp_int(lhs, rhs, 10)
        });
    }

    #[bench]
    fn cmp_int_04_digits(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1234_u64, 4321_u64));
            cmp_int(lhs, rhs, 10)
        });
    }

    #[bench]
    fn cmp_int_16_digits(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1234567812345678_u64, 8765432187654321_u64));
            cmp_int(lhs, rhs, 10)
        });
    }

    #[bench]
    fn cmp_dec_01_digit(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1_u64, 9_u64));
            cmp_dec(lhs, rhs)
        });
    }

    #[bench]
    fn cmp_dec_04_digits(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1234_u64, 4321_u64));
            cmp_dec(lhs, rhs)
        });
    }

    #[bench]
    fn cmp_dec_16_digits(b: &mut Bencher) {
        b.iter(|| {
            let (lhs, rhs) = test::black_box((1234567812345678_u64, 8765432187654321_u64));
            cmp_dec(lhs, rhs)
        });
    }

    // $ cargo +nightly bench --features=int_log
    // running 15 tests
    // test cmp_dec_01_digit    ... bench:          36 ns/iter (+/- 547)
    // test cmp_dec_04_digits   ... bench:          21 ns/iter (+/- 6)
    // test cmp_dec_16_digits   ... bench:          35 ns/iter (+/- 35)
    // test cmp_int_01_digit    ... bench:          18 ns/iter (+/- 9)
    // test cmp_int_04_digits   ... bench:          86 ns/iter (+/- 91)
    // test cmp_int_16_digits   ... bench:         439 ns/iter (+/- 121)
    // test itoa_01_digit       ... bench:           8 ns/iter (+/- 8)
    // test itoa_04_digits      ... bench:          11 ns/iter (+/- 15)
    // test itoa_16_digits      ... bench:          29 ns/iter (+/- 29)
    // test native_01_digit     ... bench:           0 ns/iter (+/- 0)
    // test native_04_digits    ... bench:           0 ns/iter (+/- 0)
    // test native_16_digits    ... bench:           0 ns/iter (+/- 0)
    // test to_string_01_digit  ... bench:         332 ns/iter (+/- 76)
    // test to_string_04_digits ... bench:         349 ns/iter (+/- 92)
    // test to_string_16_digits ... bench:         534 ns/iter (+/- 933)
    //
    // test result: ok. 0 passed; 0 failed; 0 ignored; 15 measured; 0 filtered out; finished in 47.81s
    
    // cargo +nightly bench -- cmp_dec
    // running 3 tests
    // test cmp_dec_01_digit    ... bench:          31 ns/iter (+/- 127)
    // test cmp_dec_04_digits   ... bench:          58 ns/iter (+/- 114)
    // test cmp_dec_16_digits   ... bench:          91 ns/iter (+/- 249)
    //
    // test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured; 12 filtered out; finished in 11.58s
}