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. Хотя внятно объяснить, как это связано я пока не могу