Параллельное программирование на С++ в действии — страница 26 из 53

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

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

8.2.1. Сколько процессоров?

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

В первом приближении один 16-ядерный процессор эквивалентен четырем 4-ядерным или 16 одноядерным, во всех случаях одновременно могут выполняться 16 потоков. Чтобы в полной мере задействовать имеющийся параллелизм, в программе должно быть не менее 16 потоков. Если их меньше, то вычислительная мощность используется не полностью (пока оставляем за скобками тот факт, что могут работать и другие приложения). С другой стороны, если готовых к работе (не заблокированных в ожидании чего-то) потоков больше 16, то приложение будет попусту растрачивать процессорное время на контекстное переключение, о чем мы уже говорили в главе 1. Такая ситуация называется превышением лимита (oversubscription).

Чтобы приложение могло согласовать количество потоков с возможностями оборудования, в стандартной библиотеке Thread Library имеется функция std::thread::hardware_concurrency(). Мы уже видели, как ее можно использовать для определения подходящего количества потоков.

Использовать std::thread::hardware_concurrency() напрямую следует с осторожностью; ваш код не знает, какие еще потоки работают в программе, если только вы не сделали эту информацию разделяемой. В худшем случае, когда несколько потоков одновременно вызывают функцию, которая принимает решение о масштабировании с помощью std::thread::hardware_concurrency(), превышение лимита получится очень большим. Функция std::async() решает эту проблему, потому что библиотека знает обо всех обращениях к ней и может планировать потоки с учетом этой информации. Избежать этой трудности помогают также пулы потоков, если пользоваться ими с умом.

Однако даже если вы учитываете все потоки в своем приложении, остаются еще другие запущенные в системе программы. Вообще-то в однопользовательских системах редко запускают одновременно несколько счетных задач, но бывают области применения, где это обычное дело. Если система проектировалась специально под такие условия, то обычно в ней есть механизмы, позволяющие каждому приложению заказать подходящее количество потоков, хотя они и выходят за рамки стандарта С++. Один из вариантов — аналог std::async(), который при выборе количества потоков учитывает общее число асинхронных задач, выполняемых всеми приложениями. Другой — ограничение числа процессорных ядер, доступных данному приложению. Лично я ожидал бы, что это ограничение будет отражено в значении, которое возвращает функция std::thread::hardware_concurrency() на таких платформах, однако это не гарантируется. Если вас интересует подобный сценарий, обратитесь в документации.

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

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

8.2.2. Конкуренция за данные и перебрасывание кэша

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

Рассмотрим следующий простой фрагмент кода:

std::atomic counter(0);
void processing_loop() {
 while(counter.fetch_add(
  1, std::memory_order_relaxed) < 100000000) {
  do_something();
 }
}

Переменная counter глобальная, поэтому любой поток, вызывающий processing_loop(), изменяет одну и ту же переменную. Следовательно, после каждого инкремента процессор должен загрузить в свой кэш актуальную копию counter, модифицировать ее значение и сделать его доступным другим процессорам. И хотя мы задали упорядочение std::memory_order_relaxed, чтобы процессору не нужно было синхронизироваться с другими данными, fetch_add — это операция чтения-модификации-записи и, значит, должна получить самое последнее значение переменной. Если другой поток на другом процессоре выполняет этот же код, то значение counter придётся передавать из кэша одного процессора в кэш другого, чтобы при каждом инкременте процессор видел актуальное значение counter. Если функция do_something() достаточно короткая или этот код исполняет много процессоров, то дело кончится тем, что они будут ожидать друг друга; один процессор готов обновить значение, но в это время другой уже обновляет, поэтому придётся дождаться завершения операции и распространения изменения. Такая ситуация называется высокой конкуренцией. Если процессорам редко приходится ждать друг друга, то говорят о низкой конкуренции.

Подобный цикл приводит к тому, что значение counter многократно передается из одного кэша в другой. Это явление называют перебрасыванием кэша (cache ping-pong), оно может серьезно сказаться на производительности приложения. Когда процессор простаивает в ожидании передачи в кэш, он не может делать вообще ничего, даже если имеются другие потоки, которые могли бы заняться полезной работой. Так что ничего хорошего в этом случае приложению не светит.

Быть может, вы думаете, что к вам это не относится — ведь в вашей-то программе таких циклов нет. Да так ли? А как насчет блокировок мьютексов? Когда программа захватывает мьютекс в цикле, она выполняет очень похожий код — с точки зрения доступа к данным. Чтобы захватить мьютекс, поток должен доставить составляющие мьютекс данные своему процессору и модифицировать их. Затем он снова модифицирует мьютекс, чтобы освободить его, а данные мьютекса необходимо передать следующему потоку, желающему его захватить. Время передачи добавляется к времени, в течение которого второй поток должен ждать, пока первый освободит мьютекс:

std::mutex m;
my_data data;
void processing_loop_with_mutex() {
 while (true) {
  std::lock_guard lk(m);
  if (done_processing(data)) break;
 }
}

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

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

В главе 3 мы видели, что редко обновляемую структуру данных можно защитить мьютексом типа «несколько читателей — один писатель» (см. раздел 3.3.2). Эффект перебрасывания кэша может свести на нет преимущества такого мьютекса при неподходящей рабочей нагрузке, потому что все потоки, обращающиеся к данным (пусть даже только для чтения) все равно должны модифицировать сам мьютекс. По мере увеличения числа процессоров, обращающихся к данным, конкуренция за мьютекс возрастает, и строку кэша, в которой находится мьютекс, приходится передавать между ядрами, что увеличивает время захвата и освобождения мьютекса до неприемлемого уровня. Существуют приёмы, позволяющие сгладить остроту этой проблемы; суть их сводится к распределению мьютекса между несколькими строками кэша, но если вы не готовы реализовать такой мьютекс самостоятельно, то должны будете мириться с тем, что дает система.

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

Но это не так-то просто — впрочем, просто никогда не бывает. Даже если к некоторой ячейке памяти в каждый момент времени обращается только один поток, перебрасывание кэша все равно возможно из-за явления, которое называется ложным разделением (false sharing).

8.2.3. Ложное разделение

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

Допустим, что имеется массив значений типа int и множество потоков, каждый из которых обращается к своему элементу массива, в том числе для обновления, причём делает это часто. Поскольку размер int обычно меньше строки кэша, то в одной строке окажется несколько значений. Следовательно, хотя каждый поток обращается только к своему элементу, перебрасывание кэша все равно имеет место. Всякий раз, как поток хочет обновить значение в позиции 0, вся строка кэша должна быть передана процессору, на котором этот поток исполняется. И для чего? Только для того, чтобы потом быть переданной процессору, на котором исполняется поток, желающий обновить элемент в позиции 1. Строка кэша разделяется, хотя каждый элемент данных принадлежит только одному потоку. Отсюда и название ложное разделение. Решение заключается в том, чтобы структурировать данные таким образом, чтобы элементы, к которым обращается один поток, находились в памяти рядом (и, следовательно, с большей вероятностью попали в одну строку кэша), а элементы, к которым обращаются разные потоки, отстояли далеко друг от друга и попадали в разные строки кэша. Как это влияет на проектирование кода и данных, вы узнаете ниже.

Если обращение из разных потоков к данным, находящимся в одной строке кэша, — зло, то как влияет на общую картину расположение в памяти данных, к которым обращается один поток?

8.2.4. Насколько близки ваши данные?

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

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

Да, но ведь это относится к однопоточным программам, я-то тут при чем? — спросите вы. А все дело в контекстном переключении. Если количество потоков в системе превышает количество ядер, то каждое ядро будет исполнять несколько потоков. Это увеличивает давление на кэш, поскольку мы пытаемся сделать так, чтобы разные потоки обращались к разным строкам кэша — во избежание ложного разделения. Следовательно, при переключении потоков процессором вероятность перезагрузки строк кэша возрастает, если данные каждого потока находятся в разных строках кэша. Если потоков больше, чем ядер или процессоров, то операционная система может назначить потоку один процессор в течение одного кванта времени и другой — в следующем кванте. В результате строки кэша, содержащие данные этого потока, придётся передавать из одного кэша в другой. Чем больше таких передач, тем больше на них уходит времени. Конечно, операционные системы стараются избежать такого развития событий, но иногда это все же происходит и приводит к падению производительности.

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

8.2.5. Превышение лимита и чрезмерное контекстное переключение

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

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

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

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

8.3. Проектирование структур данных для повышения производительности многопоточной программы