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

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

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

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

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

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

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

Сноска 1

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

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

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

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

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

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

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

Микроархитектура

Стандарт ISA

Модель

Протестированная частота

Ядра

ОС

Тип инстанса

Skylake

x86

i7–6700HQ

2,6 ГГц

4

Ubuntu 20.04

Ice Lake

x86

i5–1035G4

3,3 ГГц

4

Ubuntu 19.10

Graviton

AArch64

Cortex-A72

2,3 ГГц

16

Ubuntu 20.04

a1.4xlarge

Graviton 2

AArch64

Neoverse N1

2,5 ГГц

162

Ubuntu 20.04

c6g.4xlarge

Сноска 2

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

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

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

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

Сноска 3

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

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

T lock;
uint64_t counter;

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

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

Мьютекс SkylakeМьютекс SkylakeМьютекс IcelakeМьютекс IcelakeМьютекс GravitonМьютекс Graviton 3123dee81010adff04a36b21ea808ae6.svgМьютекс Graviton2Мьютекс Graviton2

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

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

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

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

Сноска 4

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

std::atomic atomic_counter{};

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

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

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

Сноска 5

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

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

Сноска 6

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

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

std::atomic 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:

Атомарный инкремент SkylakeАтомарный инкремент SkylakeАтомарный инкремент IcelakeАтомарный инкремент IcelakeАтомарный инкремент GravitonАтомарный инкремент Graviton Атомарный инкремент Graviton2Атомарный инкремент Graviton2

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

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

Сноска 7

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

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

Сноска 8

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

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

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

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

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

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

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

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

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

Сноска 9

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

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

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

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

Честная уступка SkylakeЧестная уступка SkylakeЧестная уступка IcelakeЧестная уступка IcelakeЧестная уступка GravitonЧестная уступка Graviton Честная уступка Graviton2Честная уступка Graviton2

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

Сноска 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 lock(mutex);
    while (ticket != serving.load(std::memory_order_acquire)) {
        cvar.wait(lock);
    }
}

void blocking_ticket::unlock() {
    std::unique_lock 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 (первым пришел — первым обслужен) и, если вас интересует ее реализация — она описана здесь.

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

Немного честнее: SkylakeНемного честнее: SkylakeНемного честнее: IcelakeНемного честнее: IcelakeНемного честнее: GravitonНемного честнее: Graviton Немного честнее: Graviton2Немного честнее: Graviton2

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

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

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

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, но на результат это не повлияет. Такая ситуация называется «тикет-спин», и вот каковы ее показатели по сравнению с другими кандидатами:

Тикет-спин: SkylakeТикет-спин: SkylakeТикет-спин: IcelakeТикет-спин: IcelakeТикет-спин: GravitonТикет-спин: Graviton Тикет-спин: Graviton2Тикет-спин: Graviton2

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

Сноска 12

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

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

Сноска 13

Причем, одновременная многопоточность (SMT) здесь не активирована, и, с точки зрения операционной системы, здесь действует 4 логических процессора.

Переподписка: SkylakeПереподписка: SkylakeПереподписка: IcelakeПереподписка: IcelakeПереподписка: GravitonПереподписка: Graviton Переподписка: Graviton2Переподписка: Graviton2

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

Также мы сейчас работаем примерно на порядок медленнее, чем при наилучшем решении (очередь «первым пришел — первым обслужен») на предыдущем уровне, хотя, тут ситуация сильно варьируется в зависимости от аппаратного обеспечения. На 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 за каждое временное окно.

Сноска 14

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

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

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

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

Сноска 15

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

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

© Habrahabr.ru