Как не мусорить в Java

Существует популярное заблуждение о том, что если не нравится garbage collection, то надо писать не на Java, а на C/C++. Последние три года я занимался написанием low latency кода на Java для торговли валютой, и мне приходилось всячески избегать создания лишних объектов. В итоге я сформулировал для себя несколько простых правил, как свести аллокации в Java если не до нуля, то до некого разумного минимума, не прибегая к ручному управлению памятью. Возможно, кому-то из сообщества это тоже будет полезно.

Зачем вообще избегать создания мусора

О том, какие есть GC и как их настраивать говорилось и писалось много. Но в конечном счете как ни настраивай GC — код, который мусорит, будет работать субоптимально. Всегда возникает компромисс между throughput и latency. Становится невозможно улучшить одно не ухудшив другое. Как правило накладные расходы GC измеряют изучая логи — по ним можно понять в какие моменты были паузы и сколько времени они занимали. Однако в логах GC содержится далеко не вся информация об этих накладных расходах. Объект, созданный потоком, автоматически помещается в L1 кэш ядра процессора, на котором выполняется данный поток. Это приводит к вытеснению оттуда других потенциально полезных данных. При большом количестве аллокаций полезные данные могут быть вытеснены и из L3 кэша. Когда в следующий раз поток будет обращаться к этим данным произойдет кэш мисс, что приведет к задержкам в исполнении программы. Более того, так как L3 кэш является общим для всех ядер в пределах одного процессора, мусорящий поток будет выталкивать из L3 кэша данные и других потоков/приложений, и уже они будут сталкиваться с лишними дорогостоящими кэш миссами, даже если сами они написаны на голом С и мусор не создают. Никакие настройки никаких garbage collector’ов (ни C4, ни ZGC) не помогут справиться с этой проблемой. Единственный способ улучшить ситуацию в целом — это не создавать лишние объекты без надобности. Java в отличие от C++ не имеет богатого арсенала механизмов работы с памятью, но тем не менее есть ряд способов, позволяющих свести аллокации к минимуму. О них и пойдет речь.

Использование примитивных типов

Самое простое, что можно сделать во многих случаях — это использовать примитивные типы вместо объектных. В JVM есть ряд оптимизаций, позволяющих свести к минимуму накладные расходы объектных типов, например кэширование маленьких значений целочисленных типов и инлайнинг простых классов. Но на эти оптимизации не всегда стоит полагаться, потому что они могут и не отработать: целочисленное значение может быть не быть закешированным, а инлайнинг может не произойти. Более того, при работе с условным Integer’ом мы вынуждены переходить по ссылке, что потенциально приводит к кэш миссу. Так же у всех объектов есть заголовки, которые занимают лишнее место в кэше, вытесняя оттуда другие данные. Давайте считать: примитивный int занимает 4 байта. Объектный Integer занимает 16 байт + размер ссылки на этот Integer 4 байта минимум (в случае compressed oops). В сумме получается, что Integer занимает в пять (!) раз больше места, чем int. Поэтому лучше собственноручно использовать именно примитивные типы. Приведу несколько примеров.

Пример 1. Обычные вычисления

Допустим, у нас есть обычная функция, которая просто что-то считает.

Integer getValue(Integer a, Integer b, Integer c) {
   return (a + b) / c;
}

Такой код скорее всего заинлайнится (и метод и классы) и не приведет к лишним аллокациям, но быть уверенным в этом нельзя. Даже если это произойдет, останется проблема с тем, что отсюда может вылететь NullPointerException. JVM так или иначе должна будет либо вставлять проверки на null под капотом, либо каким-то образом понять из контекста, что null в качестве аргумента прийти не может. Так или иначе, лучше просто написать этот же код на примитивах.

int getValue(int a, int b, int c) {
   return (a + b) / c;
}

Пример 2. Лямбды

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

void calculate(Consumer<Integer> calculator) {
   int x = System.currentTimeMillis();
   calculator.accept(x);
}

Несмотря на то, что переменная x является примитивом, будет создан объект типа Integer, который будет передан в calculator. Чтобы этого избежать, надо использовать IntConsumer вместо Consumer<Integer>:

void calculate(IntConsumer calculator) {
   int x = System.currentTimeMillis();
   calculator.accept(x);
}

Такой код уже не приведет к созданию лишнего объекта. В java.util.function есть целый набор стандартных интерфейсов, адаптированных для использования примитивных типов: DoubleSupplier, LongFunction и т.д. Ну а если чего-то не хватает, то всегда можно добавить нужный интерфейс с примитивами. Например вместо BiConsumer<Integer, Double> можно использовать самодельный интерфейс.

interface IntDoubleConsumer {
    void accept(int x, double y);
}

Пример 3. Коллекции

Использование примитивного типа может быть затруднено тем, что переменная этого типа лежит в некой коллекции. Предположим, что у нас есть некий List<Integer> и мы хотим узнать, какие числа в нем имеются и посчитать, сколько раз каждое из чисел повторяется. Для этого мы используем HashMap<Integer, Integer>. Код выглядит так:

List<Integer> numbers = new ArrayList<>();
// fill numbers somehow
Map<Integer, Integer> counters = new HashMap<>();
for (Integer x : numbers) {
    counters.compute(x, (k, v) -> v == null ? 1 : v + 1);
}

Этот код плох сразу по нескольким параметрам. Во-первых, он использует промежуточную структуру данных, без которой наверняка можно было бы обойтись. Ну да ладно, для простоты будем считать, что этот список потом чего-то понадобится, т.е. совсем его убрать нельзя. Во-вторых, в обоих местах используются объектный Integer вместо примитивного int. В-третьих, происходит множество аллокаций в методе compute. В четвертых, происходит аллокация итератора. Эта аллокация скорее всего заинлайнится, но тем не менее. Как превратить этот код в garbage free код? Нужно просто использовать коллекцию на примитивах из некой сторонней библиотеки. Есть целый ряд библиотек, содержащих такие коллекции. Следующий кусок кода использует библиотеку agrona.

IntArrayList numbers = new IntArrayList();
// fill numbers somehow
Int2IntCounterMap counters = new Int2IntCounterMap(0);
for (int i = 0; i < numbers.size(); i++) {
    counters.incrementAndGet(numbers.getInt(i));
}

Объекты, которые тут создаются, это две коллекции и два int[], которые находятся внутри этих коллекций. Обе коллекции можно переиспользовать, вызвав у них метод clear(). Используя коллекции на примитивах мы не усложнили наш код (и даже упростили, убрав метод compute со сложной лямбдой внутри него) и получили следующие дополнительные бонусы по сравнению с использованием стандартных коллекций:

1. Практически полное отсутствие аллокаций. Если коллекции переиспользовать, то аллокаций не будет вовсе.
2. Существенная экономия памяти (IntArrayList занимает примерно в пять раз меньше места, чем ArrayList<Integer>. Как уже говорилось, мы заботимся именно об экономном использовании кэшей процессора, а не о RAM.
3. Последовательный доступ к памяти. На тему того, почему это важно, написано много, так что я не буду на этом останавливаться. Вот пара статей: Martin Thompson и Ulrich Drepper.

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

Mutable объекты

А что делать, если примитивами обойтись не получается? Например в том случае, если нужный нам метод должен вернуть несколько значений. Ответ простой — использовать mutable объекты.

Как это выглядит на практике? Предположим, нам требуется посчитать частное и остаток от деления. И для этого мы используем следующий код.

class IntPair {
   int x;
   int y;
}

IntPair divide(int value, int divisor) {
   IntPair result = new IntPair();
   result.x = value / divisor;
   result.y = value % divisor;
   return result;
}

Как можно избавиться от аллокации в этом случае? Правильно, передать IntPair в качестве аргумента и записать туда результат. В этом случае надо написать подробный javadoc, а еще лучше использовать некую конвенцию для названий переменных, куда записывается результат. Например, их можно начинать с префикса out. Garbage free код в этом случае будет выглядеть так:

void divide(int value, int divisor, IntPair outResult) {
   outResult.x = value / divisor;
   outResult.y = value % divisor;
}

Хочу заметить, что метод divide не должен нигде сохранять ссылку на pair или передавать ее в методы, которые это могут сделать, иначе у нас могут появиться большие проблемы. Как мы видим, mutable объектами пользоваться сложнее, чем примитивными типами, поэтому если есть возможность использовать примитивы, то лучше так и поступить. По факту, в нашем примере мы перенесли проблему с аллокацией изнутри метода divide наружу. Во всех местах, где мы вызываем этот метод мы должны будем иметь некую пустышку IntPair, которую будем передавать в divide. Зачастую достаточно хранить эту пустышку в final поле объекта, откуда мы вызываем метод divide. Приведу надуманный пример: предположим, что наша программа занимается только тем, что получает по сети поток чисел, делит их и отправляет результат в тот же сокет.

class SocketListener {
   private final IntPair pair = new IntPair();
   private final BufferedReader in;
   private final PrintWriter out;

   SocketListener(final Socket socket) throws IOException {
       in = new BufferedReader(new InputStreamReader(socket.getInputStream()));
       out = new PrintWriter(socket.getOutputStream(), true);
   }

   void listenSocket() throws IOException {
       while (true) {
           int value = in.read();
           int divisor = in.read();
           divide(value, divisor, pair);
           out.print(pair.x);
           out.print(pair.y);
       }
   }
}

Для лаконичности я не стал писать “лишний” код по обработке ошибок, корректному завершению работы программы и т.д. Основная идея этого куска кода заключается в том, что используемый нами объект IntPair создается один раз и сохраняется в final поле.

Объектные пулы

Когда мы пользуемся mutable объектами мы должны сначала откуда-то взять пустой объект, потом записать в него нужные нам данные, попользоваться ими где-то, а затем вернуть объект “на место”. В вышеописанном примере объект всегда был “на месте”, т.е. в final поле. К сожалению, это не всегда получается сделать простым образом. Например, мы можем заранее не знать, сколько именно объектов нам понадобится. В этом случае нам на помощь приходят объектные пулы. Когда нам становится нужен пустой объект, мы достаем его из объектного пула, а когда он перестает быть нужен, мы его туда возвращаем. Если в пуле нет свободного объекта, то пул создает новый объект. Это уже по факту является ручным управлением памятью со всеми вытекающими последствиями. К этому способу желательно не прибегать, если есть возможность пользоваться предыдущими способами. Что может пойти не так?

• Мы можем забыть вернуть объект в пул, и тогда создастся мусор ("memory leak"). Это небольшая проблема — слегка просядет производительность, но отработает GC и программа продолжит работать.
• Мы можем вернуть объект в пул, но сохранить на него ссылку где-то. Потом кто-то другой достанет объект из пула, и в этот момент в нашей программе уже будут две ссылки на один и тот же объект. Это классическая проблема use-after-free. Это сложно дебажить, т.к. в отличие от C++ программа не упадет с сегфолтом, а продолжит неправильно работать.

Для того чтобы уменьшить вероятность совершения описанных выше ошибок можно использовать стандартную конструкцию try-with-resources. Выглядеть это может так:

public interface Storage<T> {
   T get();

   void dispose(T object);
}

class IntPair implements AutoCloseable {
    private static final Storage<IntPair> STORAGE = new StorageImpl(IntPair::new);
    int x;
    int y;

    private IntPair() {}

    public static IntPair create()
    {
        return STORAGE.get();
    }

    @Override
    public void close()
    {
        STORAGE.dispose(this);
    }
}

Метод divide может выглядеть так:

IntPair divide(int value, int divisor) {
    IntPair result = IntPair.create();
    result.x = value / divisor;
    result.y = value % divisor;
    return result;
}

А метод listenSocket вот так:

void listenSocket() throws IOException {
    while (true) {
        int value = in.read();
        int divisor = in.read();
        try (IntPair pair = divide(value, divisor)) {
            out.print(pair.x);
            out.print(pair.y);
        }
    }
}

В IDE как правило можно настроить подсвечивание всех случаев использования AutoCloseable объектов вне try-with-resources блока. Но это не стопроцентный вариант, т.к. подсвечивание в IDE может быть просто выключено. Поэтому есть еще один способ гарантировать возврат объекта в пул — инверсия контроля. Приведу пример:

class IntPair implements AutoCloseable {
    private static final Storage<IntPair> STORAGE = new StorageImpl(IntPair::new);
    int x;
    int y;

    private IntPair() {}

    private static void apply(Consumer<IntPair> consumer)
    {
        try(IntPair pair = STORAGE.get()) {
            consumer.accept(pair);
        }
    }

    @Override
    public void close()
    {
        STORAGE.dispose(this);
    }
}

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

Очевидно, что если мы храним в пуле не самописные объекты, а какие-то библиотечные, которые не имплементируют AutoCloseable, то вариант с try-with-resources тоже не прокатит.

Дополнительной проблемой здесь является многопоточность. Реализация объектного пула должна быть очень быстрой, чего довольно сложно добиться. Медленный пул может принести больше вреда для производительности, чем пользы. В свою очередь аллокация новых объектов в TLAB происходит очень быстро, гораздо быстрее, чем malloc в C. Написание быстрого объектного пула — это отдельная тема, которую я бы сейчас не хотел развивать. Скажу только, что хороших "готовых" реализаций я не видел.

Вместо заключения

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

Update:

Да, вспомнил еще один способ для тех, кто не боится побитовых сдвигов: упаковывание нескольких маленьких примитивных типов в один большой. Предположим, что нам надо вернуть два int’а. В этом конкретном случае можно не использовать объект IntPair, а вернуть один long, первые 4 байта в котором будут соответствовать первому int’у, а вторые 4 байта — второму. Код может выглядеть так:

long combine(int left, int right)
{
   return ((long)left << Integer.SIZE) | (long)right & 0xFFFFFFFFL;
}

int getLeft(long value)
{
   return (int)(value >>> Integer.SIZE);
}

int getRight(long value)
{
   return (int)value;
}

long divide(int value, int divisor) {
    int x = value / divisor;
    int y = value % divisor;
    return combine(left, right);
}

void listenSocket() throws IOException {
    while (true) {
        int value = in.read();
        int divisor = in.read();
        long xy = divide(value, divisor);
        out.print(getLeft(xy));
        out.print(getRight(xy));
    }
}

Такие методы, разумеется, надо хорошенько тестировать, потому что накосячить при их написании довольно легко. Но зато потом просто пользоваться.