Структуры очень полезны, как в стеке, так и в куче. Насколько мне известно, невозможно смоделировать эту функцию в стеке Java. Невозможность сделать это в стеке — это стыд, потому что это сильно ограничивает производительность некоторых параллельных алгоритмов, однако это напыщенная работа на другой день.
В Java все пользовательские типы должны существовать в куче. Куча Java в общем случае управляется сборщиком мусора, однако в процессе Java есть еще кое-что более широкое. С введением прямого ByteBuffer может быть выделена память, которая не отслеживается сборщиком мусора, поскольку она может быть доступна для собственного кода для таких задач, как предотвращение копирования данных в ядро и из ядра для ввода-вывода. Таким образом, один из методов управления структурами состоит в том, чтобы имитировать их в ByteBuffer как разумный подход. Это может обеспечить компактное представление данных, но имеет ограничения по производительности и размеру. Например, невозможно создать ByteBuffer размером более 2 ГБ, и весь доступ проверяется с помощью границ, что влияет на производительность. Существует альтернатива, использующая Unsafe, которая быстрее и без ограничений по размеру, как ByteBuffer .
Подход, который я собираюсь подробно описать, не является традиционной Java. Если ваше проблемное пространство имеет дело с большими данными или экстремальной производительностью, то здесь есть преимущества. Если ваши наборы данных невелики, а производительность не является проблемой, убегайте сейчас, чтобы не оказаться втянутыми в мрачное искусство управления собственной памятью.
Преимущества подхода, который я собираюсь подробно изложить:
- Значительно улучшена производительность
- Более компактное представление данных
- Способность работать с очень большими наборами данных, избегая неприятных пауз GC [1]
При любом выборе есть последствия. Используя подход, описанный ниже, вы берете на себя ответственность за управление памятью самостоятельно. Неправильная интерпретация может привести к утечке памяти или, что еще хуже, к аварийной остановке JVM! Продолжить с осторожностью…
Подходящий пример — торговые данные
Распространенной проблемой, с которой сталкиваются финансовые приложения, является сбор и работа с очень большими объемами данных о заказах и торговле. В качестве примера я создам большую таблицу данных о торговле в памяти, в которой могут выполняться аналитические запросы. Эта таблица будет построена с использованием 2 контрастных подходов. Во-первых, я возьму традиционный подход Java для создания большого массива и ссылки на отдельные объекты Trade. Во-вторых, я сохраняю код использования идентичным, но заменяю большой массив и объекты Trade на массив структур вне кучи, которыми можно манипулировать с помощью шаблона Flyweight .
Если бы для традиционного подхода Java я использовал какую-то другую структуру данных, такую как Карта или Дерево, то объем памяти был бы еще больше, а производительность ниже.
Традиционный Java-подход
|
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
public class TestJavaMemoryLayout{ private static final int NUM_RECORDS = 50 * 1000 * 1000; private static JavaMemoryTrade[] trades; public static void main(final String[] args) { for (int i = 0; i < 5; i++) { System.gc(); perfRun(i); } } private static void perfRun(final int runNum) { long start = System.currentTimeMillis(); init(); System.out.format('Memory %,d total, %,d free\n', Runtime.getRuntime().totalMemory(), Runtime.getRuntime().freeMemory()); long buyCost = 0; long sellCost = 0; for (int i = 0; i < NUM_RECORDS; i++) { final JavaMemoryTrade trade = get(i); if (trade.getSide() == 'B') { buyCost += (trade.getPrice() * trade.getQuantity()); } else { sellCost += (trade.getPrice() * trade.getQuantity()); } } long duration = System.currentTimeMillis() - start; System.out.println(runNum + ' - duration ' + duration + 'ms'); System.out.println('buyCost = ' + buyCost + ' sellCost = ' + sellCost); } private static JavaMemoryTrade get(final int index) { return trades[index]; } public static void init() { trades = new JavaMemoryTrade[NUM_RECORDS]; final byte[] londonStockExchange = {'X', 'L', 'O', 'N'}; final int venueCode = pack(londonStockExchange); final byte[] billiton = {'B', 'H', 'P'}; final int instrumentCode = pack( billiton); for (int i = 0; i < NUM_RECORDS; i++) { JavaMemoryTrade trade = new JavaMemoryTrade(); trades[i] = trade; trade.setTradeId(i); trade.setClientId(1); trade.setVenueCode(venueCode); trade.setInstrumentCode(instrumentCode); trade.setPrice(i); trade.setQuantity(i); trade.setSide((i & 1) == 0 ? 'B' : 'S'); } } private static int pack(final byte[] value) { int result = 0; switch (value.length) { case 4: result = (value[3]); case 3: result |= ((int)value[2] << 8); case 2: result |= ((int)value[1] << 16); case 1: result |= ((int)value[0] << 24); break; default: throw new IllegalArgumentException('Invalid array size'); } return result; } private static class JavaMemoryTrade { private long tradeId; private long clientId; private int venueCode; private int instrumentCode; private long price; private long quantity; private char side; public long getTradeId() { return tradeId; } public void setTradeId(final long tradeId) { this.tradeId = tradeId; } public long getClientId() { return clientId; } public void setClientId(final long clientId) { this.clientId = clientId; } public int getVenueCode() { return venueCode; } public void setVenueCode(final int venueCode) { this.venueCode = venueCode; } public int getInstrumentCode() { return instrumentCode; } public void setInstrumentCode(final int instrumentCode) { this.instrumentCode = instrumentCode; } public long getPrice() { return price; } public void setPrice(final long price) { this.price = price; } public long getQuantity() { return quantity; } public void setQuantity(final long quantity) { this.quantity = quantity; } public char getSide() { return side; } public void setSide(final char side) { this.side = side; } }} |
Компактные конструкции вне кучи
|
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
|
import sun.misc.Unsafe;import java.lang.reflect.Field;public class TestDirectMemoryLayout{ private static final Unsafe unsafe; static { try { Field field = Unsafe.class.getDeclaredField('theUnsafe'); field.setAccessible(true); unsafe = (Unsafe)field.get(null); } catch (Exception e) { throw new RuntimeException(e); } } private static final int NUM_RECORDS = 50 * 1000 * 1000; private static long address; private static final DirectMemoryTrade flyweight = new DirectMemoryTrade(); public static void main(final String[] args) { for (int i = 0; i < 5; i++) { System.gc(); perfRun(i); } } private static void perfRun(final int runNum) { long start = System.currentTimeMillis(); init(); System.out.format('Memory %,d total, %,d free\n', Runtime.getRuntime().totalMemory(), Runtime.getRuntime().freeMemory()); long buyCost = 0; long sellCost = 0; for (int i = 0; i < NUM_RECORDS; i++) { final DirectMemoryTrade trade = get(i); if (trade.getSide() == 'B') { buyCost += (trade.getPrice() * trade.getQuantity()); } else { sellCost += (trade.getPrice() * trade.getQuantity()); } } long duration = System.currentTimeMillis() - start; System.out.println(runNum + ' - duration ' + duration + 'ms'); System.out.println('buyCost = ' + buyCost + ' sellCost = ' + sellCost); destroy(); } private static DirectMemoryTrade get(final int index) { final long offset = address + (index * DirectMemoryTrade.getObjectSize()); flyweight.setObjectOffset(offset); return flyweight; } public static void init() { final long requiredHeap = NUM_RECORDS * DirectMemoryTrade.getObjectSize(); address = unsafe.allocateMemory(requiredHeap); final byte[] londonStockExchange = {'X', 'L', 'O', 'N'}; final int venueCode = pack(londonStockExchange); final byte[] billiton = {'B', 'H', 'P'}; final int instrumentCode = pack( billiton); for (int i = 0; i < NUM_RECORDS; i++) { DirectMemoryTrade trade = get(i); trade.setTradeId(i); trade.setClientId(1); trade.setVenueCode(venueCode); trade.setInstrumentCode(instrumentCode); trade.setPrice(i); trade.setQuantity(i); trade.setSide((i & 1) == 0 ? 'B' : 'S'); } } private static void destroy() { unsafe.freeMemory(address); } private static int pack(final byte[] value) { int result = 0; switch (value.length) { case 4: result |= (value[3]); case 3: result |= ((int)value[2] << 8); case 2: result |= ((int)value[1] << 16); case 1: result |= ((int)value[0] << 24); break; default: throw new IllegalArgumentException('Invalid array size'); } return result; } private static class DirectMemoryTrade { private static long offset = 0; private static final long tradeIdOffset = offset += 0; private static final long clientIdOffset = offset += 8; private static final long venueCodeOffset = offset += 8; private static final long instrumentCodeOffset = offset += 4; private static final long priceOffset = offset += 4; private static final long quantityOffset = offset += 8; private static final long sideOffset = offset += 8; private static final long objectSize = offset += 2; private long objectOffset; public static long getObjectSize() { return objectSize; } void setObjectOffset(final long objectOffset) { this.objectOffset = objectOffset; } public long getTradeId() { return unsafe.getLong(objectOffset + tradeIdOffset); } public void setTradeId(final long tradeId) { unsafe.putLong(objectOffset + tradeIdOffset, tradeId); } public long getClientId() { return unsafe.getLong(objectOffset + clientIdOffset); } public void setClientId(final long clientId) { unsafe.putLong(objectOffset + clientIdOffset, clientId); } public int getVenueCode() { return unsafe.getInt(objectOffset + venueCodeOffset); } public void setVenueCode(final int venueCode) { unsafe.putInt(objectOffset + venueCodeOffset, venueCode); } public int getInstrumentCode() { return unsafe.getInt(objectOffset + instrumentCodeOffset); } public void setInstrumentCode(final int instrumentCode) { unsafe.putInt(objectOffset + instrumentCodeOffset, instrumentCode); } public long getPrice() { return unsafe.getLong(objectOffset + priceOffset); } public void setPrice(final long price) { unsafe.putLong(objectOffset + priceOffset, price); } public long getQuantity() { return unsafe.getLong(objectOffset + quantityOffset); } public void setQuantity(final long quantity) { unsafe.putLong(objectOffset + quantityOffset, quantity); } public char getSide() { return unsafe.getChar(objectOffset + sideOffset); } public void setSide(final char side) { unsafe.putChar(objectOffset + sideOffset, side); } }} |
Полученные результаты
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
Intel i7-860 @ 2.8GHz, 8GB RAM DDR3 1333MHz, Windows 7 64-bit, Java 1.7.0_07=============================================java -server -Xms4g -Xmx4g TestJavaMemoryLayoutMemory 4,116,054,016 total, 1,108,901,104 free0 - duration 19334msMemory 4,116,054,016 total, 1,109,964,752 free1 - duration 14295msMemory 4,116,054,016 total, 1,108,455,504 free2 - duration 14272msMemory 3,817,799,680 total, 815,308,600 free3 - duration 28358msMemory 3,817,799,680 total, 810,552,816 free4 - duration 32487msjava -server TestDirectMemoryLayoutMemory 128,647,168 total, 126,391,384 free0 - duration 983msMemory 128,647,168 total, 126,992,160 free1 - duration 958msMemory 128,647,168 total, 127,663,408 free2 - duration 873msMemory 128,647,168 total, 127,663,408 free3 - duration 886msMemory 128,647,168 total, 127,663,408 free4 - duration 884msIntel i7-2760QM @ 2.40GHz, 8GB RAM DDR3 1600MHz, Linux 3.4.11 kernel 64-bit, Java 1.7.0_07=================================================java -server -Xms4g -Xmx4g TestJavaMemoryLayoutMemory 4,116,054,016 total, 1,108,912,960 free0 - duration 12262msMemory 4,116,054,016 total, 1,109,962,832 free1 - duration 9822msMemory 4,116,054,016 total, 1,108,458,720 free2 - duration 10239msMemory 3,817,799,680 total, 815,307,640 free3 - duration 21558msMemory 3,817,799,680 total, 810,551,856 free4 - duration 23074msjava -server TestDirectMemoryLayout Memory 123,994,112 total, 121,818,528 free0 - duration 634msMemory 123,994,112 total, 122,455,944 free1 - duration 619msMemory 123,994,112 total, 123,103,320 free2 - duration 546msMemory 123,994,112 total, 123,103,320 free3 - duration 547msMemory 123,994,112 total, 123,103,320 free4 - duration 534ms |
Анализ
Давайте сравним результаты с 3 преимуществами, обещанными выше.
1. Значительно улучшена производительность
Доказательства здесь довольно четкие. Использование подхода вне структуры кучи более чем на порядок быстрее. В самом крайнем случае, если взглянуть на 5-й запуск процессора Sandy Bridge, у нас есть различие в продолжительности в 43,2 раза для выполнения задачи. Это также хорошая иллюстрация того, как хорошо Sandy Bridge справляется с предсказуемыми схемами доступа к данным. Мало того, что производительность значительно лучше, она также более стабильна. Поскольку куча становится фрагментированной, и, таким образом, шаблоны доступа становятся более случайными, производительность снижается, как это можно увидеть в более поздних запусках со стандартным подходом Java.
2. Более компактное представление данных
Для нашего представления вне кучи каждый объект требует 42 байта. Для хранения 50 миллионов из них, как в примере, нам требуется 2 100 000 000 байтов. Память, необходимая для кучи JVM:
требуется память = общая память — свободная память — базовые потребности JVM
2,883,248,712 = 3,817,799,680 — 810,551,856 — 123,999,112
Это означает, что JVM требуется на ~ 40% больше памяти для представления тех же данных. Причиной таких издержек является массив ссылок на объекты Java плюс заголовки объектов. В предыдущем посте я обсуждал расположение объектов в Java.
При работе с очень большими наборами данных эти издержки могут стать существенным ограничивающим фактором.
3. Способность работать с очень большими наборами данных, избегая неприятных пауз GC
Приведенный выше пример кода запускает цикл GC перед каждым запуском и в некоторых случаях может улучшить согласованность результатов. Не стесняйтесь удалять вызов System.gc () и следите за последствиями для себя. Если вы запустите тесты, добавив следующие аргументы командной строки, то сборщик мусора очень печально выведет то, что произошло.
-XX: + PrintGC -XX: + PrintGCDetails -XX: + PrintGCDateStamps -XX: + PrintTenuringDistribution -XX: + PrintHeapAtGC -XX: + PrintGCApplicationConcurrentTime -XX: + PrintGCApplicationStoppedTime -XX: + PrintSafepointSt
Из анализа результатов я вижу, что приложение прошло 29 циклов ГХ. Время паузы указано ниже путем извлечения строк из выходных данных, указывающих, когда потоки приложения остановлены.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
With System.gc() before each run================================Total time for which application threads were stopped: 0.0085280 secondsTotal time for which application threads were stopped: 0.7280530 secondsTotal time for which application threads were stopped: 8.1703460 secondsTotal time for which application threads were stopped: 5.6112210 secondsTotal time for which application threads were stopped: 1.2531370 secondsTotal time for which application threads were stopped: 7.6392250 secondsTotal time for which application threads were stopped: 5.7847050 secondsTotal time for which application threads were stopped: 1.3070470 secondsTotal time for which application threads were stopped: 8.2520880 secondsTotal time for which application threads were stopped: 6.0949910 secondsTotal time for which application threads were stopped: 1.3988480 secondsTotal time for which application threads were stopped: 8.1793240 secondsTotal time for which application threads were stopped: 6.4138720 secondsTotal time for which application threads were stopped: 4.4991670 secondsTotal time for which application threads were stopped: 4.5612290 secondsTotal time for which application threads were stopped: 0.3598490 secondsTotal time for which application threads were stopped: 0.7111000 secondsTotal time for which application threads were stopped: 1.4426750 secondsTotal time for which application threads were stopped: 1.5931500 secondsTotal time for which application threads were stopped: 10.9484920 secondsTotal time for which application threads were stopped: 7.0707230 secondsWithout System.gc() before each run===================================Test run times0 - duration 12120ms1 - duration 9439ms2 - duration 9844ms3 - duration 20933ms4 - duration 23041msTotal time for which application threads were stopped: 0.0170860 secondsTotal time for which application threads were stopped: 0.7915350 secondsTotal time for which application threads were stopped: 10.7153320 secondsTotal time for which application threads were stopped: 5.6234650 secondsTotal time for which application threads were stopped: 1.2689950 secondsTotal time for which application threads were stopped: 7.6238170 secondsTotal time for which application threads were stopped: 6.0114540 secondsTotal time for which application threads were stopped: 1.2990070 secondsTotal time for which application threads were stopped: 7.9918480 secondsTotal time for which application threads were stopped: 5.9997920 secondsTotal time for which application threads were stopped: 1.3430040 secondsTotal time for which application threads were stopped: 8.0759940 secondsTotal time for which application threads were stopped: 6.3980610 secondsTotal time for which application threads were stopped: 4.5572100 secondsTotal time for which application threads were stopped: 4.6193830 secondsTotal time for which application threads were stopped: 0.3877930 secondsTotal time for which application threads were stopped: 0.7429270 secondsTotal time for which application threads were stopped: 1.5248070 secondsTotal time for which application threads were stopped: 1.5312130 secondsTotal time for which application threads were stopped: 10.9120250 secondsTotal time for which application threads were stopped: 7.3528590 seconds |
Из результатов видно, что значительная часть времени проводится в сборщике мусора. Когда ваши темы остановлены, ваше приложение не отвечает. Эти тесты были сделаны с настройками GC по умолчанию. Можно настроить GC для лучших результатов, но это может быть очень квалифицированным и значительным усилием. Единственная известная мне JVM, которая хорошо справляется, не налагая большого времени на паузу даже в условиях высокой пропускной способности, — это одновременный уплотнительный коллектор Azul.
При профилировании этого приложения я вижу, что большую часть времени уделяется выделению объектов и продвижению их старому поколению, поскольку они не вписываются в молодое поколение. Затраты на инициализацию могут быть удалены из сроков, но это нереально. Если используется традиционный подход Java, состояние должно быть построено до того, как запрос может быть выполнен. Конечный пользователь приложения должен ждать формирования состояния и выполнения запроса.
Этот тест действительно довольно тривиален. Представьте себе работу с подобными наборами данных, но в масштабе 100 ГБ.
Примечание. Когда сборщик мусора уплотняет область, объекты, находящиеся рядом друг с другом, могут быть удалены друг от друга. Это может привести к TLB и другим ошибкам кэша.
Дополнительное примечание о сериализации
Огромное преимущество использования таких структур вне кучи состоит в том, что их можно очень легко сериализовать в сеть или хранилище с помощью простой копии памяти, как я показал в предыдущем посте . Таким образом, мы можем полностью обойти промежуточный буфер и распределение объектов.
Вывод
Если вы хотите заняться программированием в стиле C для больших наборов данных, вы можете управлять макетом памяти в Java, отключив кучу. Если вы это сделаете, преимущества в производительности, компактности и избежании проблем GC будут значительными. Однако это подход, который не следует использовать для всех приложений. Его преимущества заметны только для очень больших наборов данных или экстремальных показателей производительности при пропускной способности и / или задержке.
Я надеюсь, что сообщество Java сможет коллективно осознать важность поддержки структур как в куче, так и в стеке. Джон Роуз проделал отличную работу в этой области, определяя, как можно добавить кортежи в JVM. Его выступление на Arrays 2.0 с Языкового Саммита JVM в этом году действительно стоит посмотреть. Джон обсуждает варианты массивов структур и структур массивов в своем выступлении. Если бы кортежи, предложенные Джоном, были доступны, то описанный здесь тест мог бы иметь сопоставимую производительность и быть более приятным стилем программирования. Весь массив структур может быть выделен одним действием, минуя копию отдельных объектов из поколения в поколение, и он будет храниться в компактном непрерывном режиме. Это позволило бы устранить существенные проблемы GC для этого класса проблем.
В последнее время я сравнивал стандартные структуры данных между Java и .Net. В некоторых случаях я наблюдал преимущество производительности .Net в 6-10 раз для таких вещей, как карты и словари, когда .Net использовал поддержку нативных структур. Давайте перенесем это в Java как можно скорее!
Из результатов также довольно очевидно, что если мы хотим использовать Java для анализа больших данных в режиме реального времени, то нашим стандартным сборщикам мусора необходимо значительно улучшить и поддерживать истинно параллельные операции.
[1] — Насколько мне известно, единственной JVM, которая хорошо справляется с очень большими кучами, является Azul Zing
Приятного кодирования и не забудьте поделиться!
Ссылка: Компактные структуры вне кучи / кортежи на Java от нашего партнера JCG Мартина Томпсона из блога Mechanical Sympathy .