Lock-free структуры данных. Диссекция очереди


    Со времени предыдущего поста из жизни lock-free контейнеров прошло немало времени. Я рассчитывал быстро написать продолжение трактата об очередях, но вышла заминка: о чем писать, я знал, но реализации на C++ этих подходов у меня не было. «Не годится писать о том, что сам не попробовал», — подумал я, и в результате я попытался реализовать в libcds новые алгоритмы очередей.
    Сейчас настал момент, когда я могу аргументированно продолжить свой цикл. В данной статье закончим с очередями.

    Кратко напомню, на чем я остановился. Были рассмотрены несколько интересных алгоритмов lock-free очередей, а под занавес приведены результаты их работы на некоторых синтетических тестах. Главный вывод — всё плохо! Надежды на то, что lock-free подход на магическом compare-and-swap (CAS) даст нам пусть не линейный, но хотя бы какой-то рост производительности с увеличением числа потоков, не оправдались. Очереди не масштабируются. В чем причина?..

    Ответ на этот вопрос лежит в особенностях архитектуры современных процессоров. Примитив CAS – довольно тяжелая инструкция, сильно нагружающая кеш и внутренний протокол синхронизации. При активном использовании CAS над одной и той же линией кеша процессор занят в основном поддержкой когерентности кешей, о чем подробнее профессор Paul McKenney с моей помощью уже писал.

    Стеки и очереди — очень недружественные для lock-free подхода структуры данных, так как они имеют небольшое число точек входа. Для стека такая точка только одна — вершина стека, для очереди их две — голова и хвост. CAS конкурирует за доступ к этим точкам, при этом проседает производительность при 100% загрузке процессора, — все потоки чем-то заняты, но только один выиграет и получит доступ к голове/хвосту. Ничего не напоминает?.. Это же классический spin-lock! Получается, при lock-free подходе на CASах мы избавились от внешней синхронизации мьютексом, но получили внутреннюю, на уровне инструкции процессора, и мало что выиграли.
    Ограниченные очереди
    Следует отметить, что все вышесказанное относится к неограниченным (unbounded) MPMC (multiple producer/multiple consumer) очередям. В ограниченных (bounded) по числу элементов очередях, которые строятся, как правило, на основе массива, данная проблема может быть не так ярко выражена за счет аккуратного рассредоточения (разброса) элементов очереди по массиву. Также более быстрые алгоритмы могут быть построены для очередей с одним писателем или/и одним читателем.


    Проблема эффективной реализации конкурентных очередей интересует исследователей до сих пор. В последние годы усилилось понимание того, что различного рода ухищрения при реализации lock-free очереди «в лоб» не дают ожидаемого результата и следует придумать какие-то другие подходы. Далее мы рассмотрим некоторые из них.

    Flat combining


    Этот метод я уже описывал в статье о стеке, но flat combining является универсальным методом, поэтому применим и к очереди. Отсылаю читателей к видеозаписи моей презентации на C++ User Group, Russia, посвященной как раз реализации flat combining.
    На правах рекламы
    Пользуясь случаем, хочу послать лучи поддержки sermp — вдохновителю и организатору C++ User Group, Russia. Сергей, твой бескорыстный труд на этом поприще бесценен!
    Читателей призываю обратить внимание на данное мероприятие и поддержать его своей явкой, а также, кому есть чем поделиться, презентациями. На своем опыте убедился, что живое общение намного круче, чем даже чтение хабра.
    Также обращаю ваше внимание на грядущую конференцию C++Russia 27-28 февраля 2015 в Москве, — приходите!


    Массив очередей



    Подход, лежащий на поверхности, но тем не менее довольно трудный для реализации, со множеством подводных камней, предложен в 2013 году в статье под названием «Замена конкуренции на сотрудничество для реализации масштабируемой lock-free очереди», как нельзя лучше подходящим к теме данного поста.
    Идея очень проста. Вместо одной очереди строится массив размером K, каждый элемент которого — lock-free очередь, представленная односвязным списком. Новый элемент добавляется в следующий (по модулю K) слот массива. Тем самым нивелируется толчея на хвосте очереди, — вместо одного хвоста мы имеем K хвостов, так что можно ожидать, что мы получим линейную масштабируемость вплоть до K параллельных потоков. Конечно, нам нужно иметь некий общий атомарный монотонно возрастающий счетчик push-операций, чтобы мультиплексировать каждую вставку в свой слот массива. Естественно, данный счетчик будет единой «точкой преткновения» для всех push-потоков. Но авторы утверждают (по моим наблюдениям, небезосновательно), что инструкция xadd атомарного добавления (в нашем случае — инкремента) на архитектуре x86 чуть быстрее, чем CAS. Таким образом, можно ожидать, что на x86 мы получим выигрыш. На других архитектурах атомарный fetch_add эмулируется CAS'ом, так что выигрыш будет не так заметен.
    Код удаления элемента из очереди аналогичен: имеется атомарный счетчик удаленных элементов (pop-счетчик), на основании которого по модулю K выбирается слот массива. Для исключения нарушения основного свойства очереди — FIFO – каждый элемент содержит дополнительную нагрузку (ticket) — значение push-счетчика на момент добавления элемента, фактически — порядковый номер элемента. При удалении в слоте ищется элемент с ticket = текущему значению pop-счетчика, найденный элемент и является результатом операции pop().
    Интересен способ, которым решается проблема удаления из пустой очереди. В данном алгоритме сначала идет атомарный инкремент счетчика удалений (pop-счетчика), а затем — поиск в соответствующем слоте. Вполне может быть, что слот пустой. Это значит, что пуста и вся очередь. Но ведь pop-счетчик уже инкрементирован, и дальнейшее его использование приведет к нарушению FIFO и даже к потере элементов. Делать откат (декремент) нельзя — вдруг в это же самое время другие потоки добавляют или удаляют элементы (вообще, «назад-отыграть-нельзя» является неотъемлемым свойством lock-free подхода). Поэтому при возникновении ситуации pop() из пустой очереди массив объявляется инвалидным, что приводит к созданию нового массива с новыми push- и pop-счетчиками при следующей вставке элемента.

    К сожалению, авторы не озаботились (как они пишут, по причине недостатка места) проблемой освобождения памяти, уделив ей лишь несколько предложений с поверхностным описанием применения схемы Hazard Pointer к своему алгоритму. Мне пока не удалось расшифровать их намеки, так что реализации этого интересного алгоритма в библиотеке libcds нет. К тому же алгоритм подвержен неограниченному накоплению удаленных элементов в случае, если очередь никогда не пуста, то есть если не происходит инвалидации массива, так как не предусматривается удаления элементов из списка-слота массива. pop() просто ищет элемент с текущим ticket'ом в соответствующем слоте, но физического исключения элемента из списка не происходит до инвалидации всего массива.

    Подытоживая, можно сказать: алгоритм интересный, но управление памятью не описано достаточно четко. Требуется дополнительное изучение.

    Сегментированные очереди


    Другой способ повысить масштабируемость очереди — нарушить её основное свойство first-in – first-out (FIFO). Так ли уж это страшно, зависит от задачи: для некоторых строгое соблюдение FIFO обязательно, для других — в некоторых пределах вполне допустимо.
    Конечно, нарушать основное свойство FIFO совсем уж кардинально не хочется, — в этом случае мы получим структуру данных, называемую пулом, в которой не соблюдается вообще никакого порядка: операция pop() возвращает любой элемент. Это уже не очередь. Для очереди с нарушением FIFO хотелось бы иметь какие-то гарантии этого нарушения, например: операция pop() возвратит один из первых K элементов. Для K=2 это значит, что для очереди с элементами A, B, C, D,… pop() возвратит A или B. Такие очереди называются сегментированными или K-сегментированными, чтобы подчеркнуть значение фактора K — ограничения на нарушение FIFO. Очевидно, что для строгой (fair) FIFO-очереди K=1.
    Насколько мне известно, впервые простейшая сегментированная очередь подробно рассмотрена в 2010 году в работе, посвященной как раз допустимым ослаблениям требований, накладываемых на lock-free структуры данных. Внутреннее строение очереди довольно просто (рисунок из вышеуказанной статьи, K=5):

    Очередь представляет собой односвязный список сегментов, каждый сегмент — это массив размером K элементов. Head и Tail указывают на первый и последний сегмент в списке соответственно. Операция push() вставляет новый элемент в произвольный свободный слот tail-сегмента, операция pop() извлекает элемент из произвольного занятого слота head-сегмента. При таком подходе очевидно, что чем меньше размер K сегмента, тем менее нарушается свойство FIFO; при K=1 мы получим строгую очередь. Таким образом, варьируя K, мы можем управлять степенью нарушения FIFO.
    В описываемом алгоритме каждый слот сегмента может быть в одном из трех состояний: свободный, занят (содержит элемент) и «мусор» (элемент был прочитан из слота). Заметим, что операция pop() переводит слот в состояние «мусор», которое не является эквивалентом состояния «свободный»: состояние «мусор» является конечным состоянием слота, запись значения в такой слот недопустима. В этом проявляется недостаток алгоритма — слот в состоянии «мусор» нельзя повторно использовать, что приводит к распределению новых сегментов даже в такой типичной для очереди последовательности операций, как чередующийся push() / pop(). Этот недостаток был исправлен в другой работе ценой значительного усложнения кода.

    Исследуем


    Итак, в libcds появились реализации двух новых алгоритмов для очередей — FCQueue и SegmentedQueue. Посмотрим их перформанс и попробуем понять, стоило ли ими заниматься.
    К сожалению, сервер, на котором я гонял тесты для предыдущей статьи, был загружен другими задачами, а впоследствии рухнул. Пришлось прогонять тесты на другом сервере, менее мощном — 2 x 12 core AMD Opteron 1.5ГГц c 64G памяти под управлением Linux, который был практически свободен — idle на уровне 95%.

    Я изменил визуализацию результатов — вместо времени выполнения теста по оси Y я теперь откладываю количество мегаопераций в секунду (Mop/s). Напомню, что тест – классический producer/consumer: всего 20 миллионов операций — 10M push и 10M pop без всякой эмуляции payload, то есть тупая долбежка в очередь. Во всех тестах lock-free очередей используется Hazard Pointer для безопасного освобождения памяти.

    Старые данные в новых попугаях
    График из предыдущей статьи в новых попугаях — MOp/s, выглядит так



    Сначала — лирическое отступление: к чему мы стремимся? Что мы хотим получить, говоря о масштабируемости?

    Идеальное масштабирование — линейное увеличение Mop/s при увеличении числа потоков, если железо физически поддерживает такое количество потоков. Реально хорошим результатом будет какое-то увеличение Mop/s, более похожее на логарифмическое. Если при увеличении числа потоков мы получаем проседание производительности, то алгоритм является немасштабируемым, или масштабируемым до некоторых пределов.

    Результаты для интрузивных очередей (напомню, интрузивный контейнер характеризуется тем, что он содержит указатель на сами данные, а не их копию, как в STL; тем самым не требуется распределять память под копию элементов, что в мире lock-free считается моветоном).

    Видно, что Flat Combining реализован не напрасно, — эта техника показывает очень хороший результат на фоне других алгоритмов. Да, увеличения производительности она не дает, но и существенного проседания не видно. Более того, существенным бонусом является то, что она практически не нагружает процессор, — всегда работает только одно ядро. Остальные алгоритмы показывают 100% загрузку ЦП при большом числе потоков.
    Сегментированная очередь показывает себя аутсайдером. Быть может, это связано со спецификой реализованного алгоритма: распределение памяти под сегменты (в данном тесте размер сегмента равен 16), невозможность повторно использовать слоты сегмента, что приводит к постоянным аллокациям, реализация списка сегментов на основе boost::intrusive::slist под блокировкой (я пробовал два типа блокировок — spin-lock и std::mutex; результаты практически не отличаются).
    Была у меня надежда, что основным тормозом является false sharing. В реализации сегментированной очереди сегмент представлял собой массив указателей на элементы. При размере сегмента равным 16 сегмент занимает 16 * 8 = 128 байт, то есть две линии кеша. При постоянной толкотне потоков на первом и последнем сегментах false sharing может проявить себя в полный рост. Поэтому я ввел дополнительную опцию в алгоритм — требуемый padding. При указании padding = размеру кеш-линии (64 байт) размер сегмента увеличивается до 16 * 64 = 1024 байт, но таким образом мы исключаем false sharing. К сожалению, оказалось, что padding практически никак не влияет на производительность SegmentedQueue. Быть может, причина этого в том, что алгоритм поиска ячейки сегмента является вероятностным, что приводит к многим неудачным попыткам чтения занятых ячеек, то есть опять-таки к false sharing. Или же false sharing вовсе не является основным тормозом для данного алгоритма и надо искать истинную причину.

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

    Для STL-like очередей, с созданием копии элемента, имеем похожую картину:


    Наконец, просто ради интереса приведу результат bounded queue – алгоритм Дмитрия Вьюкова на основе массива, интрузивная реализация:

    При числе потоков = 2 (один читатель и один писатель) эта очередь показывает 32 MOp/s, что не уместилось на графике. При увеличении числа потоков также наблюдаем деградацию производительности. В качестве оправдания можно отметить, что для очереди Вьюкова false sharing также может быть очень существенным тормозящим фактором, но опции, включающей padding по кеш-линии, для неё ещё нет в libcds.

    для любителей странного
    Попался мне и необычный Linux-сервер на IBM Power8 — два процессора 3.42 ГГц по десять ядер в каждом, каждое ядро может одновременно выполнять до 8 инструкций одновременно, итого 160 логических процессоров. Вот результаты тех же самых тестов на нем.
    Интрузивные очереди:

    STL-like очереди:

    Как видно, принципиальных изменений не наблюдается. Хотя нет, одно есть — показаны результаты для сегментированной очереди при размере сегмента K=256 — именно это K было для данного сервера близко к наилучшему.


    В заключение хочу отметить одно интересное наблюдение. В вышеприведенных тестах для читателей и писателей нет никакой полезной нагрузки (payload), наша цель — просто запихнуть в очередь и прочитать из неё. В реальных задачах какая-то нагрузка всегда есть, — мы что-то делаем с данными, прочитанными из очереди, а перед тем, как поместить в очередь, мы данные готовим. Казалось бы, payload должен приводить к проседанию производительности, но практика показывает, что это далеко не всегда так. Я не раз наблюдал, что payload приводит к существенному росту попугаев MOp/s. Причина, как мне кажется, — разгрузка внутреннего протокола синхронизации кеша, см. ещё раз статью P.McKenney. Вывод напрашивается такой: тестировать надо на реальных задачах.


    В этой статье я коснулся малой части работ, посвященных очередям, и только динамическим (unbounded), то есть без ограничения количества элементов. Как я уже говорил, очередь — одна из излюбленных структур данных для исследователей, видимо, потому, что плохо поддается масштабированию. За бортом обзора осталось множество других работ, — об ограниченных (bounded) очередях, work-stealing очередях, применяемых в планировщиках задач, single consumer или single producer очередях — алгоритмы таких очередей существенно заточены на одного писателя или читателя, а потому зачастую проще и/или намного производительнее, — и т.д. и т.п.
    Новости из микромира libcds
    За прошедшее с предыдущей статьи время была выпущена версия 1.6.0 библиотеки, в которой помимо реализации техники Flat Combining и SegmentedQueue пофикшено какое-то количество ошибок, существенно переработан SkipList и EllenBinTree.
    Репозиторий для грядущей версии 2.0 переехал на github, а сама версия 2.0 посвящена переходу на стандарт C++11, причесыванию кода, унификации интерфейсов, из-за чего нарушится пресловутая обратная совместимость (что означает, что некоторые сущности будут переименованы), и удалению костылей поддержки старых компиляторов (ну и, как водится, исправлению найденных и генерации новых багов).

    Я рад, что мне удалось-таки, несмотря на большой временной лаг, довести повествование об очередях и стеках до логического конца, ибо это не самые дружественные для lock-free подхода и современных процессоров структуры данных, да и не очень для меня интересные.
    Впереди нас ждут куда более увлекательные структуры — ассоциативные контейнеры (set/map), в частности, hash map, с красивыми алгоритмами и, надеюсь, более благодарные в плане масштабируемости.
    Продолжение, думаю, воспоследует…

    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 16

      +4
      Было бы здорово добавить padding в очередь Димы Вьюкова и сравнить с Flat Combining Queue.
      На счет меньшего проседания есть нюансы. Несомненно, судя по результатам мы видим что пропускная способность (throughput) снижается значительно медленней, но, из-за того что у нас теперь остальные потоки занимаются пассивным ожиданием, у них появляется дополнительный latency на ожидание.
      При использовании spin-loop с CASами и добавлении полезной нагрузки можно получить меньший latency с сохранением уровня throughput. Так что тестируйте свои конкретные случаи. Flat Combining может работать медленней несмотря на результаты этих экспериментов.

      Огромное спасибо за цикл статей, продолжайте в том же духе!
        0
        Полностью согласен. И спасибо за «огромное спасибо» :-)
        Все о чем Вы пишете, правильно и относится к тонкой настройке алгоритма под конкретную задачу и даже под конкретное железо. Именно поэтому я не очень доверяю попугаям, в смысле, результатам тестирования, и отношусь к ним с известной долей скепсиса. В том числе и к своим замерам. И всех призываю именно так к ним и относится.
        С другой стороны, надо как-то оценить алгоритм, и ничего лучше абстрактных синтетических тестов не придумаешь, когда нет конкретной задачи.
        Насчет Flat Combining. Если заглянете ему под капот в libcds, Вы с негодованием удивлением обнаружите, что там для ожидающих потоков по умолчанию стоит back-off стратегия sleep(2ms). «Какой грязный хак!», — скажет искушенный читатель, и будет прав. Но именно этот sleep(2) обеспечил взлет перформанса Flat Combining по сравнению со spin-loop.
          0
          Ну во первых не «взлет», а более «плавное пикирование» и то, пикирование пропускной способности. Латентность при этом только растёт:)
          На деле нет никакого взлёта перфоманса, просто выбрали один из вариантов trade-off'а:)
            0
            На моих тестах именно взлет, см. презентацию, там даны результаты как со spinlock, так и со sleep(2). Вполне допускаю, что для других задач результат может быть прямо противоположный.
            Плюсы sleep(2):
            — загрузка только одного ядра;
            — больше вероятность провести аннигиляцию пар push()/pop() на пустой очереди (если elimination включена).
              0
              Но есть минусы. Например, в случае если поток пытался сделать операцию с очередью, но у него не удалость стать «комбайном», то latency его операции может возрасти до 2ms. Если таких операций много, то и суммарное время будет большое. Более того, нить простаивает и не выполняет другую полезную работу.

              И еще, допустим у меня есть поток, который так же что-то хочет сделать с очередью, и у него «получилось стать комбайном». И для того чтобы выйти из кода работы с очередью, мы должны выполнить пачку заданий, которые успели скопиться. Даже если изначальная задача была очень простой, итоговый latency может быть бОльшим нежели мы ожидаем.

              Как в случае становления комбайном, так и в случае пассивного ожидания проблемы с latency могут быть серьезными.

              На самом деле с такой back-off стратегией любая очередь не должна деградировать по throughput с ростом числа нитей.
              Так что совсем не могу сказать что это очередь в чем-то лучше остальных по этим тестам. Хорошо бы сравнить очереди на одинаковых стратегиях back-off'а.
                0
                И опять я полностью согласен! Найти оптимальную грань между задержками и пропускной способностью всегда не просто.

                Flat Combining мне нравится именно тем, что там все перевернуто с ног на голову: вместо параллельного выполнения — откровенное делегирование своей работы другому потоку. Честно говоря, я не верил, что это может что-нибудь дать, — это диссонировало с моими взглядами. Но практика показала, что для некоторых задач метод может быть очень даже неплох. Видимо, мои тесты и относятся к этим задачам.
                  0
                  Хорошо бы сравнить очереди на одинаковых стратегиях back-off'а.

                  Действительно, хорошо бы. Займетесь?..
                  Никакой иронии, — я сам больше доверяю своим тестам, нежели чужим.
          +1
          Спасибо за увлекательную статью.
            0
            Планируется ли враппер или порт на C для библиотеки libcds?
              +2
              Мной — нет, Боже упаси!
              Прошу воспринимать эту фразу как мое личное предпочтение
                +2
                Подумав немного, я даже не представляю, как на C сделать враппер над template-классом с, фактически, десятком template-параметров, каждый из которых может принимать несколько значений, в том числе user-defined, и все это — в compile time.
                +1
                Добрый день!

                Читаю вашу серию с самого начала, пока дошел до RCU, очень много полезной информации, чтобы усвоить ее нужно время. Спасибо за Ваш труд!

                Попутно возник вопрос, а что Вы думаете про Thread Building Blocks от Intel? На первый взгляд выглядит замечательно просто.
                  +1
                  День добрый!
                  Спасибо за отзыв, рад, что инфа оказалась полезна.
                  Про ThreadBuildingBlocks (TBB). Эта либа, безусловно, заслуживает внимания. В свое время она для меня была одним из источников информации о внутреннем устройстве atomic, когда C++11 ещё не было, а atomic только обсуждался. [далее мое ИМХО, я в TBB давно не заглядывал] А также она была для меня примером, как не надо делать конкурентные контейнеры. Дело в том, что в TBB довольно многие методы помечены как not thread safe. Что толку в контейнере, половина основных методов которого not thread safe?.. Разработчиков TBB можно понять — они стремятся сделать интерфейс как в STL. Но многие вещи из STL не могут быть сделаны в конкурентном контейнере.
                  Интересно, что только вчера наткнулся на Boost GSoC-2015: одно из заданий — concurrent map. И там написано (выделено мною):
                  Strangely enough, Boost does not provide an implementation of thread safe concurrent associative sets and maps despite that the unordered implementation from Intel's Thread Building Blocks and Microsoft's Parallel Patterns Library was proposed some years ago for standardisation in N3425 Concurrent Unordered Associative Containers for C++. This is probably because that implementation (the split ordered list algorithm by Shalev and Shavit, 2006) had the serious shortcoming of not being thread safe for some operations, most importantly item deletion, and the workarounds proposed by N3425 did not appeal. Moreover, there are other concurrent hash table algorithms which do not have such shortcomings
                  Хм… Конкурентный map с небезопасной функцией удаления элементов — это конкурентный map?.. Для безопасного удаления требуется применять HazardPointer, user-space RCU, transactional memory или что-то подобное, а в TBB, судя по этой ремарке, ничего этого нет…
                  В общем, у нас с TBB разные цели :-) TBB хочет адаптировать конкурентные контейнеры под STL, я в libcds хочу сделать конкурентный контейнер только с теми методами, которые можно поддержать в multithreading окружении, и посмотреть, достаточно ли будет такого интерфейса для повседневных задач.
                    +1
                    Но в TBB есть и concurrent_hash_map, где erase потокобезопасен.
                      +1
                      Действительно, есть.
                      Почему же тогда boost предлагает для GSoC-2015 задачу concurrent map? Думаю, причина в том, что concurrent_hash_map в TBB основан на fine-grained RW-locks. Беглый взгляд на реализацию показывает, что блокировка ведется на уровне buckets, похоже.
                      Это не критика TBB, ни в коем случае. Fine-grained lock алгоритмы не менее полезны, чем lock-free, и не менее интересны. Надо будет разобраться с внутренним устройством TBB concurrent_hash_map.
                      0
                      Спасибо за развернутый ответ! Очень интересная информация! На самом деле долго думал — неужели нету надежной реализации такой популярной и очень полезное структуры как map.Получается, аналогов CDS толком-то и нету. Обязательно попробую вашу библиотеку для своего проекта.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое