Java에서의 빠른 정수 나누기

Question

정수 나누기가 느린 작업 (일반적으로 정수 곱하기보다 몇 배 느리다)은 잘 알려져 있습니다. 그러나 고정 제수로 여러 나누기 연산을 수행해야하는 경우 제수를 미리 조정하고 곱셈 및 비트 연산으로 "/"를 대체 할 수 있습니다 (Hacker's Delight의 10 장).

제물이 컴파일 타임 상수 (예 : static final long DIVISOR = 12345L;) 인 경우 JVM에서 모든 작업을 곱셈 및 비트 연산으로 DIVISOR으로 대체합니다. 저는 같은 종류의 속임수에서 흥미 롭습니다 만, 제수가 런타임에만 알려질 때. 예를 들어

, 다음 (느린) 방법 : 훨씬 빠르게 작업을 수행해야합니다

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

, 모든 / 작업을 빠르게 대체하고 있기 때문에 :

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

뭔가로 대체 할 수 (또한 분할이 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 
...