ackermann-calc-bench.rs

// $  cargo +nightly --version # you need to use rustc nightly version
// cargo 1.39.0-nightly (3596cb86b 2019-09-19)
// $ cargo +nightly bench --features unstable
//    Compiling ackermann-calc v0.1.0 (/home/mizukmb/src/ackermann-calc)
//     Finished release [optimized] target(s) in 1.12s
//      Running target/release/deps/ackermann_calc-83e1a1843dd244b1
//
// running 9 tests
// test tests::a0 ... ignored
// test tests::a1 ... ignored
// test tests::a2 ... ignored
// test tests::a3 ... ignored
// test tests::a4 ... ignored
// test tests::conv_from_u32_biguint ... ignored
// test bench::biguint_bench ... bench:  43,511,770 ns/iter (+/- 1,410,295)
// test bench::memo_bench    ... bench:   1,492,002 ns/iter (+/- 144,372)
// test bench::naive_bench   ... bench:     839,195 ns/iter (+/- 48,702)
//
// test result: ok. 0 passed; 0 failed; 6 ignored; 3 measured; 0 filtered out
#![feature(test)]
extern crate test;

use std::thread;
use num_bigint::BigUint;
use std::collections::HashMap;

fn biguint_ackermann(m: u32, n: u32) -> BigUint {
    fn work(m: BigUint, n: BigUint) -> BigUint {
        if m == b(0) {
            n + b(1)
        } else if n == b(0) {
            work(m.clone() - b(1), b(1))
        } else {
            work(m.clone() - b(1), work(m.clone(), n - b(1)))
        }
    }

    work(b(m), b(n))
}

fn naive_ackermann(m: i32, n: i32) -> i32 {
    fn work(m: i32, n: i32) -> i32 {
        if m == 0 {
            n + 1
        } else if n == 0 {
            work(m - 1, 1)
        } else {
            work(m - 1, work(m, n - 1))
        }
    }

    fn run_in_thread(m: i32, n: i32) -> i32 {
        let builder = thread::Builder::new()
            .name("large_stack_thread".into())
            .stack_size(32 * 1024 * 1024); // 32MiB

        let handler = builder.spawn(move || work(m, n)).unwrap();

        handler.join().unwrap()
    }

    run_in_thread(m, n)
}

// What's ackermann function?
// A(m,n) =
//     n+1             if m = 0
//     A(m-1,1)        if m > 0 and n = 0
//     A(m-1,A(m,n-1)) if m > 0 and n > 0
fn ackermann(m: u32, n: u32) -> BigUint {
    fn work(m: BigUint, n: BigUint, memo: &mut HashMap<(BigUint, BigUint), BigUint>) -> BigUint {
        if let Some(v) = memo.get(&(m.clone(), n.clone())) {
            (*v).clone()
        } else {
            if m == b(0) {
                let res = n.clone() + b(1);
                memo.insert((m, n), res.clone());
                res
            } else if n == b(0) {
                let res = work(m.clone() - b(1), b(1), memo);
                memo.insert((m, n), res.clone());
                res
            } else {
                let res = work(m.clone() - b(1), work(m.clone(), n.clone() - b(1), memo), memo);
                memo.insert((m, n), res.clone());
                res
            }
        }
    }

    fn run_in_thread(m: u32, n: u32) -> BigUint {
        let builder = thread::Builder::new()
            .name("large_stack_thread".into())
            .stack_size(32 * 1024 * 1024); // 32MiB

        let handler = builder.spawn(move || {
            let mut memo = HashMap::new();
            work(b(m), b(n), &mut memo)
        }).unwrap();

        handler.join().unwrap()
    }

    run_in_thread(m, n)
}

fn b(v: u32) -> BigUint {
    BigUint::from(v)
}

fn main() {
    println!("{}", ackermann(1, 0));
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::convert::TryInto;

    #[test]
    fn a0() {
        assert_eq!(ackermann(0, 0), b(1));
        assert_eq!(ackermann(0, 1), b(2));
    }

    #[test]
    fn a1() {
        assert_eq!(ackermann(1, 0), b(2));
        assert_eq!(ackermann(1, 1), b(3));
        assert_eq!(ackermann(1, 2), b(4));
    }

    #[test]
    fn a2() {
        assert_eq!(ackermann(2, 0), b(3));
        assert_eq!(ackermann(2, 1), b(5));

        for i in 0..10 {
            assert_eq!(ackermann(2, i), b(2 * i + 3));
        }
    }

    #[test]
    fn a3() {
        for i in 0..10 {
            let ui: u32 = i.try_into().unwrap();
            assert_eq!(ackermann(3, i), b(2_u32.pow(ui + 3) - 3));
        }
    }

    #[test]
    fn a4() {
        assert_eq!(ackermann(4, 1), b(65533));
    }

    #[test]
    fn conv_from_u32_biguint() {
        assert_eq!(b(5), BigUint::new(vec![5]));
    }
}

#[cfg(all(feature = "unstable", test))]
mod bench {
    use super::*;

    use self::test::Bencher;

    #[bench]
    fn naive_bench(b: &mut Bencher) {
        b.iter(|| naive_ackermann(3, 7))
    }

    #[bench]
    fn biguint_bench(b: &mut Bencher) {
        b.iter(|| biguint_ackermann(3, 7))
    }

    #[bench]
    fn memo_bench(b: &mut Bencher) {
        b.iter(|| ackermann(3, 7))
    }
}

アッカーマン関数の計算過程を表示する (その↑) / DDRの足運び最適化問題を解く ( https://booth.pm/ja/items/1575590 ) の 3.2.5 ベンチマークを取ってみる を実際に実行するための手順