elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Память это новый диск или LinkedList vs ArrayList
elizarov

"Память это новый диск, диск это новая лента". Такой мотив можно часто прочитать в блогах, посвященных написанию высокопроизводительных систем. Действительно, память становится всё дешевле и дешевле, и во многих областях становится не только возможным, но и экономически выгодным, хранить все данные системы в памяти, рассматривая диск лишь как способ их архивирования. Однако, есть и другой аспект этого высказывания. Разрыв в производительности между кэшом процессора и оперативной памятью настолько велик, что к памяти надо относится как к диску при написании любого высокопроизводительного кода.

Классическое образование в области теории алгоритмов уделяет много времени асимптотической сложности алгоритмов, но не уделяет достаточно времени практическим аспектам производительности. Например, первая структура данных рассмотренная в Главе 2 классического труда Дональда Кнута "Искусство Программирования" это линейный список. В языке Java он реализован в классе LinkedList. Альтернативой этой структуре данных является список на массиве, реализованный в классе ArrayList.

Если провести сравнительный анализ асимптотической амортизированной сложности различных базовых операций над списком, то получим следующую таблицу:

ОперацииLinkedListArrayList
Вставка или удаление элемента в конце, последовательная итерация по одному элементу O(1)O(1)
Вставка или удаление элемента в начале или в середине O(1)O(N)
Получение элемента по индексу (номеру) O(N)O(1)

Из этой таблицы видно, что есть специфические операции, на которых LinkedList или ArrayList оптимальны по асимптотической сложности, в то время как для самого простого случая добавления элементов в конец и итерации по ним, разницы в асимптотической сложности нет. Какой же список использовать по умолчанию? Кнут не дает ответа на этот вопрос, более того, начиная рассмотрение со списка он как бы намекает.

На самом деле, идеология "память это новый диск" дает нам другую установку по умолчанию: при прочих равных, структура данных которая занимает меньше памяти будет и быстрей работать. Более того, память, как и диск, работает блоками, и ключевым моментом анализа производительности становится количество блоков памяти, которые алгоритм "трогает" во время работы, а также шаблон этого доступа (последовательный или случайным).

Давайте замерим скорость работы простейшего цикла итерации по N элементам в списке случайных целых чисел:

    private final List<Integer> list; 
 
    private int runIteration() { 
        int sum = 0; 
        for (Integer integer : list) 
            sum += integer; 
        return sum; 
    }

Полный код теста выложен здесь. На моем ноутбуке (Core i5, 520M, 2.4 GHz) при запуске под Java 1.7.0_01 используя HotSpot Server VM (опция "-server") получаются следующие времена итерации в расчете на один элемент, в наносекундах:

РазмерLinkedListArrayList
1 0003.431.94
10 0003.711.95
100 0006.702.22
1 000 0007.343.43

Видно, что итерация по LinkedList почти в два раза медленней, чем по ArrayList. Как объяснить эти результаты? Давайте посчитаем, сколько памяти уходит на каждый элемент в этих списках. Объект класса Integer на 32-битной JVM занимает 16 байт с учетом заголовка объекта в 8 байт и выравнивания. Узел в LinkedList занимает 24 байта, а указатель на объект в ArrayList занимает всего 4 байта. Таким образом, общее потребление памяти на объект в LinkedList это 16+24=40 байт, а в ArrayList это 16+4=20 байт, то есть ровно в два раза меньше, что и объясняет основную разницу в скорости работы. Вся остальная вариация в деталях. Например, при размере в 100 тысяч элементов LinkedList на моей машине работает в 3 раза медленней чем ArrayList. Общий объем памяти, необходимый для хранение этих 100 тысяч элементов в массиве около 2 МБ, а в связанном списке 4 МБ. Первый еще влезает в 3 МБ кэш моего процессора, а второй уже нет.

UPDATE: Как сделать быстрей, чем ArrayList, читайте в следующей части.


  • 1
всеж мне кажется что если бы все влезало в кэш то разница была бы на порядки, а тут всего в разы, имхо замедление в linkedlist скорее всего связано с организацией хранения данных и с тем как HotSpot оптимизирует исполнение в каждом из случаев

Разница на порядки будет видна при случайном доступе в память (при случае покажу такой пример из практики). При последовательном доступе она не так велика, ибо работает автоматический prefetch.

Что же касается оптимизации исполнения, то тут можно не гадать, а просто взглянуть на соответствующий ассемблерный код. Обещаю показать в ближайшем будущем как это можно сделать даже не имея отладочной сборки JVM и не используя -XX:+PrintOptoAssembly

Ром, распиши как-нибудь, как организован последовательный доступ по LinkedList'у. Мне все время казалось, что после достаточного количества удалений-добавлений-сортировок, в нем уже все так перемешано, что реально последовательно по памяти он идти не будет.

В моем примере всё просто (см код ListIterationTiming). Я добавляю элементы последовательно, потом сразу итерирую. Так что всё будет по факту организовано последовательно в памяти (в порядке выделения памяти при добавлении элементов), за исключением может быть того, что свежевыделенная часть будет еще находиться в области памяти для новых объектов, а часть будет уже перемещена сборщиком мусора в область для старых объектов. Копирующий сборщик мусора в JVM переносит объекты в целом в том же порядке, в котором они были исходно, так что даже если там и несколько кусков, то каждый из них будет организован в памяти в порядке исходного выделения объектов.

А, ну так это у тебя "сферический конь в вакууме" получился :)
Ты заполни список рандомом, а потом отсортируй, и посмотри на результат :)

По моему опыту, как ни странно, списки в типичных Java приложениях используются именно так, как в моем тесте. В них один раз последовательно добавляют элементы, а потом один или несколько раз по ним итерируются. Этому очень способствует шаблон защитного копирования (когда объект создает личную копию переданного ему в конструкторе списка).

Тест с "перемешанным" списком тоже можно провести, только если его сортировать через Collections.sort, то внутренние узлы в LinkedList останутся в памяти последовательно и мы получим только случайный доступ к памяти хрянящей объекты Integer. Разрыв в производительности между LinkedList и ArrayList в этом случае уменьшится, ибо доминирующим временем будет случайный доступ к памяти с Ingeger-ами (на 1M элементов на моей машине получается 37.20 нс для такого LinkedList против 17.88 нс для ArrayList). Вот тут сразу наглядно видна разница на порядок, которую хотел увидеть raydac, и это при том, что случайных доступ идет только по половине памяти.


При сравнении массива с листом, надо всегда помнить про принцип работы кэша, автопрефетчи и пр. Последовательный доступ по массиву на порядок быстрее листа, особенно после того, как этот лист как следует подергали удалением-добавлением. И это влияет на производительность существенно сильнее, чем размер записи.

Я специально привел в таблице данные для 1M элементов. При таком размере уже не важно кого и когда там дергали -- всё гарантированно читается из памяти.

Автоматический prefectch в обоих случаях будет работать идеально, ибо и там и там последовательная работа с памятью. Причем данные в LinkedList будут организованы одной цепочкой (объекты Integer будут идти чередуясь с Node), а в ArrayList двумя (отдельно массив, отдельно объекты Integer). Но автоматический prefetch в процессорах Intel распознает до 4-х последовательных шаблонов обращения в память (говорю на память -- в datasheet не подглядывал).

Именно, поэтому на 1М элементов видим наиболее близкое к 2-м отношение времени итерации по LinkedList к ArrayList. Все остальные эффекты нивелируются. Важно только как быстро мы можем подчитать данные из памяти. В два раза больше данных читаются ровно в два раза медленней.

Edited at 2011-10-31 08:29 pm (UTC)

Ладно, во избежание еще одной длительной дискуссии оставлю как есть :) Тем более, что я не учел, как организовано хранение данных в ArrayList, подумал про обычный массив.

Кстати, если вы в С/С++ такими вещами пользуетесь, у некоторых компилеров (у Интела точно, у других надо маны листать) есть опция использования 32-битного указателя и лонга в 64-битном режиме (-auto-ilp32). Очень помогает подобным приложениям.

В Java такой режим включается опцией -XX:+UseCompressedOops. Подробное описание можно почитать здесь http://blogs.oracle.com/nike/entry/compressed_object_pointers_in_hotspot

Edited at 2011-11-01 06:19 am (UTC)

И, кстати, не доверяй особо автоматическим префетчам. Вставленные руками или компилятором префетчи легко разгоняют код на ощутимые 10-20% (может меньше, а может и больше, в зависимости от кода).

Это безусловно так, но не отменяет основную мысль: если используешь меньше памяти, то код будет работать быстрей (хоть с автоматическим, хоть с ручным prefetch-ем).

Забыл добавить очень важную вещь: "при прочих равных" :)
Ну и не надо забывать, что бывает код, который висит совсем не на памяти :)

Интересно, что я всё реже и реже сталкиваюсь с кодом, который вист не в памяти, хотя эффективные алгоритмы никто не отменял. Просто про эффективные алгоритмы не так интересно писать -- это классика про которую уже давно написаны сотни книг.

Ну да, у вас же обработка данных, а не вычисления :)
Хотя, даже вычислительные бенчмарки все ближе и ближе к памяти приближаются. Но у них обычно "нормальные" массивы и грамотными префетчами все сглаживается.

  • 1
?

Log in

No account? Create an account