java.util.concurrent.ConcurrentHashMap — высокооптимизированная параллельная реализация хэш-карты. Вот 5 советов, которые мы можем извлечь из его реализации:
Отказ от ответственности: методы, описанные здесь, увеличивают сложность кода, усложняя его анализ и тестирование. Поэтому, пожалуйста, применяйте их только тогда, когда вы увидели через профилирование, что ваш код находится на подходящем пути.
Используйте битовые операции вместо дорогих математических операций
Примером этого метода является использование операции ‘and’ вместо modulo в ConcurrentHashMap. ConcurrentHashMap хранит все значения в массиве. Чтобы вычислить позицию, в которой должна храниться запись, нам нужно вычислить хеш-код по модулю размера массива. Когда размер массива равен степени двух, как в случае ConcurrentHashmap, мы можем написать хеш-код и (размер массива — 1) вместо размера хеш-кода по модулю. Ниже показано это для размера 8 и хэш-кода 23:
int sizeMinusOne = 0b00000111; // 7
int hashCode = 0b00010111; // 23
int positionInArray = hashCode & sizeMinusOne; // 7Это делается, например, в методе get:
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// other code omitted
}
return null;
}В строке 5 позиция массива вычисляется с использованием (n — 1) & h. Операция и примерно на 20 процентов быстрее, чем операция по модулю. Так что если у вас есть дорогая математическая операция внутри вашего критического пути, было бы неплохо посмотреть, сможете ли вы заменить ее битовой операцией.
Используйте мелкозернистые замки
Если несколько потоков обращаются к одной и той же блокировке, это становится узким местом. Решением этой проблемы является использование мелкозернистой блокировки. Как видно из метода putVal, ConcurrentHashMap использует элементы массива в качестве мониторов для синхронизированных блокировок:
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
// other code omitted
}
}
addCount(1L, binCount);
return null;
}Если нам нужно изменить непустой элемент массива, он блокируется с помощью синхронизированного блока с элементом массива в качестве монитора. Это делается с помощью синхронизированного блока в строке 18 элемента массива, полученного в строке 9. Если используемая хэш-функция правильно распределяет элементы между элементами массива, потоки получают доступ к различным элементам массива и, следовательно, синхронизируются на разных мониторах.
Поэтому для повышения масштабируемости используйте наименьшее независимое значение в качестве блокировки. Использование этой техники приводит ко многим объектам блокировки. Поскольку входящие блокировки потребляют больше памяти, чем использование синхронизированных блоков, этот метод следует использовать с синхронизированными блоками вместо повторных входных блокировок.
Используйте изменяемые поля для чтения и блокировки для записи
Как мы уже видели, запись в методе putVal использует блокировку элемента массива. Как видно из метода get, чтение не использует блокировки, а состоит только из чтения из изменчивого поля:
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}Элемент массива принимается в строке 5 с использованием метода tabAt. Волатильное чтение выполняется в методе tabAt, как можно увидеть здесь, используя метод getObjectVolatile из sun.misc.Unsafe:
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}Если у вас есть класс с множеством операций чтения и записи, используйте эту технику. Чтение просто состоит из чтения из изменчивого поля, в то время как запись использует блокировку. В ConcurrentHashMap значения узла напрямую изменяются. Это делает необходимым объявить поля этого класса также как volatile:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
// methods omitted
}Это имеет тот недостаток, что значения могут меняться во время чтения. Более простой вариант этого метода используется в java.util.concurrent.CopyOnWriteArrayList, который включает в себя копию данных во время записи.
Ленивое создание неизменных данных
ConcurrentHashMap имеет несколько функций для создания представления этой коллекции, например:
private transient KeySetView<K,V> keySet;
public KeySetView<K,V> keySet() {
KeySetView<K,V> ks;
return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
}
public static class KeySetView<K,V> extends CollectionView<K,V,K>
implements Set<K>, java.io.Serializable {
private static final long serialVersionUID = 7249069246763182397L;
private final V value;
KeySetView(ConcurrentHashMap<K,V> map, V value) { // non-public
super(map);
this.value = value;
}
// methods omitted
}Как мы видим в строке 1, поле keySet не является изменчивым, а метод keySet (), строки с 3 по 6 не синхронизирован. Это приводит к двум проблемам: во-первых, объект KeySetView опубликован неправильно, а во-вторых, это может привести к созданию нескольких объектов KeySetView. Используя последнее поле в строке 11, мы гарантируем, что объект будет правильно инициализирован, даже если они неправильно опубликованы . И создание нескольких объектов не приводит к противоречивому состоянию, поскольку они неизменны.
Используйте java.util.concurrent.atomic.LongAdder для подсчета
Запись и удаление потоков означает необходимость обновления счетчика размера коллекции. Таким образом, изменение размера становится узким местом, даже если мы используем атомарные методы из java.util.concurrent.atomic.AtomicLong. Чтобы решить эту проблему, ConcurrentHashMap использует класс CounterCell:
/**
* A padded cell for distributing counts. Adapted from LongAdder
* and Striped64. See their internal docs for explanation.
*/
@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}Реализация этого механизма самостоятельно, вероятно, не очень хорошая идея, поскольку она довольно сложна. К счастью, JDK предоставляет реализацию используемой техники, класса java.util.concurrent.atomic.LongAdder. Идея, лежащая в основе счетчика ячеек и когда его использовать, описана в Javadoc java.util.concurrent.atomic.LongAdder:
Одна или несколько переменных, которые вместе поддерживают изначально нулевую длинную сумму. Когда обновления (метод add (long)) конкурируют между потоками, набор переменных может динамически расти для уменьшения конкуренции.
Что дальше?
Как мы могли видеть, ConcurrentHashMap полон тиков для написания высокопроизводительной, но все же поточно-ориентированной Java. В следующий раз мы рассмотрим java.util.concurrent.ConcurrentSkipListMap. Тем временем, если вы хотите проверить, является ли ваше приложение поточно- ориентированным , попробуйте vmlens бесплатно.
Я был бы рад услышать от вас о методах, которые вы используете для достижения высокопроизводительных поточно-безопасных классов.