Как стать автором
Обновить

Комментарии 158

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


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

У меня есть опыт, когда апгрейд 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, сгенерирован не случайным образом, и имеет характеристики, несколько отличные от случайного.

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

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

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

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

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


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

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

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


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


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

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

Вы несете чушь, потому что 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, т.е. максимальному значению

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

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


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


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

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

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


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

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

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


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


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

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


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

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


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

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


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

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


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

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

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

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

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

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

НЛО прилетело и опубликовало эту надпись здесь
Где реализация на GPU?

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


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

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


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

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


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

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

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

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

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

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

В POSIX есть madvise(), а в windows некоторые костыли.


Но к теме статьи это отношения примерно не имеет.

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

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

Я тоже с проблемой выделения не сталкивался. Но вот с другой проблемой столкнулся недавно. Оказывается нельзя надежно выделить 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% гарантии что сработает тут нет.


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

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


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

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


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

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


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


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

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

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

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


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


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


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

Понял, большое спасибо за отсылки, поищу-почитаю.
Забыл упомянуть, что я гуглил эти темы, делал несколько подходов, и всё равно не нашёл почти никакой информации на тему физической организации хранения данных на диске в реальных оптимизированных БД, обеспечения целостности данных при падении СУБД и других подобных тем. Даже обсуждений на форумах не нашёл, равно как и научных статей. На английском языке искал, естественно.
Как вы обеспечиваете «No crash recovery needed. No maintenance is required.» без WAL?

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


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

Посмотрите на MEM_RESERVE_PLACEHOLDER и MEM_REPLACE_PLACEHOLDER в VirtualAlloc2() и VirtualFreeEx(), они позволяют сначала разбить зарезервированный регион на два, потом закоммитить его часть.

Выглядит как то что надо, спасибо. Жаль что только десятка, прежде чем только на это полагаться придется подождать.

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

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

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

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

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

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

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


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

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

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

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

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


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

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




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


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

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

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


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


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

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

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

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

НЛО прилетело и опубликовало эту надпись здесь

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

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

Ну вы сами сказали: во всех с пайпами.


Плюс >=> — это почти композиция функций, а она слева направо.

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

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

Даже очень наивная реализация на го оказывается быстрее 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

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


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

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

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

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

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

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

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

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

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

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

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


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


#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. Сможете здесь показать вызов функции внутри цикла?


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

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

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

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

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


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


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

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

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


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

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

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

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

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


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


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


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

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

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

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


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


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

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

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

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


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


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


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

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

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

А, вы и про правую панельку! Ну давайте читать ассемблер вместе! Я, чтобы было проще анализировать, что там компилятор накомпилировал, выкину всё после определения 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?

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

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

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


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

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

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


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

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

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


took 1.382212 seconds

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

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


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

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

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


на 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).

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

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

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


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

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


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

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

А еще напомню что на других данных тоже си обгоняет. Поймите меня правильно: когда минимальные изменения в любую сторону меняют результаты эксперимента на прямо противоположные, начинает казаться, что эксперимент подставной
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;
}

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

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


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 присоединился :)

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

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


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

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

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

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

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

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

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


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

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

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


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

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


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


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

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

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

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

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

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

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

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


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

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

А где вы такую задачу увидели-то?


или можно приложить эти усилия в допиливание алгоритма на сях и получить вряд ли меньший профит

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

А где вы такую задачу увидели-то?
Зачем здесь вообще С? Чтобы понимать, когда пора остановиться… А если вы таки такой же алгоритм на С в таких же условиях обогнали — то, ну, в общем, может, и хватит уже.

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

Интересная интерпретация. Цель — сравнить и понять, когда можно остановиться, а не перегонять. В полтора-два раза медленнее сей тоже норм.


я бы за полчаса-час этот код векторизовал

Мне бы на векторизацию подсчёта слов потребовалось бы сильно больше времени.

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


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

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

Если мы берем наивную сишную реализацию (первый вариант из поста https://habr.com/ru/post/489958/#comment_21347432 ), и она быстрее — то да, можно делать такой вывод.

ну вот у нас реальный код компилируется с -msse4.2.

Нет.


Давайте возьмём самый популярный дистрибутив с wc… А, тьфу ты, у packages.ubuntu.com Ubuntu почему-то Internal Server Error. Ну возьмём пакет из debian unstable: https://packages.debian.org/sid/coreutils. Если вы посмотрите на правила сборки, то увидите, что никакого -msse4.2 там нет. В родном дереве coreutils их тоже нет (ну или я, по крайней мере, сходу не нашёл).

Я кстати недавно столкнулся с этой же проблемой — libmpg123 из убунты тормозит. Даже хотел пойти к ним ругаться. Так что да, в репах часто не оптимальные пакеты, потому видимо всякие Clear Linux часто в бенчмарках и обходят.

Нет.
«у нас» — на работе у меня, наш продакшн код компилируется с -msse4.2. И брать один из наиболее консервативных примеров конечно же зашквар. Как думаете, ААА игры, например, компилируют под generic cpu?

А у нас на прошлой работе все серверы были со свежими ксеончиками, но код собирался без -march вообще, с -mtune= opteron (потому что) и с -O1 (потому что иначе вылезало слишком много багов). Какой из этого вывод можно сделать? Особенно из последнего пункта?

Не центось и не 7й gcc случаем?

Хаха, если бы. Рхел с DTS-2, который в 2017-м, что ли, обновили до DTS-4.

Ууу, снимаю шляпу) Это 5.3 получается?
Но за 5.3 не припомню много багов за пределами того, что он не все поддерживает, sse уже с ним нормально использовали.

Аа, я неоднозначно написал :) Уровни оптимизации выше -O1 обнажали баги в «корпоративном» коде, не в gcc.


А на баги в gcc 5.3 я тоже натыкался, но это были ICE (что куда лучше рантайм-проблем). В частности, дженерик лямбды он очень не любил, например.

Да, я тоже натыкался, и в msvc тоже. Кстати, чтобы выправить код, его хорошо под свежими компилерами прогнать с -fsanitize=undefined (в старом коде от UB часто баги), address и thread тоже не помешает.

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

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

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


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

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


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


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


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


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

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

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

Но я хочу свой bool назад вместо арифетики.

Я тоже, меня от замены Bool на Int слегка корёжит, и в продакшен-коде я бы так не стал делать.


Короче, надо запилить свой efficient bool вроде


newtype EBool = EBool { digit :: Int } deriving (...)

true, false :: EBool
true = EBool 1
false = EBool 0

eand :: EBool -> EBool -> EBool
eand b1 b2 = EBool $ digit b1 * digit b2

enot :: EBool -> EBool
enot b = EBool $ 1 - digit b

и так далее. Хоть в библиотеку оформляй.

А что со стандартным Bool всё так плохо?

Да не так уж плохо, ИМХО — там улучшение типа с 2.01 секунды до 1.91 секунды, разница имхо не столь велика.


Впрочем, спасибо, вы заставили меня погуглить, что там с unboxed sums, которые должны бы по идее это чинить: в общем, если посмотреть сюда в раздел Unpacking, то там есть кусок:


(NOTE (osa): This part is not yet implemented, the patch is trivial and I'm
going to submit it soon)

Мда, как вы там живете если даже enum на объектах с гц :)

Ну вот здесь никакого гц нет ни с булами, ни без булов (ещё раз спасибо компилятору), но лишний индирекшон таки есть.

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

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

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

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

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


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

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

Первоначально я действительно не тестировал на 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, наверное, где-то у меня ошибка или это те самые непечатные символы.

characters += len(line)

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

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

Вот не менее наивная реализация без каких-либо дополнительных оптимизаций, но она работает корректно и в 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
}

# Ваш вариант из комментария выше
$ time ./wc.orig /dev/shm/test.txt
  15000001   44774631 1841822210 /dev/shm/test.txt

2.994 real  2.917 user  0.390 sys  11MB RAM

# Мой вариант из кода под спойлером в этом комментарии
$ time ./wc </dev/shm/test.txt
  15000000   44774631 1871822210

0.974 real  0.664 user  0.312 sys  11MB RAM

# Штатная утилита
$ time LANG=C wc </dev/shm/test.txt
  15000000   44774631 1871822210

7.044 real  6.858 user  0.185 sys  11MB RAM

# на Haskell: ghc 8.0.2, -O2
$ time ./haskell_wc /dev/shm/test.txt
(1871822210,44774631,15000000)

2.510 real  2.420 user  0.090 sys  1788MB RAM

# простая на С: gcc 9.2.0, -Ofast
$ time ./naive_wc </dev/shm/test.txt
lines 15000000, words 44774631, chars 1871822210
took 2.517815 seconds

2.519 real  2.433 user  0.085 sys  1782MB RAM

# оптимизированная переносимая на С: gcc 9.2.0, -Ofast
$ time ./ascii_wc </dev/shm/test.txt
lines 15000000, words 44774631, chars 1871822210
took 0.558271 seconds

0.559 real  0.472 user  0.086 sys  1783MB RAM

P.S. У меня i7-2600K, он AVX2 не поддерживает.

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


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




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

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

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


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

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

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

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

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

НЛО прилетело и опубликовало эту надпись здесь

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


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


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

НЛО прилетело и опубликовало эту надпись здесь

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


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


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

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

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


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

НЛО прилетело и опубликовало эту надпись здесь
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.