9 янв. 2012 г.

java: cache padding

Думаю, что многие уже наслышаны о магии cache padding в disruptor'е.

Однако, куда более интересный факт - наличие cache padding'а уже в самом jdk 1.5 java.util.concurrent.Exchanger:
    /**
     * A Slot is an AtomicReference with heuristic padding to lessen
     * cache effects of this heavily CAS'ed location.  While the
     * padding adds noticeable space, all slots are created only on
     * demand, and there will be more than one of them only when it
     * would improve throughput more than enough to outweigh using
     * extra space.
     */
    private static final class Slot extends AtomicReference<Object> {
        // Improve likelihood of isolation on <= 64 byte cache lines
        long q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, qa, qb, qc, qd, qe;
    }

добавлено: Спасибо вопросу Артёма и последующей дискуссии Рустана - в продолжении темы Руслан задал этот вопрос в concurrency interest, где участвовал и Doug Lea.

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

6 комментариев:

Artem Danilov комментирует...

Володь, а зачем слот размером в 128 байт, если он предназначен только для "<= 64 byte cache lines"? Я так понимаю, чтобы объект в итогде занимал как минимум 2 линии. Вот только для чего я как-то сходу понять не могу.

Еще заинтересовал метод java.util.concurrent.Exchanger#createSlot, который исползует "double-checked lazy construction". Но в отличие от классического подхода описанного в эффективной джаве Блоха, тут создание объект выноситься из synchronized блока со словами "Create slot outside of lock to narrow sync region". Бенефит такого финта для меня тоже не очеведен при контеншене.

Vladimir Dolzhenko комментирует...

@Artem

ко второму вопросу:
запись элемента массива, даже если массив volatile не пробивает барьер.
Соотвественно, чтобы она стала видна в другой нитке надо пробить барьер.
В случае, когда элемент создан на одной нитке, вторая всё равно его не увидит, потому, как не пройдёт второго ребра барьера - и она попытается сделать слот заново, и вот тут она как раз пройдёт через второе ребро, и увидит. Минус такого подхода - что будет создан мусор, но за счёт меньшего время захвата монитора.

Artem Danilov комментирует...

Зачем там synchronized я понимаю. Я не понимаю зачем сужать время завхвата монитора. Опять же я понимаю в общем случае для чего такая техника испольдзуется, но в этом конкртеном случае мне не очевидно, что это дасть бенефит рассматривая суммарное время проведенное всеми потоками в методе createSlot при контеншене на мониторе. А без контеншена дак точно только увеличит.

BegemoT комментирует...

Зачем там уменьшать время проведенное в synchronized вроде как раз понятно -- автор не хочет, чтобы монитор надувался до OS-level lock. Время, проведенное внутри конструктора -- величина неопределенная. Может быть, запрос на память будет удовлетворен из thread-local allocation buffer, тогда это быстро -- а может, придется запрашивать очередной блок из глобального буфера, тогда это очередная блокировка, и хз сколько времени. Таким образом, вероятность столкновения на мониторе внутри createSlot становится весьма приличной, а такое столкновение -- это (надолго, если не навсегда) надувшийся монитор. И теперь каждый раз при заходе в createSlot() мы будем бегать в kernel mode.

С другой стороны, вынося аллокацию из охраняемой секции мы получаем, что охраняемый блок состоит из каких-то двух инструкций -- test & store. Вероятность столкновения здесь практически 0, соответственно, монитор будет оставаться в thin mode, и будет очень дешевым -- 2 CAS-а всего. Соответственно, весь код получается гораздо более предсказуемым (в плане времени выполнения)

Цена этого решения -- ненулевая вероятность создания "лишнего" слота. Автор, видимо, посчитал, что оно того стоит, и я его понимаю -- расширение арены по логике кода происходит весьма нечасто, поэтому сколько-либо заметной нагрузки на memory allocation/GC этот код не создаст.

А вот насчет 128 байтного пэддинга я пока сам не очень понимаю. Не однажды уже его видел, так что это явно не случайность. Один из вариантов состоит в том, что, хоть там и написано "для кэш-строк в 64 байта", но тестируют они свой код на каких-нибудь многоядреных ядерных Sun серверах, где реально строка в 128 байт. И чтобы получать там вменяемые результаты -- делают пэддинг побольше. Второй вариант состоит в том, что я чего-то пока не понимаю :) У меня запланирован один эксперимент на ближайшее время --может, прояснит ситуацию

Vladimir Dolzhenko комментирует...

тот же финт содержит и com.lmax.disruptor.Sequence, что наверняка не просто так, однако - если посмотреть на com.lmax.disruptor.util.PaddedAtomicLong, то никакого двойного cache padding'а.

BegemoT комментирует...

Не, ты не путай. В Sequence -- двусторонний пэддинг в 64 байта: [pad] value [pad]. Зачем такой пэддинг нужен как раз вполне понятно -- я объяснял эту тему здесь. А вот зачем нужен односторонний пэддинг в 2 кэш-строки -- мне пока непонятно. Сегодняшний эксперимент никакой магии не обнаружил