Положите свои жирные коллекции на диету!

Фон

В каждой Java-программе используются какие-то структуры данных, будь то простой массив, куча Фибоначчи или даже что-то более экзотическое, о чем знает только поиск Google. В большинстве случаев разработчики не пишут свои собственные реализации этих структур, а используют либо те, которые предоставляются базовыми API-интерфейсами Java, либо некоторые сторонние библиотеки, такие как Apache Collections или Google Guava. За мои 10 с лишним лет разработки Java не прошло и дня, чтобы я не использовал некоторую структуру данных из API Java Collection. Эти списки, наборы и карты настолько естественны для меня, что я не колеблясь ни секунды, прежде чем писать 

Map<Integer, String> = new HashMap<Integer, String>(); 

И все было хорошо до недавнего времени …

Один из классов внутри нашего Java-агента Plumbr должен хранить целое число целых чисел как одно из его полей. Полуформальные требования заключаются в следующем:

• Нам нужна структура данных для хранения целых чисел.
• Без дубликатов
• Заказ не важен
• Нам нужно добавить в эту структуру новые элементы
• Нам нужно посмотреть, если какой-то элемент существует в этой структуре
• Количество различных элементов ограничено до пары сотен максимум
• Потребление памяти важнее скорости
• Тем не менее, производительность должна быть достойной, поэтому файлы MemoryMapped, базы данных и т. Д. Не обсуждаются.

Естественным выбором для этого требования является, по крайней мере, учитывая мой опыт, java.util.HashSet <Integer> . Итак, недолго думая, я попробовал. Это была катастрофа!

эксперимент

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

1. Напишите класс Java с методом main , который содержит необходимую структуру данных в качестве локальной переменной.
2. Добавьте бесконечный цикл в конец этого основного метода, чтобы этот поток не умер слишком быстро.
3. Используя Eclipse Memory Analyzer, возьмите дамп памяти и выясните размер оставшейся кучи для интересующей локальной переменной.

В качестве основы я использовал тот факт, что в Java целое число занимает 4 байта. Итак, для  числа COUNT целых чисел нам нужно 4 * байта COUNT . Затем мы можем рассчитать накладные расходы данной структуры данных следующим образом:

Overhead = Structure's retained heap/(4*COUNT)

Обратите внимание, что Java различает примитивы и объекты, а API-интерфейс Collection работает только с объектами. Это означает, что общие накладные расходы состоят из накладных расходов данной структуры данных коллекции и накладных расходов на использование объектов Integer, а не примитивов.

Полученные результаты

Set<Integer> set = new HashSet<Integer>();
int COUNT = 10;
for (int i = 0; i < COUNT; i++) {
  set.add(i);
}

int COUNT = 10;
Integer[] array = new Integer[COUNT];
for (int i = 0; i < COUNT; i++) {
    array[i] = i;
} 

Все идет нормально. Это сократило накладные расходы в 2-3 раза по сравнению с
HashSet . Но он все еще слишком большой на мой вкус. Поэтому я просто заменил Integer [] на int []:

int COUNT = 10; 
int[] array = new int[COUNT];
for (int i = 0; i < COUNT; i++) {
    array[i] = i;
}

и получил:

Вывод