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

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

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

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

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

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

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

Сноска 1

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

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

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

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

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

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

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

Сноска 2

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

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

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

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

Сноска 3

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

Итак, в нашей исходной реализации инкремента будет использоваться простой мьютекс типа 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++()⁴, и это даст нам атомарное сложение

Сноска 4

Кстати, здесь можно было бы использовать любую из двух версий оператора – преинкрементную или постинкрементную. Как правило, рекомендуется отдавать предпочтение преинкрементной форме ++c. На практике она может оказаться быстрее, поскольку способна возвращать измененное значение, а не делать возвращаемую копию измененного значения, которую возвращала бы после операции изменения. Сейчас этот совет редко применим к примитивным значениям, но атомарный инкремент как таковой – интересный случай, поскольку он все ставит с ног на голову. Оказывается, постинкрементная версия может быть даже лучше преинкрементной (по крайней мере, не медленнее), поскольку на аппаратном уровне базовая операция возвращает предыдущее значение. Поэтому для расчета преинкрементного значения нужна как минимум одна дополнительная операция (и, очевидно, все значительно усугубится, если в дело будет вовлечен icc)

std::atomic<uint64_t> atomic_counter{};

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

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

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

Сноска 5

Многие ISA, в том числе, POWER и ARM, традиционно включали поддержку только для CAS-подобных операций или LL/SC, без специфичной поддержки более конкретных атомарных арифметических операций. Идея, на мой взгляд, такова: поверх этих примитивов вы можете построить любую операцию, какую только захотите, и это обойдется вам ценой «всего лишь» маленького цикла повторных попыток, а в этом больше RISC-а, верно? По-видимому, эта ситуация меняется, поскольку в ARMv8.1 появился целый букет атомарных операций

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

Сноска 6

Класс AtomicInteger и другие связанные с ним классы Java, с момента введения и до Java 7, реализовывали все их атомарные операции поверх цикла CAS, поскольку CAS был единственным примитивом, которому была присуща такая возможность. В Java 8, почти ровно десять лет спустя, этот механизм был наконец-то по мере возможности заменен выделенными атомарными RMW (чтение-изменение-запись) с неплохими результатами

Давайте добавим реализацию счетчика, использующую 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 заключается в том, что эти операции используют конфликтный доступ к разделяемой переменной. Таким образом, как минимум, та строка, что содержит данные, должна быть вынесена и передана кэширующему агенту, который управляет согласованностью⁷, после чего ее резервная копия будет сделана на ядре, которое затем завладеет этим кодом

Сноска 7

На моей системе и на большинстве (во всех?) современных системах Intel это, в сущности, кэш L3, поскольку домашний агент кэширования (CHA) живет либо в кэше L3, либо в смежном с ним.

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

Сноска 8

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

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

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

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

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

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

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

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

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

Сноска 9

Еще она может работать не так, как вы ожидали, в зависимости от деталей планировщика операционной системы.

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

/**
 * Спин-очередь, использующая 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: это системный вызов, а на выполнение таких вызовов обычно требуются сотни наносекунд¹⁰ – что видно из результатов.

Сноска 10

Раньше они обходились дешевле: как показывают мои замеры, стоимость системных вызовов на большинстве аппаратного обеспечения Intel более чем удвоилась после принятия нововведений в Spectre и Meltdown.

Такая блокировка действительно может пойти быстрым путем в случае, когда 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, самому шустрому, который мы пока рассмотрели¹².

Сноска 12

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

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

Сноска 13

Причем, одновременная многопоточность (SMT) здесь не активирована, и, с точки зрения операционной системы, здесь действует 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) раз), либо не менее, чем однократно¹⁴ за каждое временное окно.

Сноска 14

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

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

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

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

Сноска 15

Фактически, можете это измерить при помощи perf – и убедитесь, что в обоих тестах при чрезмерном количестве подписок общее количество переключений контекста возрастает примерно вдвое.

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

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

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

Сноска 16

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

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

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

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

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

Сноска 17

Так бывает не всегда. Можно написать примитив, который всегда выполняет системный вызов, что ставит его на уровень 3 даже при отсутствии конфликтов. Но в этом исследовании я предусмотрел, чтобы для случая без конфликтов всегда оставался быстрый путь, при котором системного вызова не делается.

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

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

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

Сноска 18

На оборудовании Intel можно воспользоваться details.sh, чтобы без труда подбить количество атомарных инструкций – это делается при помощи счетчика производительности mem_inst_retired.lock_loads.

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

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

Сноска 19

Реализация сложения в cas-варианте в итоге выглядит чуть хуже, чем другие представленные здесь реализации, предусматривающие по одной атомарной операции. Дело в нагрузке, которая возникает из-за необходимости установить CAS-значение. Эта нагрузка фактически добавляется к цепочке зависимостей, включающей атомарную операцию; этим и объясняется разница в 5 циклов с атомарным сложением. Проблема устраняется, если вам удастся сделать слепое CAS (напр., на путях приобретения блокировок), но в данном случае такого не сделать.

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

Сноска 20

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

Итак, идея здесь в том, что по-прежнему можно практически игнорировать факторы, которые по стоимости относятся к «самому дешевому» уровню. Но не слишком этим увлекайтесь. Если вы спроектируете блокировку с единственной атомарной операцией и 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.

Сноска 21

«Дополнение полями» (padding) означает, что счетчики специально выровнены: так, чтобы каждый из них укладывался в собственную 64-байтную кэш-линию во избежание ложной разделяемости. Это значит, что, пусть у каждого счетчика всего 8 байт логической полезной нагрузки, ему требуется пространство 64 байт для хранения данных. Некоторые настаивают, что необходимо дополнять это пространство до 128, а не до 64 байт, во избежание эффекта «предвыборки смежной линии»: выбираем еще 64 байта, завершая таким образом выравнивание 128-байтной пары линий. Но я не скажу, что часто наблюдал такой эффект на современных CPU. Может быть, механизм предвыборки консервативен и не срабатывает до тех пор, пока не станет понятно в ретроспективе, что, вероятно, будет применяться выборка – либо, если сама логика предвыборки позволяет детектировать случаи ложной разделяемости и избегать их (например, замечая, в каких случаях предвыбранные линии впоследствии будут повреждаться в режиме snoop).

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

Сноска 22

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

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

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

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

Сноска 23

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

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

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

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

Сноска 24

Здесь предполагается, что sizeof(std::atomic<uint64_t>) равно 8, так и есть на всех современных платформах, которые можно считать мейнстримом. Кроме того, вы, возможно, захотите или не захотите дополнять до 64 байт версию с единственным счетчиком, во избежание потенциальной ложной разделяемости со смежными значениями, но этот случай отличается от варианта со множеством счетчиков, где дополнение полями является обязательным во избежание гарантированной ложной разделяемости.

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

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

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

Сноска 25

Думаю, в данном случае read() предоставляет те же гарантии, что и в случае с единственным счетчиком. Нестрого говоря, read() возвращает некоторое значение, что было у счетчика в какой-то момент между началом и окончанием вызова read(). Строго говоря, в пределах read() есть точка линеаризации, хотя, определить ее можно только ретроспективно, проверив возвращенное значение (а не как в подходах с единственным счетчиком, где линеаризация явно просматривается независимо от значения). Но это верно лишь потому, что единственной операцией, меняющей данные, является increment(). Если бы мы также предложили метод decrement(), то все бы сломалось: могли бы считываться такие значения логического счетчика, которые в принципе не основаны на последовательности инкрементов и декрементов. В частности, если выполнить increment(); decrement(); increment() даже зная, что эти операции строго упорядочены (например, контролируются при помощи блокировок), конкурентный вызов read() мог бы вернуть 2, пусть даже счетчик логически ни разу не превышал 1

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

Сноска 26

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

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

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

Сноска 27

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

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

Сноска 28

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

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

Сноска 29

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

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

Сноска 30

Если набросать такую реализацию, то она условно использовала бы нечто вроде единственного статического указателя thread_local на массив или словарь, который отображал бы ID, содержащийся в динамическом ключе TLS, на данные объекта. В данном случае важна скорость поиска, поэтому массив предпочтительнее, но также нам нужна возможность удалять элементы, и поэтому можно было бы выбрать тот или иной вариант хеш-таблицы. Все это, пожалуй, будет минимум вдвое медленнее, чем обычный доступ к thread_local … либо можно было бы просто воспользоваться folly или boost.

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

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

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

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

Сноска 31

На x86 четко видно, где проходит граница между «изысками» и «без изысков»: обычные обращения к памяти и инструкции «чтение-изменение-запись» — без изысков, тогда как инструкции LOCK RMW, будь то явные, например, lock inc или неявными, например, xchg [mem], reg – это уже изыски, и работают они на порядок медленнее.  Что касается работы с барьерами, есть mfence – тоже медленная и непростая инструкция, сравнимая по стоимости с инструкцией LOCKed. На других платформах, например, ARM или POWER, возможны оттенки серого: на одном конце спектра у вас по-прежнему доступ без изысков и дорогие полноценные барьеры, например, dmb на ARM или sync на POWER на другом конце. Но есть и середина спектра, в которых даются дополнительные гарантии упорядочивания, но последовательной согласованности все равно не хватает. Сюда относятся такие вещи как LDAR и LDAPR на ARM, реализующие своеобразную скользящую шкалу нагрузки и производительности. Все же, на любом заданном аппаратном обеспечении обычно можно разделить все инструкции на две категории: «дешевые» и «дорогие».

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

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

/**
 * Держит по счетчику на поток, считывающие должны суммировать
 * счетчики со всех активных потоков и прибавлять к этому 
 * аккумулированное значение от мертвых потоков.
 */
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>, но эта операция не обязательно должна быть атомарной». Нам не нужен атомарный инкремент, поскольку здесь всего один пишущий³².

Сноска 32

Единственная причина, по которой нам вообще требуется std::atomic<uint64_t> - в том, что мы имеем дело с неопределенным поведением, если к любой переменной у нас предоставляется конкурентный доступ, и как минимум один вариант такого доступа – запись. Поскольку владеющий поток выполняет операции записи, это технически нарушало бы стандарт при наличии конкурентного вызова tls_counter::read(). На самом современном оборудовании не возникает никаких проблем с конкурентными операциями чтения и записи такого рода, но, если можно не нарушать – то лучше не нарушать. На некоторых видах оборудования также может наблюдаться снос операций записи, а std::atomic гарантирует, что такого не произойдет. Таким образом, по отдельности операции чтения и записи все равно остаются атомарными.

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

Сноска 33

При использовании задаваемого по умолчанию std::memory_order_seq_cst, на x86 gcc вставляет mfence, из-за чего эта операция становится даже медленнее атомарного инкремента, поскольку mfence обычно работает медленнее инструкций с префиксом lock (семантика барьеров у нее чуть сильнее).

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

Фух!

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

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

Сноска 34

Честно говоря, тут я немного лукавлю.

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

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

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

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

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

Сноска 35

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

• Данная реализация поддерживает всего один счетчик: ключевые методы в 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), или любых других блокировок, модных на настоящий момент. Часто удается удалить системный вызов с быстрого пути, просто проверив пользовательское пространство, чтобы узнать, необходим ли в данном случае системный вызов. Например, вместо безусловной разблокировки всех ждущих при высвобождении некоторого эксклюзивного объекта, проверьте, есть ли ждущие в пользовательском пространстве³⁶ – и пропустите системный вызов, если таких ждущих нет.

Сноска 36

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

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

Сноска 37

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

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

Уровень 1

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

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

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

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

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

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

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

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

Уровень 0

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

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

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

Сноска 38

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

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

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

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

Сноска 39

Несмотря на то, что Википедия в настоящее время утверждает, будто секвентная блокировка – это конструкция, специфичная для Linux и предназначенная, прежде всего, для работы в ядре, она, на самом деле, отлично работает и сугубо в пользовательском пространстве, и не имеет жесткой привязки к Linux. Вероятно, они были изобретены не для Linux, а появились раньше этой ОС, хотя, может быть, именно в Linux эту штуку впервые назвали seqlock?

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

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

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

Итог

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

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

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

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

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

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