26 February

Объяснение: почему wc на Haskell оказался «быстрее» аналога на С

High performanceProgrammingHaskellC


После недавних статей (№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 всё-таки оказалась быстрее ;)


Подтверждение результатов и выводов для ghc 8.8.3 и на текстах Шекспира (2020-02-27)

В комментариях была высказана критика:


  1. Использования относительно старой версии Хаскель-компилятора и отсутствие результатов при использовании LLVM.
  2. Отсутствие результатов для актуальных версий gcc и clang.
  3. Искусственность, неестественность теста на случайных данных.
  4. Утверждение о том, что на "Шекспире" реализация на Haskell не замедлялась и (следовательно) результаты и выводы не верны.
  5. Отсутствие результатов системной 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 есть.

Tags:бессмысленные бенчмаркиChaskellхоливары
Hubs: High performance Programming Haskell C
+133
26.9k 68
Comments 158
Ads
Popular right now