java - Java中的快速整数除法

Question

众所周知，整数除法运算速度很慢(通常比整数乘法慢几倍)。但是，如果需要使用固定除数执行多次除法运算，则可以对除数进行一些预处理，并用乘法和位运算替换“/”(Hacker's Delight 中的第 10 章)。

正如我所测试的，如果除数是编译时常量(例如 static final long DIVISOR = 12345L;)，JVM 将完成此任务并用 DIVISOR 替换所有除法 具有乘法和位运算。我对同样的技巧很感兴趣，但是当除数仅在运行时已知时。

例如，以下(慢)方法:

void reduceArraySlow(long[] data, long denominator){
    for(int i = 0; i < data.length; ++i)
        data[i] = data[i] / denominator;
}

可以替换为:

void reduceArrayFast(long[] data, long denominator){
    SomeMagicStructure magic = computeMagic(denominator);
    for(int i = 0; i < data.length; ++i)
         // computes data[i] / denominator
        data[i] = doFastDivision(data[i], magic);
}

它必须更快地完成这项工作，因为所有 / 操作都被更快的操作所取代(而且还因为除法在 CPU 中不是管道化的)。

Answer 1

有众所周知的C/C++ libdivide用于快速整数除法的库，我对此库进行了针对 Java 的改编 libdivide4j .

使用 libdivide4j 进行快速除法如下所示:

void reduceArrayFast(long[] data, long denominator){
    FastDivision.Magic magic = FastDivision.magicSigned(denominator);
    for(int i = 0; i < data.length; ++i)
        // computes data[i] / denominator
        data[i] = FastDivision.divideSignedFast(data[i], magic);
}

一个简单的基准

public void benchmark() throws Exception {
    Random rnd = new Random();
    int nIterations = 10000;
    //let the JIT to optimize something
    for (int att = 0; att < nIterations; att++) {
        long[] data = new long[1000];
        for (int i = 0; i < data.length; i++)
            data[i] = rnd.nextLong();

        long denominator = rnd.nextLong();

        long[] slow = data.clone();
        long start = System.nanoTime();
        reduceArraySlow(slow, denominator);
        long slowTime = System.nanoTime() - start;


        long[] fast = data.clone();
        start = System.nanoTime();
        reduceArrayFast(fast, denominator);
        long fastTime = System.nanoTime() - start;

        Assert.assertArrayEquals(slow, fast);

        // print last 100 timings (JVM already warmed up)
        if (att > nIterations - 100) {
            System.out.println("\"/\" operation: " + slowTime);
            System.out.println("Fast division: " + fastTime);
            System.out.println("");
        }
    }
}

显示普通 / 和快速除法(Core i7、jdk8 64 位)的以下计时(纳秒):

"/" operation: 13233
Fast division: 5957

"/" operation: 13148
Fast division: 5103

"/" operation: 13587
Fast division: 6188

"/" operation: 14173
Fast division: 6773
...