Crate fastdivide

Yes, but what is it really ?

Division is a very costly operation for your CPU (probably between 10 and 40 cycles).

You may have noticed that when the divisor is known at compile time, your compiler transforms the operations into a cryptic combination of a multiplication and bitshift.

Fastdivide is about doing the same trick your compiler uses but when the divisor is unknown at compile time. Of course, it requires preprocessing a datastructure that is specific to your divisor, and using it only makes sense if this preprocessing is amortized by a high number of division (with the same divisor).

When is it useful ?

You should probably use fastdivide, if you do a lot (> 10) of division with the same divisor ; and these divisions are a bottleneck in your program.

This is for instance useful to compute histograms.

Example

use fastdivide::DividerU64;

fn histogram(vals: &[u64], min: u64, interval: u64, output: &mut [usize]) {

    // Preprocessing a datastructure dedicated
    // to dividing `u64` by `interval`.
    //
    // This preprocessing is not cheap.
    let divide = DividerU64::divide_by(interval);

    // We reuse the same `Divider` for all of the
    // values in vals.
    for &val in vals {
        if val < min {
            continue;
        }
        let bucket_id = divide.divide(val - min) as usize;
        if bucket_id < output.len() {
            output[bucket_id as usize] += 1;
        }
    }
}

Structs

DividerU64