lib.rs

#![feature(test)]

extern crate test;
use test::Bencher;
use std::mem;

fn break_patterns1<T>(v: &mut [T]) {
    let len = v.len();

    if len >= 8 {
        // A random number will be taken modulo this one. The modulus is a power of two so that we
        // can simply take bitwise "and", thus avoiding costly CPU operations.
        let modulus = (len / 4).next_power_of_two();
        debug_assert!(modulus >= 1 && modulus <= len / 2);

        // Pseudorandom number generation from the "Xorshift RNGs" paper by George Marsaglia.
        let mut random = len;
        random ^= random << 13;
        random ^= random >> 17;
        random ^= random << 5;
        random &= modulus - 1;
        debug_assert!(random < len / 2);

        // The first index.
        let a = len / 4 * 2;
        debug_assert!(a >= 1 && a < len - 2);

        // The second index.
        let b = len / 4 + random;
        debug_assert!(b >= 1 && b < len - 2);

        // Swap neighbourhoods of `a` and `b`.
        for i in 0..3 {
            v.swap(a - 1 + i, b - 1 + i);
        }
    }
}

fn break_patterns2<T>(v: &mut [T]) {
    let len = v.len();
    if len >= 8 {
        // Pseudorandom number generator from the "Xorshift RNGs" paper by George Marsaglia.
        let mut random = len as u32;
        let mut gen_u32 = || {
            random ^= random << 13;
            random ^= random >> 17;
            random ^= random << 5;
            random
        };
        let mut gen_usize = || if mem::size_of::<usize>() <= 4 {
            gen_u32() as usize
        } else {
            (((gen_u32() as u64) << 32) | (gen_u32() as u64)) as usize
        };

        // Take random numbers modulo this number.
        // The number fits into `usize` because `len` is not greater than `isize::MAX`.
        let modulus = len.next_power_of_two();

        // Some pivot candidates will be in the nearby of this index. Let's randomize them.
        let pos = len / 4 * 2;

        for i in 0..3 {
            // Generate a random number modulo `len`. However, in order to avoid costly operations
            // we first take it modulo a power of two, and then decrease by `len` until it fits
            // into the range `[0, len - 1]`.
            let mut other = gen_usize() & (modulus - 1);
            while other >= len {
                other -= len;
            }

            v.swap(pos - 1 + i, other);
        }
    }
}

#[bench]
fn breakv1(b: &mut Bencher) {
    let mut vec: Vec<u32> = (0..1000_000_000).collect();
    b.iter(|| {
        test::black_box(&mut vec);
        break_patterns1(&mut vec);
        test::black_box(&mut vec);
    });
}

#[bench]
fn breakv2(b: &mut Bencher) {
    let mut vec: Vec<u32> = (0..1000_000_000).collect();
    b.iter(|| {
        test::black_box(&mut vec);
        break_patterns2(&mut vec);
        test::black_box(&mut vec);
    });
}

#[test]
fn break_test() {
    let mut vec1: Vec<u32> = (0..100).collect();
    break_patterns1(&mut vec1);

    let mut vec2: Vec<u32> = (0..100).collect();
    break_patterns2(&mut vec2);

    assert!(vec1 == vec2);
}