Как предотвратить перерасход памяти при использовании Java-коллекций

Original author: Misha Dmitriev
  • Translation
Всем привет!

Наш эксперимент со ступенями по курсу «Разработчик Java» продолжается и, как ни странно, даже вполне успешно (вроде): как оказалось, что плечо планирования в пару месяцев со следующим переходом на новую ступень в любое удобное время — это куда удобнее, чем если выделять практически полгода на такой сложный курс. Так что есть подозрение, что именно сложные курсы мы скоро начнём потихоньку переводить на такую систему.

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

Поехали!



Коллекции в JDK являются стандартными библиотечными реализациями списков и мап. Если вы посмотрите на снимок памяти типичного большого приложения, написанного на Java, вы увидите тысячи или даже миллионы экземпляров java.util.ArrayList, java.util.HashMap и т. д. Коллекции незаменимы для хранения данных и манипулирования ими. Но думали ли вы когда-нибудь о том, все ли коллекции в вашем приложении оптимально используют память? Иначе говоря, если ваше приложение падает с постыдным OutOfMemoryError или вызывает длительные паузы сборщика мусора, проверяли ли вы когда-нибудь использованные коллекции на наличие утечек.

Во-первых, нужно отметить, что внутренние коллекции JDK — это не какая-то магия. Они написаны на Java. Их исходный код поставляется вместе с JDK, поэтому вы можете открыть его в своей IDE. Их код также можно легко найти в интернете. И, как выясняется, большинство коллекций не очень изящны в плане оптимизации объема потребляемой памяти.

Рассмотрим, например, одну из самых простых и самых популярных коллекций — класс java.util.ArrayList. Внутри каждый ArrayList оперирует массивом Object[] elementData. Именно здесь хранятся элементы списка. Посмотрим, как этот массив обрабатывается.

Когда вы создаете ArrayList конструктором по умолчанию, то есть вызываете new ArrayList(), elementData указывает на общий массив нулевого размера (elementData также может быть установлен в null, но массив обеспечивает некоторые незначительные преимущества реализации). Когда вы добавляете первый элемент в список, создается реальный уникальный массив elementData, и предоставленный объект вставляется в него. Для того, чтобы избежать изменения размера массива каждый раз, при добавлении нового элемента, он создается с длиной равной 10 («емкость по умолчанию»). Вот и получается: если вы больше не добавите элементы в этот ArrayList, 9 из 10 слотов в массиве elementData останутся пустыми. И даже если вы очистите список, размер внутреннего массива не сократится. Ниже приведена диаграмма этого жизненного цикла:



Сколько памяти здесь потрачено впустую? В абсолютных значениях она рассчитывается как (размер указателя объекта). Если вы используете JVM HotSpot (который поставляется с Oracle JDK), размер указателя будет зависеть от максимального размера кучи (для более подробной информации см. https://blog.codecentric.de/ru/2014/02/35gb-heap-less-32gb-java-jvm-memory-oddities/). Обычно, если вы укажете -Xmx меньше 32 гигабайт, размер указателя будет составлять 4 байта; для больших куч — 8 байтов. Таким образом, ArrayList, инициализированный конструктором по умолчанию, с добавлением только одного элемента, тратит впустую либо 36, либо 72 байта.

На самом деле, пустой ArrayList тоже тратит память впустую, поскольку он не несет никакой рабочей нагрузки, но размер самого объекта ArrayList не равен нулю и больше, чем вы, вероятно, думаете. Это потому, что, с одной стороны, каждый объект, управляемый JVM HotSpot, имеет 12- или 16-байтовый заголовок, который используется JVM для внутренних целей. Далее, большинство объектов коллекции содержат поле size, указатель на внутренний массив или другой объект “носителя рабочей нагрузки”, поле modCount для отслеживания изменений содержимого и т. д. Таким образом, даже наименьшему возможному объекту, представляющему пустую коллекцию, вероятно, понадобится не менее 32 байт памяти. Некоторые, например ConcurrentHashMap, занимают гораздо больше.

Рассмотрим еще один часто встречающуюся коллекцию — класс java.util.HashMap. Его жизненный цикл аналогичен жизненному циклу ArrayList:



Как вы можете видеть, HashMap, содержащий только одну пару «ключ-значение», тратит 15 внутренних ячеек массива, что соответствует 60 или 120 байтам. Эти цифры невелики, но важны масштабы потерь памяти для всех коллекций в вашем приложении. И получается, что некоторые приложения могут тратить достаточно много памяти таким образом. Например, некоторые популярные компоненты Hadoop с открытым исходным кодом, которые проанализировал автор, теряют около 20 процентов от своей кучи в некоторых случаях! Для продуктов, разработанных менее опытными инженерами, и не подвергающихся регулярному анализу производительности, потери памяти могут быть еще выше. Достаточно случаев, когда, например, 90% узлов в огромном дереве содержат только один или два потомка (или вообще ничего), и другие ситуации, когда куча забита 0-, 1- или 2-элементными коллекциями.

Если вы обнаружили неиспользуемые или малоиспользуемые коллекции в своем приложении, как их исправить? Ниже приведены некоторые распространенные рецепты. Здесь предполагается, что наша проблемная коллекция — ArrayList, на которую ссылается поле данных Foo.list.

Если большинство экземпляров списка никогда не используются, попробуйте инициализировать его лениво. Таким образом, код, который ранее выглядел как…

void addToList(Object x) {
    list.add(x);
}

… должен быть переделан в нечто вроде

void addToList(Object x) {
 getOrCreateList().add(x);
}
private list getOrCreateList() {
   // Чтобы сохранить память, мы не создаем список до его первого использования
   if (list == null) list = new ArrayList();
   return list;
}

Имейте в виду, что вам иногда потребуется принять дополнительные меры для решения возможных конкуренций. Например, если вы поддерживаете ConcurrentHashMap, который может быть обновлен несколькими потоками одновременно, код, который инициализирует его отложено, не должен позволять двум потокам создавать две копии этой мапы случайно:

private Map getOrCreateMap() {
   if (map == null) {
       //Удостоверимся, что другой поток не опережает нас
       synchronized (this) {
           if (map == null) map = new ConcurrentHashMap();
       }
   }
   return map;
}

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

list = new ArrayList(4); // Внутренний массив будет создан с длиной 4

Если ваши коллекции пусты или содержат только один элемент (или пару «ключ-значение») в большинстве случаев, вы сможете рассмотреть одну крайнюю форму оптимизации. Она работает только в том случае, если коллекция полностью управляется в пределах текущего класса, то есть другой код не может получить к нему доступ напрямую. Идея состоит в том, что вы меняете тип своего поля данных, например, из List в более общий Object, чтобы теперь он мог указывать либо на реальный список, либо непосредственно на единственный элемент списка. Вот краткий эскиз:

// *** Старый код ***
private List<Foo> list = new ArrayList<>();
void addToList(Foo foo) { list.add(foo); }
// *** Новый код ***
// Если список пуст, это значение равно null. Если список содержит только один элемент,
// он указывает прямо на этот элемент. В противном случае он указывает на
// реальный объект ArrayList.

private Object listOrSingleEl;
void addToList(Foo foo) {
   if (listOrSingleEl == null) { // Пустой список
       listOrSingleEl = foo;
   } else if (listOrSingleEl instanceof Foo) { // Одноэлементный
       Foo firstEl = (Foo) listOrSingleEl;
       ArrayList<Foo> list = new ArrayList<>();
       listOrSingleEl = list;
       list.add(firstEl);
       list.add(foo);
   } else { // Реальный список со множеством элементов
       ((ArrayList<Foo>) listOrSingleEl).add(foo);
   }
}

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

Вы вероятно уже задумались: откуда же я узнаю, какие коллекции в моем приложении перерасходуют память и сколько?

Если коротко: это трудно узнать без правильных инструментов. Попытка угадать объем используемой или потраченной структурами данных памяти в большом сложном приложении почти никогда ни к чему не приведёт. И, не зная точно, куда уходит память, вы можете потратить много времени в погоне за неправильными целями, в то время как ваше приложение упорно продолжает падать с OutOfMemoryError.

По этому, вам следует проверить кучу приложения с помощью специального инструмента. По опыту, наиболее оптимальным способом анализа памяти JVM (измеряется как количество доступной информации в сравнении с воздействием этого инструмента на производительность приложения) — это получить дамп кучи, а затем просмотреть его в автономном режиме. Дамп кучи — это, по сути, полный снимок кучи. Его можно получить в любой момент, вызвав утилиту jmap, либо можно настроить JVM для автоматического создания дампа, если приложение падает с OutOfMemoryError. Если вы загуглите «дамп кучи JVM», вы сразу увидите большое количество статей, в которых подробно объясняется, как получить дамп.

Дамп кучи — это двоичный файл размером с кучу JVM, поэтому его можно читать и анализировать только с помощью специальных инструментов. Существует несколько таких инструментов, как с открытым исходным кодом, так и коммерческие. Наиболее популярным инструментом с открытым исходным кодом является Eclipse MAT; есть также VisualVM и некоторые менее мощные и менее известные инструменты. Коммерческие инструменты включают профилировщики Java общего назначения: JProfiler и YourKit, а также один инструмент, созданный специально для анализа дампа кучи — JXRay (дисклеймер: последнее разработал автор).

В отличие от других инструментов, JXRay сразу анализирует дамп кучи на наличие большого количества распространенных проблем, таких как повторяющиеся строки и другие объекты, а также недостаточно эффективные структуры данных. Проблемы с описанными выше коллекциями относятся к последней категории. Инструмент генерирует отчет со всей собранной информацией в формате HTML. Преимущество такого подхода заключается в том, что вы можете просматривать результаты анализа в любом месте в любое время и легко делиться ими с другими. Вы также можете запускать инструмент на любой машине, включая большие и мощные, но «безголовые» машины в центре обработки данных.

JXRay вычисляет оверхэд (сколько памяти вы сэкономите, если избавитесь от конкретной проблемы) в байтах и в процентах от используемой кучи. Он объединяет коллекции одного и того же класса, которые имеют одинаковую проблему…



… и затем группирует проблемные коллекции, которые доступны из некоторого корня сборщика мусора через одну и ту же цепочку ссылок, как в примере ниже



Знание о том, какие цепочки ссылок и/или отдельные поля данных (например, INodeDirectory.children выше) указывают на коллекции, которые тратят большую часть памяти, позволяет быстро и точно определить код, который отвечает за проблему, а затем внести необходимые изменения.

Таким образом, недостаточно эффективно настроенные Java-коллекции могут тратить много памяти. Во многих ситуациях эту проблему легко решить, но иногда вам может потребоваться изменить свой код нетривиальными способами для достижения значительного улучшения. Очень сложно угадать, какие коллекции нужно оптимизировать, чтобы оказать наибольшее влияние. Чтобы не тратить время на оптимизацию не тех частей кода, вам нужно получить дамп кучи JVM и проанализировать его с помощью соответствующего инструмента.

THE END

Нам, как всегда, интересны ваши мнения и вопросы, которые вы можете оставить тут или заскочить на открытый урок и поспрашивать наших преподавателей там.
OTUS
Цифровые навыки от ведущих экспертов

Comments 21

    +4

    Память не тратится, как вы выразились, «в пустую», изначальный размер задается для динамической амортизации размера массивов:
    https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

      +2

      Есть еще одна реализация списка: LinkedList. В нем используется двусвязный список вместо динамического массива. Казалось бы, если нам не нужно часто брать элемент списка по индексу, то выбор очевиден.


      Но не тут-то было, если говорить о расходах по памяти

      image

        +1
        Очевидно, что LinkedList имеет дополнительные накладные расходы по памяти, на хранение ссылок на следующий/предыдущий элемент. Выбор в пользу LinkedList очевиден, когда в коде используются частые операции вставки/удаления. Сложность вставки в случае LinkedList константная, а случае динамического массива пропорциональна количеству элементов массива, но в этой статье ничего не говорится об алгоритмической сложности методов работы с «коллекциями». Память очень важный критерий, но далеко не первый при выборе структуры данных.
          0

          Спасибо за более развернутый ответ. Хотелось просто несколько успокоить читателей и показать, что не все так плохо с ArrayList или HashMap, как может показаться из этой статьи.

            0
            Только при вставках в голову/хвост
              0
              Выбор в пользу LinkedList очевиден, когда в коде используются частые операции вставки/удаления.

              Если это удаление, то легче написать обёртку, которая будет использовать внутри ArrayList и помечать удалённые элементы как null.


              Если вставка в начало, то легче написать обёртку в которой несколько ArrayList и при необходимости добавить что-то — можно просто сделать новый ArrayList и считать его элементы начальными.


              И только если вставка проводится в произвольные места во время итерации по листу и удаление проходит в этом же режиме — вот тут в LinkedList есть какой-то смысл. Да и то...

              +1
              При интенсивной аллокации и без G1 LinkedList еще и фрагментирует память
                0
                Сам создатель linkedlist намекнул что он «не нужен»: Does anyone actually use LinkedList? I wrote it, and I never use it. twitter.com/joshbloch/status/583813919019573248
                У Шипилёва кажется был разбор почему у ЛинкедЛиста нету ни одного юзкейса.
                  0
                  Если говорить безотносительно java, в реальном мире есть несколько применений связанных списков (linked list), первое что приходит в голову, например, реализация malloc в C, в который выделяет блоки памяти различного размера и организованы они в виде связанного списка. Второе, это хэш-таблицы, у которой в случае коллизий элементы объединяют в связанный список, кроме этого при помощи связанного списка достаточно просто реализуется очередь или стек. В действительности джавовская реализация LinkedList имеет очень ограниченное применение из-за того, что нет возможности работать с узлом списка (ListNode). Например, в .net вставка/удаление может производиться не только в голову или хвост, но и перед/после любого узла (node) списка, что несколько расширяет возможности использования связанных списков.
                    0
                    Второе, это хэш-таблицы, у которой в случае коллизий элементы объединяют в связанный список

                    А ведь в Джаве вместо списка можно было положить туда массив и существенно сэкономить память и немного увеличить скорость.


                    кроме этого при помощи связанного списка достаточно просто реализуется очередь или стек

                    Очередь или стек это структуры где нет вставки в середине. Тут массив просто великолепен.


                    В действительности джавовская реализация LinkedList имеет очень ограниченное применение из-за того, что нет возможности работать с узлом списка (ListNode)

                    Джавовская реализация LinkedList жрёт раз в 6 больше памяти чем ArrayList и сборщик мусора вынужден бегать по всем узлам LinkedList. Вот поэтому её и не применяют особенно. А работать с узлом списка можно с помощью итераторов.


                    Например, в .net вставка/удаление может производиться не только в голову или хвост, но и перед/после любого узла (node) списка

                    B Java тоже можно вставить куда угодно в любой момент.

                      0
                      А ведь в Джаве вместо списка можно было положить туда массив и существенно сэкономить память и немного увеличить скорость.
                      В текущей реализации используется именно список. Массив бы ничего не сэкономил, а ровно наоборот, попробуйте реализовать свою версию, поймете.
                      Очередь или стек это структуры где нет вставки в середине. Тут массив просто великолепен.
                      Особенно при вставке в начало ;). Да, при реализациях стека/очереди используют именно массив для организации циклического буфера с указателями на начало и конец элементов в буфере.
                      Джавовская реализация LinkedList жрёт раз в 6 больше памяти чем ArrayList и сборщик мусора вынужден бегать по всем узлам LinkedList. Вот поэтому её и не применяют особенно. А работать с узлом списка можно с помощью итераторов.
                      Хорошо что в java нет типов с семантикой значения, поскольку для связанных списков конечно же лучше подходят большие структуры данных, в случае использования массивов таких структур затраты на копирования убили бы производительность. Со ссылочными типами все несколько проще, потому в java LinkedList совсем непопулярен.
                      B Java тоже можно вставить куда угодно в любой момент.
                      Если я не ошибаюсь, в текущей реализации вставка add(int index, T element) связана с поиском, а это O(n)
                        0
                        В текущей реализации используется именно список.

                        Если точнее, то в текущей реализации список сделан прямо на месте. Структура Node объявлена внутри HashMap. LinkedList там не использутся.


                        Массив бы ничего не сэкономил, а ровно наоборот, попробуйте реализовать свою версию, поймете.

                        В массиве на каждый элемент приходится 8 байт. В LinkedList на каждый элемент приходится 8 байт на указатель на элемент, 8 байт на указатель на следующий узел, 8 байт на указатель на предыдущий узел и 16 байт оверхеда на объект Node.


                        Итого на один элемент в LinkedList приходится в 5 раз больше места, чем в массиве. В HashMap ссылки на предыдущие элементы нет, поэтому тут разница в 4 раза. Вот такая экономия. Если вы объясните как использование массива может привести к обратному — пожалуйста объясните.


                        Если я не ошибаюсь, в текущей реализации вставка add(int index, T element) связана с поиском, а это O(n)

                        Это не в текущей реализации, это во всех реализациях на всех языках. Если хочешь вставить элемент в произвольное место — получится O(n). Причём что в связном списке, что в динамическом массиве.


                        Но если ты перебираешь элементы и тебе надо вставить что-то после текущего, то в связном списке это O(1), потому что до нужного элемента ты уже добрался.

                          0
                          а если быть ещё точнее — начиная с 8ки (или 7ки?) — то если уровень коллизий больше некоторого числа (8-10) и ключ Comparable — то там будет вообще красно-чёрное дерево!
                            0

                            Уточнять вообще можно достаточно долго. В частности, ключ не должен быть Comparable. HashMap может построить дерево из чего угодно )).


                            Кроме того, код для дерева, которое строит HashMap — тоже весь внутри класса HashMap. Это к слову на тему переиспользования кода, абстракций всяких и всего такого.

                +1
                Я бы поспорил про ленивую инициализацию ArrayList / HashMap — начиная с какого-то билда 8ки — с конструктором по-умолчанию они внутри пустые — т.е расход только идёт на объект-обёртку (16байт?) но нет головных болей с null-reference и прочим усложнением lazy initialization.

                Если уж так хочется экономить на спичках — то стоит ещё вспомнить про autoboxing — и что это ещё тот overhead — как по памяти, так и по производительности (derefence тоже не бесплатный) — и есть для этого специализированные коллекции — trove, koloboke, eclipse collections etc.

                И самое главное, что кажется тут возможно подразумевается, но упущено — можно было сделать ArrayList, который бы всегда ужимался — но тогда будет страдать производительность, можно использовать TreeMap вместо HashMap (что фактически сделано в c++ с std::map) — это разумный trade-off — вы уж выбирайте — шашечки или ехать.

                Согласен, что если так сильно запаривает память — то выделяй для ArrayList размер (если он известен), после можно делать trimToSize, или вызывать copy-ctor — это и для ArrayList/HashMap/CHM/HashSet и т.п справедливо.
                  +1
                  Делать new ArrayList(size) при заранее прогнозируемом размере коллекции уже не модно?
                    0
                    Есть еще одна беда с ArrayList. Постоянное добавление эелементов реаллоцирует память, что приводит к неизбезной сегментации и резервации следующей кучи менеджером памяти. В итоге менеджер не может найти нужного куска, хотя пустых фрагментированных сегментов достаточно. В многопоточных нагруженных системах это приводит к полной аккупации CPU GC и ошибкам нехватки памяти. То есть свободные зарезервированные куски не такая уж и большая проблема, хотя может быть это частная беда конкретного проекта. Людям привыкшим к нативному управлению памятью, к которым я отношусь, проблема видится нерешаемой и требующей архитектурных изменений.
                      0
                      Работа GC обычно разбита на несколько этапов:
                      1. Помечает недоступные объекты (marking)
                      2. Удаление помеченных объектов (deletion)
                      3. Уплотнение кучи (heap compaction)

                      на все это необходимы определенные процессорные ресурсы и желательно отсутствие закрепленных (pinned) объектов. При любом подходе к управлению памятью следует избегать ненужных операций выделения памяти, за это придется рано или поздно заплатить. Просто наличие GC скрывает много важных деталей, ну и в конечном итоге позволяет среднему программисту относительно качественно управлять памятью, т.е. не задумываться об этом
                        0
                        Это актуально только для маленьких проектов. Любой более-менее сложный многопоточный проект рано или поздно упадет с нехваткой памяти. Надеяться на GC можно только до определенного времени. Дальше нужно переосмысливать архитектуру. Ява тут беспомощна, ничего не поделать. Как пример JMeter, который обязательно упадет в какой-то момент времени.
                          +2
                          Только не говорите такого на собеседованиях. Не возьмут же. За абсолютное непонимание платформы с которой работать собираетесь.
                            0
                            Не знаю что там сейчас спрашивают на собеседованиях. Мне это мало интересно. Мы будем дальше писать поделки с моим мнением а маркетинг продолжит продавать их другим непонимающим.

                    Only users with full accounts can post comments. Log in, please.