Rust In-Place Shuffle (rip_shuffle)

This crate contains several efficient in-place shuffling algorithms to generate random permutations. Their design and performances is analyzed in detail in the paper "Engineering Shared-Memory Parallel Shuffling to Generate Random Permutations In-Place" [M. Penschuck].

At time of writing, the default sequential implementation is 1.5 to 4 times faster than rand::shuffling. The parallel implementation can get several orders of magnitute faster. All implementations are in-place and do not use heap allocations (though, the parallel algorithms may set up a Rayon worker pool, if it's not already the case).

Usage

Include the following into your Cargo.toml file:

[dependencies]
rip_shuffle={version="0.2"}

For general use cases, we export the two traits [RipShuffleSequential] and [RipShuffleParallel] which expose the functions seq_shuffle and par_shuffle, respectively. The sequential variant seq_shuffle can be used as a drop-in replacement for rand::shuffle:

use rip_shuffle::RipShuffleSequential;
let mut data : Vec<_> = (0..100).into_iter().collect();

data.seq_shuffle(&mut rand::thread_rng());

The parallel variant imposes some constraints on the random number generator: it needs to be a [rand::SeedableRng] and support [std::marker::Send] and [std::marker::Sync]. Most prominently, this is not the case for [rand::rngs::ThreadRng]. However, you can seed a compatible instace (e.g., [rand::rngs::StdRng] or [rand_pcg::Pcg64]) from [rand::rngs::ThreadRng] and then pass them:

use rip_shuffle::RipShuffleParallel;
use rand::prelude::*;

let mut data : Vec<_> = (0..1_000_000).into_iter().collect();

let mut rng = StdRng::from_rng(thread_rng()).unwrap();
data.par_shuffle(&mut rng);

As a short-hand you can use RipShuffleParallel::par_shuffle_seed_with. This methods supports arbitrary Rngs to seed a Pcg64Mcg from them:

use rip_shuffle::RipShuffleParallel;
let mut data : Vec<_> = (0..1_000_000).into_iter().collect();

data.par_shuffle_seed_with(&mut rand::thread_rng());

Features

This crate has two default feature sets which should be appropriate for most cases and do not change the API.

• default is supposed to work with all recent rust compilers
• nightly_default requires nightly features but may yield slightly faster binaries. If you are using a non-stable compiler consider enabling this feature.

This crate supports the following features:

• unsafe_algos (enabled by default) this feature enables algorithms that rely on pointer arithmetic, but are faster than their safe variants

• seed_with (enabled by default) adds a dependency to [rand_pcg] and offers the [RipShuffleParallel::par_shuffle_seed_with] short-hand.

• prefetch (enabled by nightly_default) enables explicit prefetching via [std::intrinsics::prefetch_write_data] to speed-up shuffling. This feature does require a nightly-channel compiler.

To disable these feature, you can adopt the dependency in your Cargo.toml, for instace:

rip_shuffle={version="0.2", default-features = false, features = ["seed_with"]}