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

[Anonymous]

Я реализовал алгоритм DLX в Java 17. В дополнение к реализации, предоставляющей статистику выполнения, я хотел предоставить версию без статистики, чтобы сократить время выполнения. Я был удивлен, что версия без статистики выполняется значительно медленнее (8% на тестовой машине), чем версия со статистикой.
Я провел много тестов и свел проблему к двум различным версиям один метод MatrixEntry.
Быстрая версия:
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;
}

Медленная версия:
void coverColumn() {
columnHead.right.left = columnHead.left;
columnHead.left.right = columnHead.right;
MatrixEntry i = columnHead.lower;
while (i != columnHead) {
MatrixEntry j = i.right;
while (j != i) {
j.lower.upper = j.upper;
j.upper.lower = j.lower;
j.columnHead.rowCount--;
j = j.right;
}
i = i.lower;
}
}

Я также проверил байт-код с помощью 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


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