Многоядерность: компиляция и декомпрессия

После апгрейда начала этого многострадального года, когда я переехал с 4х ядерного процессора на 10 ядер, периодически ловлю себя на мысли, что я оказался в ситуации чувака, который купил себе sports car, чтобы каждый день стоять на нем в городских пробках. При казуальных сценариях использования ПК дома хоть какую-то серьезную нагрузку на процессор дают ну разве что игры. При этом для современных многоядерных камней речь идет о нагрузке порядка 30-40%, т.е. две трети мощностей тупо простаивает. Как по мне, для гейминга оптимум по процессору находится где-то в области нынешних бюджетных решений со схемой 4C/8T (при условии, что эти ядра будут работать на достаточно высоких частотах)... 
Да, на моем i5-12600K есть возможность выбивать красивые цифры во всякой там синтетике, типа Cinebench, но синтетика она и есть синтетика и постепенно приходит осознание, что у тебя в ПК стоит процессор, которому вообще-то место не дома, а на рабочем месте в машинах класса "workstation". Короче, в один прекрасный день, наблюдая за тем, как неторопливо идет компиляция проекта на моем ноутбуке для работы (с не самым дохлым i7-10850H), я понял, что мне определенно стоит попробовать стоящий рядом домашний ПК в роли рабочей лошадки. 

Наконец-то дошли руки поставить Visual Studio 2022, а в качестве real-world бенчмарка решено было использовать компиляцию boost (достаточно большую по размеру и сверх популярную C++ библиотеку). Скачал последнюю актуальную версию 1.80, это целых 200 мегабайт исходников. 

Перед тем, как показывать и обсуждать какие-то цифры, напомню, что в одной из прошлых заметок я поделился выводами о том, как нужно оценивать многопоточный потенциал процессора i5-12600K с учетом того, что он содержит в себе аж целых три разных вида ядер -- производительные P-ядра, их виртуальных копии для режима hyperthreading и "экономичные" E-ядра. Многочисленные бенчмарки говорят о том, что для хорошо масштабирующейся нагрузки этот процессор можно интерпретировать как содержащий 10 P-ядер: 6 фактических, +2 ядра дают 6 HT ядер (с коэффициентом 1 к 3) и +2 ядра дают 4 E-cores (с коэффициентом 1/2). Т.е. если какая задача, при переходе от выполнения на одном ядре к работе на всех 16-ти ядрах, ускоряется в 10 раз, то можно говорить о том, что она практически идеально масштабируется под многопоточность. 

Теперь о полученных результатах. Сначала я запустил компиляцию на трех P-ядрах и получил 306 секунд. Потом -- на всех ядрах и получил 100 секунд ровно. Ускорение в три раза, т.е. коэффициент от многопоточности получился 9x, что говорит о том, что такого рода нагрузка весьма достойно масштабируется и современные многоядерные монстры это то, что доктор прописал для серьезных задач по компиляции плюсового кода.
Тащите ноутбук на Threadripper! 

На этом можно было бы и остановиться, но все самое интересное оказалось впереди. 

Когда я гонял тесты, сначала всегда были следующие шаги: полностью стереть папку boost с диска и по новой распаковать туда архив с исходниками (при компиляции в оригинальной директории оказывается куча промежуточных файлов, которые валяются в разных местах и которые не очень удобно каждый раз вычищать руками). Сейчас мы говорим про zip архив, который занимает 190 Мб, содержит 70+ тысяч файлов и распаковывается примерно на 700 Мб. А распаковывается он на SSD диск настолько долго, что, в конце-концов, я обратил на это внимание как на сильно раздражающий фактор.
Присмотревшись, сначала я подумал, что распаковка в любимом Total Commander каким-то образом даже задействует многопоточность, но потом понял, что то, "что мы принимали за оргазм, оказалось астмой" и высокая CPU загрузка есть следствие агрессивной работы антивируса по свежесоздаваемым файлам... И тут меня посетила креативная мысль "а что если?...". Почему, блин, в 2022 году zip файлы до сих пор распаковываются только в один поток? 

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

***

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

Одна из самых популярных C/C++ библиотек в мире -- библиотека zlib, которая реализует inflate/deflate алгоритмы, лежащие в основе zip архивации. Еще внутри zlib есть маленький проект minizip, который демонстрирует, как использовать zlib для работы с архивами. Проект, не претендующий на что-то серьезное, сделанный скорее в качестве proof-of-concept. 
Я про minizip знал и первым делом пошел смотреть его. Тут мне сразу не понравилось API, которое предоставляло только последовательную навигацию по записям в архиве, а значит не сильно ложилось на мою изначальную идею разделения работы просто по индексам.  

Изначально трезво оценивая статус minizip, я не сильно на него и рассчитывал. Думал, что наверняка ж в природе существует надежная, удобная, быстрая и с хорошим API библиотека для работы с самым популярным форматом архивов в мире! Гугление сразу подсказывало такую -- libzip называется. Используется повсеместно, от продуктов Adobe до Google Chrome. 

API этой библиотеки приглянулся сразу. У открытого архива можно сразу по индексу получить доступ к любой записи -- то, что доктор прописал. Правда, про многопоточность было написано что-то невеселое, мол используйте исключительно в связке с мютексом, но я рассуждал так: раз записей можно открыть сколько хочешь одновременно, значит у каждой есть свое конкретное, ни с кем не разделяемое состояние. С архивом я буду работать в режиме чтение, так что почему бы всей этой истории не работать себе спокойно в любое количество потоков без синхронизации?  

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

Взяв libzip я начал с того, что написал линейное однопоточное извлечение всех данных из архива в память. На моем любимом boost_1_80_0.zip и рабочем ноутбуке это решение работало со скоростью 2300 ms, что вселяло определенные надежды, с учетом того, что Total Commander мурыжил этот архив целую вечность... Далее я написал многопоточную версию с диапазонами индексов и... она сразу же упала. Таки да, в таком режиме оно почему-то не работало, как и предупреждали в документации. Разумеется, мютекс использовать было совершенно бессмысленно, он съел бы весь прирост от многопоточности. 

Ладно, думаю, на хитрую жопу и хрен волшебный. Решил в каждом потоке создавать свой экземпляр архива и отрабатывать записи по индексам уже на них. Посмотрел на цифры. В четыре потока я не получил даже 2x прироста (результат ~1400 ms), что явно указывало на какую-то серьезную проблему. Посмотрел в исходниках библиотеки как работает открытие файла по индексу -- вроде нормально, сложности O(n) нет. Тогда я решил проверить, сколько стоит открыть архив и увидел крайне неприятную картину -- целых 350 ms!  Это тот "налог", который должен заплатить каждый поток перед тем, как сделать хоть что-то полезное, и, очевидно, что это слишком дорогая плата.  

Тут стоит сделать маленькое лирическое отступление по поводу формата zip файлов.
Да, ты сразу знаешь количество записей в архиве, но ты не можешь получить моментальный доступ к записи по ее индексу, т.к. каждая запись содержит ее имя (очевидно, переменной длины), поэтому что-то делать с записью N можно только после того, как ты последовательно пробежал по таблице с информацией о предыдущих N-1 записей.
Понятное дело, что если ваш API позволяет обраться к записи по индексу, то никто не будет каждый раз бежать по архиву, запись за записью, что найти нужную -- почти всегда, при открытии архива, сразу строят специальную таблицу, которая позволяет моментально найти запрошенный индекс. Самая аскетичная таблица такого рода содержит просто массив смещений в файле и каждый элемент в ней указывает на начало информации о записи N. Но полет фантазии тут, ясное дело, не ограничен, т.к. в эту таблицу можно скопировать массу полезной информации о записи, включая ее имя (еще и, в придачу, конвертированное сразу в unicode). Очевидно, что на архиве в 100 файлов построение такой таблицы при открытии -- фактор малозначительный, но вот если записей в архиве под 100 тысяч, то тут все становится сильно интереснее... 

Я догадываюсь, насколько скучно все это читать...

Короче, на этом этапе я понял, что libzip точно отпадает, уж больно дорогое у него построение таблицы на открытие архива. Нужно что-то такое же, но с перламутровыми пуговицами. Пошел смотреть альтернативы, коих, с учетом популярности темы, должно было быть предостаточно. А по факту оказалось, что нет. В природе существует примерно с полдюжины более менее самостоятельных решений по работе с zip архивами на C или C++, все остальное многообразие представляет собой либо фасады к ним, либо перепевки известных песен, в которых легко угадываются оригиналы. Нескромно считаю, что я пересмотрел практически все варианты, включая решения "оптимизированные для embedded" (по факту -- глючно переделанный все тот же minizip).  

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

В итоге прикрутил minizip и посмотрел на цифры. Полный процессинг данных архива -- 2100 ms. Просто последовательный проход по всем записям -- 120 ms. Уже веселее, чем 350 ms libzip на открытие, но, на самом деле, я до последнего не хотел связываться с minizip'ом, потому что он явно написан ногами и там много мест, которые должны были работать неприлично медленно. Решил посмотреть на исходники повнимательнее и решить, что с этим делать. 

Главная проблема minizip -- крайне неэффективная вычитка любых структур из файла. Они всегда вычитываются буквально по байту. Т.е. надо прочитать два dword'а -- будет восемь (!) чтений по байту из файла и побитовая из склейка в dword'ы. А всяческих структур в zip файлах хватает! 
На первом этапе я заменил все такого рода функции вычитки простых типов на одно обращение к файлу и убрал склейку битов (чем, разумеется, сломал код для платформ с big endian). И эта переделка уже дала заметный прирост при навигации по записям. 
На втором этапе -- просто вычитал весь файл архива сразу в память и таком образом убрал вообще все обращения к файловой системе. Понятно, что почти всегда данные брались из буфера/кэша, но сам факт обращения к функции ОС дико бил по производительности. 
Итоги таких нехитрых переделок: время прохода по всем записям упало со 120 ms до 8 ms, время полного извлечения данных снизилось c 2100 до 1600 ms. Однозначный profit!

Следующая оптимизация -- выкидывание двух выделений памяти в куче при каждой операции открытия текущей записи. Аллокации в куче это всегда плохо -- фрагментация, время на поиск нужного блока, блокировки против других потоков, которые тоже пытаются выделить память. Больше одной записи в minizip все равно открыть нельзя, это можно сделать только с текущей, поэтому какой смысл каждый раз под это открытие выделять два буфера, а потом их освобождать? Я перенес манипуляции с этими буферами сразу в места открытия и закрытия архива. И самое удивительное во всей этой истории, что по итогу программа стала процессить данные чуть медленнее, чем раньше. На несколько процентов, но медленнее. Честно говоря, объяснения этому феномену я так и не нашел до сих пор, но эту оптимизацию пришлось откатить. 

Еще один, к сожалению, не сработавший трюк, я назвал "clone".
Идея простая -- в начале работы каждого потока он должен "прошагать" архив до нужной записи с которой должен начать делать что-то полезное. Это далеко не бесплатная операция и для половины потоков (которым предназначена работа во второй половине архива) это стоит как минимум 4 ms каждому. А почему бы не прошагать весь архив только один раз, на этапе планирования работы, и в нужных точках (когда позиция стоит на нужной для потока начальной записи) сделать копию состояния объекта, который отвечает за работу с архивом, и передать в поток такую вот копию для взаимодействия? По факту, результаты с такой вот оптимизацией оказались плюс-минус такими же как и без нее. 

Ну и последняя, очень важная оптимизация, которая оказалась не связанной с изменениями в исходниках minizip. Когда я придумывал схему деления работы по индексам, я исходил из того, чтобы минимизировать взаимодействие между потоками, т.к. это требует синхронизации, а значит не бесплатно. Если сразу задан набор индексов, то поток его просто перемалывает вообще не обращая внимания на соседей. Но в такой схеме есть пара нехороших моментов. 
Первое -- файлы в архиве имеют разный размер, поэтому работа потокам достается в виде порций неравной величины и, очевидно, это отрицательно сказывается на итоговом результате (в моем любимом boost_1_80_0.zip подавляющее большинство файлов имеют размер в несколько килобайт, но есть один красавец размером в 8 Мб).  
Второе, не менее важное -- кэш. Записи в файле архива лежат последовательно, поэтому когда ты разбиваешь работу на N независимых участков, ты максимально неэффективно используешь кэш процессора, который должен закрывать максимально большое количество независимых областей. Записи стоит обрабатывать последовательно, тогда и нагрузка на потоки будет выравненной, и кэш будет обслуживать только одну горячую зону, в которой сосредоточена работа практически всех потоков. Хотя понятно, что тут уже появляется нехороший момент согласования работы в процессе между потоками, которого не было в старой схеме с индексами. 
Эта оптимизация при работе в многопоточном режиме дала +25% прироста скорости. 

В итоге распаковка данных архива в память на i5-12600K в один поток занимает 1340 ms, а с работой на все 16 ядер -- 160 ms. Коэффициент ускорения от многоядерности получается 8.4x, что меньше идеальных 10x, но тоже не плохо. Вообще работа с декомпрессией данных очень сильно зависит от скорости памяти и кэша. Полагаю, что именно этот момент не дает по полной программе использовать вычислительный потенциал процессора.   

***

Но самое интересное я оставил на финал.
Научившись выжимать максимум на этапе декомпрессии данных, я начал реализовывать сохранение данных на диск. Это придавало существенный практический аспект всем моим изысканиям. 
И вот тут меня ждал большой облом. После добавления сохранения данных на диск, на своем рабочем ноутбуке я получил суммарное время 43 секунды, из которых непосредственно распаковка всех данных в память занимала аж целых 350 ms... Прекрасная иллюстрация к хрестоматийному тезису: оптимизировать нужно только то, на что показывают реальные результаты профилирования. 

Почесав затылок, я решил, смеха ради, попробовать и сохранение данных сделать в несколько потоков. Результаты меня приятно поразили -- при сохранении в 10 потоков я получил итоговое время на полную обработку архива в 10.6 секунд. Ого! Работа с диском ускорилась в четыре раза!  

Перенес эксперимент с ноутбука на домашний компьютер... Однопоток сохраняет данные за 26.5 секунд. Любые игры с распараллеливанием позволяет сэкономить от силы лишь пару секунд. 
Самые догадливые уже наверняка поняли в чем тут дело. На домашней машине у меня стоит обычный SSD, а на ноутбуке -- M.2 NVMe, который умеет показывать такие вот чудеса производительности на параллельных потоках данных... 

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

Вместо итогов. В конце этой истории я снова запустил распаковку в Total Commander (для того, чтобы убедиться, что мой код корректно распаковывает все данные из архива) и измерил суммарное время... 102 секунды! Хрен его знает, почему там все так плохо, моя однопоточная реализация делает это в два с половиной раза быстрее. Но главное, это то, что многопоток, который умеет выжимать все соки из процессора и (главное!) из NVMe, дает результат на порядок быстрее!  
Мораль из всего этого будет такая: парадигма многоядерности, в которой мы живем уже почти два десятка лет, штука не такая уж и простая, поэтому вокруг нас до сих пор масса решений и программ, которые не умеют учитывать все особенности работы современного железа и выжимать из него максимум.  

зы. Разрозненное... 

#1. По ходу пьесы пытался оценить фактор антивируса. Тот, который встроен в Windows 10, кушает где-то 5% от итогового результата, что при компиляции, что при распаковке архива.
Даж не знаю, какую давать этому оценку, много это или мало. 

#2. Фокус с параллельной распаковкой работает далеко не со всеми форматами архивов. Часто, для достижения хорошего сжатия, группа однотипных файлов сжимается на основе единого словаря. В этом случае декомпрессию можно выполнять только в последовательном режиме, запись за записью, так как они зависят друг от друга. 
К примеру rar в режиме solid перепаковал boost_1_80_0.zip с выигрышем в 40%! 

#3. Работа c файловой системой в minizip "виртуализирована" через набор указателей на функции. Это и позволило легко переключиться с фактической работы с файлом на работу с регионом памяти, куда этот файл был загружен (угу, использование техники "memory mapped file" тут было бы весьма уместным). 
Так вот, эти косвенные вызовы функций через указатели наверняка отъедают лишние такты, особенно с учетом того, насколько неэффективно вычитываются структуры данных безо всяких попыток явной буферизации. В идеале, стоило бы переписать minizip в виде плюсового класса, а доступ к содержимому архива представить в виде обращений к классу-шаблону. При работе с памятью это все было бы очень красиво заинлайнено.  

#4. Хотелось бы увидеть работу моей программы на топовом M.2 накопителе. Таком, чтобы с блекджеком и PCIe 4.0. Думаю, тут реально все распаковать буквально за пару секунд.