왜 (variable1 % variable2 == 0) 비효율적입니까? 재설정합니다. 편집 3.5 : 이 코드를 사용했고 아래에

나는 자바를 처음 접했고 어젯밤에 코드를 실행하고 있었고, 이것은 실제로 나를 귀찮게했다. 나는 for 루프에서 모든 X 출력을 표시하는 간단한 프로그램을 작성하고 있었고 모듈러스를 variable % variablevs variable % 5000또는 기타 로 사용했을 때 성능이 크게 떨어졌습니다 . 누군가 이것이 왜 이것이 원인인지 설명 할 수 있습니까? 그래서 나는 더 나아질 수 있습니다 …

여기에 “효율적인”코드가 있습니다 (구문이 틀리면 죄송합니다. 컴퓨터에 코드가 없습니다.)

long startNum = 0;
long stopNum = 1000000000L;

for (long i = startNum; i <= stopNum; i++){
    if (i % 50000 == 0) {
        System.out.println(i);
    }
}

다음은 “비효율적 인 코드”입니다

long startNum = 0;
long stopNum = 1000000000L;
long progressCheck = 50000;

for (long i = startNum; i <= stopNum; i++){
    if (i % progressCheck == 0) {
        System.out.println(i);
    }
}

차이를 측정하는 날짜 변수가 있었고 일단 충분히 길어지면 첫 번째는 50ms가 걸리고 다른 하나는 12 초 정도 걸렸습니다. PC가 내 것보다 효율적이거나 그렇지 않은 경우 를 늘리 stopNum거나 줄여야 할 수도 있습니다 progressCheck.

웹 에서이 질문을 찾았지만 답을 찾을 수 없습니다. 아마 대답하지 않을 수도 있습니다.

편집 : 내 질문이 그렇게 인기가 있다고 기대하지 않았습니다. 모든 답변을 주셔서 감사합니다. 나는 매 반마다 벤치 마크를 수행했으며 비효율적 인 코드는 1/4 초 대 10 초가 걸리거나 걸리는 시간이 상당히 길었습니다. 그들이 println을 사용하고 있지만 둘 다 같은 양을하고 있기 때문에, 특히 불일치가 반복 가능하기 때문에 그것이 많이 기울어 질 것이라고는 생각하지 않습니다. 답변은 Java를 처음 사용하기 때문에 투표가 지금 어떤 답변이 가장 적합한지를 결정하게 할 것입니다. 수요일까지 하나 골라 볼게요.

EDIT2 : 오늘 밤 또 다른 테스트를 할 것입니다. 여기서 모듈러스 대신 변수를 증가시키고 progressCheck에 도달하면 하나를 수행 한 다음 해당 변수를 0으로 재설정합니다.

편집 3.5 :

이 코드를 사용했고 아래에 결과를 보여 드리겠습니다. 훌륭한 도움을 주셔서 감사합니다! 또한 long의 짧은 값을 0과 비교하려고 시도했기 때문에 새로운 모든 검사는 “65536”번 반복되어 반복적으로 동일하게 발생합니다.

public class Main {


    public static void main(String[] args) {

        long startNum = 0;
        long stopNum = 1000000000L;
        long progressCheck = 65536;
        final long finalProgressCheck = 50000;
        long date;

        // using a fixed value
        date = System.currentTimeMillis();
        for (long i = startNum; i <= stopNum; i++) {
            if (i % 65536 == 0) {
                System.out.println(i);
            }
        }
        long final1 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        //using a variable
        for (long i = startNum; i <= stopNum; i++) {
            if (i % progressCheck == 0) {
                System.out.println(i);
            }
        }
        long final2 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();

        // using a final declared variable
        for (long i = startNum; i <= stopNum; i++) {
            if (i % finalProgressCheck == 0) {
                System.out.println(i);
            }
        }
        long final3 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        // using increments to determine progressCheck
        int increment = 0;
        for (long i = startNum; i <= stopNum; i++) {
            if (increment == 65536) {
                System.out.println(i);
                increment = 0;
            }
            increment++;

        }

        //using a short conversion
        long final4 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        for (long i = startNum; i <= stopNum; i++) {
            if ((short)i == 0) {
                System.out.println(i);
            }
        }
        long final5 = System.currentTimeMillis() - date;

                System.out.println(
                "\nfixed = " + final1 + " ms " + "\nvariable = " + final2 + " ms " + "\nfinal variable = " + final3 + " ms " + "\nincrement = " + final4 + " ms" + "\nShort Conversion = " + final5 + " ms");
    }
}

결과 :

  • 고정 = 874ms (일반적으로 약 1000ms이지만 2의 거듭 제곱으로 인해 더 빠름)
  • 변수 = 8590ms
  • 최종 변수 = 1944ms (50000 사용시 ~ 1000ms)
  • 증분 = 1904ms
  • 짧은 변환 = 679ms

분할이 부족하여 단기 전환이 “빠른”방식보다 23 % 빠릅니다. 이것은 흥미 롭습니다. 256 회마다 (또는 거기에 대해) 무언가를 보여 주거나 비교해야 할 경우,이를 수행하고

if ((byte)integer == 0) {'Perform progress check code here'}

FINAL INTERNALING NOTE, 65536 (정수는 아님)과 함께 “최종 선언 된 변수”에서 모듈러스를 사용하는 것은 고정 된 값보다 (느린) 속도의 절반입니다. 이전에는 거의 같은 속도로 벤치마킹했습니다.



답변

OSR (온 스택 교체) 스텁을 측정하고 있습니다.

OSR 스텁 은 메소드가 실행되는 동안 해석 모드에서 컴파일 된 코드로 실행을 전송하기 위해 특별히 고안된 특수 버전의 컴파일 된 메소드입니다.

OSR 스터브는 해석 된 프레임과 호환되는 프레임 레이아웃이 필요하기 때문에 일반적인 방법만큼 최적화되지 않습니다. 나는 이미 다음 답변에서 이것을 보여주었습니다 : 1 , 2 , 3 .

여기에서도 비슷한 일이 일어납니다. “비효율적 인 코드”가 긴 루프를 실행하는 동안이 메소드는 루프 내부에서 스택상의 대체를 위해 특별히 컴파일됩니다. 상태는 해석 된 프레임에서 OSR 컴파일 된 메소드로 전송되며이 상태에는 progressCheck로컬 변수가 포함됩니다 . 이 시점에서 JIT는 변수를 상수로 대체 할 수 없으므로 강도 감소 와 같은 특정 최적화를 적용 할 수 없습니다 .

특히 이것은 JIT가 정수 나누기곱셈으로 바꾸지 않음을 의미 합니다. ( 최적화 컴파일러의 asm 트릭에 대해 GCC가 정수 나누기를 구현하는 이유를 GCC가 왜 사용합니까? 를 참조하십시오. 최적화가 인라인 / 상수 전파 후 컴파일 타임 상수 인 경우 최적화가 활성화 된 경우 %표현식 의 정수 리터럴 gcc -O0은 OSR 스텁에서도 JITer에 의해 최적화되는 위치와 유사하게에 의해 최적화됩니다.)

그러나 동일한 방법을 여러 번 실행하는 경우 두 번째 및 후속 실행은 일반 (OSR이 아닌) 코드를 실행하며 이는 완전히 최적화되어 있습니다. 이론을 입증하기위한 벤치 마크는 다음과 같습니다 ( JMH 사용하여 벤치마킹 ).

@State(Scope.Benchmark)
public class Div {

    @Benchmark
    public void divConst(Blackhole blackhole) {
        long startNum = 0;
        long stopNum = 100000000L;

        for (long i = startNum; i <= stopNum; i++) {
            if (i % 50000 == 0) {
                blackhole.consume(i);
            }
        }
    }

    @Benchmark
    public void divVar(Blackhole blackhole) {
        long startNum = 0;
        long stopNum = 100000000L;
        long progressCheck = 50000;

        for (long i = startNum; i <= stopNum; i++) {
            if (i % progressCheck == 0) {
                blackhole.consume(i);
            }
        }
    }
}

그리고 결과 :

# Benchmark: bench.Div.divConst

# Run progress: 0,00% complete, ETA 00:00:16
# Fork: 1 of 1
# Warmup Iteration   1: 126,967 ms/op
# Warmup Iteration   2: 105,660 ms/op
# Warmup Iteration   3: 106,205 ms/op
Iteration   1: 105,620 ms/op
Iteration   2: 105,789 ms/op
Iteration   3: 105,915 ms/op
Iteration   4: 105,629 ms/op
Iteration   5: 105,632 ms/op


# Benchmark: bench.Div.divVar

# Run progress: 50,00% complete, ETA 00:00:09
# Fork: 1 of 1
# Warmup Iteration   1: 844,708 ms/op          <-- much slower!
# Warmup Iteration   2: 105,893 ms/op          <-- as fast as divConst
# Warmup Iteration   3: 105,601 ms/op
Iteration   1: 105,570 ms/op
Iteration   2: 105,475 ms/op
Iteration   3: 105,702 ms/op
Iteration   4: 105,535 ms/op
Iteration   5: 105,766 ms/op

divVar비효율적으로 컴파일 된 OSR 스텁으로 인해 첫 번째 반복 이 실제로 훨씬 느려집니다. 그러나 메소드가 처음부터 다시 실행되는 즉시 사용 가능한 모든 컴파일러 최적화를 활용하는 제한되지 않은 새 버전이 실행됩니다.


답변

@phuclv comment에 대한 후속 조치에서 JIT 1에 의해 생성 된 코드를 확인했으며 그 결과는 다음과 같습니다.

variable % 5000(상수 분할)

mov     rax,29f16b11c6d1e109h
imul    rbx
mov     r10,rbx
sar     r10,3fh
sar     rdx,0dh
sub     rdx,r10
imul    r10,rdx,0c350h    ; <-- imul
mov     r11,rbx
sub     r11,r10
test    r11,r11
jne     1d707ad14a0h

에 대한 variable % variable:

mov     rax,r14
mov     rdx,8000000000000000h
cmp     rax,rdx
jne     22ccce218edh
xor     edx,edx
cmp     rbx,0ffffffffffffffffh
je      22ccce218f2h
cqo
idiv    rax,rbx           ; <-- idiv
test    rdx,rdx
jne     22ccce218c0h

나누기는 항상 곱셈보다 시간이 오래 걸리므로 마지막 코드 조각은 성능이 떨어집니다.

자바 버전 :

java version "11" 2018-09-25
Java(TM) SE Runtime Environment 18.9 (build 11+28)
Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11+28, mixed mode)

1-사용 된 VM 옵션 : -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,src/java/Main.main


답변

다른 사람들이 지적했듯이, 일반적인 계수 연산은 분할이 필요합니다. 경우에 따라 나누기가 (컴파일러에 의해) 곱셈으로 대체 될 수 있습니다. 그러나 더하기 / 빼기에 비해 둘 다 느릴 수 있습니다. 따라서 다음 라인을 따라 최상의 성능을 기대할 수 있습니다.

long progressCheck = 50000;

long counter = progressCheck;

for (long i = startNum; i <= stopNum; i++){
    if (--counter == 0) {
        System.out.println(i);
        counter = progressCheck;
    }
}

(사소한 옵티 미 제이션 시도로서 여기에서 사전 감소 다운 카운터를 사용합니다. 많은 아키텍처 0에서 산술 연산 직후에 비교하는 많은 아키텍처 에서 ALU의 플래그가 선행 작업에 의해 이미 적절하게 설정되어 있기 때문에 정확히 0 명령어 / CPU 사이클을 소비하기 때문입니다. 그러나 컴파일러는을 쓰더라도 자동으로 최적화를 수행합니다 if (counter++ == 50000) { ... counter = 0; }.)

루프 카운터 ( i) 또는 1 만 증가한 것을 알고 있기 때문에 모듈러스 가 실제로 필요하지 않습니다. 1 씩 증가하는 카운터가 일부 값에 도달하면

또 다른 ‘트릭’은 2의 제곱 값 / 제한을 사용하는 것 progressCheck = 1024;입니다. 2의 거듭 제곱은 비트 단위 and, 즉 비트 단위로 빠르게 계산할 수 있습니다 if ( (i & (1024-1)) == 0 ) {...}. 이것은 매우 빠르며 일부 아키텍처에서는 counter위 의 명시 적 성능을 능가 할 수 있습니다 .


답변

또한 위 코드의 성능을보고 놀랐습니다. 선언 된 변수에 따라 프로그램을 실행하는 데 컴파일러가 걸리는 시간이 전부입니다. 두 번째 (비효율적 인) 예에서 :

for (long i = startNum; i <= stopNum; i++) {
    if (i % progressCheck == 0) {
        System.out.println(i)
    }
}

두 변수 사이에서 계수 연산을 수행하고 있습니다. 여기에서, 컴파일러는 다음의 값을 확인해야 stopNum하고 progressCheck그것이 변수와 그 값이 변화 될 수 있으므로 각각의 반복 후 이러한 변수마다있는 특정 메모리 블록으로 이동.

이것이 각 반복 컴파일러가 변수의 최신 값을 확인하기 위해 메모리 위치로 이동 한 이유입니다. 따라서 컴파일 타임에 컴파일러는 효율적인 바이트 코드를 만들 수 없었습니다.

첫 번째 코드 예제에서는 변수와 상수 숫자 값 사이에서 모듈러스 연산자를 실행하여 실행 중에 변경되지 않으며 컴파일러는 메모리 위치에서 해당 숫자 값의 값을 확인할 필요가 없습니다. 이것이 컴파일러가 효율적인 바이트 코드를 만들 수 있었던 이유입니다. 당신은 선언하면 progressCheckA와 final또는으로 final static다음이 최종 변수이고 그 값은 대체 컴파일러 후 변경하지 않을 것을 실행시 / 컴파일시 컴파일러 노하우시 변수 progressCheck50000코드 :

for (long i = startNum; i <= stopNum; i++) {
    if (i % 50000== 0) {
        System.out.println(i)
    }
}

이제이 코드도 첫 번째 (효율적인) 코드 예제처럼 보입니다. 첫 번째 코드의 성능과 위에서 언급 한 것처럼 두 코드 모두 효율적으로 작동합니다. 두 코드 예제의 실행 시간에는 큰 차이가 없습니다.


답변