Идея
В 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;
}Тесты
Перейдём к тестам производительности.
Конфигурация оборудования:
CPU | Intel Core i7 7600 |
RAM | 12GB, 2400 MHz |
JVM | OpenJDK 13.0.2, windows |
Без скобок указано минимальное время теста в секундах, в скобках среднее.
MEL = MemoryEfficientList
Тест 0, добавление N int в массив. Массив создаётся сразу под все элементы. int[] добавлен для сравнения.
N | ArrayList | MEL | int[] |
10 000 000 | 0.18 (0.27) | 0.15 (0.22) | 0.09 (0.10) |
1 000 000 | 0.019 ( 0.037) | 0.015 (0.023) | 0.01 (0.01) |
В дальнейших тестах массивы не пересоздаются, это значит не тратится время на увеличение размера массива (его размер неизменен после первого прохода, результат которого игнорируется).
Тест 1, заполняем массив из N значений int, затем N раз меняем местами 2 случайных числа, для проверки считаем чек сумму.
Код для ArrayList
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);
}N | ArrayList<Integer> | MEL | MEL + getFast |
10 000 000 | 2.51 (2.99) | 1.61 (1.86) | 1.56 (1.73) |
1 000 000 | 0.17 (0.19) | 0.07 (0.09) | 0.06 (0.08) |
Экономия по памяти на объект: 24 байта. 4 / 28 = 14% от потребления памяти ArrayList<Integer>.
Тест 2, решето Эратосфена, поиск простых чисел от 1 до N
Код для ArrayList
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);
}
}N | ArrayList | MEL | MEL + getFast |
10 000 000 | 1.00 (1.05) | 0.40 (0.41) | 0.37 (0.39) |
1 000 000 | 0.035 (0.047) | 0.030 (0.040) | 0.023 (0.036) |
Экономия по памяти: 4 байта (ссылка в ArrayList) против 1 байта в MEL = 25% от исходного размера без учёта разницы в объёме занимаемом массивом результирующих чисел.
Тест 3, аналогичен первому тесту, но вместо Integer будет Vec3{float x, y, z}.
N | ArrayList | MEL | MEL + getFast |
10 000 000 | 2.24 (2.40) | 1.87 (1.91) | 1.67 (1.71) |
1 000 000 | 0.16 (0.18) | 0.15 (0.16) | 0.13 (0.14) |
На этом тесте разница становится менее заметной.
Экономия по памяти: 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 байтаN | ArrayList | MEL | MEL + getFast |
10 000 000 | 2.53 (2.64) | 5.81 (5.94) | 5.09 (5.59) |
1 000 000 | 0.15 (0.16) | 0.53 (0.56) | 0.47 (0.48) |
Здесь 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 и операции вычисления смещений.
