28 сентября 2011 г.

AtomicXXX.lazySet() strikes back

Наткнулся тут на любопытную вещь -- я всегда был уверен, что в JMM все поведение всегда можно описать с помощью несложного набора правил построения ребер happens-before. Ну, то есть, я не говорю, что применение этих правил всегда просто -- законы Ньютона тоже не очень сложные, а какой мрак и ужас из них получается, скажем, в небесной механике и движении твердого тела -- но сами правила довольно просты, и применимы к любому java-коду. Но похоже это не совсем так. Этот самый AtomicXXX.lazySet() мутит воду.

Простое объяснение -- неволатильная запись в волатильную переменную -- меня только запутывает. До этого момента в джаве, вообще-то, не было волатильной/не волатильной записи в отрыве от типа поля (ну, если не трогать сатанинский Unsafe). То есть если поле волатильное -- то все операции с ним волатильные, поле не волатильное -- все операции не волатильные.

А теперь получается такая штука, что я могу записать значение в переменную не волатильно, а потом считать его волатильно. И что за отношение порядка будет у меня между этими операциями, если они в разных потоках?

Это не праздный интерес. В коде Disruptor-а встречается такая идиома:

AtomicLong sequence = new AtomicLong();
...
//поток 1: издатель
...write some values into shared objects...
sequence.lazySet(seq);

//поток 2: обработчик
while( sequence.get() != seq ){
   //spin wait
}
...read shared objects fields

По смыслу кода понятно, что автор его уверен -- последовательность sequence.lazySet()/get() обеспечивает завершение всех операций записи, идущих до нее в program order, и видимость результатов этих операций из второго потока. Другими словами -- это практически happens-before edge. Но вот с чего он так в этом уверен -- для меня совершенно не очевидно.

Как минимум, документация lazySet() не дает никаких гарантий относительно того когда запись будет реально выполнена. Eventually -- когда-нибудь. То есть возможно, что и вообще никогда. И непонятно, в какой момент запись -- если она завершится -- будет увидена вторым потоком.

А с другой стороны -- я сейчас гоняю бенчмарки, разбирая по частям disruptor и вытаскивая какие компоненты ключевые для его производительности. И вот оказывается, что если вместо lazySet использовать обычный set() -- скорость падает в 2 раза примерно (это без нагрузки -- на холостом ходу). То есть смысл определенно есть -- но вот надежен ли этот способ оптимизации -- мне как-то неочевидно.

Задал вопрос на stackoverflow -- посмотрим, может там понимают

9 комментариев:

  1. А ви не могли бы поделится какие такие правила вы применяете для построения связей happens-before. Я потихоньку разбираю кокарренси в Java, но до святилища JMM пока не добрался - это там эти правиала описаны?

    ОтветитьУдалить
  2. Да, в JMM в том числе описаны и правила построения ребер happens-before. Хотя если честно, саму JMM я наизусть не помню :)

    Если вкратце, то ребра happens-before создают пары monitor-exit/monitor-enter (для одного объекта монитора), операции volatile write/read для одной переменной. Чуть более редкие случаи это happens-before между вызовом метода Thread.start() и началом выполнения метода Thread.run, и между завершением выполнения Thread.run и выходом из Thread.join Как-то так, в целом. Обычно в контактах методов, связанных с concurrency описывается контракт на причинность в том числе.

    ОтветитьУдалить
  3. В ссылке на bug-DB написано что реордеринг запрещается со всеми предыдущими операциями - то есть когда обработчик засечет что флаг проставлен (а это может быть неизвестно с какой задержкой в отличии от волатайла), то все изменения издателя до изменения флага должны быть видны.

    ОтветитьУдалить
  4. Это написано просто в javadoc к методу lazySet. Но "реордеринг запрещается" -- это не ребро HB. Рассуждения в терминах реордеринга -- это более низкоуровневая аргументация. И -- как мне кажется -- более сложная. Поэтому меня тревожит отход от красивой нотации частичного порядка операций в сторону membars and fences.

    Кроме того "неизвестно с какой задержкой" в том числе допускает вариант "никогда". Это тоже меня тревожит :)

    На самом деле мне ответил DL на concurrency-interest уже -- я еще немного покумекаю, и напишу очередной пост на эту тему

    ОтветитьУдалить
  5. Реордеринг влияет на visibility - а это один из аспектов HB.
    В данном случае это не HB по той причине что когда второй поток читает флаг после того как первый его изменил он может читать старое значение (то есть чтение может не "произойти раньше" записи, как в случае волатайла). Но ограничение на реордеринг, как мне кажется, достаточно чтобы в случае считывания нового значения делать выводы о том что записи "до" также видимы. Иначе Disruptor не работал бы (хотя отловить это наверное крайне непросто).

    ОтветитьУдалить
  6. Прочитал комментарии на stackoverflow - похоже действительно никаких явных гарантий нет. Одного реордеринга формально вроде не достаточно. Формально первый поток может зафлашить(скинуть в основную память) изменение флага но не зафлашить остальные изменения. К сожалению далеко не эксперт в процессорных архитектурах но это кажется маловероятным. Я так понимаю что современные модели синхронизации кешей предполагают что раз мы флашим изменение B которое локально произошло после изменения A то и изменения A тоже должны зафлашить.
    Не могли бы вы скинуть линк где вам ответили на concurrency-interest.

    ОтветитьУдалить
  7. >когда второй поток читает флаг после того как первый его изменил он может читать старое значение (то есть чтение может не "произойти раньше" записи, как в случае волатайла)

    Вы знаете, на самом деле мне кажется что гарантий "немедленного выполнения" нет и в случае честного volatile. Я сейчас перечитываю JMM чтобы уточнить, но похоже там нет гарантий _когда_ запись будет видима другими потоками. Там есть только гарантии на порядок -- _не раньше_ чем записи, идущие до нее, и _не позже_ чем записи, идущие после в program order. Т.е. запись может быть отложена -- но только вместе со всеми записями и чтениями идущими "вокруг" нее. Если это так, то разница между честным volatile и lazySet еще меньше.

    >Иначе Disruptor не работал бы

    Ну это не аргумент. То, что он работает на конкретной JVM и на конкретной архитектуре процессора (а они сильно закладываются на Intel Nehalem) -- еще не означает доказательства корректности. Да даже если он везде работает -- вполне возможно, что это только из-за особенностей нынешней реализации JVM, которая не использует _всю свободу_ предоставляемую JMM. Доказательство может быть только формальным, исходя из JMM.

    Собственно, в дискуссии на concurrency-interest выясняется, что похоже так и есть -- формально запись может быть отложена на бесконечное время, но фактически мы знаем, что у компиляторов ограниченная глубина реордеринга, и у процессоров ограниченная глубина store buffers -- так что запись точно когда-нибудь зафлешится, если поток-производитель продолжает что-то делать (писать)

    Меня, собственно, и напрягает тот факт, что я как-то уже привык доказывать корректность исходя из нотации HB-ребер. Это очень удобно. И я очень не хочу переходить на работу с барьерами. Но, видимо, в той или иной степени -- придется.

    >Формально первый поток может зафлашить(скинуть в основную память) изменение флага но не зафлашить остальные изменения

    Нет, как раз этого быть не может -- в javadocs описано, что это односторонний write-release барьер: запись флага не может случиться (стать видимой) до того, как станут видимыми записи, идущие до нее в program order.

    Меня интересовало уточнение понятия "не может быть переупорядочено". JMM в целом не формализует понятие reordering -- там используется synchronization order/HB-edges, которые задают _одновременно_ и порядок, и видимость, а reordering используется только в неформальных рассуждениях/примерах. Поэтому меня волновало, не может ли быть так, что записи идущие до lazySet _не будут переупорядочены_, но будут _видимы_ в другом порядке из-за каких-нибудь особенностей строения кэша. Т.е. я хочу сказать, что вообще-то переупорядочивание -- это только один из факторов, влияющих на видимость. И когда я рассуждаю о корректности кода меня вообще-то не волнует отдельно реордеринг -- меня волнует конечный результат -- видимость.

    Дискуссию в concurrency-interest разметало по разным месяцам. Вот одна из ссылок http://cs.oswego.edu/pipermail/concurrency-interest/2011-September/008254.html

    ОтветитьУдалить
  8. Спасибо за ответы и ссылку.

    1.Насчет "немедленных" гарантий для волатайла - да, формально их нет, поскольку формально понятие физического времени отсутствует в JMM. Но "практически" запись в волатайл не ждет других HB edge-ей чтобы сделать запись в основную память. И в этом смысле она "немедленна". Кстати обычные операции записи и чтения после запись в волатайл могу встать перед ней если это не мешает логике.
    Вот пруфлинк (хотя вы наверное читали это много раз) http://gee.cs.oswego.edu/dl/jmm/cookbook.html

    2. >Иначе Disruptor не работал бы
    Да согласен, погорячился. Поначалу подумал что это какая то новая фишка в 7-ке.
    "...формально запись может быть отложена на бесконечное время, но фактически мы знаем, что у компиляторов ограниченная глубина реордеринга..." - несмотря на это иногда JVM может делать такие оптимизации что запись некогда не будет видна другим потокам если это не противоречит JMM - смотрите единственный пост в моем блоге. Хотя практически это можно наблюдать только в синтетических тестах.

    3. "Нет, как раз этого быть не может -- в javadocs описано, что это односторонний write-release барьер: запись флага не может случиться (стать видимой) до того, как станут видимыми записи, идущие до нее в program order." - разве это не доказывает что когда второй поток все видит флаг измененным то и предыдущие записи тоже должны быть видны. Как написал Даг в приведенной вами ссылке, записи до lazySet-а будут видны но это нельзя доказать из текущей модели JMM.

    ОтветитьУдалить
  9. >Но "практически" запись в волатайл не ждет других HB edge-ей чтобы сделать запись в основную память. И в этом смысле она "немедленна".
    Она не ждет других, это правда. Я имел в виду лишь то, что момент завершения выполняющим потоком инструкции volatile write не означает, что значение уже реально записано в основную память. То есть волатильная запись это не флэш, это именно что барьер для переупорядочивания -- ни JIT не будет перемещать операции чтения-записи вокруг нее, ни процессор -- для чего JIT выдаст ему специальную инструкцию барьера памяти. Но эта инструкция не обязательно означает флэш буфера -- она лишь означает, что буфер должен быть закоммичен в определенном порядке. Это некая метка, помещаемая в буфер записи, и говорящая, что записи после него не могут быть закоммичены перед ним. Некоторые модели процессоров могут выполнять эту операцию как флэш -- это, очевидно, простейшая реализация. Некоторые могут действительно помещать в буфер соответствующую метку, и продолжать откладывать сброс буфера до последнего -- это сложнее, но потенциально более производительно, как и любые другие отложенные обращения к памяти.


    >операции записи и чтения после запись в волатайл могу встать перед ней если это не мешает логике. Вот пруфлинк (хотя вы наверное читали это много раз) http://gee.cs.oswego.edu/dl/jmm/cookbook.html

    Ага, volatile write -- это односторонний release-барьер, как и monitorExit, аналогично односторонним acquire-барьером является volatile read/monitorEnter -- только он действует "в другую сторону"

> несмотря на это иногда JVM может делать такие оптимизации что запись некогда не будет видна другим потокам если это не противоречит JMM - смотрите единственный пост в моем блоге. Хотя практически это можно наблюдать только в синтетических тестах.

    Именно, поэтому я уточнил "если поток продолжает что-то делать(писать)". Даже более того -- требуются какие-нибудь synchronization actions. Мне эту мантру раза 3 повторил DL в дискуссии на c-i. То есть если сразу после lazySet поток уходит в бесконечный цикл -- формально JVM может не делать этих записей вообще. Фактически DL указывает, что по его информации все существующие JVM реализуют lazySet консервативно -- как немедленный write, поэтому даже такого эффекта в текущих реализациях можно не ждать, но рассчитывать на это, конечно, смертный грех.
    
> разве это не доказывает что когда второй поток все видит флаг измененным то и предыдущие записи тоже должны быть видны

    Я же говорю -- меня здесь смущала неопределенность термина reordering. Формального его определения в JMM нет, там он используется только в неформальных комментариях/примерах. Он может означать как только instructions reordering, так и более общо visibility reordering. По контексту в javadoc используется термин "preceeding _stores_ reordering" -- это меня навело на мысль, что речь идет именно об instruction reorderings. А переупорядочивание инструкций -- это только один из источников переупорядочивания видимости. Вот я и подофигел -- что мне делать с этим?

    ОтветитьУдалить