Without locks

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

Самый наглядный пример реализации -- ленивый кэш. Вот, например, простейший вариант -- кэшируем только результат последнего вызова:

public class SingleLRUWaitFreeCache<In, Out> implements ICache<In, Out> {
    private final Function<In, Out> function;

    private transient Entry<In, Out> recentUsed = null;

    public static <In, Out> SingleLRUWaitFreeCache<In, Out> create( final Function<In, Out> f ) {
        return new SingleLRUWaitFreeCache<In, Out>( f );
    }

    public SingleLRUWaitFreeCache( final Function<In, Out> function ) {
        checkArgument( function != null, "function can't be null" );
        this.function = function;
    }

    @Override
    public Out get( final In key ) {
        if( key == null ){
            throw new IllegalArgumentException("null keys are not supported");
        }
        final Entry<In, Out> lru = recentUsed;
        if ( lru != null && lru.key.equals( key ) ) {
            //cache hit
            return lru.value;
        } else {
            //cache miss
            final Out value = function.apply( key );
            recentUsed = new Entry<In, Out>( key, value );
            return value;
        }
    }

    @Override
    public void purge() {
        //not strictly correct since recentUsed is not volatile
        recentUsed = null;
    }
}

class Entry<Key, Value> {
    public final Key key;
    public final Value value;

    Entry( final Key key,
               final Value value ) {
        this.key = key;
        this.value = value;
    }
}

Дополнительные условия, при которых это работает:

1. Функция function -- идемпотентна, т.е. ее повторный вызов с теми же аргументами не производит никаких дополнительных изменений в системе, по сравнению с первым вызовом. Лучше всего, чтобы она вообще была "чистой" (pure)
2. function должно быть безопасно вызывать из нескольких потоков в произвольном порядке
3. In/Out должны быть immutable объектами

Что мы получаем в итоге?

1. Никаких блокировок
2. Задержка с видимостью работает на нас -- если у разных потоков будут свои версии записанного значения, значит у каждого будет своя, самая свежая для него, версия

Так же можно реализовывать кэши произвольного размера -- только размер должен быть известен заранее. Сейчас у меня в голове бродит реализация Scatter/Gatherer на этой же основе.

Еще с JavaOne

Вспомнился еще один вопрос по JMM, который прояснился на JavaOne -- что происходит с гарантиями видимости final полей, которые дает JMM, если final поля перезаписываются через reflection? Оказывается, ведут они себя прилично -- перезапись final полей через reflection гарантирует выполнение всех mambars/fences, необходимых, чтобы перезаписанное значение стало доступным всем потокам.

How Caching Affects Hashing

How Caching Affects Hashing

UPD: Продолжение темы здесь

Finally, there's not currently space in the mark word to support both an identity hashCode() value as well as the thread ID needed for the biased locking encoding. Given that, you can avoid biased locking on a per-object basis by calling System.identityHashCode(o). If the object is already biased, assigning an identity hashCode will result in revocation, otherwise, the assignment of a hashCode() will make the object ineligible for subsequent biased locking. This property is an artifact of our current implementation, of course.отсюда

Вот так-то вот -- либо identityHashCode, либо biased locking -- вы бы что выбрали?

Biased locking

У стендов на Java One замечательные люди Алексей Шипилёв и Сергей Куксенко рассказывали много всего интересного. Например, узнал, как именно работает biased locking, и зачем он нужен.

По словам Сергея, история с оптимизацией блокировок началась с того, что лазить syscall-ами в ОС за platform-dependent мьютексами в какой-то момент показалось не очень оптимально -- большое число блокировок берется на малое время, и даже при большом числе потоков contention оказывается весьма мал. Для разруливания этого в JVM были реализованы спин-локи (Сергей называл их thin-locks) -- мы просто заводим поле ownerThreadId, и, пытаясь захватить монитор, CAS(-1, threadId)-им туда свой threadId. Если CAS удался -- мы захватили монитор. Если нет -- мы делаем еще несколько попыток в цикле (а вдруг нынешний владелец отпустит монитор буквально через пару тактов?). Количество итераций это предмет тонкого тюнинга, возможно даже адаптивного, на базе профиля предыдущих попыток. Если даже со спиннингом мы не захватили монитор -- откатываемся к OS-specific locks (Сергей назвал их fat locks).

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

Как я уже говорил, привязанную блокировку можно рассматривать как продолжение спин-лока. Мы захватываем блокировку в собственность (привязываем ее) точно так же, CAS-ом записывая свой threadId. Только в отличие от спин-лока мы не отдаем ее назад. Вместо этого мы рядом заводим дополнительное поле, reetranceCount -- где будет 0, если реально мы сейчас блокировку не используем, и глубина захвата (для поддержания реентрабельности) в случае, если используем. Это поле thread-local, пишется-читается обычными store/load, безо всяких волшебных CAS и специальных мембаров.

Самое интересное здесь это процедура отзыва привязки -- если на привязанную блокировку пришел посторонний поток, и пытается ее взять. Необычно то, что не "владеющий" блокировкой поток ее отдает -- а "пришлый" поток ее "отбирает". Выглядит это так: пришлый смотрит поле типа блокировки -- видит там "biased", смотрит ownerID, и останавливает поток с таким ID (sic!). Остановив этот поток мы гарантируем себя от изменения состояния этого монитора -- ведь только поток-владелец может его изменить. (На самом деле здесь все не так просто. Нам нужно не просто остановить поток, но и вынудить его сбросить в память все свои store buffers -- чтобы убедиться, что он не находится в процессе обновления reentranceCount. Сделать это для другого потока -- довольно нетривиальная задача, для которой готовых решений разработчиками процессоров не предусмотрено. Приходится это делать через совершенно эзотерические, заточенные под конкретный процессор "хаки" -- некоторые действия, у которых основное назначение совсем другое, но побочный эффект которых -- на данной архитектуре -- сброс буферов. Краткий обзор этих хаков, встретившийся мне в статье, способен лишить вас сна на пару дней, и опустить ЧСВ ниже плинтуса) Гарантировав себе stop-the-world для отдельно взятого монитора мы теперь считываем reentranceCount (как я понял, здесь все так легко и просто только в случае архитектур с аппаратной когерентностью кэша -- как интеловские и AMD-шные). Если reentranceCount=0, значит поток-бывший-владелец сейчас монитор не использовал, и мы можем просто сменить тип монитора на thin (spin-lock), захватить его уже на себя, и разбудить назад бывшего владельца. Если же reentranceCount > 0 -- все серьезно, и мы вынуждены откатиться к fat (OS-specific) блокировкам.

Таким образом получается, что для biased locks начальный захват умеренно дорог (один CAS), дальнейший захват очень дешев ( обычный store), отзыв привязки очень дорог (требует syscall для остановки владельца, плюс несколько CAS-ов для смены типа блокировки и захвата под себя).

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

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

ReentrantLock vs synchronized

Загадочное поведение старых и новых локов в java (регулярно обнаруживаю паттерны, где ReentrantLock быстрее, и так же регулярно -- где выигрывает synchronized) -- наконец-то получило более-менее вменяемое объяснение. Сегодня, на Java One мне рассказали всю правду о том, как и какие локи устроены.

Вкратце, ответ на мой вопрос такой: при малом уровне contention выигрывает synchronized, при большом -- ReentrantLock. synchronized выигрывает за счет того, что для него работает "привязывание" (biased locking) -- для Reentrant такая оптимизация пока не реализована. Reentrant выигрывает за счет того, что для него (в non-fair режиме) реализовано "выхватывание" (bargain) блокировки, когда поток, подошедший на блокировку точно в момент, когда ее освободил другой поток, получит блокировку немедленно, в обход уже, может быть, целой очереди давно ждущих этой блокировки потоков. Это, хотя и "не честно", зато позволяет сэкономить на переключении контекстов потоков.

Никто, разумеется, не отменял бенчмарков в конкретном приложении...