weakCompareAndSet

В классах AtomicXXX, наряду с известным методом compareAndSet (CAS) есть еще довольно странный метод weakCompareAndSet (WCAS). Не так давно я наткнулся на довольно длинную дискуссию в concurrency-interest. Хотя сама дискуссия довольно уже старая (2006г) но для меня содержала много нового, чем хочется поделиться.

Итак, чем отличается weakCAS от обычного CAS?

1. Может откатиться (ничего не изменить и вернуть false) даже если значение expected совпадает с текущим значением в ячейке памяти (другими словами -- может откатиться "без причины")
2. Не создает (=не обязан создавать) ребра happens-before

Теперь чуть подробнее:

С первым пунктом все довольно просто -- обычный CAS откатывается только в случае, значение в ячейке памяти не совпадает с ожидаемым. Если CAS вернул false -- вы можете быть уверены, что actualValue!=expectedValue. В случае с weakCAS такой уверенности нет -- значения могут совпадать, а weakCAS все равно откатится. Разумеется, можно сделать цикл с проверкой, но есть тонкости -- часто доказательство lock-free для алгоритма базируется на том, что CAS либо удался (и тогда текущий поток "продвинулся"), либо нет (и это означает, что "продвинулся" какой-то другой поток) -- в итоге всегда получается общий прогресс. С weakCAS такое рассуждение уже не прокатит -- формально говоря, он может откатываться сколько пожелает.

Второй пункт важнее и интереснее. Обычный CAS имеет семантику volatile read+write. В частности, это означает, что между двумя CAS-ами одной переменной всегда существует ребро happens-before. Именно это позволяет использовать его, например, для создания спин-локов. weakCAS такой семантики не имеет, никаких ребер не создает, и сделать на его основе спин-лок не получится.

Откуда же есть пошел weakCAS? Ну, если верить concurrency-interest, мотивация была в том, что не на всех моделях процессоров есть инструкция вида CAS. На некоторых есть альтернативный вариант -- load-linked/store conditional. CAS и LL/SC эквивалентны в том смысле, что любой алгоритм, который можно реализовать через CAS можно реализовать и через LL/SC. Но при этом LL/SC откатывается если значение по указанному адресу изменялось с момента чтения (т.е. в случае сценария ABA CAS пройдет, а LL/SC откатится). Есть еще варианты -- например, какие-то реализации LL/SC могут откатываться если изменилась любая ячейка памяти, лежащая на той же cache line, что и нужная. Чтобы на этих процессорах эмулировать честный CAS потребуется цикл с перепроверкой. Но в некоторых случаях "честности" и не нужно, и тогда можно использовать слабый CAS без дополнительных оберток.

Вторая тонкость -- на мой взгляд, более важная -- про happens before. Честный CAS, как я уже писал, состоит, собственно, из двух частей: атомарной проверки-и-присвоения, и двустороннего мембара (full fence). И если первая часть как-то очевидна (само название операции об этом и говорит), то вторая -- это некоторое дополнительная фича именно java-api для AtomicXXX. Не во всех процессорах инструкции CAS обязательно выполняют full fence, и, более того, далеко не во всех алгоритмах, требующих атомарной операции compare-and-set, обязательно требуется и full fence в каждом случае. Между тем, full fence это операция, потенциально, с большой латентностью (особенно, если ядер достаточно много). Поэтому, особенно для многоядерных систем, неплохо бы иметь возможность делать CAS без full fence, когда это необходимо. weakCAS именно такую возможность и предоставляет.

Почему тогда weakCAS малоизвестен? Ну просто потому, что в самых распространенных интеловских и AMD-шных процессорах инструкции "CAS без full fence" просто нет -- там есть только LOCK CMPXCHG, который делает точно то, что требуется спецификацией AtomicXXX.compareAndSet(...). Поэтому на этих машинах weakCAS == CAS.

Вторая причина состоит в том, что довольно сложно решить, где именно может быть применим CAS без fence. В concurrent-interest на эту тему пишут, что "если вы не Daug Lea, и у вас нет крайне веских причин оптимизировать какой-то CAS в вашем коде -- забудьте про weakCAS".

Когда же можно подумать об его использовании? Первый, очевидный, случай -- это счетчики. В частности, в дискуссии concurrent-interest выступал Cliff Click, рассказывая, что ему, для Azul box с 700-800 ядрами, требовались performance counter-ы, которые бы как можно меньше тормозили (на Azul, как я понимаю, есть более богатый выбор вариантов инструкции CAS -- и с барьерами, и без них). В самом деле, если все, что вам нужно -- это атомарный инкремент некоторой переменной -- довольно глупо в пару к нему покупать еще и full fence. Особенно если у вас 800 ядер, частенько выполняющих этот инкремент. Более общо: если вам не нужна синхронизация, а нужна только атомарная операция типа "считать-изменить-записать" -- можно использовать weakCAS, и радоваться от мысли, что, если когда-нибудь ваш код будет выполняться на Azul-ах (какая честь для вашего кода!) -- он будет работать быстрее :)

Второй случай, менее очевидный и более сложный -- когда у вас в алгоритме есть несколько последовательных CAS-ов, и вы понимаете, что "ключевым" (linearization point) из них является только какой-то один -- тогда именно его можно оставить честным, а предыдущие -- weakCAS. Мне это напоминает технику synchronization piggybacking.

Вообще, после таких обсуждений я начинаю понимать Daug Lea, который хочет добавить в джаву класс Fences с методами типа orderReads(..), orderWrites(), orderAccesses(), reachabilityFence(..)