Безопасная публикация и инициализация Java-объектов, или #когдаужепочинятdoublecheckedlocking

в 14:02, , рубрики: concurrency, double checked lock, java, java memory model, performance, когдажепочинятdoublecheckedlocking, метки: , , , , ,

Пост из серии «будни перформанс-инженеров» и «JavaOne круглый год».

К моему величайшему facepalm'у на прошедшем JavaOne была тьма вопросов про double-checked locking, и как правильно делать синглетоны. На большую часть этих вопросов уже ответил Walrus, а здесь я хочу подытожить. Надеюсь этим постом раз и навсегда поставить точку в разговорах про double-checked locking и синглетоны. А то мне придётся сделать резиновую печать с URL этого поста и ставить её спрашивающим на лоб.

I. Теоретическая подготовка: фабрики и безопасная публикация

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

Хорошая фабрика синглетонов обладает следующими свойствами:

  1. Хорошая фабрика потокобезопасна. Вне зависимости от порядка обращения из разных потоков все они получат один и тот же синглетон. Более того, синглетон будет корректно проинициализирован.
  2. Хорошая фабрика ленива (тут можно поспорить, но неленивая фабрика нам здесь неинтересна). Инициализация синглетона происходит при первом запросе на синглетон, а не при загрузке класса синглетона .
  3. Хорошая фабрика эффективна, т.е. вносит минимум накладных расходов.

Понятно, что вот такое:

public class SynchronizedFactory {
    private Singleton instance;

    public Singleton get() {
        synchronized(this) {
            if (instance == null) {
                instance = new Singleton();
            }
            return instance;
        }
    }
}

… удовлетворяет требованиям 1 и 2, но не удовлетворяет требованию 3.

На этом месте рождается идиома Double-Checked Locking. Она берёт своё начало из идеи, что нечего лишний раз синхронизироваться, если подавляющее количество вызовов уже обнаружит синглетон инициализированным. Поэтому разные люди берут и пишут:

public class NonVolatileDCLFactory {
    private Singleton instance;

    public Singleton get() {
        if (instance == null) {  // check 1
            synchronized(this) {
                if (instance == null) { // check 2
                    instance = new Singleton();
                }
            }
        }
        return instance;
     }
}

К сожалению, эта хрень не всегда работает корректно. Казалось бы, если проверка check 1 не выполнилась, то instance уже инициализирован и его можно возвращать. А вот и нет! Он инициализирован с точки зрения потока, который произвёл изначальное присвоение! Никаких гарантий, что вы не обнаружите в полях синглетона то, что вы записали внутри его конструктора, нет.

Здесь можно было бы начать объяснять про happens-before, но это довольно тяжёлый формализм. Вместо этого мы будем использовать феноменологическое объяснение, в виде понятия безопасной публикации. Безопасная публикация обеспечивает видимость всех значений, записанных до публикации, всем последующим читателям. Элементарных способов безопасной публикации несколько:

  • инициализация статическим инициализатором (JLS 12.4)
  • запись в поле, корректно защищённое локом (JLS 17.4.5)
  • запись в volatile-поле (JLS 17.4.5), и как следствие, запись в атомики
  • запись в final-поле (JLS 17.5)

Обратим внимание, что в NonVolatileDCL поле $instance…

  • не инициализируется статикой
  • не защищено локом как минимум одно чтение
  • не записывается в volatile
  • не записывается в final

То есть, по определению, публикация $instance в NonVolatileDCL безопасной не является. Смотрите, кстати, сколько из этого следует забавных возможностей для безопасной фабрики синглетонов. Начиная с уже навязшего в зубах:

public class VolatileDCLFactory {
    private volatile Singleton instance;

    public Singleton get() {
        if (instance == null) {  // check 1
            synchronized(this) {
                if (instance == null) { // check 2
                    instance = new Singleton();
                }
            }
        }
        return instance;
     }
}

… продолжая не менее классическим holder idiom, который безопасно публикует, записывая объект статическим инициализатором:

public class HolderFactory {
    public static Singleton get() {
        return Holder.instance;
    }

    private static class Holder {
        public static final Singleton instance = new Singleton();
    }
}

… и заканчивая final-полем. Поскольку в final-поле вне конструктора писать уже поздно, нужно сделать:

public class FinalWrapperFactory {
    private FinalWrapper wrapper;

    public Singleton get() {
        if (wrapper == null) {  // check 1
            synchronized(this) {
                if (wrapper == null) { // check 2
                    wrapper = new FinalWrapper(new Singleton()); 
                }
            }
        }
        return wrapper.instance;
     }

     private static class FinalWrapper {
        public final Singleton instance;
        public FinalWrapper(Singleton instance) {
            this.instance = instance;
    }
}

Вариант с безопасной публикацией через корректно синхронизированное поле у нас уже есть, в самом начале.

Кроме того, в наш зачёт с криком «volatile это дорого!» врывается новый кандидат, кеширующий поле в локале:

public class VolatileCacheDCLFactory implements Factory {
    private volatile Singleton instance;

    @Override
    public Singleton getInstance() {
        Singleton res = instance;
        if (res == null) {
            synchronized (this) {
                if (instance == null) {
                    instance = new Singleton();
                }
            }
            return instance;
        }
        return res;
    }
}

II. Теоретическая подготовка: синглетоны и безопасная инициализация

Идём дальше. Объект можно сделать всегда безопасным для публикации. JMM гарантирует видимость всех final-полей после завершения конструктора. Вот пример полностью безопасной инициализации:

public class SafeSingleton implements Singleton {
    private final Object obj1;
    private final Object obj2;
    private final Object obj3;
    private final Object obj4;

    public SafeSingleton() {
        obj1 = new Object();
        obj2 = new Object();
        obj3 = new Object();
        obj4 = new Object();
    } 
    ...
}

Замечу, что в некоторых случаях это распространяется не только на final поля, но и на volatile. Есть ещё более фимозные техники, типа synchronized в конструкторе, можете почитать у cheremin, он такое любит. В этом посте таких высоких материй мы касаться не будем.

Вот такой объект, понятно, будет небезопасным:

public final class UnsafeSingleton implements Singleton {

    private Object obj1;
    private Object obj2;
    private Object obj3;
    private Object obj4;

    public UnsafeSingleton() {
        obj1 = new Object();
        obj2 = new Object();
        obj3 = new Object();
        obj4 = new Object();
    }
  
   ...
}

На самом деле, проблемы с небезопасно опубликованным небезопасным синглетоном скажутся в некоторых специальных граничных условиях, например, если конструктор синглетона заинлайнится в getInstance() фабрики Тогда ссылка на недоконструированный объект может быть присвоена в $instance до фактического завершения конструктора.

Вот, например, хвост NonVolatileDCLFactory.getInstance() для UnsafeSingleton (конструктор синглетона заинлайнился):

178     MEMBAR-storestore (empty encoding)
178     #checkcastPP of EAX
178     MOV    [ESI + #8],EBX ! Field net/shipilev/singleton/NonVolatileDCLFactory.instance
17b     MOV    [EDI + #20],EAX ! Field net/shipilev/singleton/UnsafeSingleton.obj4
17e     MOV    ECX, ESI # CastP2X
180     MOV    EBP, EDI # CastP2X
182     SHR    ECX,#9
185     SHR    EBP,#9
188     MOV8   [EBP + 0x6eb16a80],#0
18f     MOV8   [ECX + 0x6eb16a80],#0
18f
196   B16: #    B32 B17 <- B15 B4  Freq: 0.263953
196     MEMBAR-release (a FastUnlock follows so empty encoding)
196     MOV    ECX,#7
19b     AND    ECX,[ESI]
19d     CMP    ECX,#5
1a0     Jne    B32  P=0.000001 C=-1.000000
1a0
1a6   B17: #    B18 <- B33 B32 B16  Freq: 0.263953
1a6     MOV    EAX,[ESI + #8] ! Field net/shipilev/singleton/NonVolatileDCLFactory.instance
1a6
1a9   B18: #    N523 <- B17 B1  Freq: 1
1a9     ADD    ESP,24   # Destroy frame
        POPL   EBP
        TEST   PollPage,EAX     ! Poll Safepoint

1b3     RET

Обратите внимание на присвоение $instance до присвоения $obj4.

А вот тот же самый NonVolatileDCLFactory с SafeSingleton:

178     MEMBAR-storestore (empty encoding)
178     #checkcastPP of EAX
178     MOV    [EDI + #20],EAX ! Field net/shipilev/singleton/SafeSingleton.obj4
17b     MOV    ECX, EDI # CastP2X
17d     SHR    ECX,#9
180     MOV8   [ECX + 0x6eb66800],#0
187     MEMBAR-release ! (empty encoding)
187     MOV    [ESI + #8],EBX ! Field net/shipilev/singleton/NonVolatileDCLFactory.instance
18a     MOV    ECX, ESI # CastP2X
18c     SHR    ECX,#9
18f     MOV8   [ECX + 0x6eb66800],#0
18f
196   B16: #    B32 B17 <- B15 B4  Freq: 0.24361
196     MEMBAR-release (a FastUnlock follows so empty encoding)
196     MOV    ECX,#7
19b     AND    ECX,[ESI]
19d     CMP    ECX,#5
1a0     Jne    B32  P=0.000001 C=-1.000000
1a0
1a6   B17: #    B18 <- B33 B32 B16  Freq: 0.24361
1a6     MOV    EAX,[ESI + #8] ! Field net/shipilev/singleton/NonVolatileDCLFactory.instance
1a6
1a9   B18: #    N524 <- B17 B1  Freq: 1
1a9     ADD    ESP,24   # Destroy frame
        POPL   EBP
        TEST   PollPage,EAX     ! Poll Safepoint

1b3     RET

Видно, что $instance пишется после всех полей.

Для тех, кто не запарился до сюда дочитать, небольшой бонус. HotSpot следует консервативной рекомендации из JSR-133 Cookbook: «Issue a StoreStore barrier after all stores but before return from any constructor for any class with a final field.»

Другими словами, есть специфичная для хотспота фишка:

    ...
    // This method (which must be a constructor by the rules of Java)
    // wrote a final.  The effects of all initializations must be
    // committed to memory before any code after the constructor
    // publishes the reference to the newly constructor object.
    // Rather than wait for the publication, we simply block the
    // writes here.  Rather than put a barrier on only those writes
    // which are required to complete, we force all writes to complete.
    ...

То есть, если hotspot обнаруживает в конструкторе запись хотя бы в одно final поле, то он тупо выставляет барьер в конец конструктора и таким образом обеспечивает запись всех полей в конструкторе до записи ссылки на сконструированный объект. Это имеет смысл, чтобы не делать несколько барьеров для нескольких финальных полей. То есть, только для хотспота можно сделать так:

public class TrickySingleton implements Singleton {
    private final Object barrier;
    private Object obj1;
    private Object obj2;
    private Object obj3;
    private Object obj4;

    public TrickySingleton() {
        barrier = new Object();
        obj1 = new Object();
        obj2 = new Object();
        obj3 = new Object();
        obj4 = new Object();
    }
    ...
}

… и это будет эффективно безопасной публикацией, но только на хотспоте. При этом нет особенной разницы, в каком порядке пишутся поля (но только пока *devil_laugh*).

Это несколько умозрительный случай, но внимательный читатель оценит симпатичные грабли: жил-был класс с кучей нефинальных полей и одним финальным. Тесты проходят, приложение работает, объект как будто безопасно публикуется. Потом приходит Вова и рефакторит класс, удаляя финальное поле — и всё, кранты безопасной публикации. Вова смотрит в свой коммит и не понимает, как такое возможно.

Итого, у нас есть шесть вариантов фабрик и три синглетона.

III. Ломаем DCL

Когда-то давно gvsmirnov меня спрашивал, можно ли действительно продемонстрировать такой реордеринг, который сломает DCL. Как видно из ассемблера вверху, гадкие реордеринги даже в присутствии Total Store Order'а нам может преподнести компилятор. Почему он это сделает, тайна сия велика есть, ему никто не запрещал.

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

    private volatile Factory factory;
    private volatile boolean stopped;    

    public class Runner implements Runnable {

        public void run() {
            long iterations = 0;
            long selfCheckFailed = 0;

            while (!stopped) {
                Singleton singleton = factory.getInstance();
                if (singleton == null || !singleton.selfCheck()) {
                    selfCheckFailed++;
                }
                iterations++;

                // switch to new factory
                factory = FactorySelector.newFactory();
            }

            pw.printf("%d of %d had failed (%e)n", selfCheckFailed, iterations, 1.0D * selfCheckFailed / iterations);
        }
    }

Полный проект лежит вот тут, можете поиграться. -DfactoryType, -DsingletonType выбирают фабрику и синглетон, -Dthreads регулирует количество потоков, а -Dtime — время на тест.

Синглетон проверяет свои поля методом:

    public boolean selfCheck() {
        return  (obj1 != null) &&
                (obj2 != null) &&
                (obj3 != null) &&
                (obj4 != null);
    }

… то есть по сути смотрит, были ли таки инициализированы поля у того инстанса, который отдала фабрика.

Ну что, посчитаем вероятности отказа. Гоняем тесты по 10 минут: за это время миллиарды новых синглетонов успевают создаваться, сталкиваться, разлетаться на фермионы, бозоны… чёрт, кажется, я не туда пишу. Никаким таким тестом доказать корректность многопоточного кода нельзя, тестом её можно только опровергнуть.

На приличных размеров Nehalem'е (2 sockets, 6 cores per socket, 2 strands per core = 24 hw threads), JDK 7u4 x86_64, RHEL 5.5, -Xmx8g -Xms8g -XX:+UseNUMA -XX:+UseCompressedOops, в 24 потоках; метрика — вероятность отказа:

Unsafe Safe Tricky
Synchronized ε ε ε
NonVolatileDCL 3*10-4 ε ε
VolatileDCL ε ε ε
VolatileCacheDCL ε ε ε
Holder ε ε ε
FinalWrapperDCL ε ε ε

ε < 10-11, т.е. ни одного фейла не произошло, но это не значит, что их никогда не будет :)

Что мы видим?

  • Некорректно сконструированный синглетон (Unsafe) нормально работает с корректно публикующими фабриками
  • Некорректно публикующая фабрика (NonVolatileDCL) нормально работает с корректно сконструированными синглетонами
  • Когда эти двое встречаются, начинается треш и угар, причём с приличной вероятностью отказа: фейлом оканчивается 1 вызов из 3000

Дабы меня не обвинили в великодержавном шовинизме, вот тот же тест на двухядерном NVidia Tegra2 (Cortex A9) и JDK 7u4 (ARM port), -Xmx512m -Xms512m -XX:+UseNUMA в двух потоках; метрика — вероятность отказа:

Unsafe Safe Tricky
Synchronized ε ε ε
NonVolatileDCL 2*10-8 ε ε
VolatileDCL ε ε ε
VolatileCacheDCL ε ε ε
Holder ε ε ε
FinalWrapperDCL ε ε ε

ε < 10-10, т.е. ни одного фейла не произошло, но это не значит, что они не появятся в будущем. ε существенно меньше, потому что ARM медленее, а тест выполняется те же 10 минут.

Что мы видим? Да тоже самое и видим. Несмотря на то, что x86 и ARM — очень разные платформы с точки зрения модели памяти, гарантированное поведение остаётся гарантированным. Вероятность отказа сильно упала ввиду специфики теста: глобальный эффект от безопасной публикации самой factory частично сглаживает эффекты от теста.

IV. Performance

Написать корректный параллельный код — дело не хитрое. Оберни всё глобальным локом, и вперёд. Проблема написать корректный и эффективный параллельный код. Ввиду того, что на J1 мне умудрялись говорить «ой, volatile в DCL это так дорого, мы лучше синхронизуем getInstance()», придётся наглядно показать, что к чему. Не буду показывать много графиков, покажу только пару точек с тех же платформах, где гонялась корректность.

Очень простой микробенчмарк в нашем внутреннем тёплом ламповом харнессе выглядит так:

public class SteadyBench { // все инстансы SteadyBench шарятся между потоками
    private Factory factory;

    @Setup
    public void setUp() {
        factory = FactorySelector.newFactory();
    }

    @TearDown
    public void teardown() {
        factory = null;
    }

    @GenerateMicroBenchmark(share = Options.Tristate.TRUE)  
    public Object test() {  // этот метод зовётся в цикле много-много раз
        return factory.getInstance(); 
    }
}

Поскольку наш харнесс ещё не открыт, вам придётся немножко поработать, чтобы написать полный микробенчмарк.

Брать синглетон у уже горячей фабрики — подавляющий use case в продакшене. Замечу, что микротест, который сильно амплифицирует стоимость даже элементарных операций, т.е. если что-то в этом тесте быстрее в два раза, то это не значит, что большой проект тоже разгонится в два раза с «правильной идиомой». Хотя бывает, особенно для локов.

x86, Nehalem, 24 hardware threads; метрика: миллионы операций в секунду, чем больше, тем лучше:

1 thread 24 threads
Unsafe Safe Tricky Unsafe Safe Tricky
Synchronized 46 ± 1 47 ± 1 43 ± 1 9 ± 1 25 ± 1 22 ± 2
NonVolatileDCL 386 ± 12 473 ± 1 463 ± 2 5103 ± 27 4955 ± 84 4981 ± 45
VolatileDCL 394 ± 8 405 ± 2 402 ± 8 3977 ± 33 4576 ± 26 4620 ± 19
VolatileCachedDCL 454 ± 8 465 ± 3 460 ± 6 4778 ± 180 4946 ± 70 5071 ± 87
Holder 554 ± 0 520 ± 7 540 ± 5 6125 ± 30 6131 ± 35 6114 ± 22
FinalWrapperDCL 415 ± 0 390 ± 10 359 ± 6 4566 ± 24 4585 ± 23 4231 ± 30

Что мы здесь видим?

  • про Synchronized даже говорить нечего, она раздулась в настоящий лок и там всё очень-очень плохо
  • NonVolatile работает хорошо и непринуждённо
  • Volatile иногда работает похуже, сказывается необходимость читать $instance из памяти два раза, что делает этот вариант чуть медленнее NonVolatile
  • VolatileCache частично нивелирует этот эффект; показывая, что накладных расходов на само volatile-чтение нет
  • FinalWrapper работает так же как Volatile как раз по этой причине: нужно сделать один лишний дереференс, один лишний поход в память, один лишний потенциальный cache miss
  • Holder впереди планеты всей; казалось бы, ну как? Фокус в том, что к моменту компиляции методов этой фабрики HotSpot знает, что сам холдер уже загружен, и ему не нужно делать вообще никаких проверок, а сразу отдать статический $instance

ARMv7, Cortex A9, 2 hardware threads; метрика: миллионы операций в секунду, чем больше, тем лучше:

1 thread 2 threads
Unsafe Safe Tricky Unsafe Safe Tricky
Synchronized 7.1 ± 0.1 7.1 ± 0.1 7.1 ± 0.1 1.9 ± 0.1 1.9 ± 0.1 1.9 ± 0.1
NonVolatileDCL 23.6 ± 0.1 23.6 ± 0.1 23.6 ± 0.1 45.5 ± 1.3 47.0 ± 0.1 47.0 ± 0.1
VolatileDCL 13.4 ± 0.1 13.4 ± 0.1 13.4 ± 0.1 26.6 ± 0.1 26.6 ± 0.1 26.6 ± 0.1
VolatileCachedDCL 17.4 ± 0.1 17.4 ± 0.1 17.4 ± 0.1 34.6 ± 0.1 34.6 ± 0.1 34.6 ± 0.1
Holder 24.2 ± 0.1 24.2 ± 0.1 24.2 ± 0.1 47.8 ± 0.4 47.9 ± 0.4 48.0 ± 0.1
FinalWrapperDCL 24.2 ± 0.1 24.2 ± 0.1 24.2 ± 0.1 48.1 ± 0.1 46.8 ± 1.5 46.8 ± 1.5

Что мы здесь видим?

  • всё более-менее соотносится с x86, кроме того, что...
  • volatile-чтение на ARM'е требует барьера, поэтому VolatileDCL оттормаживает
  • можно сэкономить на стоимости volatile-чтения, скешировав значение в локале, VolatileCacheDCL это и делает; однако полностью избавиться от оверхеда нельзя, до NonVolatile так и не дотянуло

V. Выводы, обобщения и оговорки

Главный вывод запечатлейте у себя: DCL работает! (кроме случаев, когда и объект небезопасный, и фабрика не безопасная).

Рецепты:

  1. Не делайте ленивую инициализацию там, где сойдёт неленивая
  2. Нужна статическая ленивая фабрика? Вам в Holder. Её особенно не выгрузишь, но зато спекулятивные оптимизации на вашей стороне
  3. Нужна нестатическая ленивая фабрика? Можете использовать NonVolatileDCL, но только если объект безопасно конструируется
  4. Нужна нестатическая ленивая фабрика, и гарантировать безопасность конструирования нельзя? Используйте Volatile(Cached)DCL или FinalWrapperDCL, в зависимости от того, чем вы хотите пожертвовать — потенциальной стоимостью volatile на ARM'е, или потенциальной стоимостью лишнего дереференса

Безопасная публикация и инициализация Java объектов, или #когдаужепочинятdoublecheckedlocking

Автор: TheShade

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js