Java: делаем Valhalla сами

Идея

В Java каждый объект — это заголовок и данные. В случае 64 битной машины заголовок равен 16 байтам. Также Java использует выравнивание объектов в памяти по 8 байт, следовательно размер объекта кратен 8 байтам. Поэтому обёртки примитивных типов такие как Integer, Double занимают по 24 байта, что весьма затратно для примитивных типов.

Проблема

Объекты в Java располагаются в куче, ссылки на них лежат в List<?>, в результате для int мы получаем 28 байт (если используется сокращение ссылок) вместо 4 и возможный разброс адресов объектов по памяти.

Для оптимизации JVM заранее инициализирует Boolean, Byte, некоторую часть значений Integer, чтобы свести затраты по памяти до 4 байт на переменную.

Решение

Посмотрим на проблему иначе: большая часть, а зачастую и весь заголовок объекта в случае таких классов не используется, поэтому логично от него избавиться, если нужно сэкономить память.

Создадим массив байт, в который будем сохранять значение примитивных типов (boolean, byte, short, char, int, float, long, double) объекта.

При взятии объекта по индексу будем создавать новый объект и записывать в него значения полей.

Реализация

Полный код доступен на github, в статье приведены сокращённые функции для пояснения принципов работы.

Работать будем через Unsafe, возможно работать через Reflect, но с ним скорость ниже на 20-30%.

Получим экземпляр Unsafe:

private static final Unsafe unsafe;  static {     try {         Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");         theUnsafe.setAccessible(true);         unsafe = (Unsafe) theUnsafe.get(null);     } catch (Exception e) {       throw new AssertionError(e);     } } 

Получим информацию о нестатичных полях объекта:

private List<Field> getCorrectFields(Class<?> clazz) { List<Field> correctFields = new ArrayList<>(); for(Field f : clazz.getDeclaredFields()) {     // игнорируем статичные поля     if((f.getModifiers() & 8) == 0)       correctFields.add(f);   }   return correctFields; }

Сохраним структуру объекта. В массив fieldOffsets сохраним offset поля, нужный для работы Unsafe, а в массив fieldTypes его тип, для оптимизации сборки/разборки объекта.

private final byte[] fieldTypes; private final long[] fieldOffsets; private int objectByteSize;   private void initFields(List<Field> correctFields) {   for(int i = 0; i < fieldTypes.length; i++) {         Field f = correctFields.get(i);         fieldOffsets[i] = unsafe.objectFieldOffset(f);         f.setAccessible(true);                if(f.getType() == boolean.class) {           fieldTypes[i] = TYPE_BOOLEAN;           objectByteSize += 1;         }         else if(f.getType() == int.class) {           fieldTypes[i] = TYPE_INT;           objectByteSize += 4;         }     } }

Здесь всё тривиально, в массив fields записываем сами поля, в fieldTypes их тип (байт от 0 до 7), параллельно считаем размер объекта в байтах.

Для создания пустого объекта в памяти потребуется функция:

private Object buildNewObject() throws Exception {       return unsafe.allocateInstance(clazz); }

На этом этапе мы можем узнать размер объекта в байтах и знаем число объектов, которые собираемся хранить. Запросим у системы память в конструкторе:

// полный код конструктора public MemoryEfficientList(Class<?> clazz, int size) {   this.clazz = clazz;   List<Field> correctFields = getCorrectFields(clazz);      fieldTypes = new byte[correctFields.size()];     fieldOffsets = new long[correctFields.size()];    initFields(correctFields);        dataSize = size;   // указатель на память     dataAddress = unsafe.allocateMemory(objectByteSize * size);      try {         // объекты для оптимизаций         firstFast = buildNewObject();         secondFast = buildNewObject();         fastInternal = buildNewObject();         oldValue = buildNewObject();     } catch(Exception ignored) {     } }

unsafe.allocateMemory возвращает указатель, поэтому с ним возможны классические операции низкоуровневой работы с памятью, например unsafe.getInt(dataArray + byteOffset) вернёт 4 байта по адресу dataArray + byteOffset.

Для сохранения объектов нужно преобразовывать его в байты и сохранять по указанному индексу:

private void decomposeObject(int pos, Object object) {         int offset = pos * objectByteSize;          for(int i = 0; i < fieldTypes.length; i++) {             long fo = fieldOffsets[i];              switch(fieldTypes[i]) {                 case TYPE_BOOLEAN: {                     unsafe.putByte(dataAddress + offset,                                     (byte) (unsafe.getBoolean(object, fo) ? 1 : 0));                     offset += 1;                     break;                 }                  case TYPE_INT: {                     unsafe.putInt(dataAddress + offset, unsafe.getInt(object, fo));                     offset += 4;                     break;                 }             }         }     }

Обратная операция, сборка объекта из байт:

private void composeObject(int pos, Object object) {         long offset = pos * objectByteSize;          for(int i = 0; i < fieldTypes.length; i++) {             long fo = fieldOffsets[i];             switch(fieldTypes[i]) {                 case TYPE_BOOLEAN: {                     unsafe.putBoolean(object, fo,                                        unsafe.getByte(dataAddress + offset) == 1);                     offset += 1;                     break;                 }                                  case TYPE_INT: {                     unsafe.putInt(object, fo, unsafe.getInt(dataAddress + offset));                     offset += 4;                     break;                 }             }         }     }

Операция добавления объекта в массив:

public boolean add(Object o) {     // добавляем объект в конец массива     decomposeObject(size, o);     size += 1;     return true; }

Извлечение объекта из массива:

public Object get(int index) {     // в функциях getFast и getFast2 вместо создания     // нового объекта используется заранее созданные     // объекты: firstFast и secondFast     Object result = buildNewObject();     composeObject(index, result);     return result; }

Удаление объекта по адресу:

public Object remove(int index) {         composeObject(index, oldValue);          final int newSize = size - 1;          if(newSize > index)             unsafe.copyMemory((index + 1) * objectByteSize,                                index * objectByteSize,                                (newSize - index) * objectByteSize);            size = newSize;         return oldValue;     }

Тесты

Перейдём к тестам производительности.

Конфигурация оборудования:

Без скобок указано минимальное время теста в секундах, в скобках среднее.

MEL = MemoryEfficientList

Тест 0, добавление N int в массив. Массив создаётся сразу под все элементы. int[] добавлен для сравнения.

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

Тест 1, заполняем массив из N значений int, затем N раз меняем местами 2 случайных числа, для проверки считаем чек сумму.

for(int i = 0; i < n; i++)   al.add(r.nextInt());  for(int i = 0; i < n; i++) {     int pos1 = r.nextInt(n);     int pos2 = r.nextInt(n);     Integer a = al.get(pos1);     Integer b = al.get(pos2);     al.set(pos1, b);     al.set(pos2, a); }

Экономия по памяти на объект: 24 байта. 4 / 28 = 14% от потребления памяти ArrayList<Integer>.

Тест 2, решето Эратосфена, поиск простых чисел от 1 до N

for(int i = 0; i < n; i++)     alIs.add(true);     alIs.set(0, false);     alIs.set(1, false);     for(int i = 0; i < n; i++) {         if(alIs.get(i) && i * i > 0) {             for(int j = i * i; j < n; j += i)               alIs.set(j, false);             alResult.add(i);       } }

Экономия по памяти: 4 байта (ссылка в ArrayList) против 1 байта в MEL = 25% от исходного размера без учёта разницы в объёме занимаемом массивом результирующих чисел.

Тест 3, аналогичен первому тесту, но вместо Integer будет Vec3{float x, y, z}.

На этом тесте разница становится менее заметной.

Экономия по памяти: 12 байт против 32 + 4 = 33% от объёма ArrayList.

Тест 4, аналогичен первому, но вместо Integer используется следующий объект:

public class LargeObject {     boolean x, y, z, w;     int i, j, k;     float a, b, c, d, e;     double g, h;     long m, n, o, p; }  // 84 байта

Здесь MEL проигрывает ArrayList, так как нужно свапать 84 байта, вместо 4.

Экономия по памяти: 84 + 16 + 4 (выравнивание) + 4 / 84 = 77% от размера ArrayList.

Так при регулярном извлечении и вставке объектов размер объекта, на котором будет прирост производительности ограничен ~20 байтами.

Также MEL показывает очень низкую производительность операции toArray, так как по сути создаёт N новых объектов на куче. Эта операция используется в Collections.sort, поэтому для MEL нужно реализовывать свой метод сортировки.

Выводы

Предположение об оптимизации скорости работы с памятью за счёт упорядочивания данных и уменьшения объёма данных оказалось верным. Прирост составляет 20-60% в зависимости от типа объекта и задачи. Если объекты большие (больше 20 байт данных) то разумнее использовать ArrayList.

В текущей реализации есть основные методы работы с коллекцией: добавление, удаление, изменение элемента. На остальные методы поставлены заглушки.

Дальнейшая оптимизация возможна за счёт оптимизации функций compose/decomposeObject. Сейчас используется цикл, вместо него можно генерировать байт код, который развернёт цикл в линейный набор команд, уберёт switch-case и операции вычисления смещений.