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

в 20:00, , рубрики: java, ram, valhalla-like, оптимизация, Программирование

Идея

В 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 и операции вычисления смещений.

Автор:
RigelGL

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js