Comments 20
Как ни странно, исходники реализации брал из OpenJDK 11.
ConcurrentHashMap.java на строке 1674? В исходниках там комментарий.Ну и хотелось бы точную версию Java, например:
$ java -version
openjdk version "11.0.4" 2019-07-16
OpenJDK Runtime Environment (build 11.0.4+11-post-Ubuntu-1ubuntu219.04)
OpenJDK 64-Bit Server VM (build 11.0.4+11-post-Ubuntu-1ubuntu219.04, mixed mode, sharing)
and must not attempt to update any other mappings of this map.
Но другой маппинг и не модифицируется. Более того, после некоторого прогрева там начинается только чтение без модификаций. Но при этом картина в профиле не меняется к лучшему.
Более того чуть выше:
Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple
Т.е. контекст указанной вами строки относится именно к ситуации, когда требуется вычисление лямды с новым результатом, а не чтение. Блокировка на чтение контр интуитивна в данном случае.
Я лишь указываю на то, что было бы не плохо предоставить чуть больше информации о причине блокировки. Например, указать, что блокировка осуществляется на конкретной строке.
А изначально напоролся на 1.8.0_222
нетуда
Хороший вопрос, достойный отдельной статьи.
Всё строится на так называемых неблокирующих алгоритмах, основывающихся на том факте, что Java даёт определённые гарантии по работе с памятью. Особенно с общей памятью в многопоточной обработке.
Если приводить максимально простой пример, то, например, можно вместо честной блокировки завести флаг в виде AtomicBoolean и перед входом в критическую секцию делать магию:
private static AtomicBoolean guard = new AtomicBoolean(false);
public void doSometing() {
if (guard.compareAndSet(false, true)) {
try {
// It's safe now. We can change the state.
} finally {
guard.set(false);
}
} else {
// Do something non-destructive.
}
}Это намного дешевле, чем честная блокировка и во многих применения этого достаточно. Даже в штатной библиотеке JRE эти подходы используются очень широко.
computeIfAbsent лочит только при создании ноды. И массовые локи могут быть в сценарии когда вы массово создаете ноды и удаляете по одним и тем же ключам (с точностью до коллизий хеша). Не надо так код писать. Хеш функцию поправьте или просто сценарий работы переосмыслите.
computeIfAbsent при получении значения не лочит ничего. Ей можно смело пользоваться и не городить велосипед.
Я тоже так думал.
Вот давайте ещё раз заглянем под спойлер с реализацией метода ConcurrentHashMap.computeIfAbsent. результат возвращается из переменной val. Где происходит присвоение в эту переменную? В 6-и местах. Я их там даже специально пометил. Хоть пометки и не очень заметными вышли, т.к. код очень разлапистый. Первое присвоение не под блокировкой. Но там просто присваивается null. А вот все остальные места — под блоками synchronized. Т.е. нет ни одного пути выполнения, который не попадал бы на блокировку. Ну кроме случая с пустой коллекцией.
Более того. Данные в нашем случае из этой коллекции вообще не удаляются. Никогда. И там используется сравнительно небольшое количество ключей. И именно это сыграло дурную шутку, т.к. в случае большого количества ключей блокировки бы размазывались по разным объектам нод и там неполучалось бы такого контеншена.
все остальные места — под блоками synchronized
Есть ещё «return fv;» в вашей версии кода вне синхронизации.
Но в сорцах 1.8.0_122 (у меня под рукой) такой строчки нет. Если пишете статью про реализацию, то будьте добры указать ТОЧНУЮ версию с ПРОИЗВОДИТЕЛЕМ. Просто «1.8.0_222» это что — Оракл, IBM J9, OpenJDK, GNU, азуль, алибаба? На чём меряли? откуда код? Почему разные?
openjdk version «11.0.1» 2018-10-16
OpenJDK Runtime Environment 18.9 (build 11.0.1+13)
OpenJDK 64-Bit Server VM 18.9 (build 11.0.1+13, mixed mode)
Открываем исходники
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
if (key == null || mappingFunction == null)
throw new NullPointerException();
int h = spread(key.hashCode());
V val = null;
int binCount = 0;
for (Node<K,V>[] tab = table;;) { //1
Node<K,V> f; int n, i, fh; K fk; V fv; //2
if (tab == null || (n = tab.length) == 0) //3
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { //4
Node<K,V> r = new ReservationNode<K,V>();
synchronized (r) {
if (casTabAt(tab, i, null, r)) {
binCount = 1;
Node<K,V> node = null;
try {
if ((val = mappingFunction.apply(key)) != null)
node = new Node<K,V>(h, key, val);
} finally {
setTabAt(tab, i, node);
}
}
}
if (binCount != 0)
break;
}
else if ((fh = f.hash) == MOVED) //5
tab = helpTransfer(tab, f);
else if (fh == h // check first node without acquiring lock //6
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv; //7
else {
boolean added = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == h &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
val = e.val;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
if ((val = mappingFunction.apply(key)) != null) {
if (pred.next != null)
throw new IllegalStateException("Recursive update");
added = true;
pred.next = new Node<K,V>(h, key, val);
}
break;
}
}
}
else if (f instanceof TreeBin) {
binCount = 2;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(h, key, null)) != null)
val = p.val;
else if ((val = mappingFunction.apply(key)) != null) {
added = true;
t.putTreeVal(h, key, val);
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (!added)
return val;
break;
}
}
}
if (val != null)
addCount(1L, binCount);
return val;
}
Запускаем простенький пример.
ConcurrentHashMap<Integer, Integer> f = new ConcurrentHashMap<>();
f.put(1,1);
f.computeIfAbsent(1, p->10);
И видим что выполнение пойдет по строкам которые я прокомментировал 1-2-3-4-5-6-7.
Ни одного synchronized блока не затронуто. Как и ожидалось.
Жду вашего примера.
Да-да. Благодаря vkovalchuk уже разобрались. И даже UPD2 уже написан по этому поводу.
Так что актуальность статьи остаётся только для Java 8 и тех страдальцев, кто пока не может с неё спрыгнуть.
#Назаметку. Осторожно, атомарные операции в ConcurrentHashMap