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と

ファスト分割が見える：

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(""); 
     } 
    } 
} 

は/通常かつ迅速分割に対して次のタイミング（ナノ秒）（コアI7を示す簡単なベンチマークは、64ビットをjdk8

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); 
} 

）：

"/" operation: 13233 
Fast division: 5957 

"/" operation: 13148 
Fast division: 5103 

"/" operation: 13587 
Fast division: 6188 

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