Как может больший объем кода выполняться быстрее, чем меньший? ⇐ JAVA

[Anonymous]

Я реализовал алгоритм DLX в Java 17. В дополнение к реализации, предоставляющей статистику выполнения, я хотел предоставить версию без статистики, чтобы сократить время выполнения. Я был удивлен, что версия без статистики выполняется значительно медленнее (8% на тестовой машине), чем версия со статистикой.
Я провел много тестов и свел проблему к двум различным версиям одиночный метод MatrixEntry.
Быстрая версия (первая строка — строка 77 в MatrixEntry.java):
int coverColumn() {
int updates = 1;
columnHead.right.left = columnHead.left;
columnHead.left.right = columnHead.right;
MatrixEntry i = columnHead.lower;
while (i != columnHead) {
MatrixEntry j = i.right;
while (j != i) {
updates++;
j.lower.upper = j.upper;
j.upper.lower = j.lower;
j.columnHead.rowCount--;
j = j.right;
}
i = i.lower;
}
return updates;
}

Медленная версия (первая строка — строка 77 в MatrixEntry.java):
void coverColumn() {
//int updates = 1;
columnHead.right.left = columnHead.left;
columnHead.left.right = columnHead.right;
MatrixEntry i = columnHead.lower;
while (i != columnHead) {
MatrixEntry j = i.right;
while (j != i) {
//updates++;
j.lower.upper = j.upper;
j.upper.lower = j.lower;
j.columnHead.rowCount--;
j = j.right;
}
i = i.lower;
}
//return updates;
}

Я также проверил байт-код с помощью javap -c MatrixEntry.class и не обнаружил никаких отличий, кроме ожидаемых дополнительных инструкций по созданию переменной в стеке, увеличению и верните его.
Чтобы обеспечить некоторый контекст кода: каждый доступ к полю представляет собой доступ к ссылке на объект другого экземпляра MatrixEntry, за исключением экземпляра rowCount. rowCount — целочисленное поле.
Я запускал тест на Linux-машине с бездействующим сервером Xeon E3-1220 v6 (на моем настольном компьютере результаты были менее стабильными). Метод Java вызывается более 309 357 294 раз, а внутренний цикл выполняется 100 722 885 573 раза за одно выполнение приложения. Я выполнил 4 запуска приложения со статистикой в ​​методе и без нее. Стандартное отклонение между запусками составляло около 4 секунд, при этом каждый запуск со статистикой занимал 22:19, а каждый запуск без статистики - 24:08 минут.
JVM представляет собой OpenJDK:
openjdk version "17.0.13" 2024-10-15
OpenJDK Runtime Environment Temurin-17.0.13+11 (build 17.0.13+11)
OpenJDK 64-Bit Server VM Temurin-17.0.13+11 (build 17.0.13+11, mixed mode, sharing)

Дополнительную информацию о реализации можно найти в репозитории GitHub, хотя я думаю, что эта контекстная информация не нужна.
Я' Я был очень озадачен результатами и попытался вернуть 0 вместо того, чтобы позволить методу вернуть void. Я даже создал версию, в которой счетчик обновлений увеличивается, но значение не сохраняется — эта версия была самой быстрой из всех (но я не позволял ей запускаться несколько раз).
Может кто-нибудь объяснит улучшенную производительность кода со встроенным счетчиком?

Байткод быстрой версии:
int coverColumn();
Code:
0: iconst_1
1: istore_1
2: aload_0
3: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
6: getfield #17 // Field right:Lde/famiru/dlx/MatrixEntry;
9: aload_0
10: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
13: getfield #13 // Field left:Lde/famiru/dlx/MatrixEntry;
16: putfield #13 // Field left:Lde/famiru/dlx/MatrixEntry;
19: aload_0
20: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
23: getfield #13 // Field left:Lde/famiru/dlx/MatrixEntry;
26: aload_0
27: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
30: getfield #17 // Field right:Lde/famiru/dlx/MatrixEntry;
33: putfield #17 // Field right:Lde/famiru/dlx/MatrixEntry;
36: aload_0
37: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
40: getfield #23 // Field lower:Lde/famiru/dlx/MatrixEntry;
43: astore_2
44: aload_2
45: aload_0
46: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
49: if_acmpeq 116
52: aload_2
53: getfield #17 // Field right:Lde/famiru/dlx/MatrixEntry;
56: astore_3
57: aload_3
58: aload_2
59: if_acmpeq 108
62: iinc 1, 1
65: aload_3
66: getfield #23 // Field lower:Lde/famiru/dlx/MatrixEntry;
69: aload_3
70: getfield #20 // Field upper:Lde/famiru/dlx/MatrixEntry;
73: putfield #20 // Field upper:Lde/famiru/dlx/MatrixEntry;
76: aload_3
77: getfield #20 // Field upper:Lde/famiru/dlx/MatrixEntry;
80: aload_3
81: getfield #23 // Field lower:Lde/famiru/dlx/MatrixEntry;
84: putfield #23 // Field lower:Lde/famiru/dlx/MatrixEntry;
87: aload_3
88: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
91: dup
92: getfield #7 // Field rowCount:I
95: iconst_1
96: isub
97: putfield #7 // Field rowCount:I
100: aload_3
101: getfield #17 // Field right:Lde/famiru/dlx/MatrixEntry;
104: astore_3
105: goto 57
108: aload_2
109: getfield #23 // Field lower:Lde/famiru/dlx/MatrixEntry;
112: astore_2
113: goto 44
116: iload_1
117: ireturn

Байткод более медленной версии:
void coverColumn();
Code:
0: aload_0
1: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
4: getfield #17 // Field right:Lde/famiru/dlx/MatrixEntry;
7: aload_0
8: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
11: getfield #13 // Field left:Lde/famiru/dlx/MatrixEntry;
14: putfield #13 // Field left:Lde/famiru/dlx/MatrixEntry;
17: aload_0
18: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
21: getfield #13 // Field left:Lde/famiru/dlx/MatrixEntry;
24: aload_0
25: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
28: getfield #17 // Field right:Lde/famiru/dlx/MatrixEntry;
31: putfield #17 // Field right:Lde/famiru/dlx/MatrixEntry;
34: aload_0
35: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
38: getfield #23 // Field lower:Lde/famiru/dlx/MatrixEntry;
41: astore_1
42: aload_1
43: aload_0
44: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
47: if_acmpeq 111
50: aload_1
51: getfield #17 // Field right:Lde/famiru/dlx/MatrixEntry;
54: astore_2
55: aload_2
56: aload_1
57: if_acmpeq 103
60: aload_2
61: getfield #23 // Field lower:Lde/famiru/dlx/MatrixEntry;
64: aload_2
65: getfield #20 // Field upper:Lde/famiru/dlx/MatrixEntry;
68: putfield #20 // Field upper:Lde/famiru/dlx/MatrixEntry;
71: aload_2
72: getfield #20 // Field upper:Lde/famiru/dlx/MatrixEntry;
75: aload_2
76: getfield #23 // Field lower:Lde/famiru/dlx/MatrixEntry;
79: putfield #23 // Field lower:Lde/famiru/dlx/MatrixEntry;
82: aload_2
83: getfield #26 // Field columnHead:Lde/famiru/dlx/MatrixEntry;
86: dup
87: getfield #7 // Field rowCount:I
90: iconst_1
91: isub
92: putfield #7 // Field rowCount:I
95: aload_2
96: getfield #17 // Field right:Lde/famiru/dlx/MatrixEntry;
99: astore_2
100: goto 55
103: aload_1
104: getfield #23 // Field lower:Lde/famiru/dlx/MatrixEntry;
107: astore_1
108: goto 42
111: return


Как предложено в комментариях, я позволил JVM распечатать сборку после компиляции C2, используя плагин hsdis и следующие флаги командной строки JVM: -XX: +UnlockDiagnosticVMOptions -XX:+DebugNonSafepoints -XX:PrintAssemblyOptions=intel -XX:CompileCommand=print,*MatrixEntry.coverColumn
Я попробовал извлечь только часть внутреннего цикла сборки , так как вся сборка довольно длинная.
Быстрый код, включая счетчик:
0x00007faf08f46705: mov r11,QWORD PTR [r15+0x350]
0x00007faf08f4670c: mov r8,QWORD PTR [rsp]
0x00007faf08f46710: mov r9d,DWORD PTR [r8+0x14] ;*getfield columnHead {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@46 (line 82)
0x00007faf08f46714: mov r13d,DWORD PTR [r13+0x24] ; ImmutableOopMap {r9=NarrowOop r13=NarrowOop [0]=Oop }
;*goto {reexecute=1 rethrow=0 return_oop=0}
; - (reexecute) de.famiru.dlx.MatrixEntry::coverColumn@113 (line 92)
0x00007faf08f46718: test DWORD PTR [r11],eax ;*goto {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@113 (line 92)
; {poll}
0x00007faf08f4671b: cmp r13d,r9d
0x00007faf08f4671e: je 0x00007faf08f46806 ;*aload_2 {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@52 (line 83)
0x00007faf08f46724: mov ebp,DWORD PTR [r13+0x1c] ; implicit exception: dispatches to 0x00007faf08f46b04
;*getfield right {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@53 (line 83)
0x00007faf08f46728: cmp ebp,r13d
0x00007faf08f4672b: je 0x00007faf08f46705 ;*if_acmpeq {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@59 (line 84)
0x00007faf08f4672d: mov r11,r13 ;*aload_2 {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@52 (line 83)
0x00007faf08f46730: mov QWORD PTR [rsp+0x8],r11
0x00007faf08f46735: data16 data16 nop WORD PTR [rax+rax*1+0x0]
;*iinc {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@62 (line 85)
0x00007faf08f46740: mov ebx,DWORD PTR [rbp+0x20] ; implicit exception: dispatches to 0x00007faf08f46aee
;*getfield upper {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@70 (line 86)
0x00007faf08f46743: mov r14d,DWORD PTR [rbp+0x24] ;*getfield lower {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@66 (line 86)
0x00007faf08f46747: test r14d,r14d
0x00007faf08f4674a: je 0x00007faf08f46a2c ;*putfield left {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@16 (line 79)
0x00007faf08f46750: cmp BYTE PTR [r15+0x38],0x0
0x00007faf08f46755: jne 0x00007faf08f4681c
0x00007faf08f4675b: mov DWORD PTR [r14+0x20],ebx
0x00007faf08f4675f: mov r11,r14
0x00007faf08f46762: mov r8,rbx
0x00007faf08f46765: xor r8,r11
0x00007faf08f46768: shr r8,0x14
0x00007faf08f4676c: test r8,r8
0x00007faf08f4676f: je 0x00007faf08f4678f
0x00007faf08f46771: test ebx,ebx
0x00007faf08f46773: je 0x00007faf08f4678f
0x00007faf08f46775: shr r11,0x9
0x00007faf08f46779: movabs rdi,0x7faf1bba1000
0x00007faf08f46783: add rdi,r11
0x00007faf08f46786: cmp BYTE PTR [rdi],0x4
0x00007faf08f46789: jne 0x00007faf08f46882 ;*putfield upper {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@73 (line 86)
0x00007faf08f4678f: mov ebx,DWORD PTR [rbp+0x20] ;*getfield upper {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@77 (line 87)
0x00007faf08f46792: test ebx,ebx
0x00007faf08f46794: je 0x00007faf08f46a38 ;*putfield left {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@16 (line 79)
0x00007faf08f4679a: cmp BYTE PTR [r15+0x38],0x0
0x00007faf08f4679f: jne 0x00007faf08f4684f
0x00007faf08f467a5: mov DWORD PTR [rbx+0x24],r14d
0x00007faf08f467a9: mov r11,r14
0x00007faf08f467ac: mov r8,rbx
0x00007faf08f467af: xor r11,r8
0x00007faf08f467b2: shr r11,0x14
0x00007faf08f467b6: test r11,r11
0x00007faf08f467b9: je 0x00007faf08f467da
0x00007faf08f467bb: test r14d,r14d
0x00007faf08f467be: je 0x00007faf08f467da
0x00007faf08f467c0: shr r8,0x9
0x00007faf08f467c4: movabs rdi,0x7faf1bba1000
0x00007faf08f467ce: add rdi,r8
0x00007faf08f467d1: cmp BYTE PTR [rdi],0x4
0x00007faf08f467d4: jne 0x00007faf08f468cb ;*putfield lower {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@84 (line 87)
0x00007faf08f467da: mov r11d,DWORD PTR [rbp+0x14] ;*getfield columnHead {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@88 (line 88)
0x00007faf08f467de: dec DWORD PTR [r11+0xc] ; implicit exception: dispatches to 0x00007faf08f46af8
;*putfield left {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@16 (line 79)
0x00007faf08f467e2: mov r11,QWORD PTR [r15+0x350]
0x00007faf08f467e9: mov ebp,DWORD PTR [rbp+0x1c] ;*getfield right {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@101 (line 89)
0x00007faf08f467ec: inc r10d ; ImmutableOopMap {rbp=NarrowOop r13=NarrowOop [0]=Oop [8]=Oop }
;*goto {reexecute=1 rethrow=0 return_oop=0}
; - (reexecute) de.famiru.dlx.MatrixEntry::coverColumn@105 (line 89)
0x00007faf08f467ef: test DWORD PTR [r11],eax ;*goto {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@105 (line 89)
; {poll}
0x00007faf08f467f2: cmp ebp,r13d
0x00007faf08f467f5: je 0x00007faf08f46705 ;*if_acmpeq {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@59 (line 84)

Медленный код возвращает void:
0x00007f0628f5c10c: mov r10,QWORD PTR [r15+0x350]
0x00007f0628f5c113: mov r11,QWORD PTR [rsp]
0x00007f0628f5c117: mov r11d,DWORD PTR [r11+0x14] ;*getfield columnHead {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@44 (line 82)
0x00007f0628f5c11b: mov r13d,DWORD PTR [r13+0x24] ; ImmutableOopMap {r11=NarrowOop r13=NarrowOop [0]=Oop }
;*goto {reexecute=1 rethrow=0 return_oop=0}
; - (reexecute) de.famiru.dlx.MatrixEntry::coverColumn@108 (line 92)
0x00007f0628f5c11f: test DWORD PTR [r10],eax ;*goto {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@108 (line 92)
; {poll}
0x00007f0628f5c122: cmp r13d,r11d
0x00007f0628f5c125: je 0x00007f0628f5c0f9 ;*aload_1 {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@50 (line 83)
0x00007f0628f5c127: mov ebp,DWORD PTR [r13+0x1c] ; implicit exception: dispatches to 0x00007f0628f5c49c
;*getfield right {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@51 (line 83)
0x00007f0628f5c12b: cmp ebp,r13d
0x00007f0628f5c12e: je 0x00007f0628f5c10c ;*if_acmpeq {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@57 (line 84)
0x00007f0628f5c130: mov r10,r13 ;*aload_1 {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@50 (line 83)
0x00007f0628f5c133: mov QWORD PTR [rsp+0x8],r10
0x00007f0628f5c138: nop DWORD PTR [rax+rax*1+0x0] ;*aload_2 {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@60 (line 86)
0x00007f0628f5c140: mov ebx,DWORD PTR [rbp+0x24] ; implicit exception: dispatches to 0x00007f0628f5c486
;*getfield lower {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@61 (line 86)
0x00007f0628f5c143: mov r14d,DWORD PTR [rbp+0x20] ;*getfield upper {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@65 (line 86)
0x00007f0628f5c147: test ebx,ebx
0x00007f0628f5c149: je 0x00007f0628f5c400 ;*putfield left {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@14 (line 79)
0x00007f0628f5c14f: cmp BYTE PTR [r15+0x38],0x0
0x00007f0628f5c154: jne 0x00007f0628f5c1fe
0x00007f0628f5c15a: mov DWORD PTR [rbx+0x20],r14d
0x00007f0628f5c15e: mov r10,rbx
0x00007f0628f5c161: mov r11,r14
0x00007f0628f5c164: xor r11,r10
0x00007f0628f5c167: shr r11,0x14
0x00007f0628f5c16b: test r11,r11
0x00007f0628f5c16e: je 0x00007f0628f5c18f
0x00007f0628f5c170: test r14d,r14d
0x00007f0628f5c173: je 0x00007f0628f5c18f
0x00007f0628f5c175: shr r10,0x9
0x00007f0628f5c179: movabs rdi,0x7f063c735000
0x00007f0628f5c183: add rdi,r10
0x00007f0628f5c186: cmp BYTE PTR [rdi],0x4
0x00007f0628f5c189: jne 0x00007f0628f5c264 ;*putfield upper {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@68 (line 86)
0x00007f0628f5c18f: mov r14d,DWORD PTR [rbp+0x20] ;*getfield upper {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@72 (line 87)
0x00007f0628f5c193: test r14d,r14d
0x00007f0628f5c196: je 0x00007f0628f5c410 ;*putfield left {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@14 (line 79)
0x00007f0628f5c19c: cmp BYTE PTR [r15+0x38],0x0
0x00007f0628f5c1a1: jne 0x00007f0628f5c231
0x00007f0628f5c1a7: mov DWORD PTR [r14+0x24],ebx
0x00007f0628f5c1ab: mov r10,rbx
0x00007f0628f5c1ae: mov r11,r14
0x00007f0628f5c1b1: xor r10,r11
0x00007f0628f5c1b4: shr r10,0x14
0x00007f0628f5c1b8: test r10,r10
0x00007f0628f5c1bb: je 0x00007f0628f5c1db
0x00007f0628f5c1bd: test ebx,ebx
0x00007f0628f5c1bf: je 0x00007f0628f5c1db
0x00007f0628f5c1c1: shr r11,0x9
0x00007f0628f5c1c5: movabs rdi,0x7f063c735000
0x00007f0628f5c1cf: add rdi,r11
0x00007f0628f5c1d2: cmp BYTE PTR [rdi],0x4
0x00007f0628f5c1d5: jne 0x00007f0628f5c2a6 ;*putfield lower {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@79 (line 87)
0x00007f0628f5c1db: mov r10d,DWORD PTR [rbp+0x14] ;*getfield columnHead {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@83 (line 88)
0x00007f0628f5c1df: dec DWORD PTR [r10+0xc] ; implicit exception: dispatches to 0x00007f0628f5c490
;*goto {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@100 (line 89)
0x00007f0628f5c1e3: mov ebp,DWORD PTR [rbp+0x1c] ;*putfield left {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@14 (line 79)
0x00007f0628f5c1e6: mov r10,QWORD PTR [r15+0x350] ; ImmutableOopMap {rbp=NarrowOop r13=NarrowOop [0]=Oop [8]=Oop }
;*goto {reexecute=1 rethrow=0 return_oop=0}
; - (reexecute) de.famiru.dlx.MatrixEntry::coverColumn@100 (line 89)
0x00007f0628f5c1ed: test DWORD PTR [r10],eax ;*goto {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@100 (line 89)
; {poll}
0x00007f0628f5c1f0: cmp ebp,r13d
0x00007f0628f5c1f3: je 0x00007f0628f5c10c ;*if_acmpeq {reexecute=0 rethrow=0 return_oop=0}
; - de.famiru.dlx.MatrixEntry::coverColumn@57 (line 84)


Подробнее здесь: https://stackoverflow.com/questions/791 ... ting-fewer