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

Конкурентность сложно как следует наладить, как минимум, тем из нас, кому не повезло писать на языках, непосредственно открывающих нутро конкурентного аппаратного обеспечения: речь о потоках и разделяемой памяти. Не менее сложно организовать конкурентность так, чтобы она работала и правильно, и быстро. Все, что вы знаете об оптимизации однопоточного кода, зачастую вам не поможет. На микроуровне (отдельные инструкции) просто невозможно применить обычные правила, актуальные для μ-операций, цепочек зависимостей, пределов пропускной способности и т.д. При конкурентности правила другие.

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

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

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

"Реалистичный" пример

Не хочу, чтобы этот пост получился совершенно абстрактным, поэтому давайте подробно разберем реалистичный (если не придираться¹) пример: как безопасно увеличивать на единицу за единицей счетчик целых чисел, охватывающий много потоков. Под «безопасностью» я понимаю «не терять инкрементов, не брать значения с потолка, не прожаривать RAM и не проделывать заметных дырок в пространстве-времени».

Источник и результаты

Источники ко всем бенчмаркам доступны здесь, поэтому вы можете проследить их и даже воспроизвести, либо прогнать эти бенчмарки на вашем собственном оборудовании. Все результаты, обсуждаемые здесь (и не только) доступны в том же репозитории, а ко всем графикам я приведу ссылки вида [data table], по которым можно перейти к конкретному подмножеству, использованному для построения графика.

Аппаратное обеспечение

Все данные по производительности предоставлены для нескольких аппаратных платформ: Intel Skylake, Ice Lake, Amazon Graviton и Graviton 2. Но, если я явно не упоминаю иной платформы, по умолчанию этот текст относится к результатам, полученным на Skylake. Хотя, конкретные числа могут отличаться, большинство количественных соотношений сохраняются и на другом оборудовании, но не всегда. Отличается не только аппаратное обеспечение, но и операционные системы, и библиотечные реализации.

Эта статья практически неизбежно скатится в сравнение разных аппаратных платформ («ого, Graviton 2 определенно выносит Graviton 1 в одну калитку»), но я ставлю перед собой иную цель. Описанные здесь контрольные точки призваны, в первую очередь, распутать разноуровневые характеристики, а не расхваливать достоинства оборудования.

Ниже вашему вниманию предлагаются подробности об используемом аппаратном обеспечении:

Уровень 2: Конфликты на уровне атомарных операций

Вы ожидаете, пожалуй, что знакомить вас с этой иерархией я начну «от быстрого к медленному» или наоборот, но здесь я собираюсь раз за разом обманывать ожидания – поэтому начнем анализ с середины и двинемся в стороны, к краям. Положим, что (с округлением) середина находится на уровне 2 – давайте прямо туда и перепрыгнем.

Простейший способ безопасно модифицировать любой разделяемый объект – воспользоваться блокировкой. Такой подход обычно просто работает с объектами любого типа, безотносительно структуры объекта или природы вносимых модификаций. Почти любой мейнстримовый CPU, выпущенный в последние 30 лет, предоставляет для пользовательского пространства те или иные инструкции блокировки³.

Итак, в нашей исходной реализации инкремента будет использоваться простой мьютекс типа T, защищающий обычную целочисленную переменную:

T lock;
uint64_t counter;

void bench(size_t iters) {
    while (iters--) {
        std::lock_guard<T> holder(lock);
        counter++;
    }
}

Эту реализацию назовем «мьютексное сложение», и на моей машине 4 CPU Skylake-S i7-6700HQ, воспользовавшись базовым std::mutex, получу следующие результаты при количестве потоков от 2 до 4:

Указанное значение является медианным для всех испытаний, а вертикальные черные линии ошибок над каждой планкой обозначают интердецильный размах, т.e., значения, соответствующие 10-й до 90-й перцентили. Там, где значения ошибок не проявляются, это значит, что нет никакой разницы между значениями p10 и p90, как минимум, в пределах рассматриваемого разрешения (100 пикосекунд).

Таким образом, базовая отметка, с которой начинает давать заметные издержки конфликт двух потоков, пытающихся изменить защищенное блокировкой целое число, составляет примерно 125 наносекунд. С увеличением количества потоков это значение немного возрастает.

Уже слышу ропот: Если вы просто изменяете единственное 64-разрядное целое число, просто пропустите блокировку и напрямую используйте атомарные операции, поддерживаемые в большинстве ISA!

Конечно же, давайте добавим пару вариантов такой операции. Ее просто сделать с шаблоном std::atomic<T>: в него можно обернуть любой тип, удовлетворяющий некоторым базовым требованиям, а затем выполнять над ним атомарные манипуляции. Проще всего было бы воспользоваться std::atomic<uint64>::operator++()⁴, и это даст нам атомарное сложение

std::atomic<uint64_t> atomic_counter{};

void atomic_add(size_t iters) {
    while (iters--) {
        atomic_counter++;
    }
}

Другой распространенный подход предполагает использование сравнения с обменом (CAS) вот так: загрузить имеющееся значение, прибавить единицу, а затем сравнить и заменить обратно, если значение не изменилось. Если же оно изменилось, то операция инкремента вступит в гонку с другим потоком, и мы попробуем еще раз.

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

(Посмотрите, например, что делает с атомарным инкрементом даже новейшая версия icc, и что в таком случае годами делалось в Java⁶). Правда, эта засада не встретилась мне ни на одной из протестированных платформ

Давайте добавим реализацию счетчика, использующую CAS как описано выше, назовем ее cas add:

std::atomic<uint64_t> cas_counter;

void cas_add(size_t iters) {
    while (iters--) {
        uint64_t v = cas_counter.load();
        while (!cas_counter.compare_exchange_weak(v, v + 1))
            ;
    }
}

Вот как она выглядит в сравнении с уже имеющимся у нас бенчмарком std::mutex:

Первый вывод, который можно сделать – что, как минимум, при таком бенчмарке, рассчитанном на нереалистичный максимальный конфликт, работа с атомарным сложением (lock xadd на атомарном уровне) значительно лучше CAS. Второй вывод в том, что std::mutex, оказывается, не так и плохо выглядит на Skylake. Он лишь немного уступает CAS-подходу на 2 ядрах и бьет его при 3 и 4 ядрах. Этот подход медленнее, чем с атомарным инкрементом, но менее, чем в три раза. Поэтому представляется, что он масштабируется в верном направлении.

Все эти операции в нашей иерархии относятся к уровню 2. Основная характеристика уровня 2 заключается в том, что эти операции используют конфликтный доступ к разделяемой переменной. Таким образом, как минимум, та строка, что содержит данные, должна быть вынесена и передана кэширующему агенту, который управляет согласованностью⁷, после чего ее резервная копия будет сделана на ядре, которое затем завладеет этим кодом

На одну только эту операцию потребуется около 70 циклов⁸.

Может ли получиться еще медленнее? Даже не сомневайтесь. Гораздо медленнее.

Уровень 3. Системные вызовы

Следующий уровень на пути вверх («вверх» в данном случае – не лучший термин…) - уровень 3. Ключевая характеристика реализаций на данном уровне заключается в том, что в этих реализациях почти при каждой операции выполняется системный вызов.

Легко писать конкурентные примитивы, которые выполняли бы системный вызов безусловно (напр., сделать такую блокировку, которая всегда пыталась бы разбудить ожидающих при помощи вызова futex(2), даже если никаких ожидающих нет), но такие примитивы мы здесь рассматривать не будем. Лучше присмотримся к случаю, в котором прокладывается быстрый путь, именно ради того, чтобы не пришлось делать системный вызов – но сам дизайн или способ использования программы подразумевают, что такой вызов обычно все равно происходит.

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

Звучит неплохо, так? Иногда – действительно, но, как мы еще увидим, такой подход может серьезно сказываться на производительности.

В нашем распоряжении есть три разнотипных честных блокировки.

Первая – это спин-очередь (ticket lock) с переменной sched_yield в цикле ожидания. Идея yield в том, чтобы предоставить время на выполнение другим потокам, которые могут удерживать блокировку. Такой подход с yield() публично порицается многими экспертами по конкурентности⁹, которые, однако, невозмутимо пользуются им на практике, как только он им понадобится

Можем назвать этот подход «уступкой по очереди», и выглядит он примерно так:

/**
 * Спин-очередь, использующая sched_yield() во время ожидания
 * чтобы очередной «номер» мог быть обслужен
 */
class ticket_yield {
    std::atomic<size_t> dispenser{}, serving{};

public:
    void lock() {
        auto ticket = dispenser.fetch_add(1, std::memory_order_relaxed);

        while (ticket != serving.load(std::memory_order_acquire))
            sched_yield();
    }

    void unlock() {
        serving.store(serving.load() + 1, std::memory_order_release);
    }
};

Отобразим на графике результаты для этой блокировки в сравнении с другими имеющимися подходами:

Так визуализируется уровень 3: работа здесь идет на порядок медленнее, чем при подходах, действующих на уровне 2. Замедление связано с вызовом sched_yield: это системный вызов, а на выполнение таких вызовов обычно требуются сотни наносекунд¹⁰ – что видно из результатов.

Такая блокировка действительно может пойти быстрым путем в случае, когда sched_yield не вызывается: если блокировка доступна, то спин-очередь не возникает, иsched_yield никогда не вызывается. Но, поскольку в этом тесте мы имеем дело с честной блокировкой, которая сочетается с острым конфликтом за ресурсы, у нас быстро формируется очередь на блокировку (подробнее опишем этот феномен ниже). Поэтому, в принципе, мы заходим в спин-очередь всякий раз при вызове lock().

Итак, сейчас-то мы полностью забурились в глубины конструкций, обеспечивающих медленную конкурентность? Ничего подобного. Сейчас мы только подошли к переправе через Стикс.

Еще раз о std::mutex

Прежде, чем двигаться далее, давайте быстро освежим в памяти реализацию std::mutex, которая обсуждалась на уровне 2 – в свете нашего определения уровня 3, согласно которому на этом уровне требуется системный вызов. Разве std::mutex также не делает системных вызовов? Если поток пытается заблокировать объект std::mutex, который уже заблокирован, то мы рассчитываем, что такое блокирование будет осуществляться при помощи примитивов, предоставляемых ОС. Так почему же это не делается на уровне 3 и медленно, как при вытеснении по очереди?

Основная причина – в том, что на практике делается мало системных вызовов. Сочетая нечестность и циклические попытки получить блокировку, я получаю всего лишь около 0,18 системных вызовов на инкремент, когда у меня на Skylake работают три потока. Таким образом, большинство инкрементов происходит без системного вызова. С другой стороны, при вытеснении по очереди производится примерно 2,4 системных вызова на инкремент, то есть, на порядок с лишним больше, соответственно, наблюдается вот такое снижение производительности.

Об этом поговорили, посмотрим, что может пойти еще медленнее.

Уровень 4: подразумеваемое переключение контекста

Следующий уровень, на котором реализация может спровоцировать значительное количество конкурентных операций – это переключение контекста.

Такая уступка блокировки не приводит к значительному количеству переключений контекста, поскольку задействованных потоков меньше, чем ядер, соответственно, потому, что отсутствует другой процесс, который нужно срочно выполнить (разве что какой-нибудь случайный фоновый процесс). Следовательно, актуальный поток остается в CPU, когда мы вызываем sched_yield. При этом сжигается много процессорного времени.

Как рекомендуют эксперты, всякий раз, когда предлагается пойти на уступку в цикле ожидания, лучше попробовать запирание (blocking lock).

Запирания

Конкурентность может быть организована так, чтобы ресурсы расходовались экономнее, и работа тогда обычно тоже идет лучше – если использовать запирание.

При таких блокировках не практикуется активное ожидание (busy waiting), а операционная система получает команду усыпить поток, пока не появится свободная блокировка. В Linux предпочтительный системный вызов для этой цели называется futex(3), тогда как в Windows для этого используется семейство API WaitFor*Object. Поверх интерфейсов ОС находятся такие вещи как std::condition_variable из С++; это универсальный механизм, позволяющий дожидаться, пока не выполнится какое-либо произвольное условие.

Наше первое запирание, опять же, основано на спин-очереди, с той вариацией, что на этот раз блокировка выполняется при помощи условной переменной, как только обнаруживается, что поток – не первый в очереди на обслуживание (то есть, что сейчас блокировку удерживает другой поток. Назовем такой случай «спин-блокировкой» (ticket blocking), и вот как она будет выглядеть:

void blocking_ticket::lock() {
    auto ticket = dispenser.fetch_add(1, std::memory_order_relaxed);

    if (ticket == serving.load(std::memory_order_acquire))
        return; // бесконфликтный случай 

    std::unique_lock<std::mutex> lock(mutex);
    while (ticket != serving.load(std::memory_order_acquire)) {
        cvar.wait(lock);
    }
}

void blocking_ticket::unlock() {
    std::unique_lock<std::mutex> lock(mutex);
    auto s = serving.load(std::memory_order_relaxed) + 1;
    serving.store(s, std::memory_order_release);
    auto d = dispenser.load(std::memory_order_relaxed);
    assert(s <= d);
    if (s < d) {
        // разбудить всех ждущих
        cvar.notify_all();
    }
}

Основное отличие от реализации, рассмотренной ранее, возникает в случае, когда мы не приобретаем блокировку немедленно (то есть, не возвращаемся из точки, помеченной комментарием // бесконфликтный случай). Вместо уступки в цикле берем мьютекс, ассоциированный с условной переменной – и ждем, пока не получим уведомление. Всякий раз, когда такое уведомление приходит, мы проверяем, не пришла ли наша очередь на обслуживание.

Даже без таких подозрительных побудок наш поток может оказаться неоднократно разбужен, так как такая блокировка подвержена проблеме громоподобного стада  (thundering herd problem), где абсолютно все ожидающие просыпаются при unlock(), хотя, в конечном итоге только один из них сможет получить блокировку.

Опробуем и второй вариант организации, которому не свойственна проблема громоподобного стада. Это очередь блокировок, где каждая блокировка ожидает на собственном частном узле в ряду таких же ждущих, поэтому только один из них (только что заполучивший блокировку) пробуждается при разблокировке. Такая очередь называется FIFO (первым пришел – первым обслужен) и, если вас интересует ее реализация – она описана здесь.

Вот как наши новые блокировки справляются с делом на фоне уже имеющихся

Вероятно, вы уже улавливаете закономерность: производительность пробила очередное дно по сравнению с более ранними вариантами. Получилось примерно на порядок медленнее, чем при подходе с уступкой, который, в свою очередь, был медленнее более ранних подходов, превратившихся на схеме в бугорки высотой по несколько пикселей – по сравнению с последним графиком. Версия с очередью блокировок работает чуть лучше, если увеличить количество потоков (особенно на Graviton 2), что можно связать с отсутствием эффекта громоподобного стада, но все равно получается очень медленно, поскольку основная проблема здесь не в громоподобном стаде, а в блокировке конвоя.

Блокировка конвоя

Честные блокировки, в отличие от нечестных, могут сцепляться в долгоиграющие конвои, каждый из которых заблокирован всего в одной точке – как только конфликт за ресурсы достигнет некоторого предела¹¹:

11. Интересная черта таких конвоев заключается в том, что им присущ гистерезис: как только блокировки выстраиваются в конвой, он начинает самоподдерживаться, даже если устранить те условия, что привели к его возникновению. Представьте себе два потока, которые захватывают одну и ту же блокировку на 1 нс раз в 10 000 нс. Уровень конфликта низок: вероятность конфликта за приобретение каждой конкретной блокировки составляет 0,01%. Однако, как только произойдет такое оспаривание, сложится ситуация, в которой блокировка, фактически, задержится на весь период, необходимый для переключения контекста (чтобы проигравший поток успел блокироваться, а затем проснуться). Вот настолько дольше 10 000 наносекунд. Поэтому конвойная блокировка установится на неограниченное количество времени, до тех пор, пока не прекратится под действием какого-то внешнего фактора (например, один из потоков не решит поработать над какой-нибудь другой задачей). Ситуацию также может исправить перезапуск – в этом может заключаться одно из многих возможных объяснений той ситуации, когда тот или иной процесс занимает CPU на 100% (но все равно демонстрирует некоторый прогресс), и исправляется ситуация только рестартом. Все также значительно усложняется, если конкурирующих потоков не два, а более. <конец сноски 11>

Рассмотрим, что произойдет, когда два потока, A и B, неоднократно пытаются приобрести блокировку. Допустим, A получает номер 1 в очереди, а B - номер 2. Таким образом, A пробует перввым, а B приходится подождать. В таких реализациях это означает блокировку (можно сказать, что поток припаркован ОС). Теперь A отпускает блокировку, видит, что B ее дожидается – и будит его. A по-прежнему работает и вскоре вновь пытается завладеть этой блокировкой, получая в очереди номер 3 – но немедленно получить блокировку не может, так как блокировка честная: A не может перескочить в очереди вперед и забрать блокировку в обмен на номер 3 прежде, чем уB, владеющего номером 2, не появится шанс заполучить эту блокировку.

Разумеется, B на все это потребуется некоторое время. Сначала его должен разбудить планировщик, а на это требуется микросекунда, а то и целых две, не меньше. Теперь B пробуждается и получает блокировку, и все тот же сценарий повторяется, только участники меняются ролями. Мораль: на каждое приобретение блокировки тратится столько времени, сколько нужно на полное переключение контекста.

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

Итак, вы уже устали наблюдать белое безмолвие пустых окошек, где при введении каждого последующего алгоритма графики всех предыдущих придавливаются к оси x и превращаются в едва заметные разноцветные бугорки?

У меня остался еще всего один пример, самый медленный. В отличие от других примеров, такого плохого случая мне в реальной практике диагностировать не приходилось, но свидетельства о таком встречаются.

Уровень 5: катастрофа

Рассмотрим спин-блокировку, идентичную первой из тех, что мы обсудили, с той оговоркой, что sched_yield(); будет заменено на ;. То есть, процесс не уступает, а активно ожидает (а вот рассказ о разновидностях спин-блокировок, все они устроены по шаблону разделяемой блокировки). Также здесь подошла бы на замену специфичная для вашего CPU «расслабляющая» инструкция, например, pause, но на результат это не повлияет. Такая ситуация называется «тикет-спин», и вот каковы ее показатели по сравнению с другими кандидатами:

Что? Не так уж плохо это и выглядит, вообще. На самом деле, только чуть-чуть уступает уровню 2, самому шустрому, который мы пока рассмотрели¹².

Картинка изменится, если показать результаты для большего количества потоков - до 6, а не всего 4¹³. Поскольку у меня в распоряжении 4 ядра, это означает, что не все тестовые потоки смогут работать одновременно:

Теперь становится понятно, почему этот уровень называется катастрофическим. Как только мы сделаем больше подписок, чем есть в наличии ядер, производительность  ухудшается примерно в пятьсот раз. От сотен наносекунд мы переходим к задержкам в сотни микросекунд. Большего количества потоков я тут не показываю, но, чем больше вы их будете добавлять – тем хуже будет становиться ситуация.

Также мы сейчас работаем примерно на порядок медленнее, чем при наилучшем решении (очередь «первым пришел – первым обслужен») на предыдущем уровне, хотя, тут ситуация сильно варьируется в зависимости от аппаратного обеспечения. На Ice Lake разница более чем сорокакратная, тогда как на Graviton это решение на самом деле немного быстрее, чем блокировка по номерам (это тоже уровень 4) при 17 потоках. Также обратите внимание на огромные усы. Это самый ненадежный бенчмарк из всего набора имеющихся, проявляет сильнейшую разбежку, причем, самые медленные и самые быстрые прогоны могут отличаться стократно.

Перегретая блокировка конвоя

Так что же здесь происходит?

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

Вообразите 5 потоков, T1, T2, …, T5, где только T5 в настоящий момент не работает. Как только поток T5 оказывается следующим в очереди на получение блокировки (скажем, сохраненное значение тикета у T5 равно dispensing), не произойдет ничего, так как все потоки от T1 до T4 активно ожидают своей очереди. Планировщик ОС не видит никаких причин прерывать их работу до окончания выделенного им временного окна. Как правило, такие окна измеряются в миллисекундах. Как только один из потоков вытеснен, скажем, T1, у T5 появляется шанс поработать, но всего могут одновременно произойти 4 приобретения блокировок  (T5 плюс любые из T2, T3, T4), пока не придет очередь T1. T1 ожидает шанса поработать снова, но, поскольку все активно ожидают, такого шанса не представится, пока не истечет очередное временное окно.

Итак, блокировка может быть приобретена всего несколько раз (максимум $(nproc) раз), либо не менее, чем однократно¹⁴ за каждое временное окно.

В современном Linux, использующем CFS, фиксированного временного окна нет, но в моей системе sched_latency_ns равно 18 000 000, то есть, ожидается, что два потока будут конкурировать за ядро, чтобы получить стандартное временное окно длительностью 9 мс. Измеренные величины, в принципе, согласуются с тем, что временное окно составляет считанные миллисекунды (до 10).

Если бы я умел рисовать схемы - обязательно поместил бы здесь рисунок с описанием происходящего.

На эту ситуацию можно взглянуть и под другим углом: в сценарии с превышением количества подписок спин-очередь подразумевает примерно такое же количество переключений контекста, как и блокирующая  очередь с выдачей номеров (blocking ticket lock)¹⁵, но в первом случае каждое переключение контекста сопровождается гигантской задержкой – потому что необходимо дождаться окончания выделенного временного окна, тогда как в случае с блокирующей очередью быстродействие ограничено лишь тем, насколько оперативно происходит само переключение контекста.

Интересно, что, хотя на этом бенчмарке в каждом ядре мощность CPU и используется на 100%, производительность бенчмарка при превышении нормального количества подписок почти не зависит от скорости самого CPU! Производительность практически не изменится, если я при помощи пропуска тактов (тротлинга) доведу частоту процессора до 1 ГГц, либо если разгоню его в турбо-режиме до 3,5 ГГц. Все остальные реализации масштабируются практически пропорционально частоте CPU. Бенчмарк масштабируется в строгом соответствии с sched_latency_ns (и sched_min_granularity_ns, если для первого установлено достаточно низкое значение): чем ниже значения для задержки планировщика, тем (пропорционально) лучше становится производительность по мере сужения временного окна – что подтверждает теорию, обрисованную выше.

Таким поведением также объясняется значительная вариативность событий, как только все доступные ядра станут перегружены подпиской: по определению не все потоки будут работать одновременно, поэтому тест станет очень чувствителен к тому, где именно происходило переключение контекста у потоков, которые сейчас не работают. В начале теста работали только 4 из 6 потоков, а два остальных были выключены из событий, так и ожидая на том барьере, который синхронизирует начало тестирования. Поскольку два отключенных потока еще не пытались получить блокировку, четыре действующих потока могут быстро разделить блокировки между собой, так как шестипоточный конвой пока не установился.

В результате возрастает «количество итераций» (работа сделана) на протяжении начального периода, который случайным образом варьируется, пока в результате первого переключения
контекста пятый поток не присоединится к состязанию, и в этот момент сложится конвой¹⁶.

С этого момента и начинается катастрофа. Результаты при этом получаются очень зашумленными: например, если задать период испытания слишком кратким, то весь тест будет укладываться в эту начальную фазу, и результаты искусственно получатся «хорошими».

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

Уровень 1: Бесконфликтные атомики

Вспомните, с чего мы начали обсуждать уровень 2: с конфликтующих атомиков. Все понятно из названия: скорость выводится на новый уровень, когда атомарные операции применяются, но конкуренции за ресурсы не происходит – либо потому, что так задумано, либо потому, что повезло. Возможно, вы заметили, что пока мы показывали результаты, как минимум, для двух потоков. Дело в том, что в однопоточном случае никаких конфликтов не возникает, поэтому все операции, рассмотренные до сих пор, будучи исполняемыми в одном потоке, относятся к уровню 1.

Ниже даны результаты для всех реализаций, которые мы пока успели рассмотреть – в однопоточном варианте:

Самые быстрые реализации выполняются примерно за 10 наносекунд, что впятеро быстрее самого быстрого решения для двух и более потоков. Самая медленная реализация (очередь «первым пришел – первым обслужен») для одного потока может потягаться с самой быстрой реализацией (атомарное сложение) для двух потоков, а если потоков будет три или четыре – то однопоточная реализация явно их уделывает.

Число, наложенное на каждые из «усов» соответствует количеству атомарных операций¹⁸ на инкремент, выполняемых при каждой из реализаций.

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

По поводу таблицы отметим, что на мьютексное сложение приходится вдевятеро с лишним больше инструкций, чем на cas-сложение (использующее сравнение с обменом), но все равно cas выполняется примерно вдвое быстрее, при соотношении атомиков в 2:1. Аналогично, уступка по тикетам и тикетная спин-очередь показывают производительность чуть лучше, чем cas-сложение, несмотря на то, что в них примерно вдвое больше инструкций, хотя в каждом из трех вариантов и предусматривается всего по одной атомарной операции¹⁹.

В последней строке таблицы показана производительность mutex3 – реализации, которую мы не обсуждали. Это простейший мьютекс, функционально примерно аналогичный std::mutex; реализация такого мьютекса описана в статье Futexes Are Tricky. Поскольку ему не требуется преодолевать два уровня абстракций²⁰, и количество инструкций в нем примерно втрое меньше, чем в std::mutex – но потери в производительности почти нет, разница составляет менее 10%.

Итак, идея здесь в том, что по-прежнему можно практически игнорировать факторы, которые по стоимости относятся к «самому дешевому» уровню. Но не слишком этим увлекайтесь. Если вы спроектируете блокировку с единственной атомарной операцией и 1000 других инструкций, то быстро она работать не будет. Кроме обеспечения производительности на уровне микробенчмаркнига есть и другие причины минимизировать количество инструкций: хорошо, когда инструкции оставляют не слишком обширный след в кэше, меньше места отводится под разные буферы для внеочередного исполнения, также возникают более щадящие компромиссы при подстановке функций и т.д.

Здесь важно отметить, что изменение уровня наших разнообразных функций не требует менять их реализацию. У нас остаются все те же немногочисленные реализации, уже рассмотренные на более низких уровнях. Вместо того, чтобы просто изменить уровень конфликта (принудительно, то есть, откорректировали руками параметры бенчмарков) с «очень высокий» на «нулевой». Таким образом, в данном случае уровень зависит не только от кода, но и от данного внешнего фактора. Разумеется, в реальной жизни не так много прока заявить: «мы собираемся свести конфликты к уровню 1, и поэтому будем обходиться всего одним потоком». Часто мы попросту не в состоянии исключить многопоточные операции.

Итак, можем ли мы выйти на уровень 1 даже при конкурентных вызовах, поступающих от
множества потоков? В рамках данной конкретной задачи – можем.

Адаптивный мультисчетчик

Как вариант, можно использовать для представления значения счетчика не один счетчик, а несколько. Попытаемся организовать ситуацию так, чтобы потоки, конкурентно выполняемые на разных CPU, давали инкремент значения на разных счетчиках. Следовательно, логическое значение счетчика разделено между всеми этими внутренними физическими счетчиками; таким образом, считывание логического значения счетчика теперь требует суммировать значения всех физических счетчиков.

Вот реализация:

class cas_multi_counter {
    static constexpr size_t NUM_COUNTERS = 64;

    static thread_local size_t idx;
    multi_holder array[NUM_COUNTERS];

public:

    /** инкремент значения логического счетчика */
    uint64_t operator++(int) {
        while (true) {
            auto& counter = array[idx].counter;

            auto cur = counter.load();
            if (counter.compare_exchange_strong(cur, cur + 1)) {
                return cur;
            }

            // Сравнение с обменом не удалось – это свидетельствует о конфликте,
            // поэтому попробуем еще раз под другим индексом
            idx = (idx + 1) % NUM_COUNTERS;
        }
    }

    uint64_t read() {
        uint64_t sum = 0;
        for (auto& h : array) {
            sum += h.counter.load();
        }
        return sum;
    }
};

Этот подход называется «cas multi», он относительно прямолинеен.

Здесь есть 64 дополненных полями²¹ физических счетчика, из суммы которых складывается значение логического счетчика. Есть локальное для потока значение idx, изначально равное нулю для каждого потока. Оно указывает на тот физический счетчик, который каждый поток должен приращивать. Вызывая  operator++, мы пытаемся при помощи CAS прирастить тот счетчик, на который указывает idx.

Но здесь нас ждет неудача, поэтому мы не просто повторяем попытку. Неудача свидетельствует о конфликте²² (это единственный случай, когда compare_exchange может не пройти в сильном варианте), так что добавим единицу к idx, чтобы при следующей попытке попробовать с другим счетчиком.

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

Сравним этот вариант с версией atomic add, рассмотренной выше – как помните, тот подход оказался самым быстрым на уровне 2. Как помните, там использовалось атомарное сложение на единственном счетчике.

При 1 активном ядре результаты получаются точно такими же, как рассмотрены ранее: подход с CAS дает такую же производительность, как алгоритм cas add²³, который
немного медленнее атомарного сложения, поскольку предусматривает дополнительную
операцию загрузки (т.e., строку с counter.load()), чтобы подготовить CAS.

Когда ядер от 2 до 4, ситуация радикально меняется. Подход с множеством счетчиков показывает одинаковую производительность, независимо от количества активных ядер. То есть, проявляет идеальное масштабирование на множестве ядер – в отличие от подхода с единственным счетчиком, который масштабируется плохо. При четырех ядрах относительное ускорение, которое обеспечивает подход с множеством счетчиков – девятикратное. На процессоре Graviton ARM от Amazon такое ускорение при применении 16 потоков почти восьмидесятикратное.

Но такое повышение производительности при инкременте, конечно же, имеет свою цену:

• Наверное, 64 счетчиков хватит каждому, но на их хранение требуется 4096 (!!) байт памяти, тогда как при подходе с атомарным сложением на те же цели уходит всего 8 байт²⁴.

• Метод read() гораздо медленнее: ему требуется перебрать и просуммировать все 64 значения – сравните с единственной операцией загрузки из более ранних подходов.

• Эта реализация компилируется в гораздо более тяжелый код: 113 байт против 15 байт при CAS-подходе с единственным счетчиком или 7 байт при подходе с атомарным сложением.

• О конкурентном поведении значительно сложнее рассуждать, его сложнее документировать. Например, сложнее объяснить условия согласованности, обеспечиваемые методом read(), поскольку операция более не является единичным атомарным считыванием.

• Здесь есть единственная локальная для потока переменная idx. При логической независимости различных экземпляров cas_multi_counter друг от друга разделяемая переменная idx свидетельствует: события, происходящие в одном счетчике, могут влиять на нефункциональное поведение других счетчиков²⁶.

Некоторые из этих недостатков отчасти устранимы:

• Для большинства практических задач, вероятно, требовалось бы гораздо меньше счетчиков. Мы также могли бы задавать размер массива счетчиков динамически, исходя из обнаруженного количества логических CPU, так как сравнительно большой массив счетчиков не дал бы серьезного увеличения производительности. Лучше того, мы могли бы сделать размер этого массива еще динамичнее, исходя из степени конфликтности: начать с единственного элемента и увеличивать их число только по мере обнаружения конфликтов. Таким образом, даже в системах с большим количеством CPU этот размер будет оставаться небольшим, если на практике серьезных конфликтов никогда не возникает. Но за это приходится нести издержки во время исполнения²⁷.

• Можно было бы оптимизировать метод read(), так, чтобы он останавливался, как только мы заметим счетчик, стоящий на нуле. Думаю, тщательный анализ покажет, что все ненулевые значения счетчика для любого экземпляра этого класса находятся в непрерывной области, которая начинается с массива счетчика²⁸.

• Можно было бы немного уменьшить отпечаток кода, аккуратно вырезав «не столь горячий»²⁹ путь в другую функцию, а также, прибегнув к магии, способствовать подстановке кратчайшего ускоренного пути (через первую операцию CAS), так, чтобы с резервным путем подстановка при этом не производилась.

• Локальную для потока переменную idx, выделяемую на экземпляр, можно было бы применить конкретно для решения проблемы «разделяемости между всех экземпляров». Для этого потребовалось бы выполнить существенный объем работы – реализовать динамическую idx систему TLS, которая позволяла бы создавать любое нужное³⁰ количество ключей, локальных для потока. Кроме того, такая система медленнее работает.

Итак, хотя нам и удалось получить симпатичный график, не сказать, что это решение явно превосходит более простые. За отсутствие конфликтов приходится расплачиваться на нескольких фронтах, поэтому не следует слепо менять более простые решения на это – оно должно быть тщательно взвешено в зависимости от конкретного практического случая.

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

Уровень 0: Без изысков

Последний и быстрейший уровень достигается, когда используются только инструкции без изысков (ванильные) – и, при этом, без конфликтов. Говоря «без изысков», я подразумеваю такие вещи как обычные операции загрузки и сохранения, не подразумевающие дополнительной синхронизации сверх той, что предоставляется аппаратной моделью памяти по умолчанию³¹.

Как приращивать счетчик атомарно, в то же время разрешая считывать его из любого потока? Для этого нужно гарантировать, что на каждый физический счетчик будет всего один пишущий. Если держать по счетчику на поток и разрешать запись в этот счетчик только тому потоку, который им владеет, то отпадает нужда в атомарном инкременте.

Очевидный способ держать по счетчику на поток – использовать хранилище, локальное в пределах потока. Примерно так:

/**
 * Держит по счетчику на поток, считывающие должны суммировать
 * счетчики со всех активных потоков и прибавлять к этому 
 * аккумулированное значение от мертвых потоков.
 */
class tls_counter {
    std::atomic<uint64_t> counter{0};

    /* защищает all_counters и накапливатель */
    static std::mutex lock;
    /* список всех активных счетчиков */
    static std::vector<tls_counter *> all_counters;
    /* аккуиулированное значение счетчиков от мертвых потоков */
    static uint64_t accumulator;
    /* объект tls_counter по одному на каждый поток */
    static thread_local tls_counter tls;

    /** добавляемся в список счетчиков */
    tls_counter() {
        std::lock_guard<std::mutex> g(lock);
        all_counters.push_back(this);
    }

    /**
     * днструкция означает, что поток уходит, так что мы
     * закладываем актуальное значение в аккумуляторе и 
     * удаляемся из массива
     */
    ~tls_counter() {
        std::lock_guard<std::mutex> g(lock);
        accumulator += counter.load(std::memory_order_relaxed);
        all_counters.erase(std::remove(all_counters.begin(), all_counters.end(), this), all_counters.end());
    }

    void incr() {
        auto cur = counter.load(std::memory_order_relaxed);
        counter.store(cur + 1, std::memory_order_relaxed);
    }

public:

    static uint64_t read() {
        std::lock_guard<std::mutex> g(lock);
        uint64_t sum = 0, count = 0;
        for (auto h : all_counters) {
            sum += h->counter.load(std::memory_order_relaxed);
            count++;
        }
        return sum + accumulator;
    }

    static void increment() {
        tls.incr();
    }
};

Этот подход похож на вариант «по счетчику на CPU», за тем исключением, что мы держим по счетчику на поток при помощи thread_local. В отличие от предыдущих реализаций, здесь мы не создаем экземпляров этого класса: есть всего один счетчик, и мы приращиваем его, вызывая статический метод tls_counter::increment().

Давайте ненадолго сосредоточимся на конкретном инкременте, находящемся внутри экземпляра счетчика, локального в пределах потока:

void incr() {
    auto cur = counter.load(std::memory_order_relaxed);
    counter.store(cur + 1, std::memory_order_relaxed);
}

Вот так пространно можно сказать: «прибавь 1 к этому std::atomic<uint64_t>, но эта операция не обязательно должна быть атомарной». Нам не нужен атомарный инкремент, поскольку здесь всего один пишущий³².

При применении нестрогого порядка памяти никаких барьеров³³ не вставляется

Нам все еще требуется способ, который позволил бы считывать все счетчики, локальные в пределах потока, и остальной код занят именно этим: есть глобальный вектор указателей на все активные объекты tls_counter, и метод read() этот вектор перебирает. Все обращения к этому вектору защищены std::mutex, поскольку доступ к нему будет происходить конкурентно. Как только поток умирает, его запись удаляется из массива, а окончательное значение добавляется к tls_counter::accumulator, который приплюсовывается к сумме активных счетчиков в read().

Фух!

Как же выглядит эта реализация сложения с tls, если сделать для нее бенчмарк?

Получается две наносекунды на инкремент, независимо от количества активных ядер. Оказывается, ровно та же скорость, как при простом инкременте переменной в памяти с применением единственной инструкции, например, inc [eax] или add [eax], 1, поэтому представляется, что это максимальная скорость для любого решения, предполагающего инкремент какого-либо значения в памяти³⁴.

Давайте посмотрим, сколько у нас получается атомиков, инструкций всего, и какова будет
производительность для трех реализаций на последнем графике, для четырех
потоков:

Здесь очень четко видно, что разница в производительности почти не связана с количеством инструкций: ранжирование по количеству инструкций получается почти обратным ранжированию по производительности! При сложении с tls количество инструкций утраивается, но такой вариант более чем в пятьдесят раз быстрее (поэтому IPC варьируется с коэффициентом более 150).

Как мы видели на последней 1 из таблицы, такое улучшение не дается даром:

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

• У нас по одному объекту на поток, а не на CPU. Для приложения со множеством потоков, которое использует счетчик, в данном случае может потребоваться создать множество отдельных счетчиков. В таком случае будет расходоваться больше памяти³⁵, и функция read() будет работать медленнее.

• Данная реализация поддерживает всего один счетчик: ключевые методы в tls_counter являются статическими. В сухом остатке имеем: для физического счетчика нужен объект thread_local, по правилам C++ он должен быть статическим. Здесь можно добавить шаблонный параметр, чтобы разрешить установку множества счетчиков на основе типов-заглушек, которые использовались бы как метки, но такое решение все равно получится более неуклюжим, чем с использованием экземпляров класса (а на некоторых платформах есть ограничения на количество переменных thread_local). От этого ограничения можно было бы избавиться тем же способом, который мы рассматривали выше для cas с переменной idx, но ценой дополнительных сложностей и снижения производительности.

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

Таблица

Давайте обобщим все уровни в следующей таблице.

В столбце ~Цена дается очень приблизительная оценка стоимости каждого «экземпляра» дорогой операции, характерной для данного уровня. Это значение следует считать весьма примерным «эшелоном» для современного оборудования Intel и AMD, но значения, в особенности, на последних уровнях, могут весьма варьироваться.

В столбце События Perf перечислены события perf из Linux, позволяющие подсчитать, сколько раз происходит операция, ассоциированная с данным уровнем. Например, на уровне 1 мы подсчитываем атомарные операции при помощи счетчика mem_inst_retired.lock_loads, и, если у нас наберется три штуки на высокоуровневую операцию, то можно ожидать, что стоимость ее составит примерно 3 x 10 нс = 30 нс. Разумеется, в данном случае вполне можно обойтись и без perf, а вместо этого посмотреть, что происходит в ассемблере.

В столбце Локально записано, является ли поведение на данном уровне локальным в пределах ядра (core local). Если да, то это означает, что операции на разных ядрах выполняются независимо и не конкурируют друг с другом, поэтому производительность масштабируется вместе с количеством ядер. Если нет, то имеют место конфликты и сериализация, поэтому пропускная способность всей системы зачастую оказывается ограничена, независимо от того, сколько ядер участвует в работе. Например, если в данный момент времени всего одно ядро выполняет атомарную операцию в кэш-линии, то пропускная способность всей системы фиксирована, и пропускная способность в пересчете на ядро снижается тем сильнее, чем больше ядер вовлечено в работу.

В таблице Ключевые характеристики я пытаюсь разложить идею уровней на удобоваримые кусочки.

Что же это все значит?

Какой вывод из всего этого можно сделать?

Я использую иерархию прежде всего, как механизм упрощения, позволяющий яснее рассуждать о конкурентности и производительности. В качестве приближения первого порядка обычно требуется учитывать лишь те операции, которые относятся к рассматриваемому уровню. То есть, если вас интересуют операции, подразумевающие конфликты на уровне атомиков (уровень 2), не нужно слишком много внимания уделять атомикам, не вызывающим конфликтов, либо подсчету инструкций: сфокусируйтесь на том, чтобы погасить конфликты. Аналогично, если вы сейчас на уровне 1 (атомики без конфликтов), часто стоит применять больше инструкций, чтобы сократить количество атомиков.

Данный руководящий принцип имеет примерно такую направленность: если вам требуется добавить 100 инструкций, чтобы удалить один атомик, то, пожалуй, дело того не стоит.

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

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

Как туда попасть?

Давайте быстро рассмотрим некоторые обычные и необычные способы, позволяющие добраться до низких уровней описанной иерархии.

Уровень 4

Вряд ли вам так уж хочется попасть на уровень 4, но уж лучше там, чем на уровне 5. Итак, если вы сохранили работу, и ваши пользователи от вас не уходят, обычно не составляет труда опуститься с уровня 5 на 4. Большая половина победы – распознать, что происходит, а тогда и решение приходит само. В большинстве случаев оказывается, что вы банально нарушали простые правила вроде «не делайте в пользовательском пространстве чистых спин-блокировок» или «у вас случайно получилась спин-блокировка», или «по этим и этим причинам случайно сложилась блокировка на уровне ядра во время ввода-вывода». Практически не бывает неустранимых причин, по которым приходится оставаться на уровне 5, обычно удается исправить ситуацию, почти не идя на компромиссы.

Всегда лучше стремиться не на уровень 4, а сразу на уровень 2, ведь и это обычно не так сложно.

Уровень 3

Переход на уровень 3 обычно требует всего лишь устранить базовую причину, по которой у вас слишком много переключений контекста. В примере, приведенном в этом посте, это означает – пожертвовать честностью. Другие варианты – не выделять потоки под выполнение слишком малых кусков работы, использовать более умные пулы потоков, не допускать чрезмерно многочисленной подписки на ядро и держать заблокированные области короткими.

Но, как правило, вам и на уровне 3 оставаться не захочется; лучше переходите прямо на уровень 2.

Уровень 2

Уровень 3 – не сказать, чтобы страшное место, но, пока вы там остаетесь, у вас все время сосет под ложечкой – ведь можно было бы ускорить работу в десять раз, а вы этого не делаете. Нужно просто избавиться от этого системного вызова или переключения контекста – и это приведет вас на уровень 2.

Большинство примитивов для конкурентности, предоставляемых в библиотеках, уже избегают системных вызовов на оптимистичном пути. Таковы, например, мьютекс pthreads, std::mutex. В Windows есть команда CRITICAL_SECTION, позволяющая обойтись без системного вызова при приобретении и высвобождении бесконфликтной блокировки. Есть, правда, некоторые заметные исключения: если вы используете мьютексный объект Win32 или семафор System V, то за каждую операцию расплачиваетесь системным вызовом. Дважды проверьте, а нельзя ли в таком случае воспользоваться внутрипроцессной альтернативой.

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

Лишние системные вызовы часто просачиваются в код, когда используются кустарные решения для синхронизации, например, при применении событий Windows для построения собственных блокировок чтения-записи или блокировок с выборкой (striped lock), или любых других блокировок, модных на настоящий момент. Часто удается удалить системный вызов с быстрого пути, просто проверив пользовательское пространство, чтобы узнать, необходим ли в данном случае системный вызов. Например, вместо безусловной разблокировки всех ждущих при высвобождении некоторого эксклюзивного объекта, проверьте, есть ли ждущие в пользовательском пространстве³⁶ – и пропустите системный вызов, если таких ждущих нет.

Если блокировка в принципе удерживается в течение краткого периода, то можно избежать ненужных системных вызовов и переключений контекста, если применить гибридную блокировку, которая в течение нужного времени³⁷ вертится в цикле ожидания, а затем закрывается. Так можно в обмен на десятки наносекунд ожидания можно сэкономить тысячи наносекунд, которые тратились бы на системные вызовы.

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

Уровень 1

Масса кода, помогающего пробиться на уровень 2, на самом деле, ведет на уровень 1. Напомню: основное отличие между уровнями 2 и 1 заключается в отсутствии конфликтов на уровне 1. Поэтому, если ваш процесс (по естественным причинам или по вашему замыслу) не слишком провоцирует конфликты, то вы можете выйти на уровень 1, просто взяв с полки готовый инструмент синхронизации, предназначенный именно для этого – например, std::mutex.

Не могу дать пошагового рецепта по сокращению конфликтов, но вот вам подробный список того, на что стоит обратить внимание:

• Старайтесь держать критические секции вашего кода настолько короткими, насколько возможно. Убедитесь, что вся тяжеловесная работа, напрямую не связанная с использованием разделяемого ресурса, делается вне критической секции. Иногда для этого требуется скопировать разделяемые данные, чтобы работать с ними «вне» блокировки – то есть, вам придется дополнительно поработать, но конфликты таким образом получится сократить.

• Для таких штук как атомарные счетчики старайтесь объединять обновления в пакеты. Например, если в течение некоторой операции вы многократно обновляете счетчик, то пусть это будет локальный счетчик в стеке, а не глобальный – а «загружайте» только окончательное значение, в самом конце.

• Старайтесь использовать такие структуры данных, которые предназначены для блокировок с высокой детализацией, блокировок с выборкой или подобных механизмов, снижающих количество конфликтов, закрывая контейнер лишь частично.

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

Применительно ко всем советам, данным выше: когда я говорю «попробуйте сделать X», я на самом деле имею в виду «попробуйте найти и задействовать готовый компонент, который делает X». Писать конкурентные структуры самостоятельно – это, пожалуй, самая последняя опция. Как бы вам ни казалось, решаемая вами задача, скорее всего, не уникальна.

Именно на уровне 1 находится масса хорошо написанного, прямолинейного и высокопроизводительного конкурентного кода. В том, чтобы оставаться на этом уровне, нет ничего дурного, ведь здесь хорошо.

Уровень 0

Не всегда бывает легко или вообще возможно устранить последние атомарные обращения на быстрых путях вашего кода, но, если вам кровь из носу нужно сэкономить еще ~10 нс, то
вот несколько вариантов:

• Стандартный подход – использовать хранилище данных, локальное в пределах потока (о чем мы уже говорили выше) – можно распространить и на другие структуры, более сложные, чем счетчики.

• Можно добиться, чтобы на каждую логическую операцию приходилось менее одной дорогостоящей атомарной инструкции, для этого объединяйте такие инструкции в пакеты. Сначала сохраняется множество операций, а затем все они разом фиксируются вместе с небольшим конкретным количеством атомарных операций. У некоторых контейнеров или конкурентных структур может быть предусмотрен пакетный API, делающий это за вас, но даже если его нет, иногда вы можете добавить пакетное объединение сами – например, вставляя коллекции элементов, а не единичные элементы³⁸.

• Многие неблокирующие структуры предлагают пути считывания, свободные от атомиков. В данном случае особенно замечательны конкурентные контейнеры в языках, где предусмотрена сборка мусора, например, ConcurrentHashMap в Java. В языках без сборки мусора не так много вариантов действовать прямолинейно, в основном потому, что проблема безопасной отдачи памяти сложна, но и на этот случай есть некоторые хорошие варианты.

• Я считаю механизм RCU (чтение-копирование-обновление) особенно мощным и подлинно универсальным, если в языке, с которым вы работаете, предусмотрена сборка мусора. Этот же механизм может удовлетворить требования по эффективному высвобождению памяти в языке без сборки мусора.

• Секвентная блокировка (seqlock) – это, на мой взгляд, недооцененная и малоизвестная альтернатива RCU, которая пусть не столь универсальна, но не вызывает проблем с высвобождением памяти. В Concurrencykit есть ее реализация. Она предусматривает путь считывания данных, работающий без атомиков. К сожалению, секвентные блокировки не получается чисто интегрировать с моделями памяти ни в Java (в Java предоставляется StampedLock, функционально аналогичная seqlock), ни в C++.

• Кроме того, в некоторых случаях можно обойтись по-процессорным, а не по-поточным подходом, используя при этом только ванильные инструкции; правда, поскольку возможно, что в любой момент случится прерывание, ситуация сильно усложняется. Здесь могут помочь перезапускаемые последовательности (rseq), есть в запасе и другие фокусы.

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

• И последнее – но об этом можно было бы сказать в первую очередь. Зачастую можно перепроектировать алгоритм или все приложение, чтобы изначально избежать совместного использования данных, либо пользоваться этой возможностью гораздо реже. Например, чтобы не приходилось постоянно обновлять разделяемую коллекцию промежуточными результатами, лучше делать как можно больше приватных вычислений, а уже в конце финально объединять результаты

Итог

Мы рассмотрели шесть различных уровней издержек, которые образуют иерархию конкурентности. Медленная часть (3, 4 и 5) – это, в принципе, баги с производительностью. Вы, должно быть, сможете выйти на уровень 2 или 1 (если в вашей программе по определению мало конфликтов за ресурсы), в большинстве вариантов это достаточно легко – и, пожалуй, именно на эти уровни следует нацеливаться по умолчанию. Уровень 1 в сценарии с явными конфликтами и уровень 0 достижимы сложнее и зачастую требуют сложных компромиссов, но и рост производительности может получиться значительным: иногда на порядок и более.

Благодарности

Автор благодарит Пола Хуонга, показавшего ему такие вещи, которые заставили автора пересмотреть, в каких сценариях достижим уровень 0, а также исправившего опечатки.

Автор благодарит @never_released за помощь в решении задачи, для которой пришлось поднимать инстанс EC2 на голом железе.

Особые благодарности matt_dz и Заку Уэнджеру за то, что помогли исправить около шестидесяти опечаток.

Автор благодарит Александра Монакова, Дэйва Андерсона, Лорана и Криау за найденные опечатки, а также Аарона Джейкобса за то, что помог яснее сформулировать определение уровня 0.