Должен признаться, заголовок этого поста немного броский. Я недавно прочитал этот пост в блоге, и это хорошее резюме обсуждений и дебатов на эту тему.
Но на этот раз я хотел бы попробовать другой подход для сравнения этих двух известных структур данных: с помощью аппаратных счетчиков производительности .
Я не буду выполнять микро-тест, ну, не напрямую. Я не буду использовать System.nanoTime (), а скорее использую HPC, такие как попадания / пропадания кэша.
Не нужно представлять эти структуры данных, все знают, для чего они используются и как они реализованы. Я сосредотачиваю свое исследование на итерации списка, потому что, помимо добавления элемента, это самая распространенная задача для списка. А также потому, что схема доступа к памяти для списка является хорошим примером взаимодействия с кэшем ЦП.
Вот мой код для измерения итерации списка для LinkedList & ArrayList:
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
55
56
57
58
59
60
61
62
63
64
|
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import ch.usi.overseer.OverHpc; public class ListIteration { private static List<String> arrayList = new ArrayList<>(); private static List<String> linkedList = new LinkedList<>(); public static void initializeList(List<String> list, int bufferSize) { for ( int i = 0 ; i < 50000 ; i++) { byte [] buffer = null ; if (bufferSize > 0 ) { buffer = new byte [bufferSize]; } String s = String.valueOf(i); list.add(s); // avoid buffer to be optimized away if (System.currentTimeMillis() == 0 ) { System.out.println(buffer); } } } public static void bench(List<String> list) { if (list.contains( "bar" )) { System.out.println( "bar found" ); } } public static void main(String[] args) throws Exception { if (args.length != 2 ) return ; List<String> benchList = "array" .equals(args[ 0 ]) ? arrayList : linkedList; int bufferSize = Integer.parseInt(args[ 1 ]); initializeList(benchList, bufferSize); HWCounters.init(); System.out.println( "init done" ); // warmup for ( int i = 0 ; i < 10000 ; i++) { bench(benchList); } Thread.sleep( 1000 ); System.out.println( "warmup done" ); HWCounters.start(); for ( int i = 0 ; i < 1000 ; i++) { bench(benchList); } HWCounters.stop(); HWCounters.printResults(); HWCounters.shutdown(); } } |
Для измерения я использую класс под названием HWCounters, основанный на библиотеке наблюдателей, чтобы получить счетчики производительности оборудования. Вы можете найти код этого класса здесь .
Программа принимает 2 параметра: первый для выбора между реализацией ArrayList или LinkedList, второй для выбора размера буфера, используемого в методе initializeList
. Этот метод заполняет реализацию списка 50К строк. Каждая строка создается заново перед тем, как добавить ее в список. Мы также можем выделить буфер на основе нашего второго параметра программы. если 0, буфер не выделяется.
Метод bench
выполняет поиск постоянной строки, которая не содержится в списке, поэтому мы полностью просматриваем список.
Наконец, main
метод, выполнить инициализацию списка, прогревает стендовый метод и измерить 1000 прогонов этого метода. Затем мы печатаем результаты из высокопроизводительных вычислений.
Давайте запустим нашу программу без выделения буфера в Linux с 2 Xeon X5680:
01
02
03
04
05
06
07
08
09
10
11
12
|
[root@archi-srv] # java -cp .:overseer.jar com.ullink.perf.myths.ListIteration array 0 init done warmup done Cycles: 428,711,720 Instructions: 776,215,597 L2 hits: 5,302,792 L2 misses: 23,702,079 LLC hits: 42,933,789 LLC misses: 73 CPU migrations: 0 Local DRAM: 0 Remote DRAM: 0 |
01
02
03
04
05
06
07
08
09
10
11
12
|
[root@archi-srv] # /java -cp .:overseer.jar com.ullink.perf.myths.ListIteration linked 0 init done warmup done Cycles: 767,019,336 Instructions: 874,081,196 L2 hits: 61,489,499 L2 misses: 2,499,227 LLC hits: 3,788,468 LLC misses: 0 CPU migrations: 0 Local DRAM: 0 Remote DRAM: 0 |
Первый запуск — реализация ArrayList, второй — LinkedList.
- Количество циклов — это количество циклов ЦП, затраченных на выполнение нашего кода. Очевидно, что LinkedList провел гораздо больше циклов, чем ArrayList.
- Инструкции немного выше для LinkedList. Но это не так важно здесь.
- Для доступа к кэшу L2 у нас есть явное различие: ArrayList имеет значительно больше пропусков L2 по сравнению с LinkedList.
- Механически, хиты LLC очень важны для ArrayList.
Вывод из этого сравнения заключается в том, что большая часть данных, к которым обращаются во время итерации списка, находится в L2 для LinkedList, но в L3 для ArrayList.
Я объясняю это тем, что строки, добавленные в список, создаются прямо перед этим. Для LinkedList это означает, что это локальная запись Node, которая создается при добавлении элемента. У нас есть больше мест с узлом.
Но давайте снова запустим сравнение с промежуточным буфером, выделенным для каждой новой добавленной строки.
01
02
03
04
05
06
07
08
09
10
11
12
|
[root@archi-srv] # java -cp .:overseer.jar com.ullink.perf.myths.ListIteration array 256 init done warmup done Cycles: 584,965,201 Instructions: 774,373,285 L2 hits: 952,193 L2 misses: 62,840,804 LLC hits: 63,126,049 LLC misses: 4,416 CPU migrations: 0 Local DRAM: 824 Remote DRAM: 0 |
01
02
03
04
05
06
07
08
09
10
11
12
|
[root@archi-srv] # java -cp .:overseer.jar com.ullink.perf.myths.ListIteration linked 256 init done warmup done Cycles: 5,289,317,879 Instructions: 874,350,022 L2 hits: 1,487,037 L2 misses: 75,500,984 LLC hits: 81,881,688 LLC misses: 5,826,435 CPU migrations: 0 Local DRAM: 1,645,436 Remote DRAM: 1,042 |
Здесь результаты совсем другие:
- Циклы в 10 раз важнее.
- Инструкции остаются прежними
- Для доступа к кэшу ArrayList имеет больше пропусков L2 / LLC, чем при предыдущем запуске, но все еще в том же порядке величины. LinkedList, напротив, имеет гораздо больше пропущенных L2 / посещений LLC, но, кроме того, значительное количество пропущенных LLC / обращений DRAM. И разница здесь.
Используя промежуточный буфер, мы отталкиваем записи и строки, которые генерируют больше пропусков кеша, а также завершают доступ к DRAM, который намного медленнее, чем попадание в кеш.
ArrayList здесь более предсказуем, поскольку мы сохраняем локальность элементов друг от друга.
Схема доступа к памяти здесь имеет решающее значение для производительности итерации списка. ArrayList более стабилен, чем LinkedList, в том смысле, что независимо от того, что вы делаете между каждым добавлением элемента, вы храните свои данные гораздо более локально, чем LinkedList.
Помните также, что перебор массива намного эффективнее для CPU, поскольку он может инициировать предварительную выборку оборудования, поскольку схема доступа очень предсказуема.