Мне было интересно, какие коллекции сколько съедают дополнительной памяти при хранении объектов. Я провёл замеры накладных расходов для популярных коллекций, предполагающих хранение однотипных элементов (то есть списки и множества) и свёл результаты на общий график. Вот картинка для 64-битной Hotspot JVM (Java 1.6):
А вот для 32-битной Hotspot:
Ниже я расскажу, как проводились измерения, а затем попытаемся разобраться, почему картинки выглядят именно так.
Материалы и методы
Измерения проводились для стандартных коллекций Java из java.util и java.util.concurrent, а также для обычного Java-массива. Коллекции IdentityHashSet и ConcurrentHashSet созданы из соответствующих Map с помощью метода Collections.newSetFromMap(). Все коллекции инициализировались по умолчанию без предварительного указания количества элементов (ну кроме массива, для которого это обязательно), а затем заполнялись тестовыми объектами с помощью метода add (а для массива просто выполнялось присваивание). Было создано около 500 коллекций каждого типа с разным количеством элементов от 1 до 10000. В качестве элементов использовались 10000 различных строк случайной длины, состоящих из случайных букв. В принципе сами элементы влияют лишь на ConcurrentHashSet, да и то незначительно, поэтому графики будут выглядеть похожим образом для любых данных.
После заполнения массивов снимался дамп памяти с процесса и анализировался с помощью Eclipse Memory Analyzer, который очень правильно подсчитал Retained set каждой из коллекций, не включив туда сами объекты, а включив только накладные расходы. Выглядит это, например, так:
Ну а дальше копирование в Excel, нехитрые математические действия и построение графика с небольшой дорисовкой в графическом редакторе.
Обсуждение результатов
Видно, что каждая коллекция имеет нижнюю границу накладных расходов и чем больше элементов, тем чаще она оказывается близко к ней. Однако для некоторых коллекций нельзя сказать, что функция накладных расходов сходится к этой границе в математическом смысле. Например, ArrayList хотя всё чаще оказывается у значения 8 байт (для 64bit), но он продолжает прыгать к значению 12 байт при каждом новом выделении памяти.
Интересно, что графики для 32bit и для 64bit очень похожи: для большинства коллекций графики отличаются вдвое кроме двух исключений: ConcurrentSkipListSet и LinkedList. Рассмотрим каждую коллекцию по отдельности и разберёмся, почему для неё график именно такой.
Array
Самый простой вариант — массив, для которого наперёд известно число элементов. В нём на каждый объект хранится ссылка: 4 (8) байт (в скобках значение для 64-битной JVM), кроме того хранится длина массива — int, 4 байта, и дескриптор объекта — 8 (16) байт. Вдобавок каждый объект выравнивается по 8 байтам из-за чего массивы с чётным числом элементов на 32bit теряют по 4 байта. Итог: по 4 (8) байт на объект плюс постоянная от 12 до 24 байт.
Пустой массив занимает 16 (24) байт.
ArrayList
Тут почти то же самое с небольшим отличием: так как заранее число элементов в массиве неизвестно, массив выделяется с запасом (по умолчанию на 10 элементов) и при необходимости расширяется чуть больше, чем в полтора раза:
int newCapacity = (oldCapacity * 3)/2 + 1;
Поэтому график прыгает до 6 (12) байт. Константа также немного больше: 40 (64) байта, так как помимо массива есть ещё сам объект ArrayList, в котором хранится ссылка на массив, фактический размер списка и количество модификаций (для выкидывания ConcurrentModificationException). Тем не менее, это самый экономный способ хранить однотипные данные, если вы заранее не знаете, сколько их будет.
Конструированный по умолчанию ArrayList без элементов занимает 80 (144) байта.
LinkedList
Для связанного списка картинка похожа на массив: стремится к асимптоте по гиперболе. Для каждого элемента списка создаётся по одному служебному объекту типа java.util.LinkedList.Entry. Каждый из этих объектов содержит по три ссылки (на сам элемент списка, на предыдущий и последующий Entry), при этом из-за выравнивания в 32bit теряется по 4 байта, поэтому в итоге требуется 24 (40) байт на каждый Entry. Константа включает в себя дескриптор объекта LinkedList, головной Entry и ссылку на него, размер списка и количество модификаций и равна 48 (80) байт. Столько же занимает пустой список, так как никакой памяти про запас здесь, конечно, не выделяется.
TreeSet
Вообще все используемые множества построены на основе Map. Отдельная реализация в некоторых случаях могла бы быть несколько компактнее, но общий код, конечно, важнее.
График тоже похож на LinkedList и массив. Для каждого элемента создаётся ветвь дерева java.util.TreeMap.Entry, которая содержит пять ссылок: ключ, значение, родитель, левый и правый ребёнок. Кроме них хранится булева переменная, указывающая цвет ветки, красный или чёрный (см. красно-чёрное дерево). Отдельная булева переменная занимает 4 байта, поэтому запись целиком занимает 32 (64) байта.
Постоянные данных в TreeMap такие: ссылка на компаратор, ссылка на корень дерева (в отличие от головоного Entry в LinkedList корень используется по назначению — ссылается на реальный элемент множества), ссылки на entrySet, navigableKeySet, descendingMap (эти объекты создаются по первому требованию), размер и количество модификаций. С дескриптором объекта TreeMap получается 48 (80) байт. Сам TreeSet добавляет только свой дескриптор и ссылку на TreeMap. В сумме выходит 64 (104) байта. Пустое множество весит столько же. Кстати, расход памяти не зависит от степени сбалансированности дерева.
HashSet
HashSet основан на HashMap, который устроен несколько хитрее. Для каждого элемента заводится запись java.util.HashMap.Entry, содержащая ссылки на ключ, значение, следующую Entry (если несколько записей попало в одну ячейку хэш-таблицы), а также само значение хэша. Всего Entry весит 24 (48) байт.
Помимо Entry есть ещё и хэш-таблица, со ссылками на Entry, которая содержит 16 элементов изначально и увеличивается вдвое, когда количество элементов превышает 75% от её размера (75% — это значение loadFactor по умолчанию, его можно указать в конструкторе). То есть при конструировании по умолчанию увеличение таблицы происходит, когда количество элементов превышает 12, 24, 48, 96 и т. д. (2n*3, последний всплеск на графике — 6144 элемента). Сразу после увеличения таблица в 2/0.75=2.67 раз больше числа элементов, то есть полный расход составляет около 34.67 (69.33) байт на элемент (не считая константы). Непосредственно перед увеличением таблица только в 1/0.75=1.33 раза больше числа элементов, и полный расход составляет 29.33 (58.67) байт на элемент. Заметьте, что расход памяти совершенно не зависит от того, насколько часто происходят коллизии хэшей.
Постоянную компоненту желающие могут вычислить сами, я только скажу, что инициализированный по умолчанию пустой HashSet весит 136 (240) байт.
LinkedHashSet
Почти то же самое, что и в HashSet. Используется java.util.LinkedHashMap.Entry, которая наследует java.util.HashMap.Entry, добавляя две ссылки на предыдущий и следующий элементы, поэтому график на 8 (16) байт выше, чем для HashSet, достигая перед расширением таблицы 37.33 (74.67), а после — рекордных 42.67 (85.33). Константа тоже увеличилась, так как наподобие LinkedList хранится головной Entry, который не ссылается на элемент множества. Свежесозданный LinkedHashSet весит 176 (320) байт.
IdentityHashSet (через newSetFromMap)
IdentityHashMap — очень интересная штука. Она нарушает стандартный контракт Map, сравнивая ключи по ==, а не по equals и используя System.identityHashCode. Ещё она интересна тем, что не создаёт объектов вроде Entry, а просто хранит все ключи и значения в одном массиве (ключи в чётных элементах, значения — в нечётных). В случае коллизии она не создаёт список, а записывает объект в первую свободную ячейку по ходу массива. Благодаря этому достигаются рекордно низкие накладные расходы среди всех множеств.
IdentityHashMap увеличивает размер массива вдвое каждый раз, когда он заполнен больше, чем на 2/3 (в отличие от HashMap этот коэффициент не настраивается). По умолчанию массив создаётся на 32 элемента (то есть размер массива 64). Соответственно, расширение происходит при превышении 21, 42, 85, 170 и т. д. ([2n/3], последний всплеск на графике — 5461). Перед расширением массив содержит в 3 раза больше элементов, чем ключей в IdentityHashMap, а после расширения — в 6 раз. Таким образом, накладные расходы составляют от 12 (24) до 24 (48) байт на элемент. Пустое множество по умолчанию занимает довольно много — 344 (656) байт, но уже при девяти элементах становится экономичнее всех прочих множеств.
ConcurrentHashSet (через newSetFromMap)
ConcurrentHashMap — первая коллекция, в которой график зависит от самих элементов (а точнее от их хэш-функций). Грубо говоря, это набор фиксированного числа сегментов (по умолчанию их 16), каждый из которых является синхронным аналогом HashMap. Часть бит из модифицированного хэш-кода используется для выбора сегмента, обращение к разным сегментам может происходить параллельно. В пределе накладные расходы совпадают с накладными расходами самого HashMap, потому что java.util.concurrent.ConcurrentHashMap.HashEntry устроен почти так же, как java.util.HashMap.Entry. Увеличение размера сегментов происходит независимо, потому график не поднимается одномоментно: сперва увеличиваются сегменты, в которые попало больше элементов.
Эта коллекция вышла на первое место по начальному размеру — 1304 (2328) байт, потому что сразу же заводится 16 сегментов, в каждом из которых таблица на 16 записей и несколько вспомогательных полей. Однако для 10000 элементов ConcurrentHashSet превышает размер HashSet всего на 0.3%.
ConcurrentSkipListSet
Реализована через ConcurrentSkipListMap и, на мой взгляд, самая сложная из описанных коллекций. Идея алгоритма была описана на Хабре, поэтому здесь я в детали вдаваться не буду. Замечу только, что результирующий объём памяти здесь не зависит от данных, но при этом недетерменирован, так как коллекция инициируется генератором псевдослучайных чисел. На основании следующего псевдослучайного числа принимается решение, добавлять ли индексную запись и на сколько уровней. На каждый элемент обязательно создаётся один объект java.util.concurrent.ConcurrentSkipListMap.Node, который содержит ссылки на ключ, значение и следующий Node, формируя односвязный список. Это даёт 24 (40) байт на каждый элемент. Кроме того, создаётся примерно одна индексная запись (java.util.concurrent.ConcurrentSkipListMap.Index) на каждые два элемента (на первом уровне есть индекс для каждой четвёртой записи, на втором для каждой восьмой и т. д.). Каждая индексная запись весит столько же, сколько и Node (там тоже три ссылки), поэтому в сумме каждый элемент требует около 36 (60) байт. Есть ещё головные записи для каждого уровня (HeadIndex), но их немного (примерно логарифм от числа элементов), поэтому ими можно пренебречь.
В пустом ConcurrentSkipListSet создаётся один HeadIndex и один пустой Node; после конструирования по умолчанию коллекция занимает 112 (200) байт.
Зачем всё это?
Результаты оказались во многом неожиданными и противоречили моим интуитивным представлениям. Так я считал, что конкуррентные коллекции должны занимать заметно больше, чем обычные, а LinkedHashSet должен располагаться где-то между TreeSet и HashSet. Ещё оказалось удивительно, что практически нигде расход памяти не зависит от самих объектов: степень сбалансированности дерева или количество коллизий в хэш-таблицах ни на что не влияют и для неконкуррентных коллекций можно заранее определить размер накладных расходов с точностью до байта. Было интересно покопаться во внутреннем устройстве разных коллекций. Есть ли в этом исследовании конкретная практическая польза — не знаю, пусть каждый решает сам.
Автор: lany
