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

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

Ответить Пред. тема След. тема

1 сообщение • Страница 1 из 1

Anonymous

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

Цитата

Сообщение Anonymous » 31 окт 2024, 18:29

Я реализовал алгоритм 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)

Код: Выделить всё

perf stat -d -d -d bin/app

отчет для быстрой версии:

Код: Выделить всё

         944020.43 msec task-clock                       #    1.002 CPUs utilized
34131      context-switches                 #   36.155 /sec
3772      cpu-migrations                   #    3.996 /sec
26375      page-faults                      #   27.939 /sec
3073656028927      cycles                           #    3.256 GHz                      (61.54%)
8314592091084      instructions                     #    2.71  insn per cycle           (69.23%)
1617667532435      branches                         #    1.714 G/sec                    (69.23%)
7376429842      branch-misses                    #    0.46% of all branches          (69.23%)
2518602003849      L1-dcache-loads                  #    2.668 G/sec                    (69.23%)
217124852119      L1-dcache-load-misses            #    8.62% of all L1-dcache accesses  (69.23%)
8360116079      LLC-loads                        #    8.856 M/sec                    (69.23%)
36950592      LLC-load-misses                  #    0.44% of all LL-cache accesses  (69.24%)
       L1-icache-loads
613369051      L1-icache-load-misses                                                (69.23%)
2518014639585      dTLB-loads                       #    2.667 G/sec                    (69.24%)
2964075      dTLB-load-misses                 #    0.00% of all dTLB cache accesses  (61.54%)
4335821      iTLB-loads                       #    4.593 K/sec                    (61.54%)
1578713      iTLB-load-misses                 #   36.41% of all iTLB cache accesses  (61.54%)

и для медленной версии:

Код: Выделить всё

        1011635.24 msec task-clock                       #    1.001 CPUs utilized
37371      context-switches                 #   36.941 /sec
1949      cpu-migrations                   #    1.927 /sec
26087      page-faults                      #   25.787 /sec
3277438029589      cycles                           #    3.240 GHz                      (61.54%)
9156368782029      instructions                     #    2.79  insn per cycle           (69.23%)
1614775762524      branches                         #    1.596 G/sec                    (69.23%)
7360324323      branch-misses                    #    0.46% of all branches          (69.23%)
2914029260930      L1-dcache-loads                  #    2.881 G/sec                    (69.23%)
216220083510      L1-dcache-load-misses            #    7.42% of all L1-dcache accesses  (69.23%)
8079066223      LLC-loads                        #    7.986 M/sec                    (69.23%)
47018889      LLC-load-misses                  #    0.58% of all LL-cache accesses  (69.23%)
      L1-icache-loads
650941335      L1-icache-load-misses                                                (69.23%)
2913664329244      dTLB-loads                       #    2.880 G/sec                    (69.23%)
2913507      dTLB-load-misses                 #    0.00% of all dTLB cache accesses  (61.54%)
4294995      iTLB-loads                       #    4.246 K/sec                    (61.54%)
1796205      iTLB-load-misses                 #   41.82% of all iTLB cache accesses  (61.54%)

Промахи при переходе составляют всего 0,46 % (в обоих случаях), но статистика производительности выделяет промахи при загрузке iTLB, что составляет 36 % против 42 %.

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

Реклама

1730388558

Anonymous

Я реализовал алгоритм DLX в Java 17. В дополнение к реализации, предоставляющей статистику выполнения, я хотел предоставить версию без статистики, чтобы сократить время выполнения. Я был удивлен, что версия без статистики выполняется значительно медленнее (8% на тестовой машине), чем версия со статистикой.
Я провел много тестов и свел проблему к двум различным версиям одиночный метод MatrixEntry.
Быстрая версия (первая строка — строка 77 в MatrixEntry.java):
[code]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;
}
[/code]
Медленная версия (первая строка — строка 77 в MatrixEntry.java):
[code]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;
}
[/code]
Я также проверил байт-код с помощью 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:
[code]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)
[/code]
Дополнительную информацию о реализации можно найти в репозитории GitHub, хотя я думаю, что эта контекстная информация не нужна.
Я' Я был очень озадачен результатами и попытался вернуть 0 вместо того, чтобы позволить методу вернуть void.  Я даже создал версию, в которой счетчик обновлений увеличивается, но значение не сохраняется — эта версия была самой быстрой из всех (но я не позволял ей запускаться несколько раз).
Может кто-нибудь объяснит улучшенную производительность кода со встроенным счетчиком?

Байткод быстрой версии:
[code]  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
[/code]
Байткод более медленной версии:
[code]  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
[/code]

Как предложено в комментариях, я позволил JVM распечатать сборку после компиляции C2, используя плагин hsdis и следующие флаги командной строки JVM: -XX: +UnlockDiagnosticVMOptions -XX:+DebugNonSafepoints -XX:PrintAssemblyOptions=intel -XX:CompileCommand=print,*MatrixEntry.coverColumn
Я попробовал извлечь только часть внутреннего цикла сборки , так как вся сборка довольно длинная.
Быстрый код, включая счетчик:
[code]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)
[/code]
Медленный код возвращает void:
[code]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)
[/code]

[code]perf stat -d -d -d bin/app[/code] отчет для быстрой версии:
[code]         944020.43 msec task-clock                       #    1.002 CPUs utilized
34131      context-switches                 #   36.155 /sec
3772      cpu-migrations                   #    3.996 /sec
26375      page-faults                      #   27.939 /sec
3073656028927      cycles                           #    3.256 GHz                      (61.54%)
8314592091084      instructions                     #    2.71  insn per cycle           (69.23%)
1617667532435      branches                         #    1.714 G/sec                    (69.23%)
7376429842      branch-misses                    #    0.46% of all branches          (69.23%)
2518602003849      L1-dcache-loads                  #    2.668 G/sec                    (69.23%)
217124852119      L1-dcache-load-misses            #    8.62% of all L1-dcache accesses  (69.23%)
8360116079      LLC-loads                        #    8.856 M/sec                    (69.23%)
36950592      LLC-load-misses                  #    0.44% of all LL-cache accesses  (69.24%)
       L1-icache-loads
613369051      L1-icache-load-misses                                                (69.23%)
2518014639585      dTLB-loads                       #    2.667 G/sec                    (69.24%)
2964075      dTLB-load-misses                 #    0.00% of all dTLB cache accesses  (61.54%)
4335821      iTLB-loads                       #    4.593 K/sec                    (61.54%)
1578713      iTLB-load-misses                 #   36.41% of all iTLB cache accesses  (61.54%)
[/code]
и для медленной версии:
[code]        1011635.24 msec task-clock                       #    1.001 CPUs utilized
37371      context-switches                 #   36.941 /sec
1949      cpu-migrations                   #    1.927 /sec
26087      page-faults                      #   25.787 /sec
3277438029589      cycles                           #    3.240 GHz                      (61.54%)
9156368782029      instructions                     #    2.79  insn per cycle           (69.23%)
1614775762524      branches                         #    1.596 G/sec                    (69.23%)
7360324323      branch-misses                    #    0.46% of all branches          (69.23%)
2914029260930      L1-dcache-loads                  #    2.881 G/sec                    (69.23%)
216220083510      L1-dcache-load-misses            #    7.42% of all L1-dcache accesses  (69.23%)
8079066223      LLC-loads                        #    7.986 M/sec                    (69.23%)
47018889      LLC-load-misses                  #    0.58% of all LL-cache accesses  (69.23%)
      L1-icache-loads
650941335      L1-icache-load-misses                                                (69.23%)
2913664329244      dTLB-loads                       #    2.880 G/sec                    (69.23%)
2913507      dTLB-load-misses                 #    0.00% of all dTLB cache accesses  (61.54%)
4294995      iTLB-loads                       #    4.246 K/sec                    (61.54%)
1796205      iTLB-load-misses                 #   41.82% of all iTLB cache accesses  (61.54%)
[/code]
Промахи при переходе составляют всего 0,46 % (в обоих случаях), но статистика производительности выделяет промахи при загрузке iTLB, что составляет 36 % против 42 %.  

Подробнее здесь: [url]https://stackoverflow.com/questions/79131410/how-can-more-code-execute-faster-than-executing-fewer[/url]

Ответить Пред. тема След. тема

1 сообщение • Страница 1 из 1

Быстрый ответ

Заголовок:

Имя пользователя:

Изменение регистра текста:

Смайлики

Ещё смайлики…

К этому ответу прикреплено по крайней мере одно вложение.

Если вы не хотите добавлять вложения, оставьте поля пустыми. Можно прикреплять файлы, перетаскивая их в окно сообщения.

Максимально разрешённый размер вложения: 15 МБ.

Имя файла:

Комментарий к файлу:

Имя файла	Комментарий к файлу	Размер	Статус

Похожие темы

Ответы

Просмотры

Последнее сообщение

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

Последнее сообщение Anonymous « 27 окт 2024, 23:11
Добавлено в форуме JAVA

Anonymous » 27 окт 2024, 23:11 » в форуме JAVA

Я реализовал алгоритм DLX в Java 17. В дополнение к реализации, предоставляющей статистику выполнения, я хотел предоставить версию без статистики, чтобы сократить время выполнения. Я был удивлен, что версия без статистики выполняется значительно...

0 Ответы

24 Просмотры

Последнее сообщение Anonymous
27 окт 2024, 23:11
Как может больший объем кода выполняться быстрее, чем меньший?

Последнее сообщение Anonymous « 29 окт 2024, 23:44
Добавлено в форуме JAVA

Anonymous » 29 окт 2024, 23:44 » в форуме JAVA

Я реализовал алгоритм DLX в Java 17. В дополнение к реализации, предоставляющей статистику выполнения, я хотел предоставить версию без статистики, чтобы сократить время выполнения. Я был удивлен, что версия без статистики выполняется значительно...

0 Ответы

10 Просмотры

Последнее сообщение Anonymous
29 окт 2024, 23:44
Как может больший объем кода выполняться быстрее, чем меньший?

Последнее сообщение Anonymous « 30 окт 2024, 09:34
Добавлено в форуме JAVA

Anonymous » 30 окт 2024, 09:34 » в форуме JAVA

Я реализовал алгоритм DLX в Java 17. В дополнение к реализации, предоставляющей статистику выполнения, я хотел предоставить версию без статистики, чтобы сократить время выполнения. Я был удивлен, что версия без статистики выполняется значительно...

0 Ответы

17 Просмотры

Последнее сообщение Anonymous
30 окт 2024, 09:34
Как может больший объем кода выполняться быстрее, чем меньший?

Последнее сообщение Anonymous « 03 ноя 2024, 09:42
Добавлено в форуме JAVA

Anonymous » 03 ноя 2024, 09:42 » в форуме JAVA

Я реализовал алгоритм DLX в Java 17. В дополнение к реализации, предоставляющей статистику выполнения, я хотел предоставить версию без статистики, чтобы сократить время выполнения. Я был удивлен, что версия без статистики выполняется значительно...

0 Ответы

16 Просмотры

Последнее сообщение Anonymous
03 ноя 2024, 09:42
Скопируйте меньший 2D-массив в больший 2D-массив в нужной позиции.

Последнее сообщение Anonymous « 16 сен 2024, 21:04
Добавлено в форуме Python

Anonymous » 16 сен 2024, 21:04 » в форуме Python

Предположим, у меня есть два 2D-массива в Python. Один размером 100х100, другой 5х5. Учитывая позицию, мне нужно скопировать содержимое массива 5x5 в массив 100x100 в этой позиции.
Я знаю, что мог бы сделать это вручную, перебирая массивы, но мне...

0 Ответы

14 Просмотры

Последнее сообщение Anonymous
16 сен 2024, 21:04

Вернуться в «JAVA»

Programmiererforum