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 на этой же основе.