Два класса, новые в 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 1I op B // cell 2I op C // cell 3((I op A) op (I op B)) op (I op C) //get() |
но в следующий раз они были устроены иначе
|
1
2
3
4
|
I op C // cell 1I op B // cell 2I 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 и соседстве . |