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

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

К счастью, написать такой опасный код на Rust практически невозможно. Это заложено в девизе языка - он построен таким образом, чтобы гарантировать безопасность потоков.

Rust обеспечивает безопасный параллелизм с:

Эта статья посвящена использованию последнего для безопасной и эффективной многопоточности.

Связь на основе сообщений по каналам - несколько производителей, один потребитель.

Rust побуждает нас делиться памятью, общаясь (вместо общения, разделяя память). Чтобы установить связь между потоками, нам нужен канал - и std::sync::mpsc был создан именно для этого.

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

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

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

Функция mpsc::channel возвращает кортеж, состоящий из отправителя и получателя. Затем в строке 6 отправляется сообщение (и отправка, и получение возвращают Result; для простоты мы предполагаем, что в таком простом примере не должно происходить ошибок - поэтому здесь используется unwrap). Наконец, в строке 8 принимается и распечатывается сообщение.

Итак, как мы можем иметь более одного отправителя (производителя сообщения)? Это просто - просто вызвав метод clone() исходного отправителя. Мы вскоре увидим это в действии, когда передадим этих отправителей рабочим потокам.

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

Поиск хэша заданной сложности с несколькими потоками выполнения

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

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

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

"000000" в строке 4 определяет сложность задачи (и поверьте мне, добавление еще одного нуля к последовательности может резко увеличить сложность). Если вам интересно, решение (значение x) для вышеуказанной проблемы - 3305951, и оно дает хэш a2a44903ffc6affe69d514ffe47721cc3a6475cbb43b37538686f2c5b46000000 (обратите внимание на завершающую последовательность нулей).

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

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

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

Для достижения первой цели мы просто скажем потоку 0 начать с номера 0, а затем проверим каждое 4-е целое число: 4, 8, 12 и так далее. В потоке 1 мы начнем с 1 и перейдем к 5, 9, 13 (и так далее). В потоке 2 мы начнем с 2 и перейдем к 6, 10, 14… видите шаблон? Таким образом, мы можем быть уверены, что каждое возможное целое число проверяется ровно один раз за запуск приложения.

Быстро напрашивается еще одно наблюдение: все эти рабочие потоки идеально подходят для создания сообщений!

Реализация

(Полный пример кода доступен на github; обратите внимание, что существуют очень незначительные различия между независимыми сущностями ниже и реальной базой кода, главным образом для того, чтобы сделать сущность более читаемой. )

основная функция

Давайте посмотрим, что происходит в функции main:

Мы начинаем с создания семафора с именем is_solution_found типа AtomicBool в строке 2. Это особый тип логического примитива, который может безопасно совместно использоваться между потоками. Поскольку мы собираемся поделиться им, нам нужно дополнительно обернуть его в Arc, что означает атомарный указатель подсчета ссылок. Это один из способов обеспечения безопасности параллелизма в Rust, и если бы мы попытались передать голый AtomicBool более чем одному потоку, компилятор пожаловался бы, потому что знаменитые правила владения Rust были бы нарушены. Arc позволяет нам разделить, поточно-безопасным способом, право собственности на базовые данные, сохраняя внутреннее количество указателей на значение. Когда последний указатель отбрасывается и счетчик достигает нуля, базовые данные также удаляются.

В строке 3 создается экземпляр канала, возвращающий его 'sender и receiver концы. Затем мы создаем четыре потока (от 0 до 4, исключительно) в строках 5–11, отдавая им приказ search_for_solution (эта функция рассматривается в следующем разделе).

Наконец, в строке 13 мы прослушиваем сообщение, поступающее из рабочих потоков: receiver.recv() блокирует основной поток, но это именно то, что нам нужно в этом случае. Когда решение будет найдено, оно появится в строке 14 в Ok случае.

search_for_solution & verify_number functions

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

Если решение найдено, семафор is_solution_found обновляется значением true (помните, как мы говорили ранее, что AtomicBool можно безопасно разделить между многими потоками). Методы store (и load) AtomicBool дополнительно принимают атрибут Ordering, который дает некоторые умные подсказки компилятору относительно оптимизации, но это выходит за рамки данной статьи. Затем по каналу отправляется сообщение с уведомлением в строке 8. Поскольку sender.send(msg) возвращает результат, мы сопоставляем результат с шаблоном и предполагаем, что больше нечего делать, когда это удается. В конце концов, мы return из функции и вызываем это в день.

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

  • … Каждые 1000 итераций (строка 13) мы дополнительно проверяем текущее значение семафора is_solution_found. Если решение было найдено (очевидно, другим рабочим потоком), мы return из функции, потому что больше просто нечего делать. Теперь вы можете спросить себя, почему, черт возьми, выполнять проверку один раз на 1000 итераций, а не каждый раз? Что ж, использование атомики влечет за собой некоторое снижение производительности, и попытка прочитать значение на каждом этапе цикла может отрицательно повлиять на скорость работы нашего приложения. Как говорится, с большой силой приходит большая ответственность. Но если решение еще не найдено…
  • … Мы просто увеличиваем счетчик оборотов цикла в строке 16.

И вот последняя деталь - функция verify_number:

Как было сказано ранее, это самая суть логики решения криптографической проблемы. Sha256::hash из ящика easy-hash используется для вычисления хеш-функции результата умножения. Если данное число решает проблему (строки 8, 9), возвращается Some(Solution(number, hash)). Если этого не произойдет, выскочит None.

Резюме

Как мы видели, каналы Rust - отличный выбор каждый раз, когда задачу можно разделить на более мелкие подзадачи, а конечный результат можно собрать в одном месте. Единый потребитель плюс передача прав собственности на данные (при передаче сообщений) гарантируют безопасную модель параллелизма.

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

Я рекомендую вам проверить полный пример кода. Попробуйте изменить значения - измените DIFFICULTY, BASE и / или THREADS. Тем не менее, вам понадобится ночной компилятор Rust, но инструкция находится в файле readme, поэтому обязательно прочтите его!

И наконец, что не менее важно, особая благодарность HadrienG с форума языков программирования Rust за просмотр моего кода и обмен бесценными советами!

дальнейшее чтение