Performance testing for fast integer division (multiplicative inverses)

julia benchmark

if VERSION < v"0.5.0-dev"
    include("/home/tim/julia/MultiplicativeInverses.jl")
    using MultiplicativeInverses
else
    using Base.MultiplicativeInverses
end

@noinline function sum_of_quotients(v, d)
    result = 0
    for i = 1:length(v)
        @inbounds result += v[i] ÷ d
    end
    result
end

n = 10^7
d = 3
numers = collect(0:n-1)
fast_d = multiplicativeinverse(d)
short = collect(0:3)
sum_of_quotients(short, d)
sum_of_quotients(short, fast_d)

@time 1
@time result = sum_of_quotients(numers, d)
@time result_fast = sum_of_quotients(numers, fast_d)
result == result_fast || error("disagree")
@show result

libdivide benchmark

#include <iostream>
#include <inttypes.h>
#include "libdivide.h"
#include <sys/time.h> //for gettimeofday()

#define NANOSEC_PER_SEC 1000000000ULL
#define NANOSEC_PER_USEC 1000ULL
#define NANOSEC_PER_MILLISEC 1000000ULL

static uint64_t nanoseconds(void) {
    struct timeval now;
    gettimeofday(&now, NULL);
    return now.tv_sec * NANOSEC_PER_SEC + now.tv_usec * NANOSEC_PER_USEC;
}


int64_t __attribute__ ((noinline)) sum_of_quotients(const int64_t *numers, int count, libdivide::divider<int64_t> fast_d) {
    int64_t result = 0;
    for (int i=0; i < count; i++) {
        result += numers[i] / fast_d; //uses faster libdivide division
    }
    return result;
}

int main() {
    int n = 10000000;
    int64_t *numers = new int64_t[n];
    for (int i = 0; i < n; i++)
        numers[i] = i;
    int64_t d = 3;
    libdivide::divider<int64_t> fast_d(d); //constructs an instance of libdivide::divider
    uint64_t start = nanoseconds();
    int64_t ans = sum_of_quotients(numers, n, fast_d);
    uint64_t end = nanoseconds();
    uint64_t diff = end - start;
    std::cout << "answer: " << ans << std::endl;
    std::cout << "d = " << d << ", n = " << n << ", time (ms) = " << double(diff)/1000000 << std::endl;
}