728x90
반응형
질문 : Java에서 2 * (i * i)가 2 * i * i보다 빠른 이유는 무엇입니까?
다음 Java 프로그램은 실행하는 데 평균 0.50 초에서 0.55 초가 걸립니다.
public static void main(String[] args) {
long startTime = System.nanoTime();
int n = 0;
for (int i = 0; i < 1000000000; i++) {
n += 2 * (i * i);
}
System.out.println((double) (System.nanoTime() - startTime) / 1000000000 + " s");
System.out.println("n = " + n);
}2 * (i * i) 를 2 * i * i 바꾸면 실행하는 데 0.60 초에서 0.65 초가 걸립니다. 어째서?
프로그램의 각 버전을 15 번씩 번갈아 실행했습니다. 결과는 다음과 같습니다.
2*(i*i) | 2*i*i
----------+----------
0.5183738 | 0.6246434
0.5298337 | 0.6049722
0.5308647 | 0.6603363
0.5133458 | 0.6243328
0.5003011 | 0.6541802
0.5366181 | 0.6312638
0.515149 | 0.6241105
0.5237389 | 0.627815
0.5249942 | 0.6114252
0.5641624 | 0.6781033
0.538412 | 0.6393969
0.5466744 | 0.6608845
0.531159 | 0.6201077
0.5048032 | 0.6511559
0.5232789 | 0.65445262 * i * i 의 가장 빠른 실행은 2 * (i * i) 의 가장 느린 실행보다 오래 걸렸습니다. 효율성이 같으면 이러한 일이 발생할 확률은 1/2^15 * 100% = 0.00305% 입니다.
답변
바이트 코드의 순서에 약간의 차이가 있습니다.
2 * (i * i) :
iconst_2
iload0
iload0
imul
imul
iadd대 2 * i * i :
iconst_2
iload0
imul
iload0
imul
iadd첫눈에 이것은 차이를 만들지 않아야합니다. 두 번째 버전이 하나의 슬롯을 덜 사용하기 때문에 더 최적입니다.
따라서 우리는 하위 수준 (JIT) 1을 더 깊이 파헤쳐 야합니다.
JIT는 작은 루프를 매우 공격적으로 펼치는 경향이 있음을 기억하십시오. 2 * (i * i) 경우에 대해 16x 풀림을 관찰합니다.
030 B2: # B2 B3 <- B1 B2 Loop: B2-B2 inner main of N18 Freq: 1e+006
030 addl R11, RBP # int
033 movl RBP, R13 # spill
036 addl RBP, #14 # int
039 imull RBP, RBP # int
03c movl R9, R13 # spill
03f addl R9, #13 # int
043 imull R9, R9 # int
047 sall RBP, #1
049 sall R9, #1
04c movl R8, R13 # spill
04f addl R8, #15 # int
053 movl R10, R8 # spill
056 movdl XMM1, R8 # spill
05b imull R10, R8 # int
05f movl R8, R13 # spill
062 addl R8, #12 # int
066 imull R8, R8 # int
06a sall R10, #1
06d movl [rsp + #32], R10 # spill
072 sall R8, #1
075 movl RBX, R13 # spill
078 addl RBX, #11 # int
07b imull RBX, RBX # int
07e movl RCX, R13 # spill
081 addl RCX, #10 # int
084 imull RCX, RCX # int
087 sall RBX, #1
089 sall RCX, #1
08b movl RDX, R13 # spill
08e addl RDX, #8 # int
091 imull RDX, RDX # int
094 movl RDI, R13 # spill
097 addl RDI, #7 # int
09a imull RDI, RDI # int
09d sall RDX, #1
09f sall RDI, #1
0a1 movl RAX, R13 # spill
0a4 addl RAX, #6 # int
0a7 imull RAX, RAX # int
0aa movl RSI, R13 # spill
0ad addl RSI, #4 # int
0b0 imull RSI, RSI # int
0b3 sall RAX, #1
0b5 sall RSI, #1
0b7 movl R10, R13 # spill
0ba addl R10, #2 # int
0be imull R10, R10 # int
0c2 movl R14, R13 # spill
0c5 incl R14 # int
0c8 imull R14, R14 # int
0cc sall R10, #1
0cf sall R14, #1
0d2 addl R14, R11 # int
0d5 addl R14, R10 # int
0d8 movl R10, R13 # spill
0db addl R10, #3 # int
0df imull R10, R10 # int
0e3 movl R11, R13 # spill
0e6 addl R11, #5 # int
0ea imull R11, R11 # int
0ee sall R10, #1
0f1 addl R10, R14 # int
0f4 addl R10, RSI # int
0f7 sall R11, #1
0fa addl R11, R10 # int
0fd addl R11, RAX # int
100 addl R11, RDI # int
103 addl R11, RDX # int
106 movl R10, R13 # spill
109 addl R10, #9 # int
10d imull R10, R10 # int
111 sall R10, #1
114 addl R10, R11 # int
117 addl R10, RCX # int
11a addl R10, RBX # int
11d addl R10, R8 # int
120 addl R9, R10 # int
123 addl RBP, R9 # int
126 addl RBP, [RSP + #32 (32-bit)] # int
12a addl R13, #16 # int
12e movl R11, R13 # spill
131 imull R11, R13 # int
135 sall R11, #1
138 cmpl R13, #999999985
13f jl B2 # loop end P=1.000000 C=6554623.000000스택에 "흘린"레지스터가 1 개 있음을 알 수 있습니다.
반응형
2 * i * i 버전의 경우 :
05a B3: # B2 B4 <- B1 B2 Loop: B3-B2 inner main of N18 Freq: 1e+006
05a addl RBX, R11 # int
05d movl [rsp + #32], RBX # spill
061 movl R11, R8 # spill
064 addl R11, #15 # int
068 movl [rsp + #36], R11 # spill
06d movl R11, R8 # spill
070 addl R11, #14 # int
074 movl R10, R9 # spill
077 addl R10, #16 # int
07b movdl XMM2, R10 # spill
080 movl RCX, R9 # spill
083 addl RCX, #14 # int
086 movdl XMM1, RCX # spill
08a movl R10, R9 # spill
08d addl R10, #12 # int
091 movdl XMM4, R10 # spill
096 movl RCX, R9 # spill
099 addl RCX, #10 # int
09c movdl XMM6, RCX # spill
0a0 movl RBX, R9 # spill
0a3 addl RBX, #8 # int
0a6 movl RCX, R9 # spill
0a9 addl RCX, #6 # int
0ac movl RDX, R9 # spill
0af addl RDX, #4 # int
0b2 addl R9, #2 # int
0b6 movl R10, R14 # spill
0b9 addl R10, #22 # int
0bd movdl XMM3, R10 # spill
0c2 movl RDI, R14 # spill
0c5 addl RDI, #20 # int
0c8 movl RAX, R14 # spill
0cb addl RAX, #32 # int
0ce movl RSI, R14 # spill
0d1 addl RSI, #18 # int
0d4 movl R13, R14 # spill
0d7 addl R13, #24 # int
0db movl R10, R14 # spill
0de addl R10, #26 # int
0e2 movl [rsp + #40], R10 # spill
0e7 movl RBP, R14 # spill
0ea addl RBP, #28 # int
0ed imull RBP, R11 # int
0f1 addl R14, #30 # int
0f5 imull R14, [RSP + #36 (32-bit)] # int
0fb movl R10, R8 # spill
0fe addl R10, #11 # int
102 movdl R11, XMM3 # spill
107 imull R11, R10 # int
10b movl [rsp + #44], R11 # spill
110 movl R10, R8 # spill
113 addl R10, #10 # int
117 imull RDI, R10 # int
11b movl R11, R8 # spill
11e addl R11, #8 # int
122 movdl R10, XMM2 # spill
127 imull R10, R11 # int
12b movl [rsp + #48], R10 # spill
130 movl R10, R8 # spill
133 addl R10, #7 # int
137 movdl R11, XMM1 # spill
13c imull R11, R10 # int
140 movl [rsp + #52], R11 # spill
145 movl R11, R8 # spill
148 addl R11, #6 # int
14c movdl R10, XMM4 # spill
151 imull R10, R11 # int
155 movl [rsp + #56], R10 # spill
15a movl R10, R8 # spill
15d addl R10, #5 # int
161 movdl R11, XMM6 # spill
166 imull R11, R10 # int
16a movl [rsp + #60], R11 # spill
16f movl R11, R8 # spill
172 addl R11, #4 # int
176 imull RBX, R11 # int
17a movl R11, R8 # spill
17d addl R11, #3 # int
181 imull RCX, R11 # int
185 movl R10, R8 # spill
188 addl R10, #2 # int
18c imull RDX, R10 # int
190 movl R11, R8 # spill
193 incl R11 # int
196 imull R9, R11 # int
19a addl R9, [RSP + #32 (32-bit)] # int
19f addl R9, RDX # int
1a2 addl R9, RCX # int
1a5 addl R9, RBX # int
1a8 addl R9, [RSP + #60 (32-bit)] # int
1ad addl R9, [RSP + #56 (32-bit)] # int
1b2 addl R9, [RSP + #52 (32-bit)] # int
1b7 addl R9, [RSP + #48 (32-bit)] # int
1bc movl R10, R8 # spill
1bf addl R10, #9 # int
1c3 imull R10, RSI # int
1c7 addl R10, R9 # int
1ca addl R10, RDI # int
1cd addl R10, [RSP + #44 (32-bit)] # int
1d2 movl R11, R8 # spill
1d5 addl R11, #12 # int
1d9 imull R13, R11 # int
1dd addl R13, R10 # int
1e0 movl R10, R8 # spill
1e3 addl R10, #13 # int
1e7 imull R10, [RSP + #40 (32-bit)] # int
1ed addl R10, R13 # int
1f0 addl RBP, R10 # int
1f3 addl R14, RBP # int
1f6 movl R10, R8 # spill
1f9 addl R10, #16 # int
1fd cmpl R10, #999999985
204 jl B2 # loop end P=1.000000 C=7419903.000000여기서 우리는 보존해야 할 더 많은 중간 결과로 인해 훨씬 더 많은 "유출"과 스택 [RSP + ...]
따라서 질문에 대한 대답은 간단합니다. JIT가 첫 번째 경우에 더 최적의 어셈블리 코드를 생성하기 때문에 2 * (i * i) 2 * i * i 보다 빠릅니다.
그러나 물론 첫 번째 버전도 두 번째 버전도 좋지 않다는 것은 분명합니다. x86-64 CPU는 최소한 SSE2를 지원하기 때문에 루프는 벡터화의 이점을 얻을 수 있습니다.
그래서 이것은 옵티마이 저의 문제입니다. 종종 그렇듯이 너무 공격적으로 펴서 발을 쏘는 동시에 다양한 다른 기회를 놓치게됩니다.
실제로 최신 x86-64 CPU는 명령어를 마이크로 연산 (µop)으로 더 세분화하고 레지스터 이름 변경, µop 캐시 및 루프 버퍼와 같은 기능을 사용하여 루프 최적화는 최적의 성능을 위해 간단한 풀기보다 훨씬 더 세밀합니다. Agner Fog의 최적화 가이드에 따르면 :
평균 명령어 길이가 4 바이트 이상인 경우 µop 캐시로 인한 성능 향상은 상당히 클 수 있습니다. µop 캐시 사용을 최적화하는 다음 방법을 고려할 수 있습니다.
- 중요 루프가 µop 캐시에 들어갈만큼 충분히 작은 지 확인하십시오.
- 가장 중요한 루프 항목과 기능 항목을 32로 정렬합니다.
- 불필요한 루프 풀기를 피하십시오.
- 추가로드 시간이있는 지침을 피하십시오.
. . .
이러한로드 시간과 관련하여- 가장 빠른 L1D 적중도 4주기 , 추가 레지스터 및 µop 비용이 들기 때문에 메모리에 몇 번 액세스해도 타이트 루프에서 성능이 저하됩니다.
그러나 벡터화 기회로 돌아가서, 얼마나 빠른지 확인하기 위해 GCC로 유사한 C 애플리케이션을 컴파일 할 수 있습니다 . 이는이를 완전히 벡터화합니다 (AVX2가 표시되고 SSE2가 유사 함) 2 :
vmovdqa ymm0, YMMWORD PTR .LC0[rip]
vmovdqa ymm3, YMMWORD PTR .LC1[rip]
xor eax, eax
vpxor xmm2, xmm2, xmm2
.L2:
vpmulld ymm1, ymm0, ymm0
inc eax
vpaddd ymm0, ymm0, ymm3
vpslld ymm1, ymm1, 1
vpaddd ymm2, ymm2, ymm1
cmp eax, 125000000 ; 8 calculations per iteration
jne .L2
vmovdqa xmm0, xmm2
vextracti128 xmm2, ymm2, 1
vpaddd xmm2, xmm0, xmm2
vpsrldq xmm0, xmm2, 8
vpaddd xmm0, xmm2, xmm0
vpsrldq xmm1, xmm0, 4
vpaddd xmm0, xmm0, xmm1
vmovd eax, xmm0
vzeroupper실행 시간 :
- SSE : 0.24 초 또는 2 배 빠름.
- AVX : 0.15 초 또는 3 배 빠름.
- AVX2 : 0.08 초 또는 5 배 빠름.
1 JIT 생성 어셈블리 출력을 얻으려면 디버그 JVM을 -XX:+PrintOptoAssembly 실행하십시오.
2 C 버전은 -fwrapv 플래그로 컴파일되어 GCC에서 부호있는 정수 오버플로를 2의 보수 순환으로 처리 할 수 있습니다.
출처 : https://stackoverflow.com/questions/53452713/why-is-2-i-i-faster-than-2-i-i-in-java
728x90
반응형
'프로그래밍 언어 > JAVA' 카테고리의 다른 글
| Java를 사용하여 줄 단위로 큰 텍스트 파일을 읽는 방법 (0) | 2021.08.03 |
|---|---|
| Java에서 싱글 톤 패턴을 구현하는 효율적인 방법 (0) | 2021.07.30 |
| Java에서 YYYY-MM-DD HH : MI : Sec.Millisecond 형식으로 현재 시간을 얻는 방법 (0) | 2021.07.28 |
| Java 문자열에서 날짜 형식 변경 (0) | 2021.07.19 |
| Java에서 .NET의 NotImplementedException과 같은 것 (0) | 2021.07.16 |