Для тех, кто не решился написать ответы к предыдущему посту

Моя душа несколько успокоилась, когда все комментировавшие предыдущий пост дали правильные ответы. А то я так часто слышу про vwrite hb vread, что начал сомневаться, помнит ли вообще кто-то, что это не совсем верное утверждение.

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

Другими словами, не существует никаких ребер happens-before между строками кода в программе — ребра существуют в конкретном сценарии выполнения этого кода (в оригинале звучит как execution — сценарий, или маршрут выполнения. Но однажды я услышал термин "трасса над кодом", и он подкупил меня своей образностью, так что я часто использую его). Нет HB между какой-то волатильной записью и каким-то волатильным чтением, есть HB между событием волатильной записи некоторого значения, и событием волатильного чтения его же (из той же переменной, понятно).

А вот вопрос немного сложнее:

Thread 1	Thread 2
volatile int va; int a;
va = 1; a = 10; va = 1;	if( va == 1 ){ int la = a; }

Какие ребра существуют здесь?

Если вы знаете, что такое happens-before...

...то ответьте мне на несколько простых вопросов. Дан такой код:

Thread 1	Thread 2
volatile int va;
va = 10;	int b = va;

Вопросы (отвечать желательно по порядку, не забегая вперед):

1. Какие здесь есть межпоточные ребра HB?
2. Может ли в b оказаться что-то, кроме 10?
3. Может ли в b оказаться 0?
4. Изменится ли что-либо, если здесь заменить volatile store на lazySet?

Off-heap: троллинг 70-го уровня

Последнее время я часто сталкиваюсь с идеей off-heap storage в java. Это когда DirectByteBuffer/Unsafe используют для организации данных вне java heap. Предположительно, это должно радикально снизить нагрузку на GC, да и, в некоторых случаях, сам доступ к данным ускорить. Сам я к этой идее относился довольно скептически: на мой взгляд у нее довольно узкая область применимости, и усилиями разработчиков JVM она становится с каждым годом еще уже. Мне кажется, многие, кто смотрит в сторону off-heap просто еще не разобрались толком, что можно делать на чистой java. Но пока это были все теоретические предположения — с Unsafe я проводил лишь один небольшой эксперимент, и, хоть предположения он, косвенно, и подтвердил, но одного эксперимента для выводов явно недостаточно. А сделать серьезный бенчмарк как-то было лениво.

StampedLock

На днях в concurrency-interest Даг Ли объявил о выходе альфа-версии StampedLock-a. Это довольно интересный вариант ReadWriteLock-а, с возможностью ультра-оптимистичных чтений практически без contention. Он дает ограниченную функциональность обычного ReadWriteLock (в частности, нет reentrancy), но добавляет методы tryOptimisticRead()/validate(stamp), и tryConvertToWriteLock(stamp). По-сути, это попытка сделать версионную структуру данных: каждый захват блокировки возвращает уникальный (ну, почти — это все-таки обычный long, который через пару лет непрерывного использования может начать повторяться) идентификатор. Этот идентификатор можно рассматривать как номер текущей версии данных, защищаемых данной блокировкой. И, используя этот идентификатор можно делать очень дешевое спекулятивное чтение:

Видео с jug.ru

Уже готово. Огромное спасибо организаторам. Сам еще не смотрел :)

Посмотреть видео на сайте Лекториума

Thread affinity binding

По следам выступления на jug.ru:

Меня спрашивали, как я задаю affinity потокам в яве в бенчмарках. Начнем с того, что из чистой явы это сделать нельзя. Но если нельзя, а очень хочется — то таки можно. Долгое время я пользовался на скорую руку сварганенным методом, подсмотренным где-то на stackoverflow. Потом какое-то время участвовал в разработке библиотеки Java-Thread-Affinity, от Питера Лоурея. В принципе, она довольно неплоха, и я могу ее вполне рекомендовать.

AtomicFieldUpdater optimized

AtomicXXXFieldUpdater — чудесные классы, открывающие значительную часть магии Unsafe без проблем с безопасностью и переносимостью. К сожалению, есть некоторая цена. Вот цитата из AtomicLongFieldUpdater.CASUpdater:

public void lazySet(T obj, long newValue) {
  if (obj == null || obj.getClass() != tclass || cclass != null) 
    fullCheck(obj);
           
  unsafe.putOrderedLong(obj, offset, newValue);
}
private void ensureProtectedAccess(T obj) {
  if (cclass.isInstance(obj)) 
    return;
  throw new RuntimeException (
        new IllegalAccessException("Class " + cclass.getName() + 
            " can not access a protected member of class " + tclass.getName() +
            " using an instance of " + obj.getClass().getName()
        )
  );
}
private void fullCheck(T obj) {
  if (!tclass.isInstance(obj))
    throw new ClassCastException();
  if (cclass != null)
    ensureProtectedAccess(obj);
}  

Выглядит все довольно страшно, хотя на практике в большинстве случаев все закончится на первых трех проверках: (obj == null || obj.getClass() != tclass || cclass != null). Эффект от них невелик, в моих бенчмарках замена AtomicUpdater на Unsafe давала 15-20% максимум в очень нагруженном конкурентном коде. По-видимому, дело в том, что результат этих проверок в правильно написанном коде всегда одинаков (false), поэтому предсказатель ветвлений в процессоре довольно быстро сообразит, какая из веток реализуется со 100% вероятностью, и будет спекулятивно выполнять код дальше. Тем не менее, иногда не хочется терять и этих процентов.

Хорошая новость состоит в том, что AtomicLongFieldUpdater — абстрактный класс, и никто не мешает вам написать свою реализацию. Например, взять за основу AtomicLongFieldUpdater.CASUpdater, и просто выбросить все "лишние" проверки. Результат будет практически drop-in-replacement для большинства сценариев использования.

Разумеется, у меня сразу возникла мысль сделать какую-то свою фабрику, на замену AtomicLongFieldUpdater.newUpdater(...), которая по-умолчанию делегировала бы к AtomicLongFieldUpdater.newUpdater, а при указании специального свойства -Djava.concurrent.run-faster начинала бы использовать оптимизированную версию. Плохая новость состоит в том, что так не получается: в конструкторе AtomicFieldUpdater-а проверяется, что вы можете создать AtomicUpdater только для того поля, которое вы и так можете видеть из создающего кода. Если я собираюсь обновлять private поле, то AtomicUpdater для него я смогу создать только изнутри этого же класса. И значит выбор реализации AtomicUpdater-а придется делать внутри каждого класса, его использующего.

HotSpot OSR

Довольно старая уже, но от этого ничуть не менее интересная статья в блоге Cliff Click (это главный инженер Azul) про тонкости JIT-компиляции.

Клифф рассказывает чем отличается "обычная" компиляция метода, и компиляция в режиме On-the-stack-Replacement (OSR), и почему эту разницу стоит иметь в виду.

Обычная компиляция случается когда JVM обнаруживает, что какой-то метод достаточно горячий, чтобы его имело смысл скомпилировать. Для этого с каждым методом связывается счетчик, который считает число вызовов метода, и число обратных переходов (backedge) (т.е. переходов "назад" по потоку инструкций) внутри метода (sic!). Вторая часть может показаться непонятной, но это просто способ считать итерации циклов, если они в методе есть. Таким образом метод будет считаться горячим не только если он часто вызывается, но и если сам он вызывается не очень часто, но внутри него есть достаточно "тяжелые" циклы.

Когда счетчик перевалит за какой-то порог (скажем, 10 000) — последовательность байт-кодов метода ставится в очередь на компиляцию. При первой же возможности JIT до нее доберется, скомпилирует, и заменит ссылку в таблице методов на оптимизированную версию. И при очередном, 11 042-м вызове исполнение пойдет уже в скомпилированный и оптимизированный метод.

Здесь все круто, но есть одно "но": чтобы подменить интерпретируемую версию компилированной нужно "выйти и снова зайти" — выполнение метода должно завершиться, и тогда очередной вызов этого метода будет уже выполнять скомпилированный код. А что делать, если внутри метода тяжелые циклы — ждать пока он в интерпретируемом режиме завершится? "Клинический" случай это когда я прямо в main написал какой-то сложный алгоритм с тройной вложенности циклом — получается, у меня вообще нет шансов увидеть его скомпилированным.

Чтобы JIT в таких ситуациях не ударял в грязь лицом, ему нужно уметь заменять версии метода на лету, прямо по ходу его выполнения. Именно такая махинация и называется подменой "на стеке", On the Stack Replacement, OSR.

Надо сразу сказать, что задача эта в общем случае очень нетривиальна, ведь скомплированная версия должна полностью "принять в наследство" от интерпретируемой текущее состояние выполнения. Но скомпилированная и интерпретируемая версии кода могут (и почти наверняка будут) очень по-разному это состояние хранить. Клифф приводит в пример простейший цикл вычисления хэш-кода строки: hash = hash*31 + ary[i]; — состояние интерпретатора будет состоять из hash, arr, i, в то время как JIT скорее всего будет хранить что-то вроде hash, p = A+12+i*2, и инкрементить p+=2 на каждой итерации. Если здесь переход вам кажется несложным, то представьте, что будет если JIT еще и развернет (unroll) цикл? Получается, для OSR мало сгенерировать сам код метода — нужно еще и сгенерировать код-"адаптер", который сможет преобразовать состояние интерпретатора в тот вид, который нужен скомпилированной версии. Но генерация такого адаптера для произвольной точки кода будет очень сложной. Проще заранее фиксировать некий набор safepoint-ов, в которых только и можно "переключаться" — тогда задача становится обозримой.

Собственно, "обычный" (не-OSR) компилятор использует в качестве таких safepoint-ов границы между методами. OSR же добавляет возможность переключаться на backedge-ах циклов.

До сих пор была довольно общеизвестная информация, ее давно и много где можно встретить. А вот что интересно: поскольку обычная и OSR компиляция стартуют с разных точек в коде, то для одного и того же метода в режиме обычной и OSR компиляции JIT получает на вход разные последовательности байткодов. OSR получает как бы "вывернутую" изнутри наружу версию кода. И результат компиляции может довольно сильно отличаться. Клифф сначала приводит простой пример: вот так выглядит код метода с простым циклом

i=0;
    loop:
    if(P) goto done;
      S3; A[i++];
    goto loop; // <<--- OSR HERE
    done:
    S2;

А так он будет выглядеть для JIT-а в случае OSR компиляции:

A=value on entry from interpreter;
    i=value on entry from interpreter;
    goto loop;
    loop:
    if(P) goto done;
      S3; A[i++];
    goto loop;
    done:

Здесь пока все довольно прозрачно: это все еще очевидно цикл прохода по массиву с шагом 1, и все оптимизации к нему все еще применимы. Но вот если взять вложенный цикл все становится сложнее:

loop1:
    if(P1) goto done1;
      S1; i=0;
      loop2:
      if(P2) goto done2;
        S3; A[i++];
      goto loop2; // <<--- OSR HERE
      done2:
      S2;
    goto loop1;
    done1:

Если представить себе, как будет выглядеть этот цикл с точки зрения OSR (это требует некоторого напряжения):

A=...value on entry from interpreter...
    i=...value on entry from interpreter...
    goto loop2;
    loop2:
    if(P2) goto done2;
      S3; A[i++];
    goto loop2;
      done2:
      S2;
      goto loop1;
      loop1:
      if(P1) goto done1;
      S1; i=0;
    goto loop2;
    done1:
   ....

Здесь уже не так-то просто разглядеть структуру цикла по массиву. Чуть упростив

A=...value on entry from interpreter...
    i=...value on entry from interpreter...
    loop2:
      if(P2) {
        S2;
        if(P1) goto done1;
        S1; i=0;
      } else {
        S3; A[i++];
      }
    goto loop2;
    done1:
    ....

В чем здесь проблема? — проблема в том, что эвристики компилятора уже не узнают здесь "итерацию по массиву". А значит у нас не будет range check elimination, и, возможно, еще каких-то вкусных плюшек. Производительность этого кода может быть раза в 2-3 хуже, чем не-OSR версии.

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

Мне здесь кажется важным вот что: совет Клиффа, если его самого чуть упросить, говорит просто "не делайте слишком много работы в одном методе". То есть требования производительности здесь идут рука об руку с требованиями чистоты и простоты кода. Пишите простой, достаточно мелко-гранулированный код — и, чаще всего, он и работать будет быстро.

Disruptor 3.0

ТАСС уполномочен заявить, что скоро выходит третья версия Disruptor-a. Michael Barker, который его сейчас развивает, дразнится — обещает прирост в производительности почти вдвое.

Если честно, мне сложно представить, чем еще можно ускорить простейший single publisher single subscriber случай. Но одно предположение у меня есть. Когда я гонял бенчмарки перед JavaOne, я пробовал заменять AtomicLongFieldUpdater.lazySet() на Unsafe.putOrderedLong(). Это то же самое по смыслу, но отсутствуют различные проверки доступа и type-safety. Разница была довольно существенной. Правда, не вдвое, процентов на 20-25. Но, поскольку больше возможностей я не вижу, то я ставлю на то, что в третьей версии Disruptor появится магический класс sun.misc.Unsafe.

Хотя будет гораздо интереснее, если я ошибусь, и будет что-то новенькое :)

Синтаксический сахарочек

Вообще, java нас не балует синтаксическим сахаром. Лично мне это даже очень нравится — терпеть не могу выкапывать суть под горой сладкого. Из-за этого отказался от мысли перейти на Scala — побоялся диабет схватить. Но иногда хочется все-таки сделать своему компоненту такой сладенький интерфейс, чтобы пальчики оближешь. И когда я нахожу в аскетической джаве какую-нибудь карамельку — я очень радуюсь :)

Например, есть у нас такой класс-мэппер

public class Mapping{
  public String map(final String arg1, final String arg2);
}

И есть какая-то реализация, скажем SimpleImmutableMapping, и хочется сделать для его конфигурирования фабрику-билдер, типа вот такой:

public class MappingBuilder{
    public MappingBuilder map( final String arg1 ){...}
    public MappingBuilder with( final String arg2 ){...}
    public MappingBuilder to( final String mapping ){...}

    public Mapping build(){...}
}
...
final Mapping mapping = new MappingBuilder()
                           .map( "A" ).with( "B" ).to("ab")
                           .map( "C" ).with( "D" ).to("cd")
                           .map( "E" ).with( "F" ).to("ef")
                           .build();

Что мне здесь не нравится? — мне не нравится дуракоустойчивость. Особенно мне не нравится то, что ее здесь нет, и это хорошо видно на скриншоте справа (Да, это у меня такая цветовая схема, нет, глаза не устают, да, мне нравится, идите в жопу).
Что будет, если я вызову в этой точке .build()? Очевидно, ничего хорошего. В лучшем случае уже во время выполнения вылетит IllegalStateException("Can't build mapping with supplied data: first argument is not enough"). Это если я позаботился о том, как мой объект себя ведет, если его используют "неправильно". В более реальном случае будет что-нибудь вроде NullPointerException из недр метода .build(). В самом паршивом случае здесь все отработает без ошибок, а веселье начнется при использовании созданного Mapping-а где-нибудь совсем в другом месте.

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

public class SimpleMapping {

  //код самого мэппера -- скучный и банальный
  .....

  //а вот дальше начинается треш и содомия
  //уберите от монитора женщин и детей, и глубоко вдохните 

  public interface FirstArgumentGivenState {
    public SecondArgumentGivenState with( final String arg2 );
  }

  public interface SecondArgumentGivenState {
    public FullMappingGivenState to( final String mapping );
  }

  public interface FullMappingGivenState {
    public Mapping build();
    public FirstArgumentGivenState map( final String arg1 );
  }

  private static class Builder implements
      FirstArgumentGivenState,
      SecondArgumentGivenState,
      FullMappingGivenState {

    public FirstArgumentGivenState map( final String arg1 ) {
      ...
      return this;
    }

    public SecondArgumentGivenState with( final String arg2 ) {
      ...
      return this;
    }

    public FullMappingGivenState to( final String mapping ) {
      ...
      return this;
    }

    public Mapping build() {
      ...
    }
  }

  public static FullMappingGivenState builder() {
    return new Builder();
  }
}
....
final Mapping mapping = SimpleMapping.builder()
    .map( "A" ).with( "B" ).to( "ab" )
    .map( "C" ).with( "D" ).to( "cd" )
    .map( "E" ).with( "F" ).to( "ef" )
    .build();

Попробуйте теперь вызвать что-то неправильно :)

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

---

По-правде, я не уверен, что придумать такое было хорошей идеей — встреть я такой адъ в чужом коде, матерился бы в голос. А ведь самому-то теперь будет сложно удержаться :)

Если серьезно, то мне кажется, делать такое в каждом Builder-е это over-engeneering. Сложность понимания "как, и зачем, черт подери, такое здесь наворочено" не окупает небольшого увеличения дуракоустойчивости. Но вот если какая-нибудь изолированная, часто используемая библиотека... Тогда к странным типам возвращаемых значений у методов Builder-а можно и привыкнуть, а вот compile time safety при широком использовании может вполне себя окупить.

Если что — похороны за ваш счет. Я предупреждал :)

UPD:Как мне подсказывает Александр в комментариях — это уже описано как паттерн Wizard. Было бы слишком оптимистично ожидать, что такую штуку еще никто не придумал. Статью рекомендую прочитать, примеры там забавные.

Cache coherency #3: false sharing

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

False sharing

...Или ложное разделение. По-правде, не очень понятно, почему именно ложное — оно самое что ни на есть настоящее, только неожиданное. Что такое true sharing? — Это когда у нас есть ячейка памяти, используемая одновременно более чем одним потоком. В предыдущих статьях я уже рассказывал, что конкурентный доступ на чтение протоколы когерентности разруливают без особого труда, а вот конкурирующие чтение и запись, и особенно запись и запись заставляют их попотеть — здесь все понятно. А false sharing это когда ячейки памяти разные, но физически попадают на один и тот же cache line. С точки зрения программиста — никакого разделения данных нет, никакого конкурирующего доступа тоже. А с точки зрения подсистемы памяти каждый cache line — это одна ячейка, и операции доступа к разным частям одной строки кэша из разных ядер конкурируют друг с другом за эту ячейку-строку. И неожиданно оказывается, что обычная запись в какую-то локальную (казалось бы) переменную стоит в несколько раз дороже, чем должна была бы:

int threadId = 0, 1, 2, ... THREADS_COUNT;
int distance = 1..8; 
long[] area = new long[THREADS_COUNT*distance];

for(int i=0...Inf){
   area[threadId*distance] = i;
}

(Готовый к исполнению код здесь). Если увеличивать distance, то можно наблюдать, как время на выполнение цикла уменьшается, вплоть до distance=8 — для интелловских архитектур, где cache line 64 байта. (Строго говоря, нужно еще убедиться, что все потоки сели на разные физические ядра, но как правило, в случае незагруженной машины системный планировщик их сам так и раскидает)

Вообще, про false sharing не писал уже только ленивый. Я лично эту тему мусолил аж 4 раза, даже тэг для этого специальный завел. Поэтому я здесь хочу остановиться на другом вопросе, который мне как-то задали в комментариях: если все так легко может стать так плохо, почему это редко когда заметно? (Есть, конечно, вариант, что не замечают потому что и не смотрят — но это недостаточно сексуальный вариант)

У false sharing есть два ощутимых эффекта: увеличение в разы времени выполнения конкретной операции записи (memory latency), и увеличение нагрузки на шину. Чтобы заметить увеличение нагрузки на шину нужно либо специально ее мониторить, либо уже использовать шину близко к режиму насыщения. Но интелловский InterConnect имеет пропускную способность что-то вроде 20Гб/с в каждую сторону — а это 20 миллионов килобайтных сообщений в секунду (в нереальном случае 100% КПД). Не то, чтобы это было недостижимо круто, но не каждая птица долетит до середины Днепракаждое приложение подходит хотя бы близко к тому, чтобы насытить шину.

А что насчет memory latency? Ну, проблема медленной памяти перед разработчиками процессоров стоит уже лет 15, за это время было придумано масса трюков, позволяющих ее как-то обойти. Часть из них — те, что про введение иерархии кэшей — в случае с false sharing не помогут, потому что они сами и являются причиной. Но на уровне процессора остается еще пара тузов в рукаве, связанных с асинхронным выполнением операций с памятью. Например, современные процессоры содержат блок префетчинга, который может предсказать доступ к памяти до того, как исполнение дойдет до соответствующей инструкции, и отправить запрос на упреждающее чтение нужного блока в кэш. Другой пример: инструкции записи тоже обычно не ждут, пока запись фактически будет выполнена — команда на запись просто сохраняется в т.н. store buffer-е, и исполнение идет дальше, а команды из буфера спускаются контроллеру памяти в асинхронном режиме.

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

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

Во-первых, когда нам важно именно время выполнения конкретной (небольшой) операции (latency, response time), а не пропускная способность в целом (throughput). Если наша операция содержит всего-то пару сотен инструкций, и несколько обращений к памяти, то заметное удорожание даже одного из этих обращений все-таки будет заметно. Процессору просто не за чем будет спрятать замедлившуюся операцию. Да, он может параллельно начать выполнять инструкции хоть из другого потока (через hyper threading), тем самым удерживая на уровне общую пропускную способность — но время выполнения конкретной операции от этого не уменьшится. Мы можем получить такую картину: система по-прежнему выполняет N операций в секунду, только время одной операции выросло с 1мкс до 2мкс. Поскольку далеко не каждого волнует время выполнение конкретной операции (особенно, когда масштаб этого времени — микросекунды), то на этой стадии false sharing часто остается просто незамеченным.

Дальше идут ситуации, когда операции с false sharing составляют заметную долю всех операций (по крайней мере, на критическом маршруте). Это как раз пример выше. Почему false sharing там заметен? Потому что там, кроме самой записи, только обвязка цикла, которая едва тянет на пару тактов. И одна-единственная запись, которая contended (счетчик цикла скорее всего будет сидеть в регистре). Даже если запись идет в L1 (~5ns) — она здесь будет доминирующей, и никакие трюки этого не замаскируют, потому что маскировать нечем. И если запись станет в разы дороже — это будет просто бросаться в глаза.

Ну и последний очевидный вариант — это когда у вас шина памяти уже близка к насыщению, и тут еще добавляется false sharing, и все становится грустно.

Т.е. получается, что в первую очередь false sharing беспокоит тех, кто разрабатывает latency-critical системы, и уж во-вторую — тех, кто разрабатывает очень high throughput, где-то близко к пиковой производительности железа.

P.S. Есть у меня еще такая любопытна идея: кажется, что чем мягче аппаратная модель памяти, тем больше у процессора возможностей "прятать" memory latency. Т.е. и прятать false sharing у него тоже больше возможностей. Однако сравнивать разные процессоры сложновато — они обычно отличаются слишком много чем, не только моделью памяти (да и где бы их все взять для тестов-то). Но можно ужесточить аппаратную модель памяти программно — расставляя барьеры памяти. Если взять тот пример, выше, и вместо обычной записи в ячейку массива делать volatile store (придется заменить массив на AtomicIntegerArray, или дергать Unsafe.putIntVolatile) — то сопутствующий lock xadd скорее всего приведет к принудительному сбросу store buffer-а. А значит не будет возможности отложить запись на "попозже", ее придется делать синхронно. Кажется, что это сделать false sharing еще более заметным.

Еще интереснее будет проверить это для Disruptor-а. На Java One меня спрашивали, почему padding в моих экспериментах никак себя не проявил — вот я сейчас думаю, что причина может быть как раз в том, что я экспериментировал с padding после того, как заменил volatile store для курсоров на lazySet (что эффект от оптимизаций некоммутативен — это не новость). Будет интересно, как появится возможность, проверить, что получится если сделать наоборот: вернуть volatile store, и поиграться с padding.

P.P.S. Вообще-то, эта статья планировалась как продолжение цикла про cache coherency. И про false sharing задумывалось как вступление и разминка. Но я что-то увлекся, и false sharing вылез на место главного героя, не оставив места запланированным атомикам. Ну я и подумал — пусть остается как есть, а атомики получат свою главную роль чуть позже :)

Simple concurrent caches

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

Есть у нас доменный объект CurrencyEntity:

public final class Entity {
 private final String isoCode;

 public Entity( final String isoCode ) {
  this.isoCode = isoCode;
 }

 @Override
 public boolean equals( final Object o ) {
  if( this == o ) {
   return true;
  }
  if( !(o instanceof Entity )) {
   return false;
  }

  final Entity entity = ( Entity ) o;

  if( !isoCode.equals( entity.isoCode ) ) {
   return false;
  }

  return true;
 }

 @Override
 public int hashCode() {
  return isoCode.hashCode();
 }
}

(важно, что объект immutable). На вход (из сети, например) программа получает Entity в виде String isoCode, но внутри, понятно, хочется оперировать type-safe представлением. Однако создавать каждый раз новый экземпляр Entity не хочется -- зачем нагружать лишний раз GC? Кроме того, известно, что реально различных isoCode не так уж много -- ну, скажем, штук 100-200. Вот как бы так их кэшировать, чтобы кэш и конкурентным был, и накладные расходы минимальны (иначе кэшировать смысла нет -- создать/удалить такой мелкий объект чего-то стоит, но не так уж дорого)?

Вариант решения:

public class FastConcurrentEntityCache{
 private static final Object FREE = null;

 private final Entity[] entries;

 public FastConcurrentEntityCache( final int size ) {
  checkArgument( size > 1, "size[%s] must be >1", size );

  entries = new Entity[size];
 }

 public Entity get( final String isoCode ) {
  final int hash = isoCode.hashCode() & 0x7fffffff;

  final int length = entries.length;
  final int index = hash % length;

  Entity cur = entries[index];

  if( cur == FREE ) {
   //cache miss
   return evaluateAndStore( isoCode, index );
  } else if( cur.isoCode.equals( isoCode ) ) {
   //cache hit
   return cur;
  } else {// already FULL, must probe

   // compute the double hash
   final int probe = 1 + ( hash % ( length - 2 ) );
   int probedIndex = index;
   for( int i = 0; i < entries.length; i++ ) {
    probedIndex -= probe;
    if( probedIndex < 0 ) {
     probedIndex += length;
    }
    cur = entries[probedIndex];
    if( cur == FREE ) {
     //cache miss
     return evaluateAndStore( isoCode, probedIndex );
    } else if( cur.isoCode.equals( isoCode ) ) {
     //cache hit
     return cur;
    }
   }
   //cache miss, and cache is full 
   throw new IllegalStateException( "Cache[size:"+entries.length+"] is full: ["+isoCode+"]" );
  }
 }

 private Entity evaluateAndStore( final String isoCode,
                                  final int index ) {
  final Entity entity = new Entity( isoCode );
  entries[index] = entity;
  return entity;
 }

 public void purge() {
  Arrays.fill( entries, null );
 }
}

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

Подробности

Вопрос: Почему это работает? Ответ: А почему бы и нет? ;)

Вообще-то стоило бы чуть подробнее остановиться на том, как именно оно работает. Обычно предполагается, что если объект уже есть в кэше, то при запросе именно он и вернется. Но в данном случае, из-за отсутствия синхронизации, состав кэша может разными потоками видиться по-разному, так что понятие "объект есть в кэше" становится не очень определенным. Так что работать это будет так: если объект есть в кэше, и виден текущему потоку -- вернется он. Если не виден (или вообще нет) -- будет создан новый экземпляр. То есть кэш не сохраняет идентичность (preserve identity) -- для одного и того же ключа isoCode в программе могут существовать несколько разных экземпляров Entity.

Второй важный момент это то, что Entity -- immutable. В многопоточном окружении запись entries[index] = entity -- это публикация ссылки на объект. Без дополнительной синхронизации (а где она? а нет ее!) это будет публикация через data race. И только особые гарантии JMM для immutable объектов дают нам возможность утверждать, что если другой поток увидел ссылку на Entity, то он увидит через нее полностью инициализированный объект.

Собственно, здесь две ключевых идеи. Во-первых, ослабление семантики -- отказ от принципа один тюбик в одни зубы "для каждого ключа значение создается строго однажды". Во-вторых, использование immutable объектов для безопасной публикации через data race. Эти две идеи в сумме и позволяют обойтись без синхронизации.

Что еще можно с этим сделать?

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

Но это не единственный вариант использования. Бывает другая задача: множество объектов в принципе не ограничено, но известно, что чаще всего используются недавние объекты. Т.е. хочется LRU кэш. И такое тоже можно:

public class FastLRUEntityCache{
 private static final Object FREE = null;

 private final Entity[] entries;

 public FastLRUEntityCache( final int size ) {
  checkArgument( size > 1, "size[%s] must be >1", size );

  entries = new Entity[size];
 }

 public Entity get( final String isoCode ) {
  final int hash = isoCode.hashCode() & 0x7fffffff;

  final int length = entries.length;
  final int index = hash % length;

  Entity cur = entries[index];

  if( cur == FREE ) {
   //cache miss
   return evaluateAndStore( isoCode, index );
  } else if( cur.isoCode.equals( isoCode ) ) {
   //cache hit
   return cur;
  } else {// already FULL, replace
   return evaluateAndStore( isoCode, index );
  }
 }

 private Entity evaluateAndStore( final String isoCode,
                                  final int index ) {
  final Entity entity = new Entity( isoCode );
  entries[index] = entity;
  return entity;
 }

 public void purge() {
  Arrays.fill( entries, null );
 }
}

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

Вопрос: А если у меня объект не immutable? Ответ: Если он не immutable, но фактически не меняется -- можно просто создать обертку

public class Freezer<T>{
   public final T item;
   public Freezer(final T item){
    this.item = item;
   }
}

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

Вопрос: А можно сделать кэш resizeable? Ответ: Можно, конечно. Но придется делать поле entities volatile -- что несколько увеличит стоимость обращения к кэшу. Я не стал с этим возиться.

Для пуристов, поясняю: да, сам по себе volatile load на широко используемых архитектурах ничего дополнительного не стоит, в сравнении с обычным load. Но он запрещает некоторые оптимизации. Например:

for( over 9000 ){
  final String isoCode = ...;
  final Entity entity = cache.get(isoCode);
  ...
}

Если entries является final (да и просто non-volatile), то компилятор может вынести его чтение за цикл. Если же entries volatile -- оно будет считываться на каждой итерации. Т.е. мы можем сэкономить что-то вроде (L1 load - register load) * (over 9000) тактов :)

Философское заключение про data race

Как мы могли увидеть, существование в програме data race сам по себе не является приговором "программа некорректная". Но существование гонки, как правило, резко увеличивает размер графа состояний программы, количество возможных сценариев выполнения. Если это не было предусмотрено -- есть близкая к 100% вероятность упустить какие-то сценарии, нарушающие заложенные в код инварианты. Но если распоряжаться гонками аккуратно, то можно осмысленно создать ситуацию, где граф состояний даже с гонкой остается обозримым. И тогда можно увидеть возможности для вот таких вот простых и эффективных решений.

Это я так, типа, хвастаюсь :)

Тестирование и документирование

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

Конечно, не новость, что примеры нужны, важны, и полезны. Но эти полезные примеры нередко оказываются рассеяны среди большого количества текста. При том, что примеры часто гораздо полезнее этого текста, и могли бы заменить бОльшую его часть.

How much memory objects take on JVM, and why this may matter

sizeof(Object): how much memory objects take on JVMs and when this may matter

Вдогонку про публикацию

Вдогонку к предыдущему посту, и к вот этому посту Алексея. Для прояснения ситуации.

Итак, вот это

public class T {
   public int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях тундры...
public T sharedRef;
 
sharedRef = new T( 10 );
 

НЕбезопасная публикация

Вот это:

public class T {
   public int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public volatile T sharedRef;
 
sharedRef = new T( 10 );
 

безопасная публикация -- потому что через volatile-ссылку.

Вот это:

public class T {
   public final int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public T sharedRef;
 
sharedRef = new T( 10 );
 

безопасная публикация -- потому что для final-полей особые гарантии.

А вот это:

public class T {
   public volatile int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public T sharedRef;
 
sharedRef = new T( 10 );
 

НЕбезопасная публикация -- потому что обычные записи (sharedRef=new T()) можно переставлять до волатильных записей! Поэтому волатильность поля field1 не гарантирует нам, что ссылка на объект T будет опубликована после инициализации этого поля.

UPD: В данном конкретном случае, когда в классе всего одно поле — публикация таки безопасна. Дискуссию по этому поводу можно прочитать здесь, а формальное доказательство здесь. Однако неочевидно, можно ли перенести это рассуждение на классы со "смешанным составом" полей (volatile+non volatile)

UPD по просьбам читателей: вот это

public class T {
   private int field1;
 
   public T( final int field1 ){
      synchronized( this ) {
         this.field1 = field1;
      }
   }
    
   public synchronized int getField1(){
      return this.field1;
   }
   
   public synchronized void setField1( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public T sharedRef;
 
sharedRef = new T( 10 );
 

Это такая хитрая штука: формально публикация небезопасна, но фактически это ненаблюдаемо -- если вы не полезете к field1 какими-нибудь неправославными методами, то для доступа через геттер/сеттер все безопасно.

(Un)Safe publication

Безопасная/небезопасная публикация ссылок — источник огромного количества ошибок в многопоточном коде. Мне иногда кажется, что таких ошибок вообще большинство. Т.е. если программист обладает >= базовыми знаниями по concurrency в яве, то почти наверняка он все равно частенько будет писать код, некорректный по JMM, и в большинстве случаев некорректность будет связана именно с понятием небезопасной публикации.

Да что я все о каких-то абстрактных программистах рассказываю. Давайте честно: unsafe publishing я регулярно обнаруживаю в своем собственном коде, и если бы только старом... Так нет — это, наверное, единственная ошибка, которую я продолжаю регулярно, раз за разом совершать при написании многопоточного кода.

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

Это первая причина. А вторая состоит в том, что такого рода нарушения JMM очень редко когда становятся причиной реальных багов. Т.е. программист очень редко получает прямую недусмысленную обратную связь от реального мира вида "написал херню — получил регулярно возникающий но сложный в отладке гейзенбаг". Обычно обратная связь приходит лишь в виде пиздюлейругани от старших товарищей — что, все же, обладает гораздо меньшим воспитательным эффектом...

Чуть подробнее...

(Не)Безопасная публикация

//есть у нас такой класс
public class T {
   public int field1;

   public T( final int field1 ){
      this.field1 = field1;
   }
}

//...где-то в дебрях кода...
public T sharedRef;

//Thread 1
sharedRef = new T( 10 ); //а почему бы и не 10? 42 сегодня взяла отгул

//Thread 2
System.out.println( "sharedRef.field1 = " + sharedRef.field1 );

Какие варианты вывода мы здесь можем наблюдать в соответствии с JMM?

Подразумеваемый вариант — все будет хорошо, ожидаемо выведется "10". Оставим эту скукотищу для стариков и женщин. Мы молоды духом, и готовы к приключениям — нам пожалуйста чтобы все ломалось, разрушалсь, взрывалось и горело, и чтобы еще секса побольше...

Ок, у меня есть специально для вас сценарий повеселее: NullPointerException. Сценарий здесь тоже довольно очевиден — поток №2 может прочитать значение sharedRef до того, как поток №1 туда запишет что-то. В таком случае поток №2 увидит значение по-умолчанию, null.

Мы такого варианта не хотим, поэтому делаем так:

//Thread 2
if( sharedRef != null ){
    System.out.println("sharedRef.field1 = " + sharedRef.field1 );
} else {
    //...
}

Увы, но здесь уже начинаются чудеса. А именно — мы все еще можем увидеть NPE в этом коде! Почему? Да потому что второе чтение sharedRef может вернуть совсем не то значение, что первое. В потоке №1 у нас есть две записи в sharedRef: первая, неявная — запись значения по-умолчанию (null). Вторая, явная — запись ссылки на созданный объект. С точки зрения потока №2 эти записи никак не упорядочены (==нет ребер hb, обязующих его видеть записи именно в "нужном" порядке), и он вполне может увидеть сначала запись sharedRef=new T(), и только потом sharedRef=null.

Disclaimer: Я не уверен на 100% действительно ли JMM допускает такие перестановки. Некоторые уважаемые люди с этим не согласны, а процедура определения возможных трасс для кода с гонками в JMM исключительно ебанутаясложная, и строго ее проходить никому не охота. Но для дальнейшего это не суть важно

Ок, это легко вылечить:

//Thread 2
final T localRef = sharedRef;
if( localRef != null ){
    System.out.println("sharedRef.field1 = " + localRef.field1 );
} else {
    //...
}

мы прикрыли свою задницу от NPE, и теперь уже можем сосредоточиться на выводимых значениях. А значений, увы, мы можем увидеть больше одного. Мы можем увидеть в выводе sharefRed.field1 = 10 — как и ожидалось. Неожиданным может быть то, что мы можем видеть и вывод sharefRed.field1 = 0. Причина все та же. Короткая строчка sharedRef = new T(10) на самом деле это целый ряд операций: (выделение памяти, заполнение полей значениями по-умолчанию, выполнение конструктора, запись ссылки в sharedRef). То, что в коде потока 1 они идут именно в таком порядке не означает, что поток 2 их увидит так же. Он совершенно спокойно может увидеть сначала присвоение ссылки на "пустой" объект с дефолтными значениями полей (увидеть ссылку до присвоения полям начальных значений он не может — это JMM явно запрещает). Более того, если бы в T было больше одного поля (field1, field2, field3...) мы могли бы увидеть в потоке 2 любую комбинацию из инициализированных/неинициализированных полей.

Эти вот два примера — это и есть суть того, что называется небезопасной публикацией, или, неформально, публикацией "через data race" (где здесь гонка — надеюсь, очевидно).

Смотрите, какая штука: в рамках каждого отдельного потока все инструкции упорядочены по happens-before (порядок HB согласован с т.н. program order — порядком инструкций в коде программы). И когда мы в потоке 2 читаем значение, записанное потоком 1 в sharedRef в строчке 14 — кажется очевидным, что раз мы его прочитали, значит эта запись произошла до нашего чтения! То есть интуитивное восприятие последовательности событий подсказывает, что сам факт чтения создает нам ребро HB — которое как раз и необходимо, чтобы весь код стал корректно синхронизированным.

И вот эта-то трактовка, кажущаяся настолько интуитивной-интуитивной, что даже в доказательстве не нуждается — она-то как раз и совершенно не верна. Фактический порядок исполнения инструкций в конкретном запуске программы — это совсем другое, нежели формальный порядок happens-before, верный для любого запуска этой программы на любом железе и под любой JVM. Это очень важный момент: если вы в ходе исполнения программы зафиксировали, что какое-то событие А произошло до события Б — это вовсе не значит, что можно утверждать, что A hb B.

Есть одно важное исключение — семантика final полей. Если бы поле field1 было бы финальным — то как раз сам факт чтения ненулевого значения sharedRef действительно порождал бы HB. Но это особое ребро HB, некоммутативное с обычными — подробнее я уже писал здесь.

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

Где-то я эту хрень уже видел...

Ну конечно. Unsafe publishing — это основа того, почему не работает double-checking locking:

private static DCLSingleton singleton = null;
public static DCLSingleton getInstance(){
   if( singleton == null ){
       synchronized( DCLSingleton.class ){
          if( singleton == null ){
              singleton = new DCLSingleton();
          }
       }
   }
   return singleton;
}

вот если какой-то поток видит singleton != null до захвата монитора — то он может видеть эту ссылку через data race. Как следствие — ссылка-то будет не нулевая, а вот содержимое может быть каким угодно.

Сюда же относится SettableFuture из этого поста — вот этот вариант:

public class SettableFuture<V> implements Future<V> {
    private V slot;

    public V get() throws InterruptedException, ExecutionException {
        synchronized( this ) {
            while ( slot == null ) {
                wait();
            }
        }
        return slot;
    }

    public void set( final V value ) {
        slot = value;
        synchronized( this ) {
            notifyAll();
        }
    }
}

Опасность небезопасной публикации в том, что она заметно усложняет создание потокобезопасного объекта. В самом деле, если нам нужен объект, корректно работающий в многопоточном окружении, и нас пока не заботит производительность — то мы можем просто защитить все методы объекта монитором — и спать спокойно?

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

Пуленепробиваемо потокобезопасный объект в яве можно создать лишь двумя способами. Первый, и самый лучший — делать его immutable. Для объектов с final полями при условии корректной инициализации Священное ПисаниеJMM отдельной главой гарантирует их безопасную работу в многопоточном окружении, даже при передаче через data race. Благослови боже immutability.

Второй, довольно некрасивый — защищать монитором все методы и еще и все конструкторы. Эта тема некоторое время муссировалась в cuncurrency-interests, и в итоге все Пророки согласились, что объект, у которого все поля закрыты, доступ к ним только через методы, а все методы и конструкторы защищены монитором — будет корректно работать, как его не передавай.

Проблема с этим, вторым, методом — в том, что о нем почти никто не знает. Существуют тонны примитивно-потокобезопасных объектов, со всеми методами synchronized, но много ли вы видели объектов с защищенным конструктором? Более того, в ранних версиях одной из священных книг (чуть ли не "Философии джавы") было даже указано, что синхронизировать конструктор нет смысла, и что это явная ошибка. Это было до ревизии модели памяти в 1.5, но кто заметил? Даже синтаксический сахар synchronized как аттрибут метода на конструктор не распространяется...

Представьте, сколько сейчас по разным библиотекам разбросано классов, которые их авторы предполагали потокобезопасными — хотя они таковыми не являются? Тут и сон с аппетитом потерять недолго.

Почему же это не тревожит широкие народные массы?

По легенде, в одном из советских НИИ годов 60-х висел плакат с летящим шмелем, и надписью: "Большая масса тела шмеля вкупе с малой несущей поверхностью его крыльев не позволяет шмелю летать. Но шмель не знает об этом, и летает только поэтому"
Ну, во-первых, потому что во многих православных паттернах работы с многопоточностью безопасность публикации обеспечивается их авторами. И работает, даже если использующий эти паттерны программист вообще не задумывается о безопасной публикации. Например, многие ли задумываются о том, что передавая в Executor Runnable со ссылкой на какие-то данные, которые нужно обработать, мы тем самым публикуем ссылку на эти данные для потоков внутри Executor-а? Между тем это именно публикация ссылки, и она безопасна — потому что об этом позаботились разработчики Executor-а.

А вот вторая причина интереснее и скандальнее. Во всем виноват Интел и его монополия :)

Дело в том, что JMM разрабатывалась, как и многое в мире джавы, так, чтобы оставить максимум свободы для потенциальных оптимизаций как разработчикам JVM, так и железу. Но, разумеется, ни те, ни другие не используют всех оставленных им возможностей — что могут, что востребовано — то и используется. (Это нормальная ситуация для любой сложной и долгоживущей системы: избыточность как плата за невозможность точного предвидения будущего. Системы без избыточности как правило нежизнеспособны в долгосрочной перспективе).

"Write once — run everywhere" — красивый, но весьма условный слоган. Везде — это где именно? Вот лично я только однажды в жизни запускал ява-код на не-x86 архитектуре — когда игрался с J2ME. А если ограничиться SE/EE — кто запускал свой код не на интелловской архитектуре? Думаю, почти никто. Если я ошибаюсь — отпишитесь в комментариях, мне любопытно в скольких неожиданных местах ваш код начал внезапно глючить :)

А что такого плохого у нас с Intel? Да все у нас хорошо, даже слишком. У интелловских x86 архитектур (т.е. не-Intanium) очень жесткая аппаратная модель памяти: total store order, TSO. Это означает, если очень упрощенно, что интелловские (и не только интелловские — архитектура x86 стандарт де-факто для большого куска рынка) процессоры выполняют записи всегда в том порядке, в котором они идут в коде программы. Другая формулировка: все потоки в системе видят все записи в одном и том же порядке, и этот порядок согласован с порядком соответствующих инструкций записи в коде потоков. Это уже гораздо больше, чем требует JMM от кода, выполняемого без дополнительных инструкций синхронизации. В частности, для случая небезопасной публикации это означает, что публикация в железной модели памяти x86 всегда безопасна. И единственным источником непредсказуемости остается JIT — который тоже может переставлять инструкции.

Может-то он может, да будет ли? Ну вот давайте, для примера, рассмотрим тот же DCL. Если взять псевдокод — getInstance() будет выглядеть примерно так (это дикая помесь байткода с явой и ассемблером — но вроде суть понятна):

if( DCLSingleton.instance != null ) 
   jmp #end;

monitorEnter DCLSingleton.class;
if( DCLSingleton.instance != null )
   monitorExit DCLSingleton.class;
   jmp #end;

localRef = allocate( sizeof(T) );
call DCLSingleton.<init>( localRef );
DCLSingleton.instance = localRef;

monitorExit DCLSingleton.class;

end:
   return DCLSingleton.instance;

Если JIT сгенерирует прямо и непосредственно вот это — то на x86 все будет в шоколаде, ни один котенок не пострадает, никакой возможности увидеть ссылку на недоинициализированный объект не будет, потому что присвоение ссылки в shared variable идет после вызова конструктора, и x86 сам записи не переставляет — значит все потоки увидят именно сначала те записи, которые выполнены в рамках конструктора, а уж потом публикацию ссылки.

Разумеется, JIT мог бы сам переставить запись DCLSingleton.instance = localRef до вызова конструктора. Но для JIT это будет довольно опасная оптимизация, потому что он же не знает, что там, внутри DCLSingleton.<init>( localRef )? Может, там программист заложился на то, что instance == null — тогда, переставив запись JIT нарушит intra-thread semantics. Поэтому сделать такое он может только если ему на стадии оптимизации текущего метода доступна информация о коде конструктора. Современные JIT-ы не выполняют межпроцедурную оптимизацию, поэтому информацию о коде вызываемого метода JIT может получить только если он еще раньше принял решение встроить (inline) вызываемый метод. Тогда код конструктора становится частью кода текущего метода, и JIT может убедиться, что упреждающая запись instance ничего не нарушит.

А зачем бы JIT-у встраивать вызов конструктора? Встраивание — это агрессивная оптимизация, применяемая для очень горячего кода. Но ведь вся идея DCL в том-то и состоит, чтобы сделать синхронизированный код не горячим. Я уж молчу, что суть синглетона в том, чтобы конструктор вообще вызвался только один раз.

Это все мои, довольно спекулятивные предположения о том, как именно работает JIT. Они могут быть неверными в деталях, но суть остается та же — JIT довольно редко делает что-то, что нарушает hardware TSO. Один уважаемый человек™ рассказывал, что он как-то потратил день чтобы так написать DCL, чтобы он ломался бы хотя бы один раз на миллиард вызовов.

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

UPD: Перечитал и ужаснулся — какое-то неверное представление тут создается :) Что я здесь хотел сказать: что есть очевидный, но довольно узкий сегмент высоконагруженного, высококонкурентного кода, в котором небезопасная публикация будет довольно стабильно генерировать ошибки даже на x86. В "обычном" же малонагруженном коде — типа начальной инициализации — в силу жесткости аппаратной модели памяти x86, и в силу того, что наиболее агрессивные оптимизации JIT применяет только к горячему коду небезопасность публикации будет незаметна. Она либо вообще не будет создавать ошибок, либо будет создавать их настолько редко и невоспроизводимо, что вы скорее примете их за баги в JVM/железе.

Тогда зачем мне весь этот гемморой?

В самом деле, возникает немного крамольная мысль: насколько оно полезно с практической точки зрения — писать корректный по JMM код? Если ошибки будут возникать только в лабораторных условиях в одном случае из миллиарда — так может я лучше потрачу время на поиск логических ошибок в коде, которые будут проявляться чаще? Система в целом не сильнее своего самого слабого звена — это применимо как к производительности, так и к надежности. Насколько оправдано тратить время на избавление от гонок в коде, если есть такие источники ненадежности как общий недостаток мозгов у разработчиков, ошибки в JVM, баги в железе и нашествие помидоров-убийц?

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

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

Мы не будем вечно сидеть на TSO. Поддержание такой строгой модели памяти стоит довольно недешево, и сильно ограничивает дальнейшее увеличение количества ядер. У интела уже есть Itanium с ослабленной моделью памяти, очевидно будут и другие модели. Кроме того на рынок серверов сейчас активно лезет ARM — и скорее всего таки пролезет. Ну и Азул тот же самый... Все идет к тому, что иметь дело с ослабленными аппаратными моделями памяти нам все равно придется — и мне кажется, лучше готовиться к этому заранее.

lazySet: тайные страницы JMM

Подолжая раскрывать темы, недостаточно раскрытые на докладе -- сейчас про lazySet. Тема это непростая, и не потому, что там все сложно, а потому, что нужно повторить основы JMM. У меня уже давно бродит мысль написать цикл статей "Скрытые главы JMM", но все руки не доходят -- это ж надо будет advanced JMM перечитать внимательно и пристально, все теоремы разбирая... Вот, может, в старости...

Так что сейчас будет краткое введение, голопом по европам.

Дисклаймер: все что идет дальше -- это мое личное понимание JMM. Оно может быть неполным, неправильным, и вообще полной херней. Я вас предупреждал!

...Когда пишут про JMM -- почти всегда пишут про частичный порядок "происходит до" (partial happens before order). Это действительно самая ходовая часть JMM -- в большинстве практических случаев достаточно знать правила формирования ребер HB, и счастье будет уже здесь, и моментально.

Но JMM гораздо более сложная конструкция, чем только HB. JMM -- это такой набор ограничений на исполнение java кода. Эти ограничения позволяют сделать одно очень сильное утверждение относительно возможных сценариев его исполнения. А именно: если у нас в коде нет гонок (data race), то любой сценарий исполнения будет sequentially consistent.

По пунктам: что такое гонки (data race)? Пусть у нас в программе есть разделяемая (т.е используемая из >1 потока) переменная, и хоть один поток в нее пишет. Почему важна запись понятно: если никто не пишет, а все только читают, то это не интересно, никаких конфликтов. А вот если есть запись и чтение(-я) -- тогда все любопытнее. Если запись и чтение не упорядочены (через HB) то говорят, что этот набор инструкций (запись и чтения) образует гонку. Код без гонок называется data race free, DRF

В чем проблема с гонками? В том, что в них становятся заметными весь тот треш, угар и содомия (для наших читателей из Питера: здесь нет пропаганды гомосексуализма, я гарантирую это!), которую творят с вашим кодом современные оптимизирующие компиляторы и (в большей степени) современные CPU и контроллеры памяти. Все эти instruction reordering, out-of-order execution, speculative branch prediction, write combining, и прочие ужасы царизма. Это то, что, по-идее, программисту видно быть не должно -- ибо он поседеет, если это увидит. Другими словами: в коде с гонками начинают течь широко используемые абстракции -- что код исполняется так, как вы его написали, что память у нас общая и однородная, и т.п. Вы начинаете видеть грязную кухню реального мира :)

Вернемся к баранам. Что такое sequentially consistent (SC) execution? Неформально: SC для многопоточной программы -- это когда ваш код исполняется так, как будто он исполняется на единственном устройстве выполнения, безо всяких буферов, кэшей и внеочередного выполнения операций. Т.е. каждая инструкция атомарна, и ее результат сразу же доступен (виден) всем остальным потокам. Инструкции выполняются строго в том порядке, как они идут в коде. Переход от исполнения кода одного потока к коду другого возможен только в промежутке между двумя инструкциями. Еще проще -- это back to i386. Разумеется, реально ваш код может исполняться как угодно -- но результат в любой точке должен быть только такой, какой возможен при каком-нибудь SC сценарии.

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

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


Теперь, когда мы прониклись величием решаемой JMM задачи, можно уже отметить одну мелочь: для того, чтобы доказать свойство (DRF -> SC) одного частичного порядка HB недостаточно. Нужны еще две важных вещи.

Во-первых это причинность (causality). Неформально: что у любого события есть первопричина. Не допускаются циклы причинности: когда А является причиной для Б, а Б -- является причиной для А. Причинность, в частности, запрещает в яве значениям переменных возникать из воздуха ("out of thin air") -- для любого прочитанного из переменной значения должна существовать в коде программы операция записи, которая это значение туда записала (и она не должна происходить после этого чтения). Для явы это архиважно, потому что если бы значение ссылки могло возникнуть из ниоткуда -- вся безопасность языка и среды накрылась бы медным тазом.

Во-вторых, это Total Synchronization Order. В JMM некоторые операции (захват/освобождение монитора, чтение/запись волатильной переменной, и всякая эзотерика, типа условных "первое/последнее действие в потоке", операция запускающая поток, операция обнаруживающая завершение потока... см подробнее JLS 17.4.2) объявлены как Synchronized Actions. Особенность этих SA в том, что они образуют Total Synchronization Order. Ключевое здесь именно total -- полный порядок, в отличие от partial happens-before order, который частичный порядок.

Частичный порядок означает, что между некоторыми операциями есть точно определенный порядок -- А всегда (во всех сценариях исполнения) идет до Б. А между некоторыми операциями такого однозначного порядка нет -- в одних сценариях исполнения В может идти до Г, в других -- Г до В. И более того -- в одном и том же сценарии исполнения один поток может видеть сначала результат Г, а потом результат В, а другой поток -- сначала результат В, а потом Г. Т.е. порядок В и Г не определен в обоих смыслах: и поскольку он в разных сценариях (запусках) может быть разным, и поскольку даже в одном сценарии он может видиться разным с разных точек зрения.

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

То есть тот факт, что synchronization actions образуют полный порядок означает (в переводе с математического на русский), что любая пара synchronization actions всегда упорядочена, и этот порядок виден всеми потоками программы одинаково.

Получается, что synchronization actions -- они уже sequentially consistent. И чтобы получить SC для всей программы нам осталось только как-то "растянуть" эту sequentially consistency на все остальные инструкции в коде. И мы это делаем с помощью частичного порядка happens-before -- присоединяя по транзитивности к уже существующим и всегда упорядоченным synchronization actions обычные инструкции. И если нам удастся по транзитивности присоединить все инструкции в программе (а это удастся если в программе нет гонок) -- то мы и получим SC для всей программы в целом!

То есть, если очень кратко -- мы создаем в программе становый хребет из synchronization actions, которые по-определению sequentially consistent. И ребрами HB присоединяем к нему то, что можно присоединить. Если в программе нет гонок -- то нам удастся присоединить все инструкции, и вся программа окажется доказуемо SC.


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

volatile va = 0;
volatile vb = 1;
a = 0;

//Thread 1:
va = 1;
a = vb;

//Thread 2: 
print( "va=" + va + ", a=" + a ); 
//может ли вывести "va=0, a=1"?

Может этот код вывести "va=1, a=0"? Т.е. может ли быть a = vb переставлено до va = 1?

Обычные ребра HB этого не запрещают: записи идущие после volatile write можно переставлять до нее, а волатильное чтение образует HB только с волатильной записью той же переменной -- чего здесь нет.

Однако если допустить, что такая перестановка возможна и допустима, то мы получаем ситуацию, когда Thread 1 видит (в соответствии со своей внутри-поточной семантикой) сначала волатильную запись va=1, а потом волатильное чтение a=vb. А Thread 2 видит другой порядок -- сначала чтение vb, потом запись va. А это означает, что у нас нет единого, согласованного между всеми потоками порядка SA-операций. То есть такая перестановка недопустима, ее нужно запрещать.

Вот здесь мы подходим (наконец-то! вы там еще не уснули?) различию между volatile write и lazySet.

Для того, чтобы обеспечить обычное ребро HB между volatile write и read одной и той же переменной достаточно всего двух барьеров -- store-store до записи:

membar(store&load|store)
store va

и load-load после чтения:

load va
membar(load|store&load)

Этого достаточно, чтобы все, что было записано до store va было гарантированно видно после load va. Но этого не достаточно, чтобы обеспечить TSO -- нужно еще запретить реордеринг для synchronized actions. И вот для этого нужен дополнительный StoreLoad после записи:

membar( store&load | store )
store va
membar( store | load )

Именно отсутствием этого store-load и отличается lazySet. lazySet не является sychronized action, он не участвует в total synchronization order, и обходится без соответствующего барьера. А store-load -- единственный необходимый явный барьер на x86 (остальные выполняются неявно, в силу довольно большой строгости аппаратной модели памяти x86). Реализуется он как lock add %esp, 0x00 -- и это довольно дорогая операция. Поэтому если вы можете доказать корректность своей программы без того, чтобы какая-то конкретная волатильная запись была частью TSO -- можно на нем сэкономить. Правда, доказать это весьма непросто. Единственный известный мне метод -- это прислать код в concurrency-interest на ревизию Дагу Ли лично :)

[*] JSR-133 Cookbook for compile writers

Код бенчмарков

Отдельные люди на JavaOne после доклада просили выложить код бенчмарков. Вот, код здесь.

Ногами прошу не бить :)

...расследования

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

В общем, одна картинка -- стоит тысячи слов. А уж знали бы вы, чего мне стоило выдрать эту картинку из своей презентации! ГуглоДокументы так просто контент не отдают:)

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

Так вот, если это среднее расстояние таково, что записываемые издателем сообщения находятся на другом кэш-лайне, чем читаемые подписчиком -- то все шоколадно, контроллер памяти работает в приемлемом режиме. А вот если расстояние окажется слишком маленьким -- издатель и подписчик будут работать в пределах одного кэш-лайна. А значит -- контроллер памяти будет играть в пинг-понг: издатель будет для записи требовать кэшлайн в в своем кэше в состоянии M, а читатель -- в своем, в состоянии S. Да, это типичный пример false sharing.

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

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

Интересная штука -- когда курсоры идут плотно друг к другу пропускная способность падает. А вот время ответа (latency) -- скорее всего тоже будет падать. Я его не измерял, но кажется очевидным, что чем меньше расстояние между первым и последним курсором в цепочке -- тем быстрее конкретное сообщение будет полностью обработано. А это значит, что бэтчинг здесь это такой размен throughput<->latency. Можно чуть поднять throughput, но ценой увеличения времени обработки одного сообщения. Можно чуть уменьшить время ответа -- но ценой падения и пропускной способности (==менее эффективного использования шины interconnect-а).


И смотрите, как любопытно выходит (дальше мои довольно умозрительные рассуждения): почти наверняка замедление работы в subscriber-batching будет проявляться только в ненагруженном режиме. В нагруженном режиме скорость движения курсоров определяется не их механикой, а нагрузкой -- курсоры двигаются настолько быстро, насколько обработчик успевает делать свою работу. А это значит, что система будет самоподстраивающейся: если нагрузки немного, и обработчики успевают все перемолоть быстро -- они догонят издателя, и будут идти за ним ноздря в ноздрю, уменьшая время ответа. Как только нагрузка вырастает, обработчики начинают не справляться с работой так быстро -- и отстают от издателя. А это сразу дает им чуть-чуть продохнуть за счет более эффективного бэтчинга (больше сообщений за раз) и за счет большего КПД использования interconnect-а. Все это, разумеется, в некоторых, небольших, пределах -- серьезное изменение нагрузки так не скомпенсируешь. Можно даже примерно прикинуть, насколько небольших: худший режим с бэтчингом у нас 15 000 пакетов/мс (~70 нс/пакет), лучший без бэтчинга 35 000 (~30нс/пакет). Разница в 40 нс -- это и есть оценка того, сколько может нам сэкономить сам Disruptor за счет автоматического перехода между режимами.

UPD: Как мне тонко намекнули в комментариях, я забыл важную часть -- гипотеза-то ценна не сама по себе, а тем, что она имеет экспериментальные подтверждения! А именно: если причина ухудшения пропускной способности при включении бэтчинга и нестабильности работы -- действительно такая, как я предположил, то должна быть корреляция между средним расстоянием между курсорами (а схеме это обозначено как gap), и пропускной способностью в конкретном эксперименте. Это можно проверить, и я это проверил. Результат -- вот он (по X -- gap, по Y -- throughput):


По-моему, все очень наглядно. Скачок производительности происходит как раз в области gap=2.5-3.0 Это отлично коррелирует с тем фактом, что размер сообщений у меня примерно 24 байта, т.е. их на 64-байтный кэшлайн умещается как раз чуть меньше 3 штук.

UPD#2: По многочисленным просьбам трудящихся числом 2 -- бенчмарки с пэддингом сообщений. Без batching 19 789 (+/- 483), с batching 20 488 (+/- 1 277).

JavaOne Moscow 2012 -- слайды с презентации

Отчитал вчера "Расчленяя Disruptor" на JavaOne. Слайды здесь. Сразу предупреждаю: слайды делались не по принципу "замена докладчику", а по принципу "лучший копирайт -- это когда без автора не разберешься".

Как разгребу текущие дела -- напишу пару постов по следам. Надо же, наконец, рассказать, почему в бенчмарках Disruptor такая большая дисперсия...

JavaOne 2012, Moscow

Мой личный предварительный маршрут по конференции (общее расписание здесь, и найти его оказалось весьма непросто!):

вторник, синий зал

(если не просплю)
11:30 - 12:25 "JDK8 и дальше" -- посмотрим, что там нам грядущее готовит
12:30 - 13:15 "...от монолитных приложений к модульным" -- ну тоже должно быть любопытно

(постараюсь не проспать)
16:30 - 17:15 "Методология оптимизации производительности"
17:30 - 18:15 "Драконы в домашнем хозяйстве: скалируемся на многоядерных машинах"

Это все Сергей Куксенко и Алексей Шипилёв, они мои любимые спикеры, во-первых по-русски говорят, во-вторых говорят, а не читают -- уже этого достаточно, чтобы к ним заглядывать. Так им этого мало -- они еще и в теме шарят! :)

среда

11:30 ‐ 12:15 "The Garbage‐First" -- тема интересная, я пока довольно мало знаю о G1, любопытно будет послушать. Но, боюсь, здоровый сон окажется важнее :)

14:15 - 15:00 "Fork/Join" -- это опять Алексей, и тема очень интересная -- судя по рассылке concurrency-interest в ForkJoin Даг Ли очень много всяких любопытных идей интегрировал. Более того, все идет к тому, что FJ станет практически умолчанием для распараллеливания. А я его еще и не трогал почти.

15:15 - 16:00 "Многоуровневая компиляция в HotSpot JVM" либо "garbage-free logger" -- вроде бы тут должен быть второй доклад, но в расписании его еще не заменили. Тема с высокопроизводительными приложениями с низким потреблением памяти на яве мне сейчас интересна. Тем более, что с одним из авторов gflogger я знаком -- пойду поддержать.

16:30 - 17:15 "Расчленяя Disruptor: магия и технология высокой производительности" -- по правде говоря, я бы сюда не пошел -- уверен, ничего нового про Disruptor мне там не расскажут. Но поскольку я там спикер -- идти придется. Да и вы тоже приходите -- мне важно ваше присутствие. Только помидоров не берите -- не понадобятся вам там помидоры, вам не до того будет...

17:30 -- 18:15 "Управление памятью в Java: минимизация потребления памяти" -- пойти собираюсь, но не уверен, что буду способен слушать -- после своего доклада я боюсь просто усну.

Скандалы, интриги...

Дошли руки посмотреть на бенчмарки самого Disruptor-а -- у него их есть немного. Сколько я помню, они сравнивали Disruptor vs ArrayBlockingQueue. Но в последних версиях в бенчмарках используются уже LinkedBlockingQueue -- якобы, они быстрее.

Интрига в том, что в их бенчмарках это действительно так -- LBQ стабильно лучше ABQ. Но в моих бенчмарках ситуация ровно обратная -- ABQ стабильно лучше. И я не могу найти причин, почему это так.


UPD: Оказывается, что LBQ быстрее на моем ноуте (Core i7 2GHz), а вот ABQ быстрее на сервере (Xeon E5620 2.4GHz). Подозрение мое падает даже не на то, что это разные модели, а больше на то, что сервер, кажется, ccNUMA, а ноут SMP. Хотя внятно объяснить, как это связано я пока не могу

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

Я тут в процессе подготовки к докладу -- прорабатываю тему 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