...и вновь продолжается бой

Я тут в процессе подготовки к докладу -- прорабатываю тему Disruptor-а. И вот любопытные вещи обнаруживаются. Вот оказывается, что чтобы скакнуть почти вдвое от производительности ABQ нет необходимости реализовывать сразу хитрую очередь из Art of MP. Достаточно убрать из ABQ Condition-ы. Да, вполне можно оставить ReentrantLock, просто вместо ожидания на Condition notEmpty/notFull сделать spin-wait:

private final T[] items;
    /** items index for next take, poll or remove */
    private int takeIndex = 0;
    /** items index for next put, offer, or add. */
    private int putIndex = 0;
    /** Number of items in the queue */
    private int count = 0;

    private final ReentrantLock lock = new ReentrantLock();

    @SuppressWarnings( "unchecked" )
    public ABQConditionFreeQueue( final int size ) {
        this.items = ( T[] ) new Object[size];
    }

    private int inc( int i ) {
        return ( ++i == items.length ) ? 0 : i;
    }

    @Override
    public void enqueue( final T item ) throws InterruptedException {
        for ( int i = 0; ; i++ ) {
            if ( count < items.length
                    && tryAcquireLock() ) {
                try {
                    if ( count < items.length ) {
                        items[putIndex] = item;
                        putIndex = inc( putIndex );
                        ++count;
                        return;
                    }
                } finally {
                    releaseLock();
                }
            }
            backoff();
        }
    }

    @Override
    public T dequeue() throws InterruptedException {
        for ( int i = 0; ; i++ ) {
            if ( count > 0 && tryAcquireLock() ) {
                try {
                    if ( count > 0 ) {
                        final T item = items[takeIndex];
                        items[takeIndex] = null;
                        takeIndex = inc( takeIndex );
                        --count;
                        return item;
                    }
                } finally {
                    releaseLock();
                }
            }
            backoff();
        }
    }

    private void backoff() throws InterruptedException {
        Thread.yield();
    }

    private void releaseLock() {
        lock.unlock();
    }

    private boolean tryAcquireLock() throws InterruptedException {
        return lock.tryLock();
    }

Большая часть кода взята из ABQ, если что. Причем без backoff() эта штука обходит ABQ вдвое, а с задержкой через Thread.yield() -- почти вчетверо. Простота залог успеха. А я в прошлый заход сразу полез в дебри CAS-free.

Keep call stacks small

В последней статье Мартина Томпсона встретил интересную идею в списке техник оптимизации:
Keep call stacks reasonably small. Still more work to do here. If you are crazy enough to use Spring, then check out your call stacks to see what I mean! The garbage collector has to walk them finding reachable objects.

Это интересная мысль, стоит ее подумать и потестировать. Т.е. она выглядит логичной -- если у вас "сверху" над вашим рабочим стеком висит еще 15 вызовов Спринга, то GC и правда на каждой итерации (даже при сборке молодого поколения) придется сканировать все эти 15 фреймов, и все достижимые из них объекты. Вопрос лишь в том, каков порядок величины этого эффекта -- начиная с какого уровня заоптимизированности кода имеет смысл начинать думать об этом, как о возможном лимитирующем факторе.

java.io.File is not immutable

Удивительно, но факт: несмотря на то, что контракт java.io.File явно указывает, что Instances of the File class are immutable; that is, once created, the abstract pathname represented by a File object will never change., однако поле File.path -- не final. Почему оно не-final тоже, в общем-то, понятно -- чертова сериализация, мать ее. Однако от нарушения контракта это не спасает. Я, поначалу, думал, что возможно safe publishing обеспечивается неявным мембаром при вызове какого-нибудь нативного метода в ходе инициализации -- но нет, авторитетные источники подтверждают -- баг как баг. И место его возле параши теперь здесь. Правда, приоритет Low, и поправлен будет не раньше 1.8 -- а до тех пор считать объект File immutable в том смысле, в котором это понимают в concurrency -- строго говоря, нельзя.

Такие вот у нас печеньки...

What the JVM Does With Your Bytecode When You're Not Looking

Øredev 2011 - JVM JIT for Dummies (What the JVM Does With Your Bytecode When You're Not Looking)

View more presentations from Charles Nutter

Arrays.sort() через Unsafe

Наблюдая за тем, как Даг Ли в последних версиях FJ активно использует Unsafe для доступа к массивам, мне пришел в голову вопрос: а что будет, если взять реализацию Arrays.sort(), и переписать ее через Unsafe[.arrayBaseOffset(), .arrayIndexScale(), .putXXX(), .getXXX()]? Казалось бы, таким образом можно избавиться от range checks. Да, JIT умеет их и сам убирать -- но лишь тогда, когда может доказать, что конкретный сценарий доступа к массиву эти самые границы гарантированно не нарушает. В сортировке доступ к массиву идет довольно причудливым паттерном, и кажется, что JIT-у вряд ли по силам доказать отсутствие необходимости проверки границ.

Я не поленился -- переписал Arrays.sort(long[]) на прямой доступ. UnsafeArraysSorter.java (у меня все еще 1.6, так что тимсорта не ждите). Прогнал тесты -- и вот фиг вам. Классическая реализация стабильно немного быстрее (+2-3% -- разброс результатов здесь маленький, так что даже такая мелочь вполне заметна).

Сижу теперь, и думаю -- да как же это? Либо JIT в целом умнее, чем я думал, либо он что-то особенное знает об Arrays.sort() :) Второй вариант мне кажется вероятнее. А власти-то -- скрывают!

Cache-coherency #2: от MSI к MESI и далее к звездам (MESIF, MOESI)

Как я и обещал в предыдущей статье -- продолжаем разбор протоколов когерентности. Самый простейший рабочий вариант, MSI, я рассмотрел, теперь мы попробуем его оптимизировать. И прежде чем начать это богоугодное занятие, неплохо бы предварительно сформулировать, что именно мы собираемся оптимизировать. Поскольку у нас нет под рукой тестового стенда, где котором ответ на этот вопрос можно было бы получить в результате нескольких сотен экспериментов, мы воспользуемся априорными догадками (зная ответ, делать априорные догадки несложно, да)

Во-первых, кажется достаточно очевидным, что сама шина, по которой происходит общение различных участников, является разделяемым ресурсом с конечной пропускной способностью, и какими-то, ненулевыми, задержками (latency). Поэтому одной из очевидных целей при оптимизации протокола является уменьшение количества запросов по шине, насколько возможно. Как минимум, для наиболее частых паттернов работы с данными.

Во-вторых, кажется так же очевидным, что основная память у нас по-прежнему является заметным тормозящим фактором, запросы к ней обрабатываются сравнительно долго, поэтому второй очевидной целью является уменьшение количества запросов к основной памяти. Опять же, насколько это возможно, или, хотя бы, для наиболее частых паттернов работы с данными.

Что же, исходя из этих целей, мы можем сделать с MSI?

Битва за эксклюзив

Любопытной особенностью MSI является то, что любой немодифицированный блок данных (не-М) считается потенциально "разделяемым" (Shared). Что здесь любопытного? -- то, что такое утверждение сильно не соответствует реалиям работы абсолютного большинства приложений.

В реальных приложениях очень значительная доля данных востребована в конкретный момент только каким-то одним потоком (==одним процессором). Для примера можно вспомнить, что часть приложений вообще однопоточная, часть использует многопоточность лишь изредка, для каких-то тяжелых вычислений. И даже в изначально сильно конкурентных приложениях заметная часть памяти -- это локальные, приватные данные конкретного потока, и лишь небольшая часть памяти действительно используется как разделяемая (т.е. с ней активно опрерируют несколько потоков примерно в одно время).

А что, собственно, такого неудобного в состоянии Shared? Неудобно то, что разделяемое состояние -- это состояние, об изменениях которого нужно отчитываться (оповещать по шине). Точнее, нас волнует один из самых частых переходов: S -> M. Сделаем мысленный эксперимент: представим себе, что у нас в кэше 1000 строк в состоянии S (это начальное состояние после загрузки из основной памяти в MSI). Сейчас, чтобы изменить любую из них, нам обязательно нужно пустить по шине "я изменяю строку №ХХХ!". Зададимся вопросом -- а в каком проценте случаев это оповещение действительно кому-то будет интересно? Для какого процента строк "может быть shared" будет означать "в самом деле shared"? Если прочитать еще раз предыдущий параграф, то можно предположить, что с большой вероятностью таких случаев будет немного. Значительная, может быть даже доминирующая часть "может быть Shared" строк на самом-то деле нифига не Shared вообще. Но мы, "на всякий случай", вынуждены заполнять шину оповещениями об их изменениях.

Возникает свежая идея: дополнить граф состояний строки еще одним состоянием -- "единственная, немодифицированная (в отличие от М) копия". Забегая вперед, это состояние мы будем называть E(xclusive). (Нам даже не придется расширять поле состояния -- для 3 состояний MSI нужно было 2 бита, и для 4 состояний нашего нового протокола все еще достаточно 2 битов).

Идея кажется весьма козырной: если бы нам удалось дополнить протокол когерентности так, чтобы все якобы разделяемые, но реально эксклюзивные копии имели тип E вместо нынешнего S -- мы бы имели возможность модифицировать такие строки втихомолку, не занимая шину никакими оповещениями.

Однако если мы попытаемся прикинуть, как можно реализовать в протоколе слежение за количеством копий -- нас поджидают некоторые сложности. Во-первых, текущее количество копий строки нужно где-то хранить. Хранить можно либо в каком-то общем реестре -- тогда нужно организовывать этот реестр, и решать проблемы арбитража для доступа на его обновление. Хранить можно вместе с самой строкой в локальном кэше (т.е. число копий расширяет "состояние строки") -- тогда возникает вопрос синхронизации этого поля.

Но это все еще цветочки -- самый главный вопрос состоит в том, каким образом поддерживать актуальность этого поля "количество копий"? Положим, если у меня есть копия строки, и текущее количество ее копий, то увеличение количества копий я могу фиксировать просто слушая шину на предмет запросов "хочу строку №ХХХ" (хотя уже даже здесь надо допридумывать метод, как я узнаю текущее количество копий изначально -- когда еще только буду запрашивать свою копию -- но этот-то вопрос еще обозрим). А вот как мониторить уменьшение количества копий? Основная причина "пропадания" копии -- это просто вытеснение ее из чьего-то кэша новыми данными. Но если оглашать по шине все вытеснения -- это будет очень существенное увеличение трафика!

В самом деле, несложно прикинуть: размер кэша как правило гораздо меньше общего объема данных, обрабатываемых программой. Это значит, что почти каждый блок данных пребывает в кэше лишь небольшое время, после чего вытесняется оттуда другим блоком. Отсюда легко понять, что количество вытеснений с довольно высокой точностью будет просто равно количеству загрузок. То есть, если мы будем оповещать по шине о вытеснениях -- мы удвоим (по крайней мере, по количеству запросов) тот трафик, который уже порождается на шине запросами на загрузку данных из памяти

Похоже, мы попадаем из огня да в полымя -- прямолинейная попытка оптимизации заводит нас дальше, чем хотелось бы.

За неимением гербовой -- попробуем писать на туалетной...

Ок, давайте попробуем не требовать слишком многого. Кажется, что строго разделить Shared и Exclusive состояния будет стоить нам слишком дорого -- ладно, попробуем разделить их не совсем строго. Попытаемся найти, при каких обстоятельствах можно легко гарантировать, что какая-то строка сейчас принадлежит только одному кэшу -- и оставим более сложные случаи без специальной обработки. Т.е. Exclusive у нас будет точным состоянием -- мы гарантируем, что строка с таким состоянием действительно существует только в одном кэше. А Shared останется не точным -- может, есть еще другие копии, а может быть и нет.

Видится две возможности. Первая из них -- это момент загрузки строки. В этот момент адрес запрашиваемой строки виден всем на шине -- так пусть все, у кого уже есть ее копия, в этот момент отчитаются каким-нибудь сигналом, типа "а у меня такая уже есть!". Если вместе с запрошенной строкой мы получаем еще и сигналы "а у меня есть" -- мы сразу ставим ее состояние в S. Если таких сигналов не приходит -- мы загружаем ее в столь вожделенное нами E.

Вторая возможность -- это если у нас сейчас строка в M, и мы выполнили сброс изменений в основную память. В этом случае мы знаем, что больше ни у кого пока этой строки нет (состояние М это нам гарантирует), поэтому мы имеем право сменить статус не на S, а на E.

Эта часть выглядит логично, но ее применимость весьма условна -- потому что модифицированные строки у нас нигде по собственному желанию в память не сбрасываются, это всегда происходит по необходимости. Либо строка просто вытесняется из кэша новой строкой -- тогда возможность ее поставить в E бесполезна, ведь она вытесняется. Либо сброс значения спровоцирован чьей-то сторонней попыткой чтения той же строки -- и тогда, опять же, завершив write back, кэш сбросит строку в Invalid.

Подведем итог. Чтобы реализовать возможность загружать строки сразу в E нам нужно, чтобы каждый кэш мониторил шину на предмет запросов на чтение всех строк, которые он сам содержит (в любом состоянии, кроме I, разумеется -- а раньше было достаточно мониторить шину только на предмет запросов строк, которые у меня в M).

Если кэш обнаруживает запрос, на строку, которая есть у него -- он проверяет, в каком она у него состоянии. Если состояние M -- тут все, как и раньше (прерываем транзакцию, форсируем write back...). Если состояние S -- просто запускаем по шине сообщение "у меня такая есть". Если состояние E -- запускаем по шине "у меня такая есть" и меняем свое состояние на S.

Кэш, желающий загрузить строку, посылает на шину обычный запрос "хочу строку №ХХХ". Но теперь он еще и продолжает мониторить шину на предмет обратной связи. Если на шине появляются комментарии "а у меня такая есть" -- он запоминает этот факт, и, когда дождется получения строки, ставит ей статус Shared. Если же комментарии отсутствуют -- строка загружается в Exclusive.

Какой профит мы получаем от всех этих усложнений? Мы получаем возможность модифицировать строки в E без дополнительных оповещений по шине, просто молча меняя их состояние на M.

Встречайте, MESI

Увы, но все вышеперечисленное, к сожалению, уже было придумано до нас. Причем задолго до нас. В общих чертах это похоже на протоколы когерентности Write-once и его чуть более оптимизированного наследника, MESI. MESI, придуманный некогда (не смог сходу нагуглить когда именно) в университете Иллинойса, используется для поддержания когерентности начиная с Pentium, и, с некоторыми усовершенствованиями, до наших дней.

Собственно, прочитать про него в подробностях (по правде говоря -- очень кратких подробностях) можно по ссылке выше. Для удобства я скопировал из статьи сюда ссылку на диаграмму переходов для его состояний (по клику открывается в полный размер). От "изобретенного" нами протокола он отличается только одной деталью -- два-в-одном запросом RFO, request for ownership. RFO это запрос на чтение строки, принудительно загружающий ее в Exclusive. RFO примерно эквивалентен склееным в одну транзакцию запросам "дай строку №ХХХ" и "модифицирую строку №ХХХ".

Действие RFO такое: я получаю запрошенную строку, а все остальные, у кого еще есть ее копия, эту копию выкидывают (переводят в I). В случае, если у кого-то строка была в M, и выбросить ее просто так нельзя, используется уже знакомый нам механизм: владелец строки в состоянии M прерывает транзакцию, сбрасывает в память модифицированную строку, меняет ее состояние у себя на E. Через какое-то время исходный кэш повторяет RFO.

С этим сдвоенным запросом есть некоторые разночтения, относительно его точной семантики. Например, на приведенной выше диаграмме его нет -- вместо него есть запрос RWIM, read with intent to modify, который сразу переводит строку в M (т.е. это будет точный аналог "дай строку №ХХХ" и "модифицирую строку №ХХХ"). RFO же загружает строку в E. Я не уверен, является ли эта разница реально существующей (например, зависит от реализации протокола), или это просто кто-то что-то неправильно понял. Но это не так важно -- с точки зрения именно трафика на шине разницы между RFO и RWIM по сути нет -- если уж я загружаю строку в E, то я собираюсь ее модифицировать, но переход E->M трафика на шине не порождает, это, по-сути, внутреннее дело того кэша, в котором строка сейчас содержится.

Еще на диаграмме есть приятный бонус для внимательных читателей -- в виде небольшой неточности, которую вы можете попробовать поискать сами :) А кто нетерпелив -- может просто выделить ответ: На пути "read" -> "miss" -> "1 copy" из узла "snooping core's state: E/M" есть, на самом деле, еще один, третий выход: "snooping core's state: S". Как мы уже обсуждали, состояние S не точное, поэтому, даже если физически на данный момент копия строки есть только в одном кэше, она вполне может быть там в состоянии S. Добавить этот выход несложно -- мы просто присоединяемся к маршруту "Multiple copies of state S" шагом раньше.

Вообще, надо заметить, что MESI это не столько прямо точно-детально проработанный протокол, с точно прописанными способами перехода между состояниями. Скорее, это шаблон: общая идея в виде 4-х состояний и графа переходов между ними. Конкретные детали -- каким именно обменом какими сообщениями по шине обеспечивается конкретный переход -- MESI не специфицирует, это оставлено на откуп реализациям. Правильнее, наверное, будет говорить о семействе протоколов MESI, или о том, что конкрентный протокол использует в основе MESI.

Что дальше: Intel MESIF

До сих пор мы старались выполнить программу оптимизации по одному направлению -- уменьшение трафика на шине. Но, возвращаясь к началу статьи, есть еще одно направление -- уменьшение количества запросов к основной памяти (пора бы уже уточнить, что "основная память" -- это не обязательно прямо-таки RAM, в нашем контексте это "общая память", в отличие от "локальных" кэшей каждого CPU. То есть чаще всего в роли "основной памяти" будет выступать тандем L2[+L3]+RAM, а в роли локальных кэшей -- L1).

Внимательный читатель наверняка уже заметил, что до сих пор, во всех случаях, когда какой-то кэш просил дать ему строку #XXX, мы адресовали этот запрос контроллеру основной памяти. И это часто выглядело довольно нелогично, потому что во многих случаях копии запрошенной строки уже есть в каком-то из локальных кэшей. Поскольку локальный кэш заметно быстрее основной памяти, кажется, что он мог бы и ответить на запрос -- это и пропускную способность шины памяти сохранило бы, и уменьшило бы время ожидания запрошенной строки.

Позволить локальным кэшам, имеющим копию строки, отвечать на запросы ее копии вместо основной памяти -- это довольно очевидная оптимизация базового MESI. У меня нет точных сведений, с какого момента она начала применяться, но кажется, что уже довольно давно. Однако, у простейшей реализации этой идеи есть подводные камни. Один из них -- это множественные ответы для часто используемых (читаемых) строк. В самом деле, пусть строка №42 сейчас уже сэширована в 3-х различных кэшах (как Shared, разумеется), и по шине приходит очередной запрос на ее копию. Легко понять, что либо запрашивающий получит 3 ответа подряд (с идентичным содержимым, разумеется), либо необходимо придумывать дополнительный протокол арбитража, позволяющий решить, кто именно из 3-х счастливых обладателей просимых данных сейчас будет отвечать. (Легко видеть, что проблема возникает только с Shared строками -- у E строк есть эксклюзивный владелец, а с M-строками мы будем разбираться далее)

Intel в своих Nehalem'ах постаралась уменьшить мусорный трафик множественных ответов за счет добавления еще одного состояния -- F(orwarded). Получился протокол MESIF. Состояние Forwarded -- это подтип Shared -- выделенный Shared, первый среди равных. То есть, если сейчас копии строки присутствуют в нескольких кэшах, то (скорее всего, хотя не обязательно) одна из этих копий будет F, а остальные S. Как несложно догадаться, именно та копия, которая F, и будет отвечать на запросы.

Любопытно, каким образом назначается состояние F. Алгоритм назначения напоминает эстафетную палочку -- в F всегда оказывается та копия, которая была создана последней. Т.е. начинаем мы, как обычно, с того, что в каком-то кэше лежит строка в Exclusive. При запросе копии другим кэшом -- кэш-владелец E-строки отвечает на запрос вместо основной памяти, и одновременно меняет состояние своей строки на Shared. А вот новая копия, созданная по его ответу, будет как раз в Forwarded. И на следующий запрос копии будет отвечать уже ее владелец -- и, ответив, он сбросит состояние своей строки на обычное S, а только что созданная копия в другом кэше станет новым F -- и так далее...

Логика здесь такая: во-первых, статистически, последняя загруженная копия скорее всего будет и последней выгруженной. То есть такая передача ответственности позволяет как можно дольше избегать пропадания выделенной копии (пропадания за счет вытеснения). А во-вторых, передача ответственности позволяет балансировать нагрузку -- дополнительные обязанности по ответу на запросы копии не висят постоянно на одном и том же кэше, а передаются от кэша к кэшу эстафетой.

Дополнительные бонусы возникают в случае NUMA архитектуры -- собственно, Nehalem именно ей и является. В случае NUMA ответственная F-копия будет чаще оказываться в "территориально" более близком блоке кэша -- более близком к тому, который следующим захочет получить копию.

Под конец хочется заметить, что здесь -- как и в случае с Exclusive -- разработчики предпочли простоту точности. А именно: описанная схема не гарантирует, что среди нескольких Shared строк всегда будет хотя бы одна Forwarded (хотя гарантирует, что Forwarded будет не больше одной). Forwarded копия может быть вытеснена из кэша так не успев никому передать своей эстафеты. Как тогда ведет себя система я точно сказать не могу, скорее всего просто на очередной запрос ответит основная память. И новая копия станет F. Но допуская эту, не очень вероятную ситуацию, мы взамен получаем простой и дешевый протокол назначения и поддержания выделенного ответственного кэша. В то же время попытавшись гарантировать существование и единственность F-копии мы бы залезли бы в такие же дебри, как и с Exclusive состоянием ранее.

AMD: MOESI

Еще одно интересное расширение к MESI предлагает AMD в своих Opteron-ах -- пожалуй, даже более интересное, чем предыдущее. Целью здесь тоже выступает снижение трафика с основной памятью, но здесь мы стараемся оптимизировать трафик записи. А именно, в MESI любое чтение строки, которая у кого-то находится в модифицированном состоянии, вызовет сложную последовательность телодвижений. Ну, вы уже, наверное, выучили эту мантру: отмена транзакции, сброс модифицированных данных в основную память, смена состояния своей копии на Shared, перезапрос копии... Возникает вопрос: зачем так сложно (и долго), когда кэш, владеющий M-копией может просто ответить на запрос чтения, переслав свои (самые актуальные!) данные? Это позволит убить трех ушастых сразу: и запрос чтения будет выполнен гораздо быстрее, и трафик на межпроцессорной шине будет меньше, и сброс данных в основную память можно отложить до более удобного случая.

Идея здравая, хотя ее реализация чуть сложнее, чем кажется поначалу. Проблема, которую нужно решить -- как быть с повторными модификациями строки, если ее данные уже размножены? AMD решила ее дополнив MESI состоянием O(wned). Получившийся MOESI работает, насколько мне удалось понять, таким образом: во-первых, функции M-состояния расширяются -- кэш, который содержит строку в таком состоянии, должен отвечать на запросы копии этой строки. Отвечая на такой запрос, он меняет свое состояние строки с M на O, а получивший копию кэш ставит ее в S.

Owned состояние, таким образом, означает "копия не синхронизирована с памятью, и существуют другие копии". Пока Owned строка существует, она продолжает отвечать на все запросы копии. Если процессор, владеющий этой строкой, снова решит ее модифицировать -- состояние меняется снова на M, и бродкастом рассылается запрос на инвалидацию для всех Shared-копий.

Разумеется, любой запрос на вытеснение Owned строки будет задержан на время сброса ее данных в основную память.

Отличие от реализации интела здесь в намерении -- интел оптимизировал чтение, тогда как AMD -- запись. Как мне видится, на архитектуре с MOESI будет эффективно выполняться сценарий "писатель-читатель". Если один поток пишет данные в разделяемую память, а второй, с некоторой задержкой, их оттуда читает, то MOESI позволит всю эту передачу данных выполнять без участия основной памяти -- непосредственно от кэша к кэшу.


Продолжение следует: в следующей серии я попробую разобрать, как на уровне протокола кэш-когерентности выглядят типичные шаблоны concurrency.

Ссылки

MESI @ wikipedia -- оттуда же ссылки на MESIF/MOESI протоколы

MESIF/MOESI

Cache-coherency #1: Basics, MSI

Поскольку я сам в настоящее время разбираюсь с организацией межпроцессорного взаимодействия, хочется иногда упорядочить полученную информацию. Я решил делать это в форме написания статей статей :) И начну с протоколов поддержания когерентности.

Что такое когерентность кэшей (cache coherence)? Это (применительно к многопроцессорным системам с кэш-памятью) свойство согласованности данных, вообще говоря разбросанных по различным кэшам. Очевидно, что если у нас одни и те же данные могут быть скэшированы в кэш-памяти разных уровней, и в локальных блоках кэш-памяти разных процессоров/ядер -- при модификации этих данных легко может случиться, что существует множество несогласованных версий одних и тех же данных. Можно, конечно, возложить обязанность разруливать все эти конфликты на программиста -- но это слишком жестоко. Поэтому производители процессоров обычно реализуют какой-либо аппаратный механизм поддержания согласованности данных различных кэшей между собой, и с основной памятью. Где-то (как например на Интеллах) этот протокол весьма функционален, и делает для программиста почти все, кроме, разве что, минета. Где-то (тут я затрудняюсь с точными примерами, на ум приходят только ARM и почившая Alpha) заметная часть работы возложена на программиста (или компилятор) -- от него требуется явно расставлять в коде инструкции барьеров памяти, форсирующие синхронизацию данных.

Из предыдущего абзаца становится понятно, что когерентность кэша довольно тесно связана с аппаратной моделью памяти соответствующей системы. Собственно, аппаратная модель памяти складывается из тех гарантий, что дает протокол когерентности кэшей (если он вообще дает какие-то), плюс особенности внутрипроцессорных оптимизаций (наличие буферов записи, упреждающее чтение, и прочая уличная магия). По моделям памяти, надеюсь, я еще напишу не одну телегу :)

Возможных вариантов организации когерентности -- пруд пруди. Поскольку меня интересуют многоядерные системы -- я буду рассматривать наиболее часто используемую здесь реализацию когерентности через "подслушивание" (snooping).

Что такое подслушивание (snooping): у нас есть общая шина, к которой подключены кэши всех ядер, и к ней же подключен контроллер основной памяти (InterConnect -- это как раз она). Любые запросы отправляются бродкастом на шину, и видны (слышны?) всем участникам вечеринки сразу. Принципы коммуникации через шину:

1. Шина считается надежной средой -- т.е. нет никаких циклов запрос-подтверждение. Если я запустил по шине какую-то транзакцию, и она завершилась -- значит все участники ее видели, и все с ней согласны. Не возможна ситуация, что кто-то мог не получить сообщение, или кто-то мог не успеть ответить. Разумеется, это все с точки зрения высокоуровневых протоколов -- на уровне реализации в железе, возможно, такие циклы и есть, но с этим уровнем я не знаком. При этом, все-таки, довольно очевидно, что это свойство ограничивает масштабируемость snoop-based систем поддержания когерентности -- реализовать надежный протокол без подтверждений в больших масштабах будет сложно.
2. "It's more blessed to ask forgiveness then permission": если я хочу что-то сделать, я не спрашиваю остальных участников "согласны ли вы?" -- я просто начинаю транзакцию, реализующую мое намерение. Начатую мной транзакцию видят все участники, поэтому если кто-то из них имеет что-то сказать против -- он прерывает транзакцию, и начинает свою. Влезать в чужую транзакцию -- это вполне регулярный элемент протоколов кэш-когерентности.
3. При этом все участники действуют все-таки кооперативно -- например, "протестующий" участник не тянет тупо одеяло на себя, а помогает исходной транзакции, которую он прервал -- просто выполняя свою дополнительную транзакцию, он в чем-то подправляет исходную. Другой пример: если я прервал чью-то транзакцию, все участники коммуникации полагают, что мне есть что сказать важного, поэтому, на ближайший такт все (кроме меня) добровольно замолкают, давая мне возможность спокойно высказаться.

MSI: plain and easy

Придумать протокол поддержания когерентности начального уровня не так уж сложно. Особенно это становится просто, когда знаешь ответ. Сколько состояний элементарного блока данных (такой блок называется cache line -- строка кэша) нам нужно для самого минимального протокола кэш-когерентности? Как минимум, нам нужна возможность различать, когда строка в моем локальном кэше "свежая" (т.е. ее содержимое не отличается от содержимого основной памяти), и когда она "несвежая" (изменена мною, и еще не синхронизирована с памятью). Отсюда мы и будем плясать.

Второе ("грязное") состояние логично называется M(odified), и его особенность в том, что если допустить возможность иметь одну и ту же строку в нескольких разных кэшах в таком состоянии -- мы получим проблему слияния изменений. То есть если у нас копия одного участка памяти в кэшах разных процессоров, и каждый процессор внес в нее свои изменения -- то результат в основной памяти будет зависеть от порядка сброса данных в основую память. Нам нужно либо как-то формализовывать этот порядок (что само по себе отдельный гемморой), либо допускать, что результат будет неопределенным (зависеть от порядка сброса кэшей). По-сути, и в том, и в другом случае мы заметно усложняем модель памяти, поддерживаемую нашим протоколом -- что, безусловно, будет добавлять седых волос программистам. Возможно, кто-то так и делает -- но не мы :)

В протоколе MSI принято решение разрубить этот гордиев узел на корню -- мы просто не допускаем такой ситуации. А именно -- Modified это по смыслу Exclusive Modified, и конкретная строка кэша в каждый момент времени может быть в таком состоянии не более чем в одном из кэшей. Другими словами: если я вижу в кэше процессора №2 строку №42 со статусом M -- я могу утверждать, что сейчас больше ни в чьем другом кэше строка №42 не скэширована.

Теперь мы можем перейти к первому состоянию -- когда строка "свежая", не модифицированная. Или, что то же самое, ее содержимое совпадает с содержимым основной памяти. Это состояние (неожиданно) называется S(hared). Почему "разделяемое"? -- потому что в этом состоянии есть важное свойство: строка с таким состоянием может быть свободно скэшированной в хоть во всех кэшах сразу. Что дает возможность эффективно читать одни и те же данные хоть всем ядрам одновременно, не мешая друг другу -- просто каждый получит свою копию в своем персональном кэше. Это свойство "разделяемости" для нас очень важно, поэтому и Shared, а не, скажем, Clean (хотя можно читать и как Sync'ed, при желании).

Третье, и последнее состояние -- I(nvalid). Это, по смыслу, просто отсутствие такой строки в кэше. Флаг "removed".

MSI в движении

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

...Итак, процессор №1 делает запрос на блок данных №42. Его локальный кэш обнаруживает, что таких данных в нем нет (либо нет вообще, либо они есть в состоянии Invalid). Кэш открывает на шине транзакцию "дайте мне кто-нибудь блок данных №42". Если больше ни у кого этот блок не скэширован, то на запрос отвечает основная память -- просто пересылает ему нужный блок. То же самое происходит, если блок у кого-нибудь скэширован, и находится в состоянии Shared: на запрос по-прежнему отвечает основная память, остальные участники молчаливо со всем соглашаются.

Жизнь становится чуть сложнее, если блок есть у кого-нибудь в состоянии Modified. Если процессор №2, слушая шину, видит на ней транзакцию чтения строки, которая у него в состоянии M -- он отменяет транзакцию (посылает на шину всем стоять, трамвай, прижаться к стенке #ABORT). Транзакция чтения отменяется, в следующий такт (в который -- помните? -- все остальные будут вежливо молчать) процессор №2 начинает процедуру write-back -- транзакцию сохранения измененных им данных в основную память. Завершив ее, процессор №2 изменит состояние своей копии строки №42 на Shared. Процессор №1, дождавшись освобождения шины, повторит запрос на чтение строки №42 -- и теперь уже беспрепятственно получит ее от основной памяти (т.е. мы возвращаемся к предыдущему абзацу).

Что если я хочу изменить данные? Самый простой здесь случай -- это если у меня строка уже в кэше, и в состоянии Modified. Это значит: а) больше ее ни у кого нет, и б) она уже была мной модифицирована. Тогда я ее просто еще разок меняю, и никому об этом не обязан отчитываться (т.е. на шину в этом случае вообще ничего не идет -- я ведь знаю, что эта строка гарантированно ни у кого больше не скэширована, а значит -- никого больше не интересует).

Отдельного внимания достоин вопрос о том, когда же я все-таки сброшу свои M-строки в основную память. Один из таких случаев рассмотрен выше -- я вынужден это сделать немедленно, если кто-то другой потребует модифицированные мною данные. Другой, довольно очевидный случай -- когда строка будет вытесняться из кэша другими данными (кэш-то, увы, не резиновый). Собственно, в простейшем варианте этих двух триггеров достаточно. Как видно, мы стараемся отложить запись в основную память насколько возможно. Такая стратегия называется "отложенная запись" (write back). Есть более раритетная стратегия "сквозной записи" (write through) -- при этом каждая запись в кэш сразу же дублируется в основную память. Сейчас, насколько мне известно, этот способ почти не применяется

Вернемся к модификации -- она чуть сложнее, если строка у меня в данный момент в состоянии Shared. Тогда я уже не могу быть уверен, что ее больше нет ни у кого (S это не "гарантированно shared", это "может быть shared"). Поэтому я вынужден, на всякий случай, оповестить всех о своих гнусных планах испортить девственно чистую строку: я объявляю по шине что-то вроде "я модифицирую строку №42". Если у кого-то эта строка есть (а если она есть -- она может быть только тоже в Shared) -- эти кэши, услышав мое оповещение, переводят ее в Invalid (==удаляют).

Последний вариант: если строки в моем кэше еще вообще нет. Простейшим способом здесь будет вылить чайник на плиту и свести задачу к предыдущей: начать так же, как в случае чтения, получить строку в S, и потом, отдельной транзакцией, перевести ее в M.

Собственно, на этом про MSI, в его простейшем варианте -- все. Продолжение (MESI, MESIF, MOESI) в следующих сериях...


UPD:

А, собственно, зачем нам что-то лучшее?

Недостатков и возможностей оптимизации в описанной версии протокола -- не счесть. Для затравки -- парочка самых интересных.

Во-первых, передача строки из одного кэша в другой получается нерационально дорогой. Пусть у нас есть простейшая модель Поставщик-Потребитель, когда один процессор пишет данные в какую-то область памяти, а второй их оттуда читает. Как эта штука будет выглядеть с точки зрения протокола: сначала Поставщик затребует себе строку в S, потом объявит по шине что хочет перевести ее в M, потом запишет в нее данные. Затем Потребитель дойдет до этого же участка памяти, запросит строку из памяти. Поставщик вмешается, и отменит транзакцию чтения, взамен ее запустит транзакцию сброса своей строки в основную память. Потребитель дожидается окончания этой транзакции, запрашивает данные из памяти -- и получает их в Shared. Итого: 5 транзакций, из них 2 чтения из основной памяти и одна запись в нее. При этом легко себе представить идеальный протокол, который, в этом случае, потребует одного чтения, одной пересылки кэш-кэш, и одной записи в основную память, отложенной на неопределенное время.

Во-вторых -- очень неэффективны постоянные переходы S->M. Любая строка начинает свою жизнь в кэше как "потенциально разделяемая", хотя большинство данных скорее всего будут обрабатываться только одним потоком, и, поэтому, будут загружаться в кэш только одного ядра. Но при этом все равно модифицируя только что загруженную строку мы вынуждены оповещать всех по шине "на всякий случай".

False sharing: @Contended, etc...

В статье про false sharing я рассуждал о том, как можно было бы решить проблему на разных уровнях качественности. Одно из предложений было ввести аннотацию типа @PreventFalseSharing, которая бы намекала JVM, что объекты этого типа недурно бы аллоцировать выравнивая их в памяти по границам кэш-строк. Уже в комментариях Алексей мне признался, что аннотация @Contended уже какое-то время обсуждается во внутренностях Оракла.

Другое мое предложение было что JIT мог бы и сам определять в рантайме, какие объекты испытывают contention, и перемещать их в памяти с тем, чтобы contention уменьшить. Это не кажется особо фантастической идеей -- у интелловских процессоров есть внутренние performance counter-ы, считывая которые можно многое узнать о том, на что тратит время процессор. Поскольку узнать о существовании false sharing можно, остальное кажется обычной адаптивной оптимизацией, в которой JIT традиционно силен.

Так вот, вчера, в concurrency-interest Nathan Reynolds (из Оракла) признался, что эта идея тоже уже разрабатывается -- ему известно о целых двух группах. Одна в Интеле, одна в Оракле. У Интела даже был прототип, который, правда, требовал перезапуска JVM для применения собранного профиля.

Правда, по его словам, от обеих групп "что-то уже давно ничего не слышно" :)

Disruptor #3.2: Эксперименты с производительностью -- update

Последняя серия экспериментов закончилась на том, что между самой оптимизированной реализацией очереди и Disruptor-ом все еще оставалось порядка 10% разницы (27 против 30*10^6 сообщений/сек на моем сервере). По косвенным данным, оставшиеся 10% можно было списать на записи ссылок в массив -- в очереди это делается при каждом enqueue, Д же заполняет массив только однажды (Тут надо заметить, что в моем бенче этот эффект так заметен, потому что я тестирую холостой ход -- полезная нагрузка, передаваемая в сообщении у меня всего 1 long. В реальной жизни полезная нагрузка будет побольше, так что одна дополнительная операция записи ссылки потеряется за несколькими операциями записи полей сообщения -- инфа 100%). Еще я грешил на false sharing by card marking -- поскольку ячейки массива идут подряд, их dirty flags должны быть тоже рядом, и должны обновляться при каждой перезаписи. Из этого я сделал вывод, что в 1.7 с +UseCondCardMark все будет шоколадно -- но это фиг проверишь, потому что 1.7 ставить я все еще не готов.

По зрелому размышлению я пришел к выводу, что card marking здесь не при делах. У меня же ссылки в массив пишутся только одним потоком -- который выполняет enqueue. Вот если бы я на dequeue очищал ссылку в null (как, собственно, стоило бы делать в production-ready коде) -- тогда другое дело. Но же я выкинул очистку на одной из первых оптимизаций -- так что у меня по любому single writer получается.

А вот как проверить, что сама запись ссылки порождает 10% оверхеда -- мне пришло в голову вчера. Все довольно просто: у меня же очереди используют пул сообщений (чтобы не плодить лишнюю аллокацию). Пул, естественно, имеет тот же размер, что и очередь (зачем ему больше?), поэтому после первого же прохода все элементы во внутреннем буфере очереди фиксированы -- на следующих проходах они перезаписываются поверх себя же. Достаточно вместо set сделать там test-and-set -- и можно будет проверять.

Эксперименты были запущены, и -- бинго! -- наконец-то мы совершенно догнали Д :) 30*10^6 msg/sec. Предположение о том, что во всем (в оставшихся 10%) виновата запись ссылки в буфер таким образом, похоже, оправдывается. Процесс разборки магии Д на компоненты на этом можно считать закрытым.

Единственное, что остается для меня все еще не понятным -- это нестабильность результатов. Типичные результаты запуска выглядят так:

Turn # 1 takes 67058 ms; 7456232 ops/sec
Turn # 2 takes 15854 ms; 31537782 ops/sec
Turn # 3 takes 16058 ms; 31137128 ops/sec
Turn # 4 takes 16201 ms; 30862292 ops/sec
Turn # 5 takes 16111 ms; 31034697 ops/sec
Turn # 6 takes 15794 ms; 31657591 ops/sec
Turn # 7 takes 60603 ms; 8250417 ops/sec

Это совершенно не похоже на нормальное распределение вокруг среднего :) Ощущение, что система может функционировать в одном из 2 режимов -- либо все хорошо, либо случается какое-то гавно. ЖопойИнтуитивно я ощущаю, что это тот же случай, что и у Питера -- где-то тут недостаточно полей (padding), из-за чего при неудачной дефрагментации после GC внезапно возникает false sharing. Но вот где именно я пока понять не могу. Вроде бы все важные переменные у меня обложены полями по самые гланды...

Thread Affinity

Peter Lawrey, которого я уже как-то упоминал, решил написать свою собственную библиотеку для привязки потоков к ядрам из джавы. Ну, понятно, с шахматами и поэтессами. Его реализация (сам код можно посмотреть здесь) изначально основывалась на JNI-обертке вокруг sched_setaffinity(3)/sched_getaffinity(3). Я не смог удержаться, и вписался -- благодаря чему теперь у него есть и "моя" реализация, использующая JNA. Буду стараться уговорить его забить на поддержку JNI -- гемморой с поддержанием portable build для сборки JNI-обертки по-моему не стоит свеч.

Что меня заинтересовало в его реализации -- так это дизайн. Вместо тривиального setAffinityMask/getAffinityMask он ввел абстракцию "блок кода, выполнение которого привязано к ядру". Выглядит это так:

public void run() {
            final AffinityLock al = AffinityLock.acquireLock();
            try {
                //performance-critical block of code
            } finally {
                al.release();
            }
        }

С текущей реализацией есть несколько проблем.

Во-первых, реализация-то есть только для unix/linux -- для платформ, поддерживающих sched_setaffinity. Моя попытка портировать на винду сходу не удалась -- SetThreadAffinity я еще нашел, а вот где взять GetThreadAffinity -- так и не разобрался. Поскольку у меня еще и нет винды для тестов -- эту часть я решил отложить.
Попытка портировать на Мак (что для меня очень актуальна) обломалась еще более серьезно -- на Маке вообще нет возможности назначать привязку. Интерфейс взаимодействия с планировщиком потоков, который представляет MacOS X начиная с 10.5+ позволяет только давать рекомендации планировщику, относительно того, что данные потоки неплохо бы поместить "как можно ближе" друг к другу -- в смысле разделяемых кэшей. Это практически обратное тому, что хочется.

Во-вторых, сама по себе идея запрещать relocation для preformance-critical (скорее, latency-critical, если уж быть точным) потоков -- она, конечно, хороша. Но это далеко не все, чего бы хотелось от интерфейса управления привязками. Навскидку, я могу придумать такие пункты:

1. Запрещать перемещение потока во время выполнения определенного кода. Это то, что делает библиотека Питера. Т.е. мне пофигу, на каком ядре будет выполняться код, но я хочу, чтобы это ядро было фиксированным все время выполнения данного участка кода. Что я пытаюсь этим выиграть? -- я хочу не тратить время на смену контекста и прогревание кэша при перемещении потока.
2. Закрепить ядро за конкретным потоком эксклюзивно. Расширение предыдущего пункта -- мало того, что я хочу запретить перемещение моего потока с текущего ядра, так я еще и хочу запретить перемещение любого другого потока на это ядро (и, разумеется, выпинать с этого ядра те потоки, которые уже на нем сидят сейчас). Что я хочу выиграть здесь? -- в основном, я хочу получить весь кэш ядра только для своего потока.
   Сложность здесь в том, что внутри работающей JVM есть хуева туча потоков, выполняющих всякие системные надобности. Начиная от совсем внутренних потоков JVM, типа GC/Finalizer и JIT-compiler, и кончая потоками, запускаемыми внутри стандартной библиотеки -- типа всяких таймеров, чистильщиков очередей слабых ссылок, и прочего мусора. Получить доступ к этим потокам, чтобы можно было явно запретить им использовать определенные ядра -- довольно непросто.
   Немного усиленный вариант -- запретить использование не только конкретного логического ядра, а именно физического -- т.е. в случае hyper-threading запретить использование парного аппаратного потока. Смысл такой: "а ну отъебитесь все от моего кэша".
   Дополнительная, хоть и сомнительная, опция -- распространить эту эксклюзивную привязку на всю систему. То есть не только в рамках текущего процесса JVM все потоки кроме выделенного обходят данное ядро стороной -- но и глобально во всей системе никто более на это ядро не претендует. Сомнительна эта опция потому, что кажется не очень хорошей идеей позволять конкретному приложению вмешиваться в работу планировщика потоков на уровне всей системы -- не по чину ему.
3. Связать группу потоков (идея из MacOS X API). Т.е. я хочу, чтобы определенная группа потоков была расположена на таких ядрах, коммуникация между которыми будет максимально дешева. При этом мне все равно, какие именно это ядра.

Вопрос состоит в том, как именно максимально абстрактно соединить в одном API все эти опции...

P.S. Как мне подсказывают, это мой сотый пост за время ведения блога. Ура мне!

final-поля для безопасной публикации

В догонку к обсуждениям семантики final-полей. Обычный класс, с изменямыми полями, сложно безопасно опубликовать через data race (т.е. без синхронизации):

sharedRef = new Mutable();

Но можно опубликовать через "обертку" -- класс с final-ссылкой:

sharedRef = new ImmutableReference(new Mutable());

И у меня давно уже бродит идея -- почему бы не сделать сам класс для себя "публикующей оберткой"?

public class SelfPublisher {

    private int value;

    private final SelfPublisher safeThis;

    public SelfPublisher( final int value ) {
        this.value = value;
        this.safeThis = this;
    }

    public int getValue(){
        return safeThis.value;
    }
}

Насколько я вижу -- это позволит совершенно безопасно публиковать его через даже data race. Ценой -- увы -- дополнительных затрат памяти на избыточное поле. Ну и дополнительной операции присваивания в конструкторе.

P.S. Код -- уродлив, по моим критериям изящества. Это, скорее, трюк, чем пример для подражания :) И use case для него тоже довольно туманен. Но сама идея мне показалась любопытной.

Гарантии для final-полей

На днях была интересная переписка с Глебом Смирновым, автором статьи про модель памяти на Хабре. Мы обсуждали тонкости спецификации final-полей. Камнем преткновения был такой пример:

public class A {
    public int value;
    public final int finalValue;

    public A(final int value, final int finalValue) {
        this.value = value;
        this.finalValue = finalValue;
    }
    ....
}

//где-то в коде Thread1:
public A sharedReference = new A();

//где-то в коде Thread2:
if( sharedReference != null ){
    //
    final int finalValue = sharedReference.finalValue;
    final int value = sharedReference.value;
}

Довольно общеизвестно, что спецификация final-полей в JMM гарантирует, что доступ к .finalValue корректный (== запись значения в .finalValue внутри конструктора происходит до чтения .finalValue через общедоступную ссылку, присвоенную после завершения конструктора). Вопрос в том, является ли корректным в том же смысле чтение поля .value? Т.е. можно ли сесть на хвост (piggyback) той магии, которая приводит к корректной передаче значений final-полей между потоками?

На первый взгляд кажется, что можно -- ведь обычные ребра happens-before транзитивны: A hb B, B hb C => A hb C. При этом дано, что действия, идущие до А в program order идут до А и в happens-before order -- т.е. в рамках одного потока частичный порядок HB совпадает с порядком инструкций в коде программы. Значит, поскольку присвоение значения полю .value в конструкторе происходит до присвоения .finalValue, а присвоение .finalValue происходит до чтения в потоке 2, а оно, в свою очередь, происходит до чтения .value в потоке 2 -- то по транзитивности получается, что присвоение .value в конструкторе happens-before чтения .value в потоке 2.

Однако©, на самом деле© -- это неправда. Ну, мне так кажется :)

---

Во-первых, определение отношения порядка в случае операций с final-полями содержит такое уточнение (Евангелие от ИоанаJMM, 17.5.1): Given a write w, a freeze f, action a (that is not a read of a final field), a read r1 of the final field frozen by f and a read r2 such that hb(w, f), hb(f, a), mc(a, r1) and dereferences(r1 , r2), then when determining which values can be seen by r2, we consider hb(w, r2) (but these orderings do not transitively close with other happens-before orderings). (выделение мое)

То есть то отношение порядка, порождаемое семантикой final-полей -- это такое особое happens-before. Оно почти как обычное happens-before, но не транзитивно с ним.

Во-вторых, чтобы быть совсем строгим, я попытаюсь продраться через формальное определение семантики в 17.5.1. Читать такое на русском я когда-то очень неплохо умел, но буржуйский -- другое дело, так что прошу ногами пианиста не бить, он играет как умеет. Лучше в комментариях предлагайте свои варианты трактовки. Итак, поехали:

---

Чтобы определить семантику final-полей нам понадобится несколько новых терминов. А именно:

Заморозка (freeze) -- это специальное действие, которое происходит в момент завершения (нормального, или с выбросом исключения) конструктора объекта, содержащего final-поле.

Помимо заморозки нам понадобятся еще два специальных частичных порядка (кроме уже всем знакомого happens-before):

• порядок разыменования (dereference chain, обозначается далее как dereferences(a,b))
• порядок доступа к памяти (memory chain, обозначается далее как mc(a,b))

Оба этих порядка считаются частью сценария выполнения (трассы над кодом, execution), и поэтому, для конкретного сценария, считаются фиксированными. Эти два частичных порядка должны удовлетворять определенным ограничениям (но решение, удовлетворяющее этим ограничениям, не обязано быть единственным)

---

То, что идет дальше, лично мне кажется смесью определений самих порядков ("что такое MC/DC"), и условий (которые формулируются, в том числе, в терминах только что введенных MC/DC), которым должны удовлетворять допустимые по JMM сценарии исполнения. Мне это кажется очень неудобным для восприятия, но я оставляю эту часть как она есть

Порядок разыменования, dereferences: Если A -- чтение/запись поля объекта О, причем О инициализирован не текущим потоком, тогда в текущем потоке должна существовать операция чтения R, которая видит адрес объекта О, и такая, что dereferences(R, A). Другими словами: операция чтения адреса объекта должна происходить до (в смысле порядка разыменования) любой операции чтения/записи полей объекта.

Порядок доступа к памяти, mc:

1. Если чтение R видит результат записи W, то mc(W,R) (запись происходит до чтения в смысле частичного порядка доступа к памяти)
2. Если dereferences(А,Б) (А происходит до Б в смысле порядка разыменования), то и mc(А, Б) (А происходит до Б и в смысле порядка доступа к памяти) Т.е dereferences является "подмножеством" mc.
3. Если W -- запись адреса объекта О, производимая не тем потоком, который О инициализировал, то, в этом же потоке должно существовать некоторое чтение R, которое видит адрес объекта О, и такое, что mc(R,W) (R происходит до W в смысле порядка доступа к памяти)

---

Теперь само определение семантики final-полей:
Дано:

1. Некоторая запись W
2. Заморозка F
3. Произвольное действие с памятью (кроме чтения final-поля) A
4. Чтение R1 финального поля, замороженного F
5. Чтение R2

Пусть между собой эти действия связаны такими соотношениями: hb(W,F), hb(F, A), mc(A, R1), dereferences(R1, R2).

Тогда: определяя, какие значения могут быть прочитаны R2, мы можем полагать, что W и R2 связаны порядком happens-before: hb(W, R2). Но: это отношение порядка не транзитивно с другими отношениями порядка HB.

Отдельно заметим, что отношение порядка разыменования (dereferences) рефлексивно -- т.е. dereferences(a,a) всегда верно. Поэтому в определении выше R2 может совпадать с R1.

Только те записи, что подходят под определение семантики final-полей -- гарантированно упорядочены до чтения final-поля. (Я понимаю этот пункт просто как еще одно напоминание, что гарантии, даваемые для final-полей распространяются ровно настолько, насколько указывает данное определение, и не дальше)

---

Теперь попробую изложить то же самое на простом языке и более развернуто.

hb(W,F): Наша "некоторая запись" происходит до завершения конструктора, или до "заморозки", что то же самое в данном случае.

hb(F, A): "некоторое действие с памятью" происходит после завершения конструктора ("заморозки").

mc(A, R1): Чтение final-поля видит результат "некоторого действия с памятью"

dereferences(R1, R2): R2 это либо само чтение значения поля (т.е. R2==R1), либо это чтение поля/элемента какого-то объекта, доступного по цепочке ссылок, начинающейся в final-поле.

Что это за загадочное "некоторое действие А"? Насколько я понимаю смысл -- это должна быть публикация ссылки на объект. Но точнее описать не могу -- для меня пока загадка, почему же это действие описано настолько абстрактно -- может ли А быть чем-то кроме публикации ссылки?

---

Уф. Выдыхаем...

Что можно видеть из этого определения? Во-первых, возможности "сесть на хвост" -- по крайней мере, в том смысле, в котором был пример в начале статьи -- нельзя. Семантика final-полей гарантирует видимость записей, идущих до freeze только для тех чтений, что идут через цепь разыменований, начиная с самого final-поля. Поскольку увидеть .value через эту цепь нельзя, то видимость значения, записанного в это поле в конструкторе не гарантируется.

В этом определении мне интересны еще несколько вещей (помимо его зубодробительности, конечно).

Во-первых, оно идет в некотором смысле в обратном направлении по отношению к обычным определениям JMM. В "обычном" определении логика такая: мы сначала определяем упорядоченность действий (через набор правил порождения ребер happens-before + транзитивность), а потом говорим, что если hb(А,Б) => то Б гарантированно видит результат действия А. Здесь же ситуация обратная: мы говорим, что если Б видит результат А => то определенные действия происходящие до А происходят до определенных действий, происходящих после Б.

Во-вторых здесь необычная ситуация с определением того, для каких операций чтения/записи пригодно это определение. Формально все начинается с любой операции записи, идущей до заморозки. Но в конце оказывается, что ребро HB можно установить по этому определению начиная с любой записи -- да не к любому чтению. А поскольку ребро это еще и не транзитивно -- то получается, что ограничивая спектр операций чтения, на которых ребро может заканчиваться -- мы тем самым ограничиваем и спектр операций записи, на которых оно может начинаться. А именно: ребро может начинаться только на таких операциях записи, результаты которых могут увидеть чтения из того самого ограниченного списка. Для других операций записи эффект ребра HB просто не наблюдаем :) Причем если бы нам оставили транзитивность -- мы бы могли по транзитивности продлить ребро HB с "разрешенного" чтения до следующей в program order операции, которая уже могла бы быть любым (в том числе и "не разрешенным") чтением. Но у нас транзитивность отобрали. И поэтому вместо любой операции записи это определение позволяет проводить ребра HB только от таких записей, которые а) происходят до завершения конструктора б) результаты которых видны по цепочке ссылок начиная с final-поля, инициализированного в этом конструкторе.

В третьих, обратите внимание, что от записей W не требуется, чтобы они происходили внутри конструктора. Они могут происходить где угодно, только бы была возможность показать, что они происходят до завершения конструктора (до заморозки). Это как раз и означает, что мы можем передать в конструктор объекта сколь угодно сложный объектный граф, заполненный где-то на стороне (но гарантированно до окончания конструктора), присвоить в конструкторе ссылку на него final-полю, и далее мы можем быть уверены, что всё его содержимое будет видимо любому потоку, читающему граф через разыменование final-поля. Это тоже своеобразный piggybacking, и вот такой piggybacking моделью памяти джавы разрешен.

Java puzzle System.exit and locks.

Встретил сегодня у Peter Lawrey в его блоге Vanilla Java статью с головоломкой. Известно, что при вызове System.exit() секции finally не выполняются. А что будет с блокировками?

private static final Object lock = new Object();

public static void main( String... args ) {
    Runtime.getRuntime().addShutdownHook( new Thread( new Runnable() {
        @Override
        public void run() {
            System.out.println( "Locking" );
            synchronized ( lock ) {
                System.out.println( "Locked" );
            }
        }
    }));
    synchronized ( lock ) {
        System.exit(0);
    }
}

Что напечатает этот код?

Собственно, уже по тому, как это подано -- можно догадаться об ответе :) Да, код напишет Locking, после чего зависнет -- JVM не будет завершаться.

Лишнее напоминание о том, что это только на уровне языка java конструкция synchronized( lock ){..} выглядит чем-то неразделимым. На уровне байт-кода инструкции monitorenter/monitorexit -- вполне себе отдельные инструкции, и вовсе не обязаны идти парами в рамках одного метода. И блок synchronized на уровне байт-кода выглядит примерно как

monitorenter lock
try{
   ...
}finally{
    monitorexit lock
}

И то, что System.exit() может эту парность разорвать -- выглядит здесь уже довольно очевидно

UPD: Как мне правильно указали в комментариях, парность/непарность здесь ни при чем. Согласно спецификации Runtime.exit() (она более подробная, чем у System.exit) выполнение кода приостанавливается в точке вызова exit(), и выполняется shutdown sequence. Первая фаза shutdown sequence -- выполнение, каждый в своем, отдельном потоке, shutdown hooks. Поскольку основной поток остановлен в точке вызова exit() -- монитор захвачен. Поскольку shutdown hook выполняется в отдельном потоке -- он подвисает на попытке захватить монитор. И, в полном соответствии со спекой, подвисший shutdown hook подвешивает и весь процесс завершения JVM.

StackOverflow: AtomicReferenceFieldUpdater semantic

Очередной интересный вопрос на stackoverflow -- неочевидное место в документации к AtomicReferenceFieldUpdater:

Note that the guarantees of the compareAndSet method in this class are weaker than in other atomic classes. Because this class cannot ensure that all uses of the field are appropriate for purposes of atomic access, it can guarantee atomicity and volatile semantics only with respect to other invocations of compareAndSet and set.

Автору вопроса (да и мне теперь тоже) не очень понятен смысл фразы "weaker guarantees" -- в чем именно-то они "слабее"?. Что за загадочная фраза "all uses of the field are appropriate for purposes of atomic access" -- какие использования поля здесь имеются в виду "подходящими" для атомарных операций, а какие -- нет?

Меня сильно смущает приводимый пример с тем, что атомарность и волатильность поддерживаются только между вызовами compareAndSet() и set(). А что с обычным присвоением (this.value = ...)? Я-то наивно считал, что set() полностью эквивалентен по семантике обычному присвоению значения полю (поля, с которыми работает *Updater, обязаны быть volatile -- это проверяется при создании *Updater-а), просто set() это то же самое, только через reflection, с соответствующими дополнительными проверками и накладными расходами. Получается -- это не так?

Исследования кода показывают, что, например, в обычных AtomicXXX классах set() -- это просто присвоение:

public class AtomicReference<V>  implements java.io.Serializable {
    //...
    private volatile V value;
    //...
    public final void set(V newValue) {
        value = newValue;
    }

В AtomicReferenceFieldUpdaterImpl это несколько иначе:

public void set(T obj, V newValue) {
        if (obj == null || obj.getClass() != tclass || cclass != null ||
            (newValue != null && vclass != null &&
             vclass != newValue.getClass()))
           updateCheck(obj, newValue);

        unsafe.putObjectVolatile(obj, offset, newValue);
    } 

Но название putObjectVolatile(..) как бы намекает, что это то же самое, что и обычное присвоение значения волатильному полю.

Будем ждать прояснения ситуации.

UPD: В дискуссии с ryakh прояснилось, что же имеется в виду. Судя по всему, этот любопытный пункт в документации оставлен для платформ, на которых нет аппаратной поддержки для атомарных CAS-ов (или чего-то, им равномощного). В этом случае реализация RMW-операций потребует использования програмных блокировок. Но блокировки могут обеспечить атомарность только по отношению к другим операциям, защищенным той же блокировкой. Таким образом возникает выбор: либо на таких платформах надо все операции volatile store защищать программными блокировками -- что будет дико неэффективно. Либо оставлять обычные операции чтения/записи volatile-переменных как есть, а блокировками защищать только операции классов AtomicXXX и XXXUpdater. Но во втором случае мы получаем потенциальную возможность для обычной записи volatile a = 3 пересечься с атомарным изменением

synchronized(internalLock){ 
    if(a == 1) {
        /*a=3 может вклиниться сюда*/ 
        a = 2; 
    }
}.

Отсюда и получается ограничение, описанное в документации: если вы используете XXXUpdater для выполнения CAS-ов над каким-то полем, то вы должны забыть про обычную запись в это поле, и использовать для этого только метод XXXUpdater.set() -- только тогда рантайм может гарантировать, что атомарные изменения действительно будут атомарными на всех доступных платформах.

Хочу заметить, что чтение можно спокойно делать напрямую, без XXXUpdater.get() -- чтение, очевидно, никак не интерферирует с атомарными изменениями.

Мне кажется, это еще один пример того, что write once, run anywhere -- слоган довольно условный. Есть масса способов написать на джаве вполне рабочую программу, которая будет годами отлично выполнять свои функции на целом спектре аппаратных платформ -- но не будет полноценно кроссплатформенной из-за какой-нибудь такого рода пропущенной "мелочи".

На этом примере так же легко можно видеть, как желание дать разработчикам более низкоуровневые инструменты вступает в противоречие с кроссплатформенными абстракциями. В самом деле, если бы у нас были только классы AtomicXXX -- полностью инкапсулирующие все манипуляции со своим значением -- никаких уточнений в документацию и не потребовалось бы. Но нам дали XXXUpdater, с помощью которого можно несколько улучшить компоновку объектов в памяти, и уменьшить затраты памяти -- и в нагрузку мы получили еще и тонкости взаимодействия между атомарными изменениями через Updater, и обычными записями...

Puzzler из concurrency-interest

Замечательную штуку вчера продемонстрировал Hans Boehm в листе рассылки concurrency-interest (любопытно, что тема началась с запроса на легализацию разных трюков с s.m.Unsafe -- дискуссии concurrency-interest частенько очень сильно плутают). Ханс писал про опасность методов типа lock.tryLock() -- в смысле сложности их правильного понимания. Вот, например, код:

//Thread 1:
x = 17;
l.lock();

//Thread 2:
while ( l.tryLock() ) {
    l.unlock();
}
... x ...  // какое значение у x в этой точке?

Чтобы ответить на вопрос, обязан ли x быть равным 17 в конце второго потока надо ответить на вопрос "есть ли здесь data race?"

С одной стороны, с точки зрения "универсального" определения программа считается data race free если для всех sequentally consistent трасс над ней отсутствует конкурентный доступ к данным. В данном случае, кажется, это выполняется -- во всех SC трассах сначала в x пишется 17, и только потом x читается -- поэтому кажется, что код data race free, а значит после цикла во втором потоке x должен быть равен 17.

С другой стороны, JMM определяет data race free несколько иначе -- все конкурирующие доступы к данным должны быть упорядочены через happens-before. Поскольку между потоком 1 и 2 нет никаких ребер HB, то доступы к x на запись и на чтение в разных потоках не упорядочены через HB, и, следовательно, они образуют гонку -- а значит, значение x после цикла во втором потоке не определено.

---

Найти правильную точку зрения сравнительно просто -- достаточно вспомнить, что критические секции (и вообще, и в java в частности) имеют семантику "можно войти, нельзя выйти" (roach motel semantics) -- код может вноситься внутрь секции, но не может выноситься из нее. Это значит, что x=17 и l.lock() в потоке 1 могут быть переупорядочены -- присвоение может быть внесено в критическую секцию. Это сразу дает право сказать, что здесь таки есть гонка, и значение x во втором потоке действительно не определено.

Но меня это объяснение не полностью удовлетворяет -- мы здесь просто предъявили пример преобразования кода, допустимого в соответствии с JMM, и дающего неопределенный результат всего примера. А хочется же понять, где в рассуждениях ошибка.

А ошибка в рассуждениях в том, что, когда мы придумываем SC трассы над кодом, мы делаем два неявных предположения о том, что такое лок. Первое из них -- что лок неявно содержит некое состояние -- каким потоком он сейчас захвачен. Это состояние меняется вызовами lock()/unlock(), а так же запрашивается, и, возможно, меняется вызовом tryLock(). И это предположение верно -- у лока действительно есть это внутреннее состояние.

Но есть еще и второе предположение -- что изменения этого состояния методами lock()/unlock()/tryLock() -- имеют семантику volatile store/load. И вот это уже не верно. В соответствии со спецификацией, lock()/tryLock() имеют (==обязаны иметь) только семантику acquire, а unlock() -- только семантику release. А это значит, что мы не все трассы рассмотрели.

Путаницы добавляет тот факт, что на реализация блокировок обычно делается через CAS, а CAS на x86 имеет семантику full fence. То есть на x86 для любой реализации монитора (из мне известных) lock() будет иметь семантику full fence просто в силу того, что аппаратная модель памяти соответствующего процессора более слабых барьеров не предусматривает. И код Ханса будет скорее всего работать корректно (==не будет содержать гонок). Но это особенности именно аппаратной модели памяти конкретного процессора. Скажем, на пресловутых Azul-ах есть CAS без семантики барьера, и есть односторонние барьеры. И там вполне можно реализовать (правда, не на уровне java, а разве что на уровне интринсиков JIT-а) монитор, у которого lock() будет иметь честную семантику только acqiure.

Собственно, если я правильно понял Ханса, он и обращает внимание на то, что с введением методов типа tryLock() монитор становится легко принять за этакую неявную volatile переменную -- что не соответствует реальной семантике операций с мониторами.

В продолжение темы: глубже в synchronized vs ReentrantLock

После провокационной статьи Мартина у нас с Алексеем Шипилевым и Артемом состоялась любопытная переписка. Результаты ее более полно описал Артем, в своей статье.

Для меня там была одна важная, но неожиданная деталь. С предыдущей своей попытки разобраться в различиях synchronized и RL блокировок у меня создалось ощущение, что они во многом схожи. То есть synchronized имеет иерархию biased->thin(spin)->fat (строго говоря, скорее thin->(biased|fat) ), а RL имеет иерархию spin->park (с опциональным "выхватыванием" (barging). Это значит (как мне казалось), что оба типа блокировок почти идентичны на уровнях thin-fat. Я видел synchronized lock как (thin+fat) реализованный на уровне JVM + biasing, а ReentrantLock -- как (thin+fat) реализованный на уровне java + barging. При этом (thin+fat) часть у них очень близка (так мне казалось).

Оказывается, что это неправда. Действительно, и у synchronized и у RL есть части thin (CAS-based), и fat (OS-level parking). Но они сильно отличаются по политикам перехода между этими двумя режимами. А именно:

ReentrantLock на каждую попытку захвата монитора сначала пытается захватить монитор быстрым CAS-ом, и, в случае неуспеха этого благого начинания -- паркуется. То есть, по-сути, у RL нет "состояния" thin/fat -- он всегда является их суперпозицией.

synchronized же имеет явное поле (часть markword, вроде бы) "текущий тип блокировки" -- со значениями biased/thin/fat. И у него есть определенные правила перехода между этими типами. В частности, лок стартует в состоянии thin. Если привязка блокировок включена, то, по истечении определенного времени (biasing delay) если лок все время захватывается одним потоком -- он становится biased. Если лок захватывается разными потоками, но остается при этом uncontended (т.е. в каждый момент времени им владеет только один поток) - лок остается в состоянии thin. Если же случается столкновение потоков на блокировке, то лок "надувается" (inflate) -- переходит в состояние fat.

Так вот, тонкость здесь в том, что "сдувается" однажды надутый лок очень редко. Здесь (на данный момент) очень консервативная реализация, которая предполагает, что уж если лок однажды оказался contended -- то он таким и будет дальше, и метаться туда-сюда тут не стоит -- дороже обойдется (изменение типа лока требуют во-первых CAS, во-вторых, частенько, довольно непростой координации всех потоков, сейчас этот лок задействовавших -- это все непросто, и недешево).

Вторая тонкость состоит в том, что "надувшийся" (fat) монитор -- это еще не kernel-space lock. Это свой собственный, JVM-ный, библиотечный лок, который сначала немного спиннится в user-space, и только потом, если спиннингом разрулить contention не удалось -- все-таки идет на поклон к батькеOS thread scheduler-у, прося разрулить ситуевину.

И когда говорят об адаптивном спиннинге в приложении к synchronized мониторам -- имеют в виду именно этот спиннинг внутри "надувшегося" монитора -- последний шанс разрулиться перед прыжком в омут с головойkernel space.

Если посмотреть на эту картину, то получается, что с точки зрения алгоритмов, у RL перед synchronized нет ни одного преимущества -- все, что умеет делать RL умеет и synchronized, но synchronized умеет делать и больше. Но при этом RL проще -- что может оказаться критичным, например, если наш конкретный use case этих сложностей не требует, а попадает на область применимости простейшего uncontended CAS lock-а -- RL может выиграть, например, за счет более простого memory layout-а.

То есть если мы пишем некий компонент, который хотим сделать просто потоковобезопасным (thread-safe) -- то есть мы допускаем его использование в многопоточном окружении, но не рассчитываем на особо большую нагрузку -- то пользуем synchronized и не парим себе мозг. synchronized наиболее адаптивен -- может сам приспособиться к различным профилям нагрузки. Плюс к тому, biased locking + поддержка со стороны JIT-а (выбрасывание блокировок по результатам escape analysis, эскалация блокировок, и прочая белая магия) делает synchronized исключительно эффективным в тех случаях, когда конкретный объект используется в однопоточном сценарии.

Если же мы пишем конкурентный компонент -- то есть заранее предполагаем его использование именно в многопоточном окружении, и под высокой нагрузкой -- то тут уже можно смотреть в сторону ReentrantLock -- весьма возможно, что при стабильно высоком профиле нагрузки он выиграет за счет более простой внутренней логики. Но а) все равно придется тестировать б) если нам нужен совсем-совсем максимум -- то, скорее всего, все равно придется смотреть в сторону самодельных решений на базе атомиков.

Вывод я для себя делаю такой -- что теоретические рассуждения о том, в каких ситуациях RL лучше synchronized -- это очень условная вещь. Теоретически ни один априори не лучше. Только эксперименты спасут мировую революцию.

P.S. Алексей -- спасибо за терпеливые разъяснения :)

Снова о biased locking

Очередной виток истории начался с провокационного поста Мартина Томпсона (это автор Disruptor-а, если чё) -- и его продолжения, написанного после того, как Мартину указали на некоторые мелкие недостатки его бенчмарков :)

Во-первых, поднятый Мартином вопрос "есть ли сейчас смысл в привязанных блокировках" породил переписку Дэйва Дайса с Клиффом Кликом. В этой переписке довольно отчетливо высказана интересная мысль -- что привязанные блокировки скорее всего скоро отойдут в прошлое. Почему? Потому что это, по меткому выражению Клиффа "software solution to a hardware problem (expensive CAS)".

То есть привязка блокировок была введена потому, что ранние версии CAS-ов на мультипроцессорах были гораздо менее эффективны, чем теоретически могли бы -- просто инженерам Интела было не до их оптимизации. Теоретически ничего не мешает реализовать CAS, который, в uncontended случае, будет выполняться со скоростью обычного store. Но пока суд да дело, пока инженеры учились делать процессоры с быстрым CAS-ом -- нужно было сделать какую-то затычку, на программном уровне. И этой затычкой и стали привязанные блокировки -- которые программным трюком сводят формально необходимый для блокировки CAS к обычному store.

Сейчас же Клифф хвастается тем, что на Azul-ах uncontended {CAS + full_fence} (обычный CAS у них не имеет семантики барьера) выполняется за 5-6 тиков. На текущих Nehalem-ах локальный CAS требует 10-15 тиков (против мифических >100, с которых все когда-то начиналось) -- и есть шанс, что будет оптимизироваться дальше. В таких условиях Клифф пишет, что в версиях jdk для Azul они уже отказались вовсе от biased locking -- нет смысла, обычный CAS-lock выигрывает у любой реализации biasing. Для версии своего jdk под x86 они все еще используют biased locks (правда, какую-то свою реализацию -- не такую, как у Sun/Oracle JDK) -- но видимо, это вопрос времени.

С другой же стороны, обновленные бенчи Мартина показывают, что пока что, на Nehalem-ах, с использованием стандартного Oracle JDK, biased locks обходят RL/synchronized где-то в 10 раз. Хотя к бенчам Мартина я теперь отношусь как-то с осторожностью :(

Хорошая архитектура...

...позволяет откладывать принятие ключевых решений. Хорошая архитектура максимизирует количество непринятых решений. (с) Боб Мартин

Прочитал сегодня на хабрахабре, и просто поразился -- насколько это соответствует моему собственному ощущению. Огромное спасибо Бобу, и автору статьи за вербализацию.

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

Задачка с stack overflow

Ways to improve performance consistency -- некий Peter Lawrey -- довольно продвинутый чувак, если судить по его блогу -- написал message-passing штукакенцию, отдаленно напоминающую дизруптор -- в том смысле, что используется что-то вроде массива как носитель, и потоки передают друг другу сообщения, извещая друг друга мембарами. Правда, в качестве массива он использует ByteBuffer.allocateDirect(). Смысл этого для меня пока не очень понятен, но такова уж его идея.

Проблема у мужика в том, что результаты бенчмарков у него скачут примерно вдвое-втрое. И он спрашивает сообщество "WTF, gays?".

Причем его более тщательные исследования намекают, что скачки производительности происходят после срабатывания GC. Это как бы намекает, что дело тут в memory layout-е, который может меняться после дефрагментации памяти в ходе сборки мусора.

С одной стороны, ситуация похожа на ту, что я наблюдал в своих экспериментах. С другой -- в его коде пишутся не ссылки, а просто числа (ByteBuffer только их и принимает) -- а для long[] в качестве носителя у меня результаты вполне себе повторяемые, скачков в разы там нет. Это несколько удивляет.

Моя текущая версия происходящего состоит в том, что Питер использует для привязки к ядрам taskset. Но taskset привязывает процесс целиком. Это значит, что никак не фиксируется, как раскиданы по ядрам потоки внутри процесса. GC запускается, скорее всего, в отдельном потоке -- и создает нифиговую пиковую нагрузку -- при этом в момент его запуска собственно бенчмаркирующие потоки приостановлены (stop-the-world). Очень логично, что в этот момент ОС решедулит потоки, так, что ничего не делающие потоки скидываются на одно ядро, а потоку GC, аццки вкалывающему, выделяется ядро в безраздельное пользование. Соответственно, после того, как сборщик мусора успокоился, ОС почему-то не возвращает потоки назад, на отдельные ядра. Тут возникает вопрос "почему", но мне кажется, что это сценарий реалистичный -- обычно такие важные алгоритмы пишутся довольно консервативно, в духе "нет веских причин -- ничего не трогай". Т.е. если нет веских причин, перебрасывать потоки между ядрами шедулер не будет -- противное может привести к тому, что в каких-то ситуациях ему придется постоянно перекидывать потоки, что, понятно, хреново.

Жду от мужика отзыва -- мои сервера сейчас слишком заняты, чтобы я себе мог позволить погонять бенчмарки самому.

UPD: Питер отписался по результатам. Мое предположение оказалось неверным -- потоки не решедулятся (UPD2: на самом деле, они как раз решедулятся -- но это не оказывает существенного влияния на производительность). Причина оказалась (по его словам) в том, что буфер и счетчики в определенных случаях оказывались лежащими последовательно в памяти. Поскольку паддинг у его счетчиков сделан только после используемого поля value, то буфер, идущий в памяти перед счетчиками может легко заползти на их строку (я писал про такой сценарий в статье про false sharing). Вот и получается фигня всякая...

Disruptor #3.1.4.1: Эксперименты с производительностью -- анализ

Что можно сказать по поводу результатов экспериментов? Картина получается довольно непростая. Первый вопрос: какой из результатов Disruptor брать за основной -- при разнице в 3 раза между производительностью на малых и больших размерах буфера. Мое мнение, что за основу стоит брать именно 30 миллионов ops/sec, которые он выдает на большом буфере. 75 миллионов на малом буфере с батчингом кажутся мне артефактом "холостого хода". Другими словами, я почти уверен, что если начать использовать более-менее тяжелые объекты событий, и более-менее тяжелые обработчики, то этот результат радикально изменится. На это намекает и гиганский разброс результатов различных экспериментов, и то, что LMAX в реальном своем продакшене сообщает о размере очереди в 2М, и то, что при увеличении размера буфера результаты с батчингом и без него сходятся к одному значению пропускной способности в "жалкие" 30 миллионов операций.

Но если принять за рабочую гипотезу, что реперная точка Disruptor -- 30 миллионов оп/сек, то получается, что потестировать эффект от батчинга у меня толком не получилось -- разница между Д с батчингом и без него становится артефактом эксперимента на холостом ходу. Это не очень-то и удивительно -- батчинг, предположительно, должен сглаживать неравномерности во входном потоке данных, но ведь у нас-то входной поток искусственный, и никаких заметных неравномерностей не содержит, негде батчингу развернуться. Но дело в том, что батчинг -- это принципиальное отличие Disruptor-а от очередей -- отличие в интерфейсе/контракте, а не в реализации (для того, чтобы допустить пакетную обработку в очереди потребуется изменить ее интерфейс). И именно это принципиальное отличие надежно оценить и не удалось. Пичалька...

Тем не менее, если мы принимаем производительность Д за 30 млн. оп/сек, то самая базовая, "тупая" реализация single enq single deq queue может дать нам примерно треть от этой производительности. Применяя к этой тупой реализации последовательно: 1) пул для уменьшения аллокации объектов 2) оптимизацию spin-loop-ов 3) volatile write -> lazySet 4) остаток от деления -> битовая маска -- мы получаем ускорение чуть больше чем вдвое -- т.е. 2/3 от производительности Д, причем вклад от этих трех оптимизаций сравним.

Строго говоря, эти оптимизации не вполне независимы -- то есть, применив их в другой последовательности мы скорее всего получим другие цифры для эффекта каждой из них. Поэтому оценивать их вклад точнее, чем по порядку величины смысла я не вижу.

Ближе подойти к Д мне не удалось (я не готов ставить пока не особо стабильный jdk1.7 с его -XX:+UseCondCardMark на рабочий сервер), но косвенные эксперименты с заменой ссылок на long показывают, что очень вероятно, что еще 1/3 производительности теряется на false sharing by card marking.

И если это так, то самым "доходным" решением в дизайне Д признается идея применить заранее заполненный буфер. Поскольку это сразу позволило им и избежать аллокации объектов-событий, и нагрузки на GC для их сборки, и избежать false sharing при модификации ссылок. В сумме это дает почти половину разницы в производительности между Д и самой тупой реализацией SESDQueue. Остальные тонкости -- в том числе padding (на который любит напирать Мартин в своем блоге), и кэширование условий в spin-loop-ах, и lazySet (о которых он не упоминает:) ) -- на фоне этого выглядят довольно бледно.

Очень впечатляет рывок, который получается заменой Object[] -> long[] -- более чем втрое подскакивает производительность. Выглядит это так, что запись ссылочных полей стоит весьма недешево, по крайней мере в многопоточном окружении.

Вот такая получилась загогулина. Напоминаю только, что все это про холостой ход -- под нагрузкой результаты могут сильно отличаться, и ключевые факторы в производительности могут стать другими.