30 декабря 2011 г.

Thread Affinity

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

Что меня заинтересовало в его реализации -- так это дизайн. Вместо тривиального setAffinityMask/getAffinityMask он ввел абстракцию "блок кода, выполнение которого привязано к ядру". Выглядит это так:
public void run() {
            final AffinityLock al = AffinityLock.acquireLock();
            try {
                //performance-critical block of code
            } finally {
                al.release();
            }
        }
С текущей реализацией есть несколько проблем.

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

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

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

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

16 декабря 2011 г.

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

В догонку к обсуждениям семантики final-полей. Обычный класс, с изменямыми полями, сложно безопасно опубликовать через data race (т.е. без синхронизации):
sharedRef = new Mutable();
Но можно опубликовать через "обертку" -- класс с final-ссылкой:
sharedRef = new ImmutableReference(new Mutable());
И у меня давно уже бродит идея -- почему бы не сделать сам класс для себя "публикующей оберткой"?
public class SelfPublisher {

    private int value;

    private final SelfPublisher safeThis;

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

    public int getValue(){
        return safeThis.value;
    }
}
Насколько я вижу -- это позволит совершенно безопасно публиковать его через даже data race. Ценой -- увы -- дополнительных затрат памяти на избыточное поле. Ну и дополнительной операции присваивания в конструкторе.

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

9 декабря 2011 г.

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

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

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

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

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

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

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



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

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

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



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

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

Помимо заморозки нам понадобятся еще два специальных частичных порядка (кроме уже всем знакомого happens-before):
  • порядок разыменования (dereference chain, обозначается далее как dereferences(a,b))
  • порядок доступа к памяти (memory chain, обозначается далее как mc(a,b))
Оба этих порядка считаются частью сценария выполнения (трассы над кодом, execution), и поэтому, для конкретного сценария, считаются фиксированными. Эти два частичных порядка должны удовлетворять определенным ограничениям (но решение, удовлетворяющее этим ограничениям, не обязано быть единственным)


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

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

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


Теперь само определение семантики final-полей:
Дано:
  1. Некоторая запись W
  2. Заморозка F
  3. Произвольное действие с памятью (кроме чтения final-поля) A
  4. Чтение R1 финального поля, замороженного F
  5. Чтение R2
Пусть между собой эти действия связаны такими соотношениями: hb(W,F), hb(F, A), mc(A, R1), dereferences(R1, R2).

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

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

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



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

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

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

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

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

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



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

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

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

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

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

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

6 декабря 2011 г.

Java puzzle System.exit and locks.

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

public static void main( String... args ) {
    Runtime.getRuntime().addShutdownHook( new Thread( new Runnable() {
        @Override
        public void run() {
            System.out.println( "Locking" );
            synchronized ( lock ) {
                System.out.println( "Locked" );
            }
        }
    }));
    synchronized ( lock ) {
        System.exit(0);
    }
}
Что напечатает этот код?

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

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

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

1 декабря 2011 г.

StackOverflow: AtomicReferenceFieldUpdater semantic

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

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

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

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

Исследования кода показывают, что, например, в обычных AtomicXXX классах set() -- это просто присвоение:
public class AtomicReference<V>  implements java.io.Serializable {
    //...
    private volatile V value;
    //...
    public final void set(V newValue) {
        value = newValue;
    }
В AtomicReferenceFieldUpdaterImpl это несколько иначе:
public void set(T obj, V newValue) {
        if (obj == null || obj.getClass() != tclass || cclass != null ||
            (newValue != null && vclass != null &&
             vclass != newValue.getClass()))
           updateCheck(obj, newValue);

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

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

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

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

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

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