После недавних статей (№10xd34df00d, №2chapuza, №3picul) сравнивающих скорость работы реализаций упрощенной утилиты wc у меня оставался только один вопрос — Как простая реализация на Haskell оказалась быстрее простой реализации на C ?!
2020-02-27: Подтверждены результаты и выводы для ghc 8.8.3 и на текстах Шекспира (в конце под спойлером).
Кратко напомню ТЗ
Для текстового файла размером 1.8Гб (1_871_822_210 байт) необходимо посчитать количество строк, слов и символов. С рядом упрощений: только 8-битная кодировка символов, конец строк только в стиле Unix, границами слов считаются пробелы и все символы меньше Char(14), чтение только из файла (допустимо отображение в память).
Region,Country,Item Type,Sales Channel,Order Priority,Order Date,Order ID,Ship Date,Units Sold,Unit Price,Unit Cost,Total Revenue,Total Cost,Total Profit
Sub-Saharan Africa,South Africa,Fruits,Offline,M,7/27/2012,443368995,7/28/2012,1593,9.33,6.92,14862.69,11023.56,3839.13
Middle East and North Africa,Morocco,Clothes,Online,M,9/14/2013,667593514,10/19/2013,4611,109.28,35.84,503890.08,165258.24,338631.84
Australia and Oceania,Papua New Guinea,Meat,Offline,M,5/15/2015,940995585,6/4/2015,360,421.89,364.69,151880.40,131288.40,20592.00
Sub-Saharan Africa,Djibouti,Clothes,Offline,H,5/17/2017,880811536,7/2/2017,562,109.28,35.84,61415.36,20142.08,41273.28
Europe,Slovakia,Beverages,Offline,L,10/26/2016,174590194,12/4/2016,3973,47.45,31.79,188518.85,126301.67,62217.18
Asia,Sri Lanka,Fruits,Online,L,11/7/2011,830192887,12/18/2011,1379,9.33,6.92,12866.07,9542.68,3323.39
Sub-Saharan Africa,Seychelles ,Beverages,Online,M,1/18/2013,425793445,2/16/2013,597,47.45,31.79,28327.65,18978.63,9349.02
Sub-Saharan Africa,Tanzania,Beverages,Online,L,11/30/2016,659878194,1/16/2017,1476,47.45,31.79,70036.20,46922.04,23114.16
Sub-Saharan Africa,Ghana,Office Supplies,Online,L,3/23/2017,601245963,4/15/2017,896,651.21,524.96,583484.16,470364.16,113120.00
Sub-Saharan Africa,Tanzania,Cosmetics,Offline,L,5/23/2016,739008080,5/24/2016,7768,437.20,263.33,3396169.60,2045547.44,1350622.16
Asia,Taiwan,Fruits,Offline,M,2/9/2014,732588374,2/23/2014,8034,9.33,6.92,74957.22,55595.28,19361.94
Middle East and North Africa,Algeria,Cosmetics,Online,M,2/18/2011,761723172,2/24/2011,9669,437.20,263.33,4227286.80,2546137.77,1681149.03
Asia,Singapore,Snacks,Online,C,1/28/2013,176461303,2/7/2013,7676,152.58,97.44,1171204.08,747949.44,423254.64
Australia and Oceania,Papua New Guinea,Clothes,Offline,L,6/20/2011,647164094,7/14/2011,9092,109.28,35.84,993573.76,325857.28,667716.48
Asia,Vietnam,Personal Care,Online,M,4/4/2010,314505374,5/6/2010,7984,81.73,56.67,652532.32,452453.28,200079.04
Sub-Saharan Africa,Uganda,Personal Care,Online,M,6/19/2014,539471471,7/21/2014,451,81.73,56.67,36860.23,25558.17,11302.06
Sub-Saharan Africa,Zimbabwe,Office Supplies,Offline,C,3/28/2011,953361213,4/8/2011,9623,651.21,524.96,6266593.83,5051690.08,1214903.75
Sub-Saharan Africa,Ethiopia,Cosmetics,Online,M,7/7/2011,807785928,7/25/2011,662,437.20,263.33,289426.40,174324.46,115101.94
Europe,France,Cosmetics,Online,M,12/7/2015,324669444,1/18/2016,5758,437.20,263.33,2517397.60,1516254.14,1001143.46
Ранее полученные результаты
"Зачётное" время конечно зависит от машины, компилятора и опций сборки. Поэтому я буду использовать только значения полученные локально и собственноручно на престарелом i7-4600U CPU @ 2.10GHz. В том числе поэтому я использовал не последние версии компиляторов — мне так было удобнее и от этого ничего принципиально не меняется. На всякий упомяну, что для исключения влияния обмена с диском файл с данными размещался в /dev/shm/ (tmpfs).
Для начала результаты "попавшие в зачёт", с учетом ограниченных возможностей Haskell-компилятора (не умеет автовекторизацию, оптимизацию для конкретной модели CPU):
| Реализация | Сборка | Результат в секундах |
|---|---|---|
Системная утилита wc |
- | 19.416 |
| на Haskell | ghc 8.0.2, -O2 | 2.811 |
| простая на С | gcc 8, -Ofast | 3.067 |
| оптимизированная переносимая на С | gcc 8, -Ofast | 0.637 |
Не удивительно, что оптимизированная человеком (мной) С-версия существенно быстрее простой реализации на Haskell. Но меня заинтересовало почему простая реализация на С всё-таки уступает "Хаскелю". Конкретно в этих моих тестах с использованием не последней версии ghc результаты отличаются незначительно (2.811 < 3.067), но при использовании актуальной версии компилятора Haskell отношение получается примерно 2:3 в пользу Haskell. Всё это сподвигло меня на выяснения причин.
Тем не менее, для полной картины сначала стоит показать остальные результаты. Включая получаемые как просто включением оптимизации под конкретный процессор, так и ручным кодированием с использование интринсиков AVX2:
| Реализация | Сборка | Результат в секундах |
|---|---|---|
| на Haskell | ghc 8.0.2, -O2 -mavx2 | 2,789 |
| простая на С | gcc 8, -Ofast -march=haswell | 2.914 |
| простая на С | clang 8, -Ofast -march=haswell | 1.124 |
| оптимизированная переносимая на С | gcc 8, -Ofast -march=haswell | 0.634 |
| оптимизированная AVX2 на С | gcc 8, -Ofast -march=haswell | 0.269 |
Здесь стоит отметить, что включение AVX2 не повлияло на результат реализации на Haskell, а вот clang сделал автовекторизацию (что легко увидеть в CompilerExplorer), за счёт чего скорость увеличилась более чем вдвое. В свою очередь, оптимизированная вручную версия с AVX2 по скорости ожидаемо приближается к пропускной способности памяти.
Смотрим внутрь кода из-под Haskell
Собственно я не собирался глубоко лезть к дракону в ж анализировать результат работы компилятора. Мне было интересно посмотреть на самый внутренний цикл, в котором происходит посимвольная обработка и понять почему вдруг Хаскель оказался быстрее.
Поигравшись с опциями я пришел к выводу, что получить самый подходящий для анализа код позволяет опция -ddump-asm. Из исходника wc.hs генерируется примерно 24К ассемблерного кода. По-быстрому увидеть глазами нужный цикл не получилось, но grep cmp позволил быстро локализовать релевантные инструкции сравнения: cmpq $33,%rbx; cmpq $32,%rbx; cmpq $10,%rbx; cmpb $4,%bl. После этого было легко найти искомый цикл.
Достаточно быстро я понял в чём дело и набросал на С примерный аналог генерируемого Хаскель-компилятором цикла обработки. Рисовать блок схему мне показалось излишним и менее выразительным чем просто привести код на C:
static _Bool process_chunk(const unsigned char *text, const size_t bytes,
_Bool prev) {
result.chars += bytes;
for (size_t i = 0; i < bytes;) {
if (text[i] > ' ') {
// под-цикл по "словам"
result.words += !prev;
prev = 1;
while (++i < bytes && text[i] > ' ')
;
} else {
// под-цикл по пробелам
prev = 0;
do {
_Bool non_space = text[i] != ' ' && text[i] - 9 > 4;
result.words += !prev && non_space;
result.lines += text[i] == '\n';
prev = non_space;
}
while (++i < bytes && text[i] <= ' ');
}
}
return prev;
}Этот код упрощен ради демонстрации сути Haskell-цикла, но работает корректно без лишних накладных расходов и налогов на абстракцию. Давайте посмотрим насколько это будет быстро, добавив для наглядности "зачётные" показатели:
| Реализация | Сборка | Результат в секундах |
|---|---|---|
| на С по мотивам Haskell | gcc 8, -Ofast | 1.331 |
| на Haskell | ghc 8.0.2, -O2 | 2.811 |
| простая на С | gcc 8, -Ofast | 3.067 |
| оптимизированная переносимая на С | gcc 8, -Ofast | 0.637 |
Совершенно "внезапно" сгенерированный Haskell-компилятором код, но реализованный на С оказался вдвое быстрее! На всякий случай, ещё раз напомню, что новый ghc вероятно покажет результат немного лучше.
Теперь можно проанализировать почему реализация на Haskell оказалось быстрее простой реализации на C, а заодно ещё раз посмотреть на тестовые данные (под спойлером в самом начале):
- Следуя простейшим правилам
ghcстал преобразовывать decision tree по значению символов, одновременно пытаясь минимизировать переходы. В результате разделил обработку на два суб-цикла: для символов "больше пробела" и "меньше или равно пробелу". - Суб-цикл по символам "больше пробела" не меняет состояния, не имеет внутренних зависимостей по данным и поэтому выполняется существенно быстрее второго под-цикла. Чем больше средняя длина слов, тем быстрее будет работать такой код, а одно "слово" в 1.8 Гб будет идеальным вариантом ;)
- Если посмотреть на тестовые данные, то там подавляющее большинство символов больше пробела. Более того, "пробельные" символы идут по-одному (фактически это только пробелы и переводы строк). Поэтому предсказание переходов работает очень хорошо — только по одному промаху на каждое слово.
Если немного присмотреться к результатам, то легко увидеть что средняя длина слова 1871822210 / 44774631 = 41.8 символов, а строка в среднем состоит из 44774631 / 15000000 = 2.98 слов.
Фактически тестовые данные подобраны крайне удачны именно для обработки кодом сгенерированным Хаскель-компилятором. Если взять текст с более-менее случайным распределением пробелов, то предсказание переходов будет ошибаться и результат будет значительно хуже. Проверим?
Получим 1.8 Гб случайных данных (3068561 * 610 = 1871822210):
$ dd if=/dev/urandom of=/dev/shm/rand.dat bs=3068561 count=610Стоит пояснить, что получаемый "случайный мусор" с точки зрения задачи является абсолютно корректными данными и при этом его статистические показатели гораздо ближе к тому, что мы называем "текстом" в контексте задачи. Средняя длина слова составляет 1871822210 / 210195110 = 8.9, а остальные параметры не важны. Конечно, такой "текст" отличается по массе параметров от естественного языка и не является идеальным тестовым набором. Но очевидно, что этот "текст" гораздо ближе к здравому смыслу чем первоначальные данные со средней длиной слова в 41 символ. Теперь посмотрим каковы будут итоговые "зачётные" показатели на таких данных:
| Реализация | Сборка | Результат в секундах |
|---|---|---|
| на С по мотивам Haskell | gcc 8, -Ofast | 1.331 => 3.532 |
| на Haskell | ghc 8.0.2, -O2 | 2.811 => 4.812 |
| простая на С | gcc 8, -Ofast | 3.062 => 3.071 |
Вариант на С по мотивам Хаскель-кода замедлился сильнее всего — это следствие намеренного упрощения кода ради наглядности и демонстрации проблемы. Реализация на Хаскель замедлилась не столь сильно, но теперь она существенно медленнее самого простого кода на C. А скорость наивной реализации на С ожидаемо не изменилась.
Получается что реализация на Haskell оказалась быстрее благодаря "удачности" тестовых данных, которые просто маскировали недостаток. Соответственно, результаты показанные в первой статье не отражает реального положения дел, а самая простая реализация на C всё-таки оказалась быстрее ;)
В комментариях была высказана критика:
- Использования относительно старой версии Хаскель-компилятора и отсутствие результатов при использовании LLVM.
- Отсутствие результатов для актуальных версий gcc и clang.
- Искусственность, неестественность теста на случайных данных.
- Утверждение о том, что на "Шекспире" реализация на Haskell не замедлялась и (следовательно) результаты и выводы не верны.
- Отсутствие результатов системной
wcна случайных данных.
Как видите я решил устранить эти замечания и окончательно поставить все точки над всеми Ё. Для этого было проведено два забега на другой машине с i7-7820HQ CPU @ 2.90GHz под управлением 64-битной версии Fedora 31.
Для первого теста был взят текст произведений Шекспира объемом 5_777_367 байт. Этот текст был "зачитан до дыр" для получения объема порядка 1.8Гб:
$ wget http://www.gutenberg.org/files/100/100-0.txt
$ for i in `seq 1 333`; do cat 100-0.txt >> test.txt; doneВ результате получился текстовый файл размером 1_923_863_211 байт. Давайте посмотрим насколько Хаскель и C любят Шекспира:
| Реализация | Сборка | Результат в секундах |
|---|---|---|
Системная утилита wc |
- | 12.687 |
| на С по мотивам Haskell | gcc 9.2.1, -Ofast | 4.947 |
| на С по мотивам Haskell | clang 9.0.1, -Ofast | 4.689 |
| на Haskell | ghc 8.8.3, -O3 | 6.339 (!) |
| на Haskell | ghc 8.8.3, -O3 -fllvm | 4.893 (!) |
| простая на С | gcc 9.2.1, -Ofast | 2.445 |
| простая на С | clang 9.0.1, -Ofast | 2.347 |
Результаты для случайных данных из /dev/urandom размером 1_871_822_210 байт:
| Реализация | Сборка | Результат в секундах |
|---|---|---|
Системная утилита wc |
- | 16.878 |
| на С по мотивам Haskell | gcc 9.2.1, -Ofast | 3.322 |
| на С по мотивам Haskell | clang 9.0.1, -Ofast | 3.344 |
| на Haskell | ghc 8.8.3, -O3 | 3.976 |
| на Haskell | ghc 8.8.3, -O3 -fllvm | 2.513 |
| простая на С | gcc 9.2.1, -Ofast | 2.376 |
| простая на С | clang 9.0.1, -Ofast | 2.244 |
Последняя версия ghc 8.8.3 не показала видимых различий от 8.0.2, но подключение LLVM (в данном случае 9.0.1) действительно дало ускорение. Тем не менее, простая реализация на C по-прежнему быстрее, а в случае естественного текста существенно быстрее. "Вильям Шекспир" не только подтвердил корректность вчерашнего теста на данных из /dev/urandom, но и оказался тяжелее.
Отдельно стоит отметить, что совершенно не подтвердилась информация от 0xd34df00d, о том что реализация на Haskell обрабатывала тексты Шекспира с той же скоростью что и тестовые данные из первой статьи. Напротив, замедление налицо и оно больше чем на случайных данных.
Таким образом, все результаты и выводы еще раз подтверждены, а сомнения полностью развеяны.
Дисклаймер: Этот статья написана не для того чтобы показать "тормознутось" Хаскеля или "превосходство" C (ибо у каждого языка свое назначение), но чтобы обратить внимание: чуть менее чем все подобные "хайповые" бенчмарки и сравнения содержат достаточно недочётов чтобы не принимать их всерьёз. При этом всё же уместно напомнить тезис, что языки без zero cost abstraction никогда не смогут конкурировать по скорости кода с теми, где zero cost abstraction есть.
