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






После недавних статей (№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 есть.

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (135):

  1. 0xd34df00d
    /#21322702 / +2

    Прям не ожидал такой серии статей, любо-дорого читать!


    В том числе поэтому я использовал не последние версии компиляторов — мне так было удобнее и от этого ничего принципиально не меняется.

    У меня есть опыт, когда апгрейд ghc на одну мажорную версию вперёд (т. е. ЕМНИП 8.2 > 8.4) улучшил производительность одной кодовой базы на 30%. А у вас 8.0, это очень старая версия. Я своё не зря собирал 8.8.


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

    Она, увы, показывает то, что генерирует родной ghc'шный кодген, а я во всех дальнейших экспериментах использовал LLVM.


    По-быстрому увидеть глазами нужный цикл не получилось, но grep cmp позволил быстро локализовать релевантные инструкции сравнения: cmpq $33,%rbx; cmpq $32,%rbx; cmpq $10,%rbx; cmpb $4,%bl.

    Снимаю шляпу. Я грепал по cmp.*$32 (чтобы найти сравнения с пробелом), но что-то адекватное у меня не нагрепалось за то время, что я был готов на это потратить.


    Другое дело, что я искал в дизасме готового бинарника, а не в дампе.


    Совершенно "внезапно" сгенерированный Haskell-компилятором код, но реализованный на С оказался вдвое быстрее! На всякий случай, ещё раз напомню, что новый ghc вероятно покажет результат немного лучше.

    Я бы даже сказал «намного лучше».


    Взял вашу версию «на C по мотивам Haskell», схоронил в файл main3.c, запустил на той же машине, где все прочие эксперименты:


    7:18:09 d34df00d@build2 ~/hwc % clang -O3 main3.c -o main3 && ./main3 /var/tmp/portage/test.txt
    lines 15000000, words 44774631, chars 1871822210
    took 1.382212 seconds

    У gcc ещё хуже.


    Время работы хаскель-версии на этой машине, напомню, 1.45 с.


    На всякий стоит показать что такой "рандомный" текст имеет гораздо лучшие статистические показатели: средняя длина строки 1871822210 / 7313229 = 255.95, средняя длина слова 1871822210 / 210195110 = 8.9, количество слов в строке 210195110 / 7313229 = 28.74. Эти значения можно вывести по теории вероятности, но для проверки стоило сверить реально получаемые значения с теоретическими. Такой тестовый набор представляется мне гораздо ближе к реальности (по средней длине слов и строк), чем первоначальные тестовые данн

    Ничего не хочу сказать, но обычный человекочитаемый текст, на который чаще всего и натравливают wc, сгенерирован не случайным образом, и имеет характеристики, несколько отличные от случайного.

    • yleo
      /#21324614

      Вероятно у меня будет время чтобы добавить результаты от более новых компиляторов из Fedora 31 на чуть более современно процессоре.

    • Antervis
      /#21326174

      Если немного присмотреться к результатам, то легко увидеть что средняя длина слова 1871822210 / 44774631 = 41.8 символов, а строка в среднем состоит из 44774631 / 15000000 = 2.98 слов.

      Ничего не хочу сказать, но обычный человекочитаемый текст, на который чаще всего и натравливают wc, сгенерирован не случайным образом, и имеет характеристики, несколько отличные от случайного.

      смею предположить, что распределение длины реальных слов должно быть ближе к Максвелловскому, а распределение длины случайного числа точно экспонента. Однако медианная длина слова в ваших тестовых данных тоже шибко далека от реальности так что оба хороши. С длиной строк так же, но там менее важно — средняя строка должна быть достаточно длинной чтобы не париться по поводу миспредиктов. Я бы конечно подставлял литературный текст, а не генерировал, но это от лени чтобы быть максимально точным.

      • yleo
        /#21326334

        Скорость хаскель-кода зависит только от средней длины слов, а картина распределения как и длина не играет роли (с поправкой что слово не может быть длиннее строки). Видимо это не очевидно и (соответственно) должно быть явно разъяснено в статье. Поэтому я намерено ушел от поиска "идеального" текста в качестве тестовых данных. По той же причине оба замечания беспочвенны.


        Использование данных /dev/urandom абсолютно оправдано и неплохо иллюстрирует недостаток хаскель-кода, тогда как первоначальные данные этот недостаток маскируют — это главное. Случайные данные не являются идеальным тестовым набором, но использование "идеального текста" (какой он и почему именно такой?) будет скорее перфекционизмом.

        • Antervis
          /#21326908

          … а картина распределения как и длина не играет роли...
          играет. Бранч предиктор же тоже не совсем глупый и быстро адаптируется если ему подавать на вход, например, слова только из 8 символов разделенных единичными пробелами. Для вашего распределения бранч предиктор адаптируется на 9 знаков, а при миспредикте 10-й итерации гарантированно угадает на 11-й. А вот для векторизованного кода это не играет роли (условный переход для wasspace должен оптимизироваться, ну или его легко убрать вручную)

          • yleo
            /#21326940 / -2

            Вы несете чушь, потому что 9 знаков — это среднее значение случайной величины.

            • yleo
              /#21327170

              Вот интересно, какова логика минусующих?


              Даже если (вдруг, внезапно) бранч-предиктор адаптируется на 9 знаков, то для любой другой длины (а она случайна) он ошибётся.


              С пробелами ошибок будет меньше, ибо в большинстве случаев они будут одиночными. Однако, будут и не одиночные проблемные символы, в то время как в исходном тестовом наборе они всегда одиночные (и предиктор действительно будет это угадывать).

              • VolCh
                /#21327316

                "Вы несёте чушь" не всем могло понравиться

            • Antervis
              /#21328864

              Вы несете чушь, потому что 9 знаков — это среднее значение случайной величины.
              так у вас экспоненциальное распределение. Давайте на примере: для случайного числа в диапазоне [0..10000) есть 10 однозначных комбинаций (0..9), 90 двузначных (10..99), 900 трехзначных (100..999) и 9000 четырехзначных (1000..9999). Средняя длина числа получается (10*1 + 90*2 + 900*3 + 9000*4) / 10000 = 3.889, что очень близко к 4, т.е. максимальному значению

              Да и какая же это «чушь» если она подтвердилась вашими же экспериментами, кроме как для реализаций, которые компиляторы смогли векторизовать (о чем я тоже упоминал)?

              • yleo
                /#21329050

                Замечательно ;)


                Тогда покажите, пожалуйста, как средняя длина слов получилась 8.9, а не 42?


                Ну и какова средняя длина цепочек единичных бит (the runs of ones) в данных из /dev/urandom?

                • technic93
                  /#21329742

                  8.9 Это отношение пробельных символов ко всем.

                  • yleo
                    /#21329762

                    Нет, подумайте.


                    Для данных из /dev/urandom соотношение не-пробельных символов к пробельным (пробел и все что меньше 14) будет равно (256-14-1)/(1+14) = 16,06(6).

                    • technic93
                      /#21329798

                      А я посчитал — численно

                      • yleo
                        /#21329818

                        Не понял что вы посчитали и как.
                        Поясните.

                        • technic93
                          /#21330442

                          Сгенерировал случайный массив где вероятность нулей 1/N и вероятность единиц (N-1)/N. Получил что средняя длина слова из единиц N. Распределение длин слов экспоненциальное.

                          • yleo
                            /#21330896

                            Да, но чем меньше N чем хуже у бранч-предиктора с угадыванием переходов. Поэтому исходные тестовые данные с 40-буквенными словами искажали реальное положение дел, о чем собственно и написано в тексте статьти.


                            Короче, я уже примерно совсем не понимаю о чем разговор.
                            В статье говориться:


                            • первоначальные тестовые данные плохие (потому что очень длинные слова).
                            • просто "случайный мусор" будет честнее по длине слов и позволит увидеть проблему.
                            • перепроверка "Шекспиром" всё подтвердила.

                            Позволяют ли случайные данные что-то предсказывать бранч-предиктору?


                            • Да, конечно. ибо для всех условных переходов статистика существенно отличается от 50/50 (это изначально очевидно).

                            Позволяют ли случайные данные (со средней длинной слова 8.9) предиктору предсказывать переход на 9 символе?


                            • нет, потому что нет значимой статистической разницы.
                            • даже если будет генерироваться такое предсказание, то толку не будет.
                            • исходя их статистики предиктор будет предсказывать переходы в продолжение не-пробельных символов (их просто больше).

                            • technic93
                              /#21331296

                              Дискуссия уже далеко ушла от кода и перешла на статистику. К выводу статьи у меня вопросов нету.


                              Не понятно почему у вас все же 8.9 получается а у меня другое. Об этом были мои комментарии.
                              Я не уверен что бранч предиктор достаточно умный чтобы находить периоды во входных данных. Но если да, то как минимум дисперсия важна.

                              • yleo
                                /#21331856

                                А теперь понятно, а то я всё смотрел на это через предсказатель переходов.


                                Короче, по вашей наводке (спасибо) я понял что немного продолбал пока возился с /dev/urandom. Сначала при экспериментах я чистил выхлоп для получения ASCII-текста (посредством tr). Получил подтверждение гипотезы, перенес результаты в текст. Но после решил убрать "чистку" для упрощения, замерив результаты заново. Но вот цифры в выражении 1871822210 / 210195110 = 8.9 не обновил :(

                                • technic93
                                  /#21331866

                                  Окей, спасибо за развернутые ответы.

          • yleo
            /#21327166

            На всякий — все результаты и выводы подтвердились для ghc 8.8.3, LLVM-бакендом и на текстах Шекспира.
            См под спойлером в конце статьи.

            • technic93
              /#21328968

              Условный Шекспир это хорошо для 16го века, но нам в 21ом актуально логи условного nginx)

              • powerman
                /#21330446

                Только мне кажется, что Вы придираетесь? :)

                • technic93
                  /#21330504

                  Это же шутка была, я даже смайлик поставил в конце)

    • IvanBulb
      /#21326692 / -5

      Где реализация на GPU?
      каким образом за 0.2 сек читается файл на 1.8ГБ?)))

      нормальным временем для данной задачи будет только время РАВНОЕ чтению файла с диска)
      все остальное — мартышкин труд кодировщиков средней руки)))

      надо бы Короткевича позвать — как раз для него тема))

      • 0xd34df00d
        /#21326740 / +2

        Где реализация на GPU?

        А зачем? И почему не на FPGA?


        каким образом за 0.2 сек читается файл на 1.8ГБ?)))

        Из tmpfs у меня (и из эквивалентных механизмов у других авторов), как написано, наверное, в каждой статье.


        нормальным временем для данной задачи будет только время РАВНОЕ чтению файла с диска)
        все остальное — мартышкин труд кодировщиков средней руки)))

        Вопрос в том, сколько времени вы готовы на это потратить. И yleo, и picul очень хорошо постарались сделать версии с другим алгоритмом, с broadword programming, с SSE/AVX2, и так далее. Но это уже другой класс задач.


        Надо бы мне уже написать статью про моё впечатление от реакций на бенчмарки, где хаскель-код оказывается на уровне (или обгоняет) алгоритмически эквивалентный код на С. За последние полгода я узнал много интересного.

      • viirtus
        /#21326746

        Файл размещался в tmpfs (читай в RAM), о чём указано в статье.

    • yleo
      /#21327164

      Все результаты и выводы подтвердились для ghc 8.8.3, LLVM-бакендом и на текстах Шекспира.
      См под спойлером в конце статьи.

  2. Siemargl
    /#21322714 / +2

    Использование mmap это уже нечестный трик.

    Назвать программу переносимой с mmap? o_O
    Попробуй собери это на Windows

    И в общем и целом, 33 строчки на Хаскеле практически гораздо лучше, чем 90 (или 140) строк на С.

    • yleo
      /#21322776

      1. Никто не собирался делать это переносимым дальше POSIX и загромождать исходный код. Под "переносимостью" прежде всего подразумевалась отсутствие привязи к x86 (особенно всяческие SIMD).
      2. mmap() ничего не меняет, но остался по историческим причинам. Если аккуратно закомментировать, то всё должно работать (хотя я уже не помню проверял или нет).
      3. В windows есть CreateFileMapping() и MapViewOfFile(). Поправить элементарно, либо WSL.

      • ncr
        /#21324182

        Говорят, в Windows при последовательном чтении MapViewOfFile точно ничего не дает, а то и замедляет. Как в других ОС не знаю, но вряд ли сильно иначе.

        • qrck13
          /#21325052

          MapViewOfFile в Windows вообще убог. Linux-овый mmap позволяет спокойно отмапить файл в разы (а то и на порядки) превышающий по размеру оперативную память компьютера, и OS будет грамотно подменять странички по мере доступа. А MapViewOfFile будет сразу пытаться выделить обьем оперативки равный отмапливаемому участку, и если такого обьема нет свободно — отвалится с ошибкой.

          • VioletGiraffe
            /#21325940

            Странно. Я никогда не использовал голый WinAPI, но в нескольких проектах ускорял файловые операции с помощью Qt (QFile::map), и всегда это давало хороший прирост, в разных сценариях. И как раз недавно на скорую руку проверил, что возможно без проблем замапить 100 гигабайт (а физической памяти у меня втрое меньше).

            • lieff
              /#21326422

              Я тоже с проблемой выделения не сталкивался. Но вот с другой проблемой столкнулся недавно. Оказывается нельзя надежно выделить Magic Ring Buffer (то есть одну и ту же память смапить 2 раза подряд).


              Логичным решением было бы зарезервировать место VirtualAlloc с MEM_RESERVE и в это адресное пространство сделать MapViewOfFile 2 раза по фиксированному адресу.


              Так вот это не работает, область MEM_RESERVE надо обязательно сделать VirtualFree, что не дает гарантии что после освобождения это пространство кто другой в процессе не займет. Из за этого в либах делают итерации попыток: https://github.com/gnzlbg/slice_deque/blob/master/src/mirrored/winapi.rs#L78 и 100% гарантии что сработает тут нет.


              Если кто подскажет решение буду благодарен. Вообще странно что о такой простой вещи не подумали, и непонятно зачем вообще тогда нужна функциональность мапа по фиксированному адресу.

              • yleo
                /#21326550

                Не считая перехода на linux решение примерно одно: suspend-ить все треды (кроме текущего) перед VirtualFree() и resume-ть после окончания манипуляций. Работающую реализацию можно подсмотреть у меня в libmdbx (используется для ремапинга), ибо есть нюансы.


                То что qrck13 пишет о MapViewOfFile() иногда происходит из-за антивирусов (пытаются заглянуть в эти замепленные файлы).

                • lieff
                  /#21326628

                  А какой-нибудь APC не может произойти и выделить память? А так же всякие CreateRemoteThread и то что после CreateToolhelp32Snapshot может добавиться тред.
                  Ну то есть для целиком своего приложения наверно можно, но для генерик либы, что может встраиваться куда угодно, например в игру, где еще система защиты работает выглядит опасно.


                  На лине и маке да, такой проблемы нет.

                  • yleo
                    /#21326772

                    Может-может, и VirtualAllocEx() из другого процесса… Т.е. конечно это все костыли.


                    В libmdbx гонки с новыми тредами обходятся захватом SlimRwLock в специфических местах. А для общего случая нужно мешать хук на создание тредов, с локом внутри.


                    С другой стороны, в худшем случае адреса окажутся заняты.

                • VioletGiraffe
                  /#21327032

                  Ох, как я удачно наткнулся на ваш проект! Извините, что не по теме дискуссии спрашиваю, но не хотите ли вы написать статью с высокоуровневым обзором технических решений, благодаря которым достигнуты выдающиеся характеристики и фичи libmdbx? Я пишу на коленке собственную микро-СУБД для своих проектов, и у меня очень много вопросов из области computer science, то есть непонятно, как в принципе, алгоритмически, реализовать некоторые вещи, даже без прицела на быстродействие.

                  Например, вот несколько вопросов, ответы на которые мне бы очень помогли, да и просто интересны даже безотносительно моего проекта:

                  • Как вы обеспечиваете «No crash recovery needed. No maintenance is required.» без WAL? Я размышлял на эту тему (как сделать работу с файлом БД безопасным относительно падения процесса СУБД или внезапного отключения компьютера), и сумел только переизобрести WAL.
                  • Как у вас физически организовано хранение данных в файле? Я понимаю, что B+-tree, но это только малая часть ответа :) Это дерево мапится в память, и вы с ним работаете прямо как с обычной структурой данных в RAM, или всё-таки с учётом дисковой специфики?
                  • Как обеспечивается транзационность, особенно в контексте пункта 1, то есть сохранности данных при внезапном падении процесса?

                  • yleo
                    /#21327062

                    Спасибо за отзыв!


                    Да, статья о libmdbx планируется в ближайшее время (как и статьи о libfptu, libfpta, реализации double-to-string по готовности планируемых доработок). Всё это по мере наличия времени и желания, без обязательств.


                    MDBX является развитием LMDB. Информация об этом есть в README вместе со списком отличий/доработок. В свою очередь по LMDB в Сети есть масса информации. Должны быть доступны записи моих докладов на Highload++ (но там очень плохой звук).


                    На остальные ваши вопросы нет простых ответов, которые можно было-бы дать в два часа ночи в подобном комментарии.

                    • VioletGiraffe
                      /#21327066

                      Понял, большое спасибо за отсылки, поищу-почитаю.
                      Забыл упомянуть, что я гуглил эти темы, делал несколько подходов, и всё равно не нашёл почти никакой информации на тему физической организации хранения данных на диске в реальных оптимизированных БД, обеспечения целостности данных при падении СУБД и других подобных тем. Даже обсуждений на форумах не нашёл, равно как и научных статей. На английском языке искал, естественно.

                  • arthuriantech
                    /#21328946 / +1

                    Как вы обеспечиваете «No crash recovery needed. No maintenance is required.» без WAL?

                    Если коротко, в LMDB используется CoW, из-за чего при падении процесса отпадает необходимость в транзакционном журнале — больше не нужна "перемотка" транзакций с контрольной точки. В то же время, отсутствие WAL затрудняет реализацию репликации.


                    Есть неплохая бумага от автора LMDB по внутреннему устройству этой базы данных.
                    http://www.lmdb.tech/media/20130406-LOADays-LMDB.pdf

          • wadeg
            /#21340036

            Linux-овый mmap позволяет спокойно отмапить файл в разы (а то и на порядки) превышающий по размеру оперативную память компьютера, и OS будет грамотно подменять странички по мере доступа
            С какой стати? В винде, естественно, то же самое. Достаточно прочесть MSDN, там общая схема расписана.

            А MapViewOfFile будет сразу пытаться выделить обьем оперативки равный отмапливаемому участку
            Не будет. Кто-то кого-то обманул. Все принципиально везде похоже: выделяется только диапазон виртуальной памяти. При доступе к еще неотображенной странице прозрачно возникает исключение, в результате страница отображается в память, читается из файла и операция доступа перезапускается уже к странице в памяти.

            Вы же даже не пытались прочесть хотя бы в таком общем виде, но перлы типа «MapViewOfFile в Windows вообще убог» смело издаете. Не надо так.

            • qrck13
              /#21340042

              Не будет. Кто-то кого-то обманул.

              Я это видел лично, пытаясь отмапить ~100gb на машине с 64Gb RAM (из которых на момент попытки было больше половины свободно).
              Как кто-то выше написал, скорее всего дело в антивирусах которые пытаются "проверить" и всосать весь маппинг в память сразу.

              • wadeg
                /#21340052

                Даже если поверить, что это так (а я, уж извините, не поверю уже хотя бы потому, что с таким антивирусом все компьютеры просто не могли бы работать) — так вот, даже если поверить, то как это ваше «MapViewOfFile в Windows вообще убог» появилось?
                Ну и заодно и «А MapViewOfFile будет сразу пытаться выделить обьем оперативки равный отмапливаемому участку»?

                • qrck13
                  /#21340092

                  Можете не верить, мне от этого ни холодно ни жарко ;)

                • yleo
                  /#21340214 / +1

                  В Windows это действительно убого, но по другим причинам:


                  • Через API невозможно создать отображение больше размера файла (только посредством NtExtendSection()).
                  • Нельзя уменьшить отображенный в память файл.
                  • Отсутствует аналог madvise().

                  Так что если отобразить в память 64Гб файла нулевого размера, то в этот файл сначала будет записано 64 Гб нулей, что внешне может выглядеть как описывает qrck13.

                  • wadeg
                    /#21341200

                    Это все абсолютно логично, и это все документировано. И если кто-то не прочел хотя бы статью msdn перед использованием API и потом удивляется, что размер файла устанавливается равным запрошенному, то это его проблема, а вовсе не причина издавать перлы типа «MapViewOfFile в Windows убог».

                    • yleo
                      /#21341286

                      Хм, по-мне так это как-раз таки формулировка упомянутого "перла" в виде сухих аргументов.

  3. chapuza
    /#21322730

    Я там где-то уже писал, с удовольствием повторюсь тут, поскольку это квинтэссенция моего мнения в целом по проблеме:


    Я думаю, что в 2020 все компиляторы в натив сделают примерно одинаково.
    Все виртуальные машины сделают чуть хуже, но не сильно.
    Любого, кто так не сможет, надо на свалку.

    А дальше надо выбирать язык по совершенно другим параметрам.




    Ну и это, вот этот ваш пассаж:


    реализация на Haskell оказалась быстрее просто благодаря «удачности» тестовых данных

    это не совсем честно, конечно. wc — утилита, которая предназначена для работы с текстом, а не с бинарным мусором. Так что это C на неудачных данных взлетает, а не наоборот. В данном случае можно (и нужно) полагаться на то, что на входе — текст, если гнаться за оптимизацией. Тот же grep вас вообще (без сопутствующих ключей) отправит в пешее эротическое при попытке поиска до бинарнику.

    • yleo
      /#21322810

      Вы что-то совсем не верно поняли, возможно мне стоит переформулировать текст или сместить акценты (но пока лень).


      Код сгенерированный ghc в принципе не оптимальный, но показывает хорошие результаты только на сильно смещенных данных. Он особенно хорош если в гигабайтном тексте будет одно слово. Поэтому хаскель-коду буквально сильно повезло с тестовыми данными в первой статье.


      Далее, случайные данные с точки зрения ТЗ являются не мусором, а совершенно корректными данными с более естественными статистическими показателями. Данные из /dev/urandom взять было просто удобнее, но если взять любой текст то результат будет примерно аналогичным. Пожалуйста попробуйте и отпишите, если сомневаетесь.

      • chapuza
        /#21322868 / +1

        А, и правда, неверно понял. Пардон.

      • 0xd34df00d
        /#21322926

        Далее, случайные данные с точки зрения ТЗ являются не мусором, а совершенно корректными данными с более естественными статистическими показателями. Данные из /dev/urandom взять было просто удобнее, но если взять любой текст то результат будет примерно аналогичным. Пожалуйста попробуйте и отпишите, если сомневаетесь.

        Я Шекспира брал, среди прочего, подобно одному из тестов исходного автора статьи. Разница в скорости выполнения была в пределах погрешности.

  4. DoubleW
    /#21324122

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

    • chapuza
      /#21327662

      Хаскель должен хорошо с хода читаться людьми, для которых родной язык RtL (иврит, арабский).

      • 0xd34df00d
        /#21331576

        Или которые учили математику, где композиция функций записывается справа налево (f 0 g 0 h, вот это всё).

        • chapuza
          /#21332200

          Я вырос с Ван дер Варденом под подушкой, да и диплом у меня по применениям теории групп. Но, видимо, годы и лисповое прошлое берут свое, и без скобок, пайпов, или хотя бы 0, как в джулии, — я до сих пор путаюсь.

    • PsyHaSTe
      /#21327758

      А что собственно в нем инопланетного? Лично у меня потребовалось наверное несколько часов чтобы попривыкнуть, и несколько дней чтобы свободно начать читать.

  5. cy-ernado
    /#21324516

    Даже очень наивная реализация на го оказывается быстрее wc (скорее всего из-за буферизации или еще каких срезанных углов):


    package main
    
    import (
        "bufio"
        "fmt"
        "os"
        "flag"
        "strings"
    )
    
    func main() {
        flag.Parse()
        file, err := os.Open(flag.Arg(0))
        if err != nil {
            panic(err)
        }
        scanner := bufio.NewScanner(file)
        var lines, words, characters int
        for scanner.Scan() {
            lines++
    
            line := scanner.Text()
            characters += len(line)
            words += len(strings.Split(line, " "))
        }
        fmt.Printf("%10d %10d %10d %s\n", lines, words, characters, file.Name())
    }

    $ time ./wc test.txt 
      15000001   44774631 1841822210 test.txt
    real    0m2,897s
    user    0m2,873s
    sys 0m0,492s
    $ time LANG=C LC_ALL=C wc test.txt 
      15000000   44774631 1871822210 test.txt
    real    0m4,419s
    user    0m4,196s
    sys 0m0,213s

    Откуда-то взялась лишняя строчка, но мне не интересно в этом разбираться, как и дальше оптимизировать этот код.


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

    • yleo
      /#21324606

      TL;DR с системной утилитой wc нет смысла соревноваться — лежачего не бьют. Но на самом деле wc учитывает юникодные варианты пробелов и подсчитывает печатную дли строк (с табуляциями и вот это вот всё). Остальное подробности в комментариях к первой статье.

      • cy-ernado
        /#21324622 / +1

        Полностью с вами согласен, добавил свой вариант, чтобы сделать абсурдность сравнения еще более очевидной :)

      • 0xd34df00d
        /#21325320

        Но на самом деле wc учитывает юникодные варианты пробелов

        Не учитывает, если выбрана сишная локаль.

        • arheops
          /#21332182

          Но выбор локалей то он учитывает.
          Это к тому, что в WC куча кода для совместимости с разными средами

          • 0xd34df00d
            /#21336298

            Выбор локалей делается один раз перед выбором нужного цикла, а не для каждого символа/строки/етц. Короче, это O(1)-задача.

            • Antervis
              /#21338706 / +1

              Я восхищен вашей способностью хитро изворачивать факты. В журналистику не хотели податься?

              Локаль вводит табличный лукап на каждой итерации. При этом таблицы символов для wc являются по сути такими же внешними, как и текст. Единственное что они бы могли захардкодить latin1/utf8 реализации. Добавочные расходы от поддержки локали очевидно пропорциональны числу символов, т.е. O(N). Или, другими словами, они увеличивают константу про которую вы забыли

              • lieff
                /#21340856 / +2

                Собственно про это я уже писал, glibc версии возьмут структуру локали из TLS и сделают лукап в табличке. При этом там еще будет вызов функции: https://gcc.godbolt.org/z/MC2oZi. Видно что накладные расходы существенны даже с случае си локали и тут ничего не сделать — только явно использовать/переключить на оптимизированные функции.

                • 0xd34df00d
                  /#21342426

                  Ух, какая прелесть. Вот бы поведение функции в цикле доказывать на примере поведения функции вне цикла.


                  Давайте немножко поменяем ваш пример и таки напишем какой-нибудь простенький цикл, раз уж мы рассуждаем о циклах, ну например:


                  #include <stdio.h>
                  #include <ctype.h>
                  
                  int test(char *str, int count) {
                      for (int i = 0; i < count; ++i)
                          if (isspace(str[i]))
                              return true;
                  
                      return false;
                  }

                  Давайте теперь посмотрим на дизасм:


                  test(char*, int):
                    test esi, esi
                    jle .L4
                    push rbp
                    mov ebp, esi
                    push rbx
                    mov rbx, rdi
                    sub rsp, 8
                    call __ctype_b_loc
                    mov rdi, rbx
                    mov rdx, QWORD PTR [rax]
                    lea eax, [rbp-1]
                    lea rcx, [rbx+1+rax]
                    jmp .L3
                  .L13:
                    add rdi, 1
                    cmp rcx, rdi
                    je .L12
                  .L3:
                    movsx rax, BYTE PTR [rdi]
                    test BYTE PTR [rdx+1+rax*2], 32
                    je .L13
                    add rsp, 8
                    mov eax, 1
                    pop rbx
                    pop rbp
                    ret
                  .L12:
                    add rsp, 8
                    xor eax, eax
                    pop rbx
                    pop rbp
                    ret
                  .L4:
                    xor eax, eax
                    ret

                  Это g++-9.2 -O2. Сможете здесь показать вызов функции внутри цикла?


                  И с вами при этом ещё соглашаются.

                  • Antervis
                    /#21342610

                    Сможете здесь показать вызов функции внутри цикла?
                    call __ctype_b_loc

                    • 0xd34df00d
                      /#21342614

                      Ага. И это правда внутри цикла? Может, назовёте тогда лейбл, соответствующий этому циклу?

                    • arthuriantech
                      /#21342628

                      Вызов __ctype_b_loc происходит до цикла. Он возвращает таблицу, по которой уже происходит лукап при каждой итерации.

                  • lieff
                    /#21344454

                    Так я разве писал что адрес таблички не выносится за цикл? Мне казалось это очевидно, но могут быть проблемы, например компилер может вынести из одного цикла, но не из второго, я с таким сталкивался (с PGO обычно сильно умнеет в этом плане).


                    Так же доп регистр создает доп давление на внутренний цикл + там есть лишний and который тоже может проявиться: https://gcc.godbolt.org/z/givtXP


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

              • 0xd34df00d
                /#21342412

                Локаль вводит табличный лукап на каждой итерации.

                А доказать это утверждение сможете?


                Единственное что они бы могли захардкодить latin1/utf8 реализации.

                Да, могли бы. Тем более, что нынче системы, где кодировка C locale отлична от ASCII-кодировки, а первые 127 символов отличны от ASCII/UTF-8/Latin1, вроде как не очень распространены.

                • Antervis
                  /#21342644

                  Локаль вводит табличный лукап на каждой итерации
                  А доказать это утверждение сможете?
                  Вызов __ctype_b_loc происходит до цикла. Он возвращает таблицу, по которой уже происходит лукап при каждой итерации
                  (с) arthuriantech

                  Ага. И это правда внутри цикла? Может, назовёте тогда лейбл, соответствующий этому циклу?
                  с каких пор «табличный лукап» обязан быть отдельным вызовом функции?

                  • 0xd34df00d
                    /#21342648

                    Вызов __ctype_b_loc происходит до цикла. Он возвращает таблицу, по которой уже происходит лукап при каждой итерации

                    Вы так говорите «табличный лукап», как будто это что-то плохое.


                    Или, чуть более подробно, осталось показать, что табличный лукап в таблице, которая спокойно будет лежать в L1, легко предсказываться и приводить к branchless-коду, медленнее последовательности из двух-трёх сравнений.


                    Интересно, кстати, связано ли это каким-либо образом с тем, что в одном из соседних тредов предлагали для хаскель-кода завести таблицу пробельных символов и заменить лукап на чтение из неё?..


                    с каких пор «табличный лукап» обязан быть отдельным вызовом функции?

                    На всякий случай: вопрос, на который вы отвечали, был «Сможете здесь показать вызов функции внутри цикла?».

                    • Antervis
                      /#21342656

                      Вы так говорите «табличный лукап», как будто это что-то плохое.
                      если сравнивать с векторизованным кодом, то это что-то очень плохое, ведь лукап не векторизуется.
                      занудство не в тему
                      Точнее, есть набор gather инструкций, начиная с AVX2, но относительно поэлементного mov'а дает выигрыш только в числе инструкций исходного кода. Да и для побайтных алгоритмов не поможет.

                      • 0xd34df00d
                        /#21342660

                        если сравнивать с векторизованным кодом, то это что-то очень плохое, ведь лукап не векторизуется

                        Этот код компилятором вообще не векторизуется, даже если вы руками напишете сравнение с 32 и [9..13] вместо этого несчастного isspace. Для векторизации надо применять человеческую смекалочку.


                        Поэтому, если честно, этот аргумент выглядит притянутым за уши.


                        это был изначально ошибочный вопрос.

                        Учитывая контекст дискуссии — нет.

                        • Antervis
                          /#21342670

                          Этот код компилятором вообще не векторизуется
                          взял "простую на С" и она как-то да векторизуется.
                          Учитывая контекст дискуссии — нет.
                          в контексте дискуссии речь изначально шла про «табличный лукап», а вы первый начали говорить про «вызов функции внутри цикла».

                          • 0xd34df00d
                            /#21342678

                            взял "простую на С" и она как-то да векторизуется.

                            А теперь всё же возьмите те компиляторы, которые мы тут обсуждаем (clang 9 и gcc 9.2) — ни один из них это не векторизует, поэтому в рамках данного сравнения это проблемой не является.


                            Вот кто б так код на хаскеле защищал, чесслово.


                            Но clang/llvm из trunk молодец, да.


                            в контексте дискуссии речь изначально шла про «табличный лукап», а вы первый начали говорить про «вызов функции внутри цикла».

                            Вообще-то не первый. Я лишь отвечал на указание на то, что вызов isspace означает вызов функции.

                            • Antervis
                              /#21342712

                              gcc то я выставил 8.1, в статье тоже 8-й. Да и вы же вроде и топили за использование компиляторов последних версий? Или это только про хаскель было?

                              • 0xd34df00d
                                /#21342720

                                А, вы и про правую панельку! Ну давайте читать ассемблер вместе! Я, чтобы было проще анализировать, что там компилятор накомпилировал, выкину всё после определения process_chunk (ну и с него, естественно, сниму static), и результат на всякий случай тут процитирую:


                                process_chunk:
                                        mov     ecx, edx
                                        add     QWORD PTR result[rip], rsi
                                        test    rsi, rsi
                                        je      .L4
                                        mov     r9, QWORD PTR result[rip+16]
                                        mov     r8, QWORD PTR result[rip+8]
                                        add     rsi, rdi
                                .L3:
                                        movzx   edx, BYTE PTR [rdi]
                                        xor     eax, eax
                                        cmp     dl, 10
                                        sete    al
                                        add     r9, rax
                                        cmp     dl, 32
                                        setne   al
                                        cmp     dl, 13
                                        seta    dl
                                        xor     ecx, 1
                                        add     rdi, 1
                                        and     eax, edx
                                        and     ecx, eax
                                        movzx   ecx, cl
                                        add     r8, rcx
                                        mov     ecx, eax
                                        cmp     rdi, rsi
                                        jne     .L3
                                        mov     QWORD PTR [rsp-16], r8
                                        movq    xmm0, QWORD PTR [rsp-16]
                                        mov     QWORD PTR [rsp-16], r9
                                        movhps  xmm0, QWORD PTR [rsp-16]
                                        movups  XMMWORD PTR result[rip+8], xmm0
                                        ret
                                .L4:
                                        mov     eax, edx
                                        ret

                                Так вот, цикл — это от метки .L3 до инструкции jne .L3. В этом промежутке нет ни единой векторной инструкции, ни единого векторного регистра.


                                А вот когда цикл заканчивается (если jne не срабатывает, и выполнение проваливается), тогда да, тогда есть пяток mov'ов разных видов с векторным регистром — код выгружает то, что он насчитал в регистрах во внутреннем цикле, во внешнюю относительно него статическую переменную result.


                                Почему он это делает через xmm-регистр здесь (так, что по факту запись в статическую переменную происходит одной командой), но не делает аналогичной загрузки через xmm-регистр, когда он инициализирует r9 и r8 — я не знаю. Может, компилятор думает, что стек рядом, в кэше, поэтому первые четыре mov'а будут быстрыми, хрен знает. Я не компилятор. Требований атомарной записи тут вроде как нет (да и mov векторного регистра в память ЕМНИП не обязан быть атомарным).


                                Кстати, повезло, что одновременное обращение к этой переменной из разных тредов — UB, и компилятор смог этим воспользоваться, иначе оно бы долбилось в эту статическую переменную на каждой итерации — прикиньте, как быстро бы всё работало, а?


                                Уф, ну вот, прочитали ассемблер. Объясните только, почему защищаете код на сях, говоря о некорректности моего сравнения, вы, а объясняю смысл того, что компилятор С-кода там накомпилировал, я? Разве это не должно быть, ну, наоборот?


                                Да, извините, что я так немного жёстко, просто такой систематический confirmation bias начинает задалбывать. Как-то не ожидал от хабра.


                                Да и вы же вроде и топили за использование компиляторов последних версий? Или это только про хаскель было?

                                А последняя версия clang — 9.0.чётотам, а не trunk. Я же не использовал предрелизный ghc-8.10 с предрелизным LLVM?

                                • Antervis
                                  /#21343570

                                  каюсь, плохо прочитал листинг

                                  просто такой систематический confirmation bias начинает задалбывать. Как-то не ожидал от хабра.
                                  вы сравнили сишный wc и реализацию его частного случая на хаскеле, после чего сделали вывод, что хаскель превосходит си в быстродействии. И откуда взялся confirmation bias?

                                  Ну да ладно, главное что табличный лукап нашли.

                                  • 0xd34df00d
                                    /#21347174 / -1

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

                                    Хаскель превосходит даже аналогичный код на сях (ну, если не выкручивать -march=native и заниматься прочим подобным). Или вы сравниваете с вручную SIMD-оптимизированными версиями?


                                    Ну да ладно, главное что табличный лукап нашли.

                                    Осталось доказать, что это что-то плохое.

                                    • technic93
                                      /#21347296

                                      Ну не знаю, я честно проверил в соседнем треде про march=native и у меня оно дает иногда отрицательный результат на синтетических данных.


                                      В этом треде вот эта версия "на С по мотивам Haskell" переносимая и работает в два раза быстрее на одних данных. И нету никакой векторизации. Или что-то все равно не так?

                                      • 0xd34df00d
                                        /#21347312

                                        Свои числа для одной из версий (не знаю, совпадает ли она с тем, что вы проверяли) я уже приводил: 1.45 с для хаскеля, 2.0 с для C/gcc и больше 2 секунд для C/clang (или, возможно, gcc и clang наоборот — но не суть).

                                        • technic93
                                          /#21347440

                                          Перечитал ваш первый комментарий


                                          took 1.382212 seconds

                                          Это оно или нет? Может сделаете такую же табличку как и в статье только на своей машине, извините в мешанине комментариев тяжело.

                                          • 0xd34df00d
                                            /#21347444

                                            Нет, это не оно: это эквивалентный, но отличный алгоритм.


                                            Эквивалентность и отличность мы, впрочем, обсуждаем чуть ниже, присоединяйтесь!

                                    • Antervis
                                      /#21347330

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

                                      • 0xd34df00d
                                        /#21347338

                                        Ага, это, например?


                                        на Haskell ghc 8.0.2, -O2 2.811
                                        простая на С gcc 8, -Ofast 3.067

                                        Я не говорю о том, что тут древний ghc 8.0.2. С ним я не сравнивал, но вот от перехода с 8.6 на 8.8 у меня код ускорился значимо (с 1.6 с чем-то до 1.45).

                                        • Antervis
                                          /#21347390 / +1

                                          Ага, это, например?
                                          а потом поменяли компилятор и «простая на си» начала работать в два с половиной раза быстрее. А потом
                                          Cовершенно «внезапно» сгенерированный Haskell-компилятором код, но реализованный на С оказался вдвое быстрее!
                                          А когда подставили другие данные, «простая на си» оказалась в полтора раза быстрее. А когда сишную реализацию еще и оптимизировали, так и во все 5.

                                          Но мы ведь сравниваем худший результат си с лучшим результатом хаскеля, верно?
                                          Да, извините, что я так немного жёстко, просто такой систематический confirmation bias начинает задалбывать. Как-то не ожидал от хабра.
                                          ©

                                          • 0xd34df00d
                                            /#21347396

                                            а потом поменяли компилятор и «простая на си» начала работать в два с половиной раза быстрее

                                            Это где? Вы про clang? Там, если что, включено -march=haswell (или, что эквивалентно для той из машин, где я это бенчмаркал, -march=native).


                                            А потом совершенно «внезапно» сгенерированный Haskell-компилятором код, но реализованный на С оказался вдвое быстрее!

                                            Вас не смущает, что это другой алгоритм?


                                            Такой вам вопрос, чтобы синхронизировать терминологию: сортировка обычным квиксортом с википедии и сортировка квиксортом, который для массивов длины меньше N переключается на другой, э, алгоритм — это один и тот же алгоритм или нет?

                                            • Antervis
                                              /#21347428

                                              Это где? Вы про clang? Там, если что, включено -march=haswell (или, что эквивалентно для той из машин, где я это бенчмаркал, -march=native).
                                              sse4.2, который есть на любом актуальном процессоре, хватит для существенного ускорения.
                                              Вас не смущает, что это другой алгоритм?
                                              а автор утверждает что тот же самый, ведь код «по мотивам». Врет, да?

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

                                              • 0xd34df00d
                                                /#21347432

                                                sse4.2, который есть на любом актуальном процессоре, хватит для существенного ускорения.

                                                Опять начинаются попытки притянуть решение к ответу.


                                                а автор утверждает что тот же самый, ведь код «по мотивам». Врет, да?

                                                Я правильно понимаю, что для вас эта функция


                                                static _Bool process_chunk(const unsigned char *text, const size_t bytes,
                                                                           _Bool prev) {
                                                  result.chars += bytes;
                                                  for (size_t i = 0; i < bytes; ++i) {
                                                    result.lines += text[i] == '\n';
                                                    _Bool now = text[i] != ' ' && text[i] - 9 > 4;
                                                    result.words += now & !prev;
                                                    prev = now;
                                                  }
                                                
                                                  return prev;
                                                }

                                                и эта функция


                                                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;
                                                }

                                                реализуют одинаковый алгоритм?

                                                • technic93
                                                  /#21347464

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


                                                  wc :: BS.ByteString -> (Int, Int, Int)
                                                  wc s = (bs, ws, ls)
                                                    where
                                                      State { .. } = BS.foldl' go (State 0 0 0 0) s
                                                  
                                                      go State { .. } c = State (bs + 1) (ws + addWord) (ls + addLine) isSp
                                                        where
                                                          isSp | c == 32 || c - 9 <= 4 = 1
                                                               | otherwise = 0
                                                          addLine | c == 10 = 1
                                                                  | otherwise = 0
                                                          addWord = (1 - wasSpace) * isSp

                                                  Алгоритм уже разный. Но на самом деле ближе к первому более прямолинейному варианту на Си. А вообще интересно почему ghc сгенерировал на самом деле примерно второй код на си. Есть ли какая то закономерность в том как он разворачивает fold?


                                                  P.S присоединился :)

                                                  • 0xd34df00d
                                                    /#21347512

                                                    Но на самом деле ближе к первому более прямолинейному варианту на Си.

                                                    Ну вот и я так тоже считаю. И сравнивать логичнее, значит, с ним, ИМХО.


                                                    А вообще интересно почему ghc сгенерировал на самом деле примерно второй код на си. Есть ли какая то закономерность в том как он разворачивает fold?

                                                    Хороший вопрос. У меня нет какой-то адекватной интуиции о том, как ведёт себя оптимизатор ghc на этом уровне. В fold для строк ничего специального нет, оптимизатором он должен сворачиваться в совершенно обычный и привычный императивный цикл.

                                                    • technic93
                                                      /#21347542

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

                                                      • 0xd34df00d
                                                        /#21347556

                                                        Я что то не уверен что второй си вариант это хаскель, т.к. почему он тогда быстрее в два раза?)

                                                        Ну это зависит — вот про второй вариант я и писал, что на моей машине он работает за 1.38 секунд, что не так уж далеко от хаскелевских 1.45.

                                                        • technic93
                                                          /#21347570

                                                          А ну это с новым ghc, а я смотрю на выхлоп старого, тут много всяких артифактов от этого стейта.

                                                          • 0xd34df00d
                                                            /#21347598

                                                            Там над оптимизатором работают систематически и постоянно (правда, последнее время это больше GC касается), так что опыт между разными ghc трансферится так себе.


                                                            Но это даже хорошо — был на работе проект, о котором я тут где-то рядом писал (с самодельным JIT и вот этим всем) — от одного апгрейда ghc ускорился процентов на 30.

                                                • Antervis
                                                  /#21347466

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

                                                  • 0xd34df00d
                                                    /#21347510

                                                    вам можно а мне нельзя?

                                                    Скорее наоборот.


                                                    вторая, которая быстрее, должна реализовывать тот же алгоритм, что и хаскель.

                                                    Жаль, что вы не ответили на очень прямой и простой вопрос.


                                                    А почему не первая? Первая куда ближе к тому, что делает код на хаскеле, разве нет?


                                                    Почему вы так хотите сравнивать именно реализацию более быстрого алгоритма на хаскеле с более медленным на си?

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

                                                    • Antervis
                                                      /#21347572

                                                      Я хочу сравнивать наиболее близкие реализации
                                                      Вот есть у нас четыре варианта сишного кода разной степени оптимизации: wc, наивный, подтюненный и векторизованный. Часть этих вариантов ускоряется в зависимости от опций компилятора и разрешенных наборов инструкций. Ну, допустим, у подтюненной алгоритм другой (ну напишите на хаскеле другой алгоритм, в чем проблема то?), транковые компиляторы вам не нравятся а AVX2 запустятся не на всех процах (процы 10-летней давности в AVX2 умеют, между прочим). Допустим. Но почему вариант с наивной под clang 8 -Ofast -msse4.2 вас не устроил? И компилятор не самый новый, и опции вполне себе не запредельные, и алгоритм тот же.

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

                                                      • 0xd34df00d
                                                        /#21347592

                                                        Ну, допустим, у подтюненной алгоритм другой (ну напишите на хаскеле другой алгоритм, в чем проблема то?)

                                                        Допустим. Но почему вариант с наивной под clang 8 -Ofast -msse4.2 вас не устроил? И компилятор не самый новый, и опции вполне себе не запредельные, и алгоритм тот же.

                                                        Да я-то ничего не имею против такого варианта (и против -march=native ничего не имею, и против версии с интринсиками ничего не имею, даже против голого асма ничего не имею), но вы ведь понимаете, что это другая задача?

                                                        • Antervis
                                                          /#21347628

                                                          о вы ведь понимаете, что это другая задача?
                                                          А какая задача то? «Написать код на си который будет близок, но не превзойдет хаскель»? Хе хе. Если вы провели у себя в голове какую-то границу допустимого уровня оптимизаций, то поведайте. Вот на мой взгляд, соотношение «прирост производительности к усложнению кода» в подтюненной относительно наивной очень хороший.

                                                          • 0xd34df00d
                                                            /#21347692

                                                            Показать, как можно взять чуть менее оптимальный код на хаскеле и очень малой кровью сделать из него чуть более оптимальный код на хаскеле. Желательно без ручного ковыряния unlifted-типов, без раскорячивания IO (посмотрите ужасы на the benchmark game, я так не хочу делать), и тому подобного.


                                                            Зачем здесь вообще С? Чтобы понимать, когда пора остановиться. Если такой же алгоритм на С в таких же условиях на три-четыре порядка быстрее (такое у меня бывало), то останавливаться рано (а если дальше не прёт — ну, пора признать, что в этой задаче увы, без раскорячивания IO и всяких# ужасов# с# unlifed#-типами# никак#). А если вы таки такой же алгоритм на С в таких же условиях обогнали — то, ну, в общем, может, и хватит уже.

                                                            • Antervis
                                                              /#21348512

                                                              ну с формулировкой задачи «слегка перегнать наивный си на хаскеле» какой смысл сравнивать языки, если у нас результат сравнения в «дано»?

                                                              А если вы таки такой же алгоритм на С в таких же условиях обогнали — то, ну, в общем, может, и хватит уже.
                                                              или можно приложить эти усилия в допиливание алгоритма на сях и получить вряд ли меньший профит

                                                          • PsyHaSTe
                                                            /#21348596 / +1

                                                            Смысл "написать простой код, не заморачиваясь с оптимизациями", а потом посмотреть, как компилятор такой код прожуёт, и какая у него будет производительность. В этом плане смысл в том, чтобы написать наивный цикл с ифом внутри и ожидать, что компилятор его вынесет за цикл. Если не вынес — не надо ему руками "помогать", чтобы стало "честнее" — потому что в реальном коде вы так не будете делать только если в бенчах не заметили узкое место.


                                                            Тут ведь та же проблема что и со всеми бенчами: знать, где остановиться, потому что в пределе всё сведется к тому, на каком языке ДСЛ к ассемблеру писать проще.

                                                            • Antervis
                                                              /#21348932 / +1

                                                              потому что в реальном коде вы так не будете делать только если в бенчах не заметили узкое место.
                                                              ну вот у нас реальный код компилируется с -msse4.2. В бенчах с ним наивная сишная реализация обходит хаскелевскую. Я должен сделать вывод что си быстрее?

                                                            • technic93
                                                              /#21349018 / +1

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


                                                              Ну вот хаскель каким-то образом сделал из c == 32 два сравнения с >= 33 и c < 32. Потом, зачем-то это сравнивали на csv файле где запятые не учитывали как разделитель и это прокатило. А вот Шекспиру это не помогло, даже наоборот всё испортило.


                                                              А GCC (уже по традиции) нагенирировал код который не зависит от данных.


                                                              Если цель показать что Хаскель умеет выкидывать GC и прочею фигню то это хорошо. Вот старый ghc не смог выкинуть State со стэка при fold, а новый видимо смог — тоже плюс.


                                                              Если как вы говорите цель посмотреть какой компилятор лушче справляется с наивным кодом, то даже с ограничениями, 1) идиоматичная версия на Си работает быстрее на реальных данных 2) версия на си более читабельная т.к. там все еще остался bool и && вместо арифметики хаскеля.

                                                              • PsyHaSTe
                                                                /#21349176

                                                                1. про реальные данные вопрос спорный, но я склонен согласиться
                                                                2. а вот читаемость это чистая вкусовщина. Мне вот вариант на хаскелле кажется читаемее (по крайней мере наивная версия, которая в 9 раз медленнее).

                                                                • technic93
                                                                  /#21349238

                                                                  Я склонен согласится что в целом декларативный код более читаем чем императивный, а на голом си я кодить не хочу. Но я хочу свой bool назад вместо арифетики. А ещё лучше человеко-читаемые and, or, not вместо этих палочек и крючочков, но это уже точно вкусовщина :)

                    • arthuriantech
                      /#21342668

                      Вы так говорите «табличный лукап», как будто это что-то плохое.

                      Как будто.
                      Да, поместится в L1 и будет работать быстро, увеличивая давление на кеш. Если положить на одну чашу весов два предсказуемых if, а на вторую — переход по таблице 384 байта, то я не ручаюсь, что из этого будет быстрее. Надо проверять.

                      • 0xd34df00d
                        /#21342676

                        увеличивая давление на кеш

                        Который тут в любом случае работает в режиме «загрузили кешлайн, обработали кешлайн, выкинули кешлайн и забыли про него». Мы проходим по всем данным ровно один раз, и лишние 384 байта тут погоды не сделают. Главное — чтобы места хватало на следующие данные из оперативки.

    • Kabdim
      /#21324852

      .

      • cy-ernado
        /#21325168

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


        Ну и я не ставил себе целью произвести абсолютно точные измерения, очевидно, что wc делает больше работы, да и ресурсов потребляет меньше (гошный рантайм ест несколько мегабайт + bufio.Scanner имеет довольно большой максимальный буфер). Ни в коем случае не хочу сказать что-то вроде "го побеждает си в 20 строчек".

        • yleo
          /#21325216

          В статье есть упоминание про /dev/shm, это tmpfs. Видимо авто предыдущего комментария заметил это и удалил свое примечание.

          • cy-ernado
            /#21325328

            Первоначально я действительно не тестировал на tmpfs, полагая, что файл целиком уместился в кеше. Сейчас специально сделал на tmpfs, результаты аналогичные:


            $ time ./wc /tmp/space/test.txt 
              15000001   44774631 1841822210 /tmp/space/test.txt
            
            real    0m2,842s
            user    0m2,784s
            sys 0m0,395s
            
            $ time LANG=C LC_ALL=C wc /tmp/space/test.txt 
              15000000   44774631 1871822210 /tmp/space/test.txt
            
            real    0m4,447s
            user    0m4,226s
            sys 0m0,209s
            
            $ df -h | grep /tmp
            tmpfs           3,0G  1,8G  1,3G  59% /tmp/space

            А еще я сейчас заметил, что у моего варианта отличается и количество characters от вывода wc, наверное, где-то у меня ошибка или это те самые непечатные символы.

            • chapuza
              /#21327676

              characters += len(line)

              Единичку бы добавить, возврат каретки — тоже, знаете ли, целый байт занимает :)

    • powerman
      /#21326974 / +1

      Откуда-то взялась лишняя строчка

      Вот не менее наивная реализация без каких-либо дополнительных оптимизаций, но она работает корректно и в 3 раза быстрее Вашего варианта (просто за счёт отсутствия ненужных операций вроде преобразования []byte в string или удаления \r?\n из конца строк).


      wc.go
      package main
      
      import (
          "bufio"
          "bytes"
          "fmt"
          "log"
          "os"
      )
      
      func main() {
          var lines, words, characters int
          scanner := bufio.NewScanner(os.Stdin)
          scanner.Split(scanLines)
          for scanner.Scan() {
              line := scanner.Bytes()
              characters += len(line)
              words += bytes.Count(line, []byte{' '}) + 1
              if line[len(line)-1] == '\n' {
                  lines++
              }
          }
          if err := scanner.Err(); err != nil {
              log.Fatal(err)
          }
          fmt.Printf("%10d %10d %10d\n", lines, words, characters)
      }
      
      func scanLines(data []byte, atEOF bool) (advance int, token []byte, err error) {
          if atEOF && len(data) == 0 {
              return 0, nil, nil
          }
          if i := bytes.IndexByte(data, '\n'); i >= 0 {
              return i + 1, data[0 : i+1], nil
          }
          if atEOF {
              return len(data), data, nil
          }
          return 0, nil, nil
      }

  6. technic93
    /#21325406 / +1

    Да у меня абсолютно похожие выводы есть но к другой статье уважаемого 0xd34df00d :) Все никак не дойдут руки написать...

  7. PsyHaSTe
    /#21325648

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


    Но верно написано, что YMMW, может оказаться, что данные могут неудачно лечь на дефолтный оптимизатор, и придется лезть руками. Впрочем, узкие места оптимизировать придется на любом языке, да и скорости "в 2 раза медленнее си" за глаза в большинстве прикладных задач.




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

    • yleo
      /#21327174

      Все результаты и выводы подтвердились для ghc 8.8.3, LLVM-бакендом и на текстах Шекспира.
      См под спойлером в конце статьи.

  8. somurzakov
    /#21325710

    очень интересная серия дискуссий, узнал много нового для себя, включая AVX,SSE и прочие трюки. Спасибо всем участникам

  9. kovserg
    /#21326658 / -2

    AVX, SSE и прочие фигня всё это в данном случае. Есть еще другие способы оптимизации:
    1. файл большой => следует читать асинхронно, пока читает обрабатывать прочитанное. Задача проста: обработать данные до получения следующего блока.
    2. для обработки выбрать блоки которые целиком помещаются в кэш. Это даст прирост больший чем векторные инструкции ожидающие готовности памяти.
    3. приводить результаты в абсолютных величинах Gb/s и сравнивать с максимальной пропускной способностью в %. Например по отношению к HDD 160Mb/s, SSD 500Mb/s… 4Gb/s, RAM 40-80Gb/s

    • Antervis
      /#21326798

      AVX, SSE и прочие фигня всё это в данном случае. Есть еще другие способы оптимизации:
      1. файл большой => следует читать асинхронно.
      вы же понимаете, что в данном случае прирост от SSE на порядки выше чем от распараллеливания?
      2. для обработки выбрать блоки которые целиком помещаются в кэш. Это даст прирост больший чем векторные инструкции ожидающие готовности памяти.
      авторы сишной реализации это делали. Ну или может быть они наообум взяли константу 64 Кб, хз.
      3. приводить результаты в абсолютных величинах Gb/s и сравнивать с максимальной пропускной способностью в %. Например по отношению к HDD 160Mb/s, SSD 500Mb/s… 4Gb/s, RAM 40-80Gb/s
      ну поделите 1.8 Гб файла на (грубо) 0.3..3 с тестов, получите 600..6000 Мб/с. А еще файл в tmpfs, т.е. HDD/SSD не должен влиять.

    • yleo
      /#21326856 / +1

      AVX, SSE и прочие фигня всё это в данном случае. Есть еще другие способы оптимизации:

      Ой не говорите, ерундой какой-то занимаемся.


      1. файл большой => следует читать асинхронно, пока читает обрабатывать прочитанное. Задача проста: обработать данные до получения следующего блока.

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


      1. для обработки выбрать блоки которые целиком помещаются в кэш. Это даст прирост больший чем векторные инструкции ожидающие готовности памяти.

      Это даст прирост если данные читаются больше одного раза, а в здешнем баловстве это не так. Поэтому хватает prefetch. Более того, в подобных практических задачах всегда выгоднее не засорять кэш данными читаемыми однократно. Т.е. буквально для AVX2 будет выгоднее делать предвыборку вручную в потоковом режиме, обрабатывания данные кэш-линияим (по 64 байта).


      1. приводить результаты в абсолютных величинах Gb/s и сравнивать с максимальной пропускной способностью в %. Например по отношению к HDD 160Mb/s, SSD 500Mb/s… 4Gb/s, RAM 40-80Gb/s

      В этом есть здравое зерно, но нет рациональности. Поскольку варианты кода сравнивались между собой на одной машине по wall clock, и намеренно без дискового обмена.


      В целом — спасибо, посмешили.
      Всё-же желательно читать статьи перед тем так блистать в комментариях.

      • kovserg
        /#21326948 / -1

        Ой не говорите, ерундой какой-то занимаемся.

        Именно. Ваши файлы всегда в tmpfs?
        В целом — спасибо, посмешили.

        Точно самый быстрый вариант 6.5Gb/s из 40Gb/s возможных, т.е. 16% от максимума.
        По поводу prefetch вы правильно заметили надо не попорядку читать данные, а так что бы инициировать загрузку кэш линий и потом уже дочитывать оставшиеся из 64х байт и вести подсчеты, когда грузятся следующие линии.

        • yleo
          /#21326976

          Либо прочитайте все четыре статьи, либо ложитесь спать.

          • DoubleW
            /#21330404

            Зря человека заминусят — интересный вопрос он поднял.
            Итак ваш ЦПУ i7-4600U CPU @ 2.10GHz согласно сайту Интел работает с памятью либо 1333(10.6Gb/s) либо 1600(12.8Gb/s).
            И скорее всего у вас двухканальная память, теоретически пиковая пропускная способность должна быть где то в районе 18-22Gb/s(с учетом накладных расходов).
            Самый же быстрый вариант показывает навскидку всего 7.2Gb/s.
            Наверное ос предпочитает упихать файл в памяти так что «двухканальность» не работает.
            И имеем около 30% накладных расходов нас чтении файла с tmpfs.

            • yleo
              /#21330800

              Он его как-то не к месту поднял.


              Конечно так можно оценивать насколько эффективно (близко к пределу) работает та или иная реализация (особенно образом SIMD).


              Но это сложнее и НЕ РАЦИОНАЛЬНО если требуется просто выяснить что быстрее (при запуске на одной машине, т.е. в равных постоянных условиях).

              • DoubleW
                /#21331800

                Ну зато навскидку видно что еще не все выжали даже с avx, еще практически наполовину можно как то ускорить код (пуcть и задействовав второй поток?).

                • yleo
                  /#21331870

                  С точки зрения алгоритма это довольно простая и не особо интересная задачка. При определенно опыте достаточно очевидно, что в зависимости от поколения CPU и компилятора можно достаточно близко подойти к пределу (memory bandwidth). Собственно я об этом заявил примерно сразу.


                  Второй поток тут не нужен, точнее вреден. Достаточно организовать обработку блоками по 64 байта (кэш-линиями) и уменьшить зависимость по данным (несколько счетчиков, которые сложить в конце). Если совсем "упороться", то нужно делать prefech или упреждающее потоковое чтение с учетом кол-ва активных каналов к памяти (т.е.
                  с учетом актуального интерливинга банков DDR при отображении на адреса).


                  Но к теме этой статьи это не имеет отношения, по крайней мере пока в Хаскель не завезли интриниски для SIMD ;)

                  • 0xd34df00d
                    /#21336612

                    Но к теме этой статьи это не имеет отношения, по крайней мере пока в Хаскель не завезли интриниски для SIMD ;)

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


                    Ну и я завожу — посмотрите, это ли не чудо? Кстати, уж коли вы в асме шарите, порекомендуйте стиль форматирования ассемблера для всех этих вещей вроде unrolls, чтобы и читабельно было, и понятно, что происходит. Охота, чтобы примеры были приятными.