Crate fastdivide

Yes, but what is it really ?

Division is a very costly operation for your CPU. 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 ?

If you do a lot (> 10) of division with the same divisor ; and this division is 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