Статьи

Как работают классы LongAccumulator и DoubleAccumulator?

Два класса, новые в Java 8, заслуживают некоторого внимания: LongAccumulator и DoubleAccumulator . Они предназначены для безопасного накопления (подробнее о том, что это означает позже) значений между потоками, при этом они чрезвычайно быстры. Тест стоит тысячи слов, вот как это работает:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
class AccumulatorSpec extends Specification {
  
    public static final long A = 1
    public static final long B = 2
    public static final long C = 3
    public static final long D = -4
    public static final long INITIAL = 0L
  
    def 'should add few numbers'() {
        given:
            LongAccumulator accumulator = new LongAccumulator({ long x, long y -> x + y }, INITIAL)
        when:
            accumulator.accumulate(A)
            accumulator.accumulate(B)
            accumulator.accumulate(C)
            accumulator.accumulate(D)
        then:
            accumulator.get() == INITIAL + A + B + C + D
    }

Таким образом, аккумулятор принимает двоичный оператор и объединяет начальное значение с каждым накопленным значением. Это означает, что ((((0 + 1) + 2) + 3) + -4) равно 2 . Не уходи пока, есть гораздо больше, чем это. Аккумулятор может принимать и другие операторы, как показано в этом примере использования:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
def 'should accumulate numbers using operator'() {
    given:
        LongAccumulator accumulator = new LongAccumulator(operator, initial)
    when:
        accumulator.accumulate(A)
        accumulator.accumulate(B)
        accumulator.accumulate(C)
        accumulator.accumulate(D)
    then:
        accumulator.get() == expected
    where:
        operator                 | initial           || expected
        {x, y -> x + y}          | 0                 || A + B + C + D
        {x, y -> x * y}          | 1                 || A * B * C * D
        {x, y -> Math.max(x, y)} | Integer.MIN_VALUE || max(A, B, C, D)
        {x, y -> Math.min(x, y)} | Integer.MAX_VALUE || min(A, B, C, D)
}

Очевидно, что аккумулятор будет работать так же хорошо в тяжелой многопоточной среде – для которой он был разработан. Теперь вопрос в том, какие другие операции разрешены в LongAccumulator (это относится и к DoubleAccumulator ) и почему? На этот раз JavaDoc не очень формальный (жирный):

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

Чтобы понять, как работает LongAccumulator , какие типы операций разрешены и почему это так быстро (потому что это, по сравнению, например, с AtomicLong ), давайте начнем с обратного, метода get() :

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
transient volatile long base;
transient volatile Cell[] cells;
  
private final LongBinaryOperator function;
  
public long get() {
    Cell[] as = cells; Cell a;
    long result = base;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                result = function.applyAsLong(result, a.value);
        }
    }
    return result;
}

Который может быть переписан как не совсем эквивалентный, но легче читаемый:

1
2
3
4
5
6
public long get() {
    long result = base;
    for (Cell cell : cells)
        result = function.applyAsLong(result, cell.value);
    return result;
}

Или даже более функционально без внутреннего состояния:

1
2
3
4
5
public long get() {
    return Arrays.stream(cells)
            .map(s -> s.value)
            .reduce(base, function::applyAsLong);
}

Мы ясно видим, что существует некоторый массив cells и что в конце мы должны пройти через этот массив и последовательно применить нашу операторную функцию к каждому элементу. Оказывается, LongAccumulator имеет два механизма для накопления значений: один base счетчик и массив значений в случае высокой конкуренции за блокировку потока. Если LongAccumulator используется без конкуренции за блокировку, используется только одна переменная и переменная volatile base , как в AtomicLong . Однако в случае сбоя CAS этот класс возвращается к массиву значений. Вы не хотите видеть реализацию, она состоит из 90 строк, иногда с 8 уровнями вложенности. Что вам нужно знать, так это то, что он использует простой алгоритм, чтобы всегда назначать данный поток одной и той же ячейке (улучшает локальность кэша). Отныне у этой темы есть своя, почти приватная копия counter. Он делится этой копией с несколькими другими потоками, но не со всеми – у них есть свои собственные ячейки. Таким образом, в итоге вы получите массив полусчитанных счетчиков, которые должны быть агрегированы. Это то, что вы видели в методе get() .

Это снова возвращает нас к вопросу, какие операторы ( op ) разрешены в LongAccumulator . Мы знаем, что та же самая последовательность накоплений при низкой нагрузке приведет, например, к:

1
((I op A) op B)  //get()

Это означает, что все значения агрегируются в базовую переменную и не используется массив счетчиков. Однако при высокой нагрузке LongAccumulator будет разбивать работу, например, на две группы (ячейки), а затем накапливать группы:

1
2
3
4
(I op A)              //cell 1
(I op B)              //cell 2
  
(I op A) op (I op B)  //get()

или наоборот:

1
2
3
4
(I op B)              //cell 1
(I op A)              //cell 2
  
(I op B) op (I op A)  //get()

Ясно, что все вызовы get() должны давать один и тот же результат, но все зависит от свойств предоставляемого оператора op ( + , * , max и т. Д.)

Коммутативный

У нас нет контроля над порядком ячеек и их назначением. Вот почему ((I op A) op (I op B)) и ((I op B) op (I op A)) должны возвращать один и тот же результат. Более компактно, мы ищем такие операторы op где X op Y = Y op X для всех X и Y Это означает, что op должен быть коммутативным .

Нейтральный элемент (идентичность)

Клетки логически инициализируются с идентичным (начальным) значением I Мы не контролируем количество и порядок ячеек, поэтому значение идентификатора можно применять много раз в любом порядке. Однако это деталь реализации, поэтому она не должна влиять на результат. Точнее, для каждого X и любой op :

1
X op I = I op X = X

Это означает, что тождественное (начальное) значение I должно быть нейтральным значением для каждого аргумента X для оператора op .

Ассоциативность

Предположим, у нас есть следующие ячейки:

1
2
3
4
I op A                              // cell 1
I op B                              // cell 2
I op C                              // cell 3
((I op A) op (I op B)) op (I op C)  //get()

но в следующий раз они были устроены иначе

1
2
3
4
I op C                              // cell 1
I op B                              // cell 2
I op A                              // cell 2
((I op C) op (I op B)) op (I op A)  //get()

Зная, что op коммутативно, а I – нейтральный элемент, мы можем доказать, что (для каждого A , B и C ):

1
2
3
((I op A) op (I op B)) op (I op C) = ((I op C) op (I op B)) op (I op A)
(A op B) op C = (C op B) op A
(A op B) op C = A op (B op C)

Что доказывает, что op должен быть ассоциативным, чтобы LongAccumulator действительно работал.

Заворачивать

LongAccumulator и DoubleAccumulator – это узкоспециализированные классы, впервые появившиеся в JDK 8. JavaDoc довольно неудачен, но мы попытались доказать свойства, которые оператор и начальное значение должны заполнять, чтобы они могли выполнять свою работу. Мы знаем, что оператор должен быть ассоциативным , коммутативным и иметь нейтральный элемент. Было бы намного лучше, если бы JavaDoc четко заявил, что это должен быть абелев моноид ;-). Тем не менее, в практических целях эти аккумуляторы работают только на сложение, умножение, минимальное и максимальное значения, поскольку это единственные полезные операторы (с соответствующим нейтральным элементом), которые хорошо играют. Например, вычитание и деление не являются ассоциативными и коммутативными, поэтому не могут работать. Что еще хуже, аккумуляторы будут вести себя недетерминированно.

Ссылка: Как работают классы LongAccumulator и DoubleAccumulator? от нашего партнера JCG Томаша Нуркевича в блоге о Java и соседстве .