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

После недавних статей (№10xd34df00d, №2chapuza, №3picul) сравнивающих скорость работы реализаций упрощенной утилиты wc у меня оставался только один вопрос — Как простая реализация на Haskell оказалась быстрее простой реализации на C ?!

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

Кратко напомню ТЗ

Для текстового файла размером 1.8Гб (1_871_822_210 байт) необходимо посчитать количество строк, слов и символов. С рядом упрощений: только 8-битная кодировка символов, конец строк только в стиле Unix, границами слов считаются пробелы и все символы меньше Char(14), чтение только из файла (допустимо отображение в память).

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

"Зачётное" время конечно зависит от машины, компилятора и опций сборки. Поэтому я буду использовать только значения полученные локально и собственноручно на престарелом i7-4600U CPU @ 2.10GHz. В том числе поэтому я использовал не последние версии компиляторов — мне так было удобнее и от этого ничего принципиально не меняется. На всякий упомяну, что для исключения влияния обмена с диском файл с данными размещался в /dev/shm/ (tmpfs).

Для начала результаты "попавшие в зачёт", с учетом ограниченных возможностей Haskell-компилятора (не умеет автовекторизацию, оптимизацию для конкретной модели CPU):

Не удивительно, что оптимизированная человеком (мной) С-версия существенно быстрее простой реализации на Haskell. Но меня заинтересовало почему простая реализация на С всё-таки уступает "Хаскелю". Конкретно в этих моих тестах с использованием не последней версии ghc результаты отличаются незначительно (2.811 < 3.067), но при использовании актуальной версии компилятора Haskell отношение получается примерно 2:3 в пользу Haskell. Всё это сподвигло меня на выяснения причин.

Тем не менее, для полной картины сначала стоит показать остальные результаты. Включая получаемые как просто включением оптимизации под конкретный процессор, так и ручным кодированием с использование интринсиков AVX2:

Здесь стоит отметить, что включение 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-компилятором код, но реализованный на С оказался вдвое быстрее! На всякий случай, ещё раз напомню, что новый 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 символ. Теперь посмотрим каковы будут итоговые "зачётные" показатели на таких данных:

Вариант на С по мотивам Хаскель-кода замедлился сильнее всего — это следствие намеренного упрощения кода ради наглядности и демонстрации проблемы. Реализация на Хаскель замедлилась не столь сильно, но теперь она существенно медленнее самого простого кода на C. А скорость наивной реализации на С ожидаемо не изменилась.

Получается что реализация на Haskell оказалась быстрее благодаря "удачности" тестовых данных, которые просто маскировали недостаток. Соответственно, результаты показанные в первой статье не отражает реального положения дел, а самая простая реализация на C всё-таки оказалась быстрее ;)

$ wget http://www.gutenberg.org/files/100/100-0.txt
$ for i in `seq 1 333`; do cat 100-0.txt >> test.txt; done