Оптимизация многопоточного кода C++

оптимизация кода c

Уже много лет твой компьютер умеет выполнять код любимого ПО параллельно, на всех своих ядрах и процессорах. Да что там компьютер — скоро холодильники смогут обсчитывать гастрономические предпочтения хозяина в несколько потоков, недаром IoT движется по планете семимильными шагами. И казалось бы, уже весь софт давным-давно должен уметь максимально эффективно нагревать атмосферу вокруг тебя, нагружая транзисторы твоего ПК многопоточностью, но все не так замечательно, как хотелось бы.

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

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

Рекомендуем: Лучшие клиенты Git GUI для Windows

Сферическая задача в вакууме

Допустим, нам нужно написать серверное приложение, которое принимает одно-единственное подключение по UDP-протоколу и как-то нехитро обрабатывает входящие датаграммы, например считает статистику по пришедшим данным. Основная проблема в том, что данные идут на очень больших скоростях, например 10 Гбит/c. Чтобы справиться с такой нагрузкой, нам надо проявить определенную сообразительность и не ударить в грязь лицом.

Хорошая новость состоит в том, что устройство, на котором наше ПО будет запущенно, принадлежит полностью нам, можно грузить процессор на 100%, и никто нас за это не поругает, главное — обсчитать как можно больше пакетов и максимально не допустить потерь. Размер данных в UDP-датаграмме не может превышать 512 байт (к примеру).

Архитектура приложения

Из описания задачи сразу становится понятно, что без всех ядер ПК нам тут не обойтись. Первое, что придет в голову более-менее опытному разработчику, — это выделить один поток на прием входящих датаграмм и создать пул потоков для их обработки. Размер пула обычно делают равным количеству доступных ядер у машины.

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

Для потоков из пула, которые обрабатывают UDP-пакеты, мы реализуем очередь из этих самых пакетов. Как только главный поток получает датаграмму, он сразу кладет ее в очередь и пытается прочитать следующую порцию данных из сокета. Потоки пула при этом придерживаются той же модели работы, что и main thread. В частности, они будут крутить цикл вычитки пакетов из очереди, не засыпая на ожидании, если очередь пуста.

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

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

Конечно, мы могли бы использовать readers-write lock, чтобы обеспечить одновременно чтение из очереди потокам пула, когда не ведется запись. Но проблема в том, что датаграммы будут сыпаться с большой частотой и основная конкуренция за разделяемый ресурс у обработчиков данных окажется не друг с другом, а с главным потоком.

Очередь

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

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

Таким образом, вырисовывается примерный интерфейс класса, который будет имплементировать нашу структуру данных. Назовем его RingQueue. Класс будет иметь как минимум два метода: push и pop. Причем метод push() будет возвращать булев результат, где true обозначает успешное добавление в очередь, а false — очередь полна.

Теперь, когда мы определились с общими принципами, по которым будет работать наш класс, давай подумаем о реализации.

Реализация на основе std::mutex

Первое, что приходит в голову для имплементации класса RingQueue, — это использовать STL vector в качестве хранилища для элементов очереди и STL mutex для защиты данных в многопоточной среде. Ниже представлен код класса RingQueue на основе vector и mutex.

С первых строк видно, что RingQueue является шаблонным классом. Это напрямую не относится к многопоточности, но таким образом мы достигаем нужного уровня универсальности. Тип T — это тип элементов, хранимых в очереди. В нашей реализации единственное требование к T — это поддержка move-семантики.

Конструктор RingQueue в качестве параметра принимает свой размер size и создает вектор длиной size + 1. Как мы говорили выше, очередь должна занять максимально возможный объем оперативной памяти. Единицу к size мы прибавляем для того, чтобы обеспечить корректный доступ к элементам по принципам кольцевого буфера.

Метод push() — шаблонный метод, причем используется фича variadic templates из C++ 11. Это также сделано для универсальности, чтобы иметь возможность передать произвольное количество аргументов в вызов конструктора T(). Напрямую к многопоточности variadic templates не относится. Внутри метода мы сразу же блокируем mutex, а затем пытаемся положить элемент в очередь. Для этого мы первым делом смотрим, не полна ли очередь, сравнивая индекс вставки (m_pushPos) с индексом извлечения (m_popPos). Если они равны, то считаем, что мест больше нет, и возвращаем false. Если же очередь еще может принять новые элементы, мы получаем item по индексу вставки, инициализируем его новыми значениями, а затем сдвигаем на индекс вставки на следующую позицию.

Особенность метода pop() в том, что ссылку на извлекаемый элемент он возвращает через обратный вызов, а не с помощью оператора return. Метод pop() может гарантировать неизменность извлекаемого элемента только при заблокированном mutex. Выводя ссылку на элемент за блокировку, мы автоматически получаем data race. Конечно, мы бы могли отдавать копию объекта, но это лишние затраты на вызов конструктора копирования, в котором может происходить что угодно, в том числе какие-то тяжелые операции. В высоконагруженных приложениях такое крайне не рекомендуется. С другой стороны, надо помнить, что поскольку обратный вызов осуществляется под блокировкой, то существует шанс deadlock в случае, если код callback недостаточно щепетилен и каким-то образом пытается повторно обратиться к RingQueue.

Но вернемся к описанию происходящего в pop(). После блокировки mutex мы первым делом сдвигаем индекс извлечения и проверяем, есть ли что-нибудь в очереди. Если индекс извлечения равен текущему индексу вставки, то считаем, что очередь пуста, в противном случае достаем из вектора нужный элемент и отдаем ссылку на него клиентскому коду через callback.

Теперь давай еще раз взглянем на получившийся код. Основная его проблема в блокировке. Пока мы что-то кладем в очередь в одном потоке, другой поток не может достать нужный ему элемент для обработки и просто засыпает. И наоборот, когда один поток вызывает метод pop(), другой простаивает, ожидая, когда завершится вызов функции члена push(). Конечно, метод push() — очень легкий метод и не занимает много тактов процессора. Но, во-первых, мы не можем сказать того же про операцию извлечения элемента (мы не знаем, что происходит при вызове callback), а во-вторых, при высоких нагрузках вероятность того, что потоки будут ждать друг друга, значительно увеличивается, несмотря на потенциальную легковесность push/pop-операций.

Оптимизированная реализация на основе std::mutex

Чтобы избежать описанной проблемы, воспользуемся методом try_lock() класса std::mutex. Эта функция пытается заблокировать мьютекс, но в случае, если это успел сделать какой-то другой поток, она возвращает false. Давайте взглянем на модифицированный код push/pop-методов.

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

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

Реализация на основе std::atomic

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

Как видно из кода, мы объявили m_popPos и m_pushPos атомарными переменными. Метод load() типа atomic позволяет получить текущее значение переменной, а store() — синхронно записать новое значение, которое станет немедленно доступно всем CPU. Кроме того, функция fetch_add() атомарно увеличивает значение переменной.

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

Оптимизированная реализация на основе std::atomic

К счастью, std::atomic поддерживает несколько видов семантики упорядочивания доступа. По умолчанию используется std::memory_order_seq_cst — sequentially-consistent, или последовательно согласованный доступ. Это самая строгая и понятная для разработчика семантика. При ее использовании работа с атомарными переменными в нескольких потоках выглядит как однопоточный код. Другими словами, все потоки выполняемого процесса видят изменения ячейки памяти в одинаковом порядке. Обратная сторона этой простоты — высокие накладные расходы, о которых говорилось выше.

Для увеличения производительности можно использовать менее строгие семантики, в частности семантику захвата-освобождения (memory_order_acquire и memory_order_release) и семантику ослабленного упорядочивания (memory_order_relaxed). К сожалению, в рамках данной статьи у нас не получится разобраться с тем, что это такое и как это работает. Это довольно сложные концепции, которые требуют развернутых объяснений с детальными примерами. Неправильный выбор семантики упорядочивания доступа может сделать поведение программы непредсказуемым. Но к счастью, на рабочий код, который использует продвинутое упорядочивание, мы посмотреть можем.

Тестирование производительности

Теперь у нас есть целых четыре варианта реализации класса RingQueue, каждый следующий лучше и быстрее предыдущего. Настало время проверить, насколько хорошо работают наши реализации. Для этого мы напишем небольшой тест на google benchmark фреймворке. Код теста можно увидеть ниже.

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

Тип решения Время, наносекунды
mutex 245
mutex::try_lock 32
atomic sequentially-consistent 26
atomic aquire-release and relaxed 4

Как мы видим, каждое из введенных нами усовершенствований повышает производительность вставки-извлечения в разы. Самый примитивный вариант с использованием std::mutex выполняет операции push-pop за 245 наносекунд, а вот использование try_lock() улучшает быстродействие более чем в семь раз. Оно и неудивительно, ведь в первом варианте RingQueue при высокой конкуренции за разделяемый ресурс наши потоки значительную часть времени просто спят.

Переход от mutex::try_lock варианта к std::atomic с семантикой упорядочивания по умолчанию дает прирост производительности «всего» на 18%, но при этом мы решаем проблему, при которой значительная часть вызовов push() завершалась бы неудачно.

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

Конечно, не стоит рассматривать эти числа как абсолютные, они представляют ценность в сравнении друг с другом. Результат будет зависеть от железа и уровня загрузки ресурсов системы. Для тестов использовалась следующая конфигурация: Ubuntu 16.04, Intel Core i7 4790k, 16 Гбайт DDR3 1600 МГц. Кроме того, наш бенчмарк не учитывает количество неудачных попыток добавления в очередь. Этот параметр тоже важен для оценки быстродействия класса RingQueue.

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

Рекомендуем: Оптимизация Android-приложений

Понравилась статья? Поделиться с друзьями:
Добавить комментарий