В прошлом году я переписал Enjarify на Go и Rust, чтобы узнать больше о языках и сравнить сложность, многословность, производительность и подверженность ошибкам языков, и я написал пост с подробным описанием моих выводов. Для простоты я измерял только однопоточную производительность, но ряд комментаторов посчитали, что это было несправедливо по отношению к Go, потому что простой параллелизм является одним из основных преимуществ языка, под которым они предположительно подразумевали параллелизм, Роб Пайк не выдерживает. . Поэтому я решил распараллелить код и написать новый пост с подробным описанием результатов.

Оптимизация

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

Исходный пост просто сравнивал мой код как есть. Однако при написании версии Rust у меня было несколько идей по оптимизации, которые я хотел попробовать перенести на версию Go, а версия Go также содержала кучу кода, который был написан скорее простым, чем быстрым. Я решил потратить некоторое время, пытаясь оптимизировать (однопоточный) код Go и Rust, чтобы увидеть, насколько разница в производительности является естественной, а не из-за неоптимальных вариантов реализации.

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

Кроме того, я также обновил языковые версии, но это имело в основном негативные последствия. CPython поднялся до 3.5.2, что фактически замедлило его примерно на 5%. Обновление до последней версии Rust не дало заметного эффекта. Go 1.8rc1 был примерно на 10% медленнее, поэтому я остановился на 1.7. Обратите внимание, что это только для исходного однопоточного теста - в более поздней параллельной версии не было заметной разницы между 1,7 и 1,8, но я использовал числа 1,7 для согласованности. Большим победителем стал Pypy. В моем предыдущем посте Pypy был опущен из-за того, что он медленнее, чем CPython, но любая ошибка, которая была исправлена ​​за это время, поэтому Pypy теперь включен.

Rust стал на 64% быстрее, а Go стал на 76% быстрее, что снизило соотношение Go / Rust с 2,15 до 2,0. Также интересно, что Pypy был почти таким же быстрым, как неоптимизированная версия Go из исходного сообщения. Это указывает на то, что если Pypy доступен, и вы мало что знаете об оптимизации Go и имеет значение только однопоточная производительность, вы можете не увидеть увеличения скорости от переписывания кода Python в Go, хотя версия Go все равно будет быстрее для краткосрочных задач. из-за отсутствия JIT-разминки.

В любом случае, взяв это за основу, пришло время распараллелить код Go и Rust. Я не стал беспокоиться о версии Python по понятным причинам.

Дизайн

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

Очевидным подходом было бы распараллелить цикл хэш-тестов и запустить тесты 1792 параллельно. Однако это выглядело немного искусственно, поскольку не привело бы к каким-либо улучшениям для нормального использования Enjarify. Другое очевидное место для распараллеливания - это основной цикл трансляции, который переводит каждый класс в предоставленном файле (ах) dex в файл классов Java, процесс, который полностью независим от других классов. Нет смысла пытаться распараллелить с более высокой степенью детализации, потому что перевод каждого отдельного класса по своей сути является последовательным из-за того, что все методы и поля в классе используют один пул констант.

Распараллеливание цикла перевода будет хорошо работать при обычном использовании Enjarify, когда вы обычно переводите один файл apk с тысячами классов, но не сильно поможет при хэш-тестах, когда один файл с 1–6 классами переводится сотни раз. Поэтому в своих экспериментах я решил, что и цикл хэш-тестов, и цикл трансляции должны быть параллельны.

Go

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

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

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

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

Ржавчина

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

Rayon выполняет всю буферизацию и упорядочение результатов за вас, поэтому его намного удобнее использовать, чем версию Go. В этом случае большая часть работы была связана с переписыванием моих лупов в стиле iter/map/collect. Как только это было сделано, фактическое распараллеливание сводилось просто к импорту Rayon и изменению iter на par_iter.

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

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

Полученные результаты

На моей 8-ядерной машине (4 физических ядра) результирующий код Go снизился до среднего значения 48,0 секунды, а код Rust снизился до 23,7 секунды. Это означает, что у обоих было ускорение примерно в 3,4 раза. Есть несколько возможных объяснений отсутствия полного масштабирования - закон Амдала, затраты на синхронизацию, конфликты кешей между ядрами и т. Д., Но я не пытался глубоко исследовать это. Удивительно, что коэффициент ускорения для двух языков примерно одинаков, поскольку нет априорной причины, по которой какой-либо из этих факторов был бы одинаковым в обоих случаях. В любом случае это означает, что код Rust был примерно в два раза быстрее кода Go в каждом тесте - неоптимизированном, оптимизированном и параллельном.

Бонусный раунд - Результаты трансляции

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

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

Go

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

Цикл перевода в main.go остался нетронутым.

Ржавчина

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

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

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

Как и большинство библиотек Rust, Rayon и Futures :: CpuPool принимают закрытие, которое представляет работу, которую необходимо выполнить. В Rayon они имеют ограниченную область видимости - работа гарантированно завершится до того, как вы вернетесь, и, следовательно, замыкания могут безопасно содержать ссылки на стек. Фактически, они могут в основном делать все, что может делать не-закрывающий код в одном и том же месте, а вывод типа замыкания в Rust означает, что он просто работает.

К сожалению, Futures этого не поддерживает. CpuPool::spawn_fn() имеет 'static привязку, что означает, что переданные замыкания не могут ссылаться на какие-либо данные стека, так как они думают, что они могут пережить порождающий поток.

Для внешнего цикла хеш-тестов это было несложно слишком обойти. Я просто засунул пул и тестовые файлы внутрь Arcs. Однако мне потребовалось время, чтобы придумать подходящий способ клонирования и перемещения их в закрытие, поскольку сообщение об ошибке rustc в этом случае совершенно бесполезно.

С другой стороны, цикл перевода замыкается на DexClass<'a>, что не так просто исправить. DexClass анализируется из входного файла dex, и он заимствовал ссылки в указанный файл. К сожалению, весь код синтаксического анализа dex и весь код, который использует проанализированные данные, предполагает, что он работает с заимствованными ссылками. Нет безопасного способа сделать его статичным, не внося серьезных изменений в код, чего я не хотел делать, тем более что это изначально излишняя пессимизация.

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

После всего этого код, наконец, скомпилирован ... и запущен ... и не дал никаких результатов.

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

Окончательные результаты

Обе версии передают результаты на консоль без снижения производительности. Версия Go немного «дёргается» - она ​​делает паузу на некоторое время, затем сразу распечатывает кучу результатов, а затем снова делает паузу. Это не удивительно, поскольку результаты выполняются параллельно и хранятся в буфере, но это немного разочаровывает. Использование небуферизованного выходного канала уменьшило рывки, но не устранило их.

Версия на Rust лишь немного дёргается. Вам нужно будет очень внимательно посмотреть, чтобы отличить его от исходной последовательной версии, не считая того факта, что теперь он работает в 3,5 раза быстрее.

Я не думаю, что резкость доказывает, что Rust лучше - вероятно, это просто случайность, какой алгоритм планирования здесь лучше, но это была интересная разница.

Версия Rust также снизилась с 23,7 секунды до 23,1 секунды. Я не уверен, связано ли это с Rayon или CpuPool или это связано с распечаткой результатов параллельно с вычислениями.

Заключение

Распараллеливание неплохо ни на одном из языков. У каждого свои недостатки. В случае с Go это связано с отсутствием реальной системы типов. В случае с Rust это связано с тем, что библиотеки незрелые и не делают все, что вам нужно.

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

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