Статьи

ArrayList против LinkedList

Апрель 3, 2019

Должен признаться, заголовок этого поста немного броский. Я недавно прочитал этот пост в блоге, и это хорошее резюме обсуждений и дебатов на эту тему.

Но на этот раз я хотел бы попробовать другой подход для сравнения этих двух известных структур данных: с помощью аппаратных счетчиков производительности .

Я не буду выполнять микро-тест, ну, не напрямую. Я не буду использовать 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, поскольку он может инициировать предварительную выборку оборудования, поскольку схема доступа очень предсказуема.

Ссылка: ArrayList против LinkedList от нашего партнера по JCG Жана-Филиппа BEMPEL в блоге Java Advent Calendar .
39
Share: