Как реализован LongAccumulator, чтобы он был более эффективным?

Я понимаю, что новая Java (8) представила новые инструменты синхронизации, такие как LongAccumulator (под атомным пакетом).

В документации говорится, что LongAccumulator более эффективен, когда обновление переменной из нескольких потоков является частым.

Интересно, как это реализовано, чтобы быть более эффективным?

Ответ 1

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

class Accumulator {
    private final AtomicLong value = new AtomicLong(0);
    public void accumulate(long value) {
        this.value.addAndGet(value);
    }
    public long get() {
        return this.value.get();
    }
}

Если вы создадите один экземпляр этого класса и вызовите метод accumulate(1) из одного потока в цикле, выполнение будет очень быстрым. Однако, если вы вызываете метод в том же экземпляре из двух потоков, выполнение будет примерно на две величины медленнее.

Вы должны взглянуть на архитектуру памяти, чтобы понять, что происходит. Большинство систем в настоящее время имеют неравномерный доступ к памяти. В частности, каждое ядро имеет свой собственный кеш L1, который обычно структурирован в строки кэша с 64 октетами. Если ядро выполняет операцию создания атома в ячейке памяти, сначала нужно получить эксклюзивный доступ к соответствующей строке кэша. Это действительно дорого, если у него пока нет эксклюзивного доступа из-за необходимой координации со всеми другими ядрами.

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

class Accumulator {
    private final AtomicLong[] values = {
        new AtomicLong(0),
        new AtomicLong(0),
        new AtomicLong(0),
        new AtomicLong(0),
    };
    public void accumulate(long value) {
        int index = getMagicValue();
        this.values[index % values.length].addAndGet(value);
    }
    public long get() {
        long result = 0;
        for (AtomicLong value : values) {
            result += value.get();
        }
        return result;
    }
}

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

Чтобы сделать это очень быстро, вам нужно рассмотреть еще несколько вещей:

Различные счетчики атомов должны располагаться в разных строках кэша. В противном случае вы заменяете одну проблему другой, а именно ложный обмен. В Java вы можете использовать long[8 * 4] для этой цели и использовать только индексы 0, 8, 16 и 24.
Количество счетчиков должно выбираться с умом. Если слишком мало разных счетчиков, все еще слишком много переключателей кеша. если слишком много счетчиков, вы теряете пространство в кешках L1.
Метод getMagicValue должен возвращать значение с близостью к идентификатору ядра.

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

Ответ 1

Ответ 2