Комментарии 46
Да, корректно :)
Тормозить меня не пугает, пока оно только POC, который я изоморфирую в эликсир. Я вот буквально на днях так фингертриз, на которых хаскелевы секвенсы, так утащил. Чую, скоро свою реализацию моноида на коленке выпущу.
код в статье я смог прочитать не без труда
Давайте я очень краткий курс бойца тут устрою, в благодарность за ваши развернутые ответы в интересных дискуссиях.
<<_::binary-size(2), ?\n, rest::binary>>Это строка, первые 16 бит — любые, потом возврат каретки, потом сколько угодно байт (модификатор binary). Так можно матчить и биты тоже.
%{bc: bc, wc: wc, lc: lc, ns?: ns}Встроенный тип. Реализован как hashmap. Порядок элементов не гарантируется.
[42] |> Enum.map(fn e -> e * 2 end)
# same as
Enum.map([42], fn e -> e * 2 end)синтаксический сахар для передачи первого параметра в функцию. В чем-то похож на хаскелевский ($), но left associative (потому что нам не завезли partial application из коробки).
@foo 42
@spec ...Атрибуты модуля, доступные во время компиляции. @spec, @type — предопределенные, их компилятор понимает без нас. Остальные — почти просто константы, которые разворачиваются во время компиляции, но, они все доступны из хуков времени компиляции и могут быть использованы более тонко (в коде выше это просто пресеты).
Принимает AST и возвращает AST, который будет вставлен компилятором вместо вызова в BEAM.
Кажется, больше ничего в коде выше смутить не может.
Похоже флеш-синдром заразен ;)
Тем не менее, в комментариях к "первой" статье есть пара заслуживающих упоминания моментов:
- Оригинальная утилита
wcделает больше чем было реализовано на Хаскеле. Можно думать разное про авторовwc, но оптимизацией скорости они точно не заморачивались и поэтому мерятся с болезнымwcджентльменам не к лицу. В целом, как было отмечено, такой "бенчмаркинг" без ТЗ где-то между бредом и жульничеством. - Функционально-равнозначная коду на Haskell
наивная реализация на Cможет выдать результат в разы быстрее. Но тут мнения несколько разошлись, в частности:
- Нет единого мнения какой компилятор
Cи с какими опциями оптимизации/кодогенерации следует использовать. Причина разногласий видимо в том, чтоclangс опциями-Ofast -march=nativeвыполняет (не идеальную, но все же) авто-векторизацию, и в результате реализация наCоказывается в разы быстрее. А как дела с автовекторизацией у компилятора Хаскеля и какой именно набор инструкций он задействует в общем случае (пока) не ясно. - У обоих авторов (реализаций на
Cи на Хаскеле) быстрее работает собственный вариант, а верификации результатов третьими лицами не было.
- Нет единого мнения какой компилятор
Желающим докопаться до сути и составить собственно мнение стоит ознакомиться с топиками на Hacker News (1, 2), где уже звучали обвинения в FUD и во введении в заблуждении относительно скорости в адрес евангелистов Хаскеля и еже с ним.
Судя по коду — заморачивались. Ну серьезно, незаморачивающиеся люди не будут учитывать недавние длины строк и писать цикл для поиска конца строки руками из-за того, что memchr на слишком коротких строках тормозит, вызывая его, если последние строки были достаточно короткими.
Заморачивались, но не до такого уровня как приведенный хаскель код. Ну серьезно, yleo же вполне наглядно показал что будет если на си тоже изначально учитывать только asccii. Почему авторы wc так сделали — гадать бесполезно, надо спрашивать у них. Но для бенчмарка с приведенным хаскелем он не подходит и идеоматичность тут вообще непричем.
По поводу -march=native и опций — надо еще учесть, что у gcc по дефолту стоят безопасные вызовы рантайма, чтобы их отключить надо добавить -U_FORTIFY_SOURCE. Так же возможно понадобятся -fno-stack-protector и frame pointer omission, в зависимости как поступает ghc.
В общем корректный бенчмарк да еще разных компиляторов дело сложное, подводных камней тут масса.
На оптимизацию wc (включая упомянутые мной кусочки) потратили менее получаса? Не верю, извините.
На wc не уверен, т.к. у него больше опций, а вот на вариант потипу yleo — да, во всяком случае в принципе столько, сколько уйдет у меня на это на си. То что си многословнее, тяжелее подстановки — я не спорю. Но ваш посыл, что напишите идеоматично на си и на хаскеле и получите быстрее хаскель — не верно.
Вот посыл напишите такие мелкие консольные утилиты на языках, которые для этого предназначены, например на перле, а не на си. Времени потратите меньше, а скорость будет возможно даже такая же, как на си. И корректное сравнение с вариантом yleo — вот тогда было бы все корректно в статье.
А coreutils — у него задача предоставить core утилиты на голом железе, с зависимостью только от си компилятора, который можно уместить в 300кб кода на нем же (привет tcc). Но кажется все знают что для текстового процессора не лучший выбор.
А там же нет вызовов рантайма. Вы просто бежите по куску памяти и просто инкреметируете счётчики. Там даже вызовов функций может не быть, если компилятор всё заинлайнил (или если используется прямая проверка на пробельные символы, как в предложенных альтернативных С-вариантах).
В wc есть вызовы glibc, может и не влияет, но надо проверять. Так же ghc стандартные isspace, — поддерживает только latin1 (как я понял), а в glibc — поддерживает локали и надо ходить в tls.
У ghc даже стека в привычном смысле нет, хехе. Вот это как раз сравнивать будет очень сложно.
Вот и я про то, надо глянуть асм, скорее всего -fomit-frame-pointer тоже потребуется для корректного сравнения.
Что си, что хаскель можно попробовать еще ускорить. Можно попробовать 16бит табличку, можно попробовать читать по 4-8 байт и разбираться с прочитанным в регистре (для парсинга http заголовков это помогало, односимвольные слова возможно ухудшит).
Что си, что хаскель можно попробовать еще ускорить. Можно попробовать 16бит табличку, можно попробовать читать по 4-8 байт и разбираться с прочитанным в регистре (для парсинга http заголовков это помогало, односимвольные слова возможно ухудшит).
Немного не так. Начало правильное, но не хватает главного. Если интересно, могу объяснить как (на самом деле чисто функциональный подход, т.е. при правильном алгоритме и хорошем хаскель-компиляторе реализации будут работать быстрее и с одинаковой скоростью).
Интересно конечно, с ходу больше не могу придумать как еще можно ускорить.
Основная задержка из-за зависимости по данным при подсчете слов, т.е. состояние всегда зависит от текущего и предыдущего символов (пробел или не пробел).
Эту зависимость нужно сузить, позволив максимальному кол-ву операций выполняться параллельно. Сделать это проще всего следуя стратегии map-reduce.
Каждый символ следует рассматривать как вектор, перемещающий состояние счетчика в некотором пространстве. Сложение этих векторов не коммутативно, т.е. результат зависит от порядка. Поэтому следует отображать эти вектора в другое "удобное" пространство, в котором их проекции легко складывать. Затем нужно будет применить результат к состоянию анализатора, т.е. отобразить результат сложения в инкремент счетчика слов.
typedef struct {
uint16_t m[4];
} hyper_t;
static hyper_t sym2hyper[65536];
static uint8_t hyper2value[512];
static void build_hyper(void) {
/* подготовительная магия наполнения sym2hyper и hyper2value */
}
static unsigned map(const unsigned char *text, size_t i, size_t n) {
return sym2hyper[*(uint16_t *)(text + i + n * 2)].m[n];
}
static unsigned reduce(unsigned prev,
unsigned hyper_a, unsigned hyper_b,
unsigned hyper_c, unsigned hyper_d) {
return prev + hyper_a + hyper_b + hyper_c + hyper_d;
}
static unsigned apply(unsigned hyper) {
result.lines += hyper & 15;
result.words += hyper2value[hyper >> 4];
return /* состояние для следующей итерации */ (hyper >> 8) & 16;
}
static unsigned process_chunk(const unsigned char *text,
const size_t bytes,
unsigned prev) {
result.chars += bytes;
for (size_t i = 0; i < bytes; i += 8)
prev = apply(reduce(prev,
map(text, i, 0),
map(text, i, 1),
map(text, i, 2),
map(text, i, 3)));
return prev;
}Этот код выдает результат за 0.55 секунды, т.е. примерно вдвое быстрее чем наивная версия авто-векторизованная clang-ом с -march=native. Но пока я не уверен в его полной корректности, ибо нужно доделать "магию" (уже лень, но буду сопротивляться).
Интересная мысль, кстати. Это может и моему коду помочь.
Можно догенерить псттернов на несколько спейсов, за которыми не спейс, и избежать сложения, в котором эрланг традиционно слаб.
Но лень :)
Кстати, вопрос: а почему никто пока не упомянул GPU (или я упустил по невнимательности?).
Кармак вон недавно какую-то дичь рассказывал: https://twitter.com/ID_AA_Carmack/status/1228824996228800513
Почему дичь?
В современных картах вроде по несколько тысяч cuda ядер + данные в памяти были оптимизированы под GPU, а под CPU, вероятно, не была использована векторизация. Цифра большая (очень), но я бы не сказал что прямо дичь.
UPD:
Из треда:
I was trying to extract maximum performance from the int8 tensor operations and GPU memory bandwidth, so everything is pre-tiled and transposed as necessary to make the GPU happy. The CPU version is doing tons of indexing calculations to match the tensor fragment layouts
and just doing int8 mads with sum+=a*b, and it probably isn't ordered right for L1 cache. I would expect putting similar effort into a multithreaded AVX512 version with optimal layout on CPU could get many 100x, and perhaps 1000x faster.
Неэквивалентное сравнение из-за -march=native (как вы дальше и пишете). Я считаю, что было бы честно упомянуть, что без этой опции вариант на С медленнее (а хаскель собирается без нее или какого-либо ее эквивалента).Хм, а где вы увидели какую-либо мою нечестность?
В вашей статье было упоминание про Gentoo и сборку
-march=native, а также была таблица, в которой в том числе были результаты при использовании LLVM. Поэтому был использован clang и опции-Ofast -march=native, что общепринято для бенчмарков. Эти опции были сразу приведены вместе с первым исходным кодом и результатами.
Потом вы сами собрали и запускали C-версии как без
-march=native, так и используя gcc. Получив при этом другие результаты.
Итого: результат наивной С-реализации зависит от компилятора и опций оптимизации/кодогенерации. Что абсолютно ожидаемо, и в точности (как мне кажется) отражено в моем первом комментарии выше.
Кроме этого, слабость компилятора Haskell в отношении -march=native не должна является поводом отказа от этой оптимизации.
Не в разы, а менее чем в два раза (clang с -march=native на моей машине с вашим исходником отрабатывает за 0.9 секунд, что менее чем в два раза быстрее искомых 1.45).
По-факту результаты получены на разных машинах с разными версиями компиляторов. У меня цифры другие. На машине с AVX512 или на E2K скорость C-реализации будет еще больше.
А, вы невнимательно читали статью! -march=native использовалься только для сишного wc (потому что сишный wc собирается emerge'м, а менять флаги ради одного этого теста было лень, тем более, что этот флаг даёт фору сишному коду, а не хаскель-версии).
Вы переоцениваете мои интеллектуальные резервы — просто просмотрел "по-диагонали" ;)
Если серьезно, то я не особо заморачивался с -march=native, а следовал простому сценарию: есть железка, перем от неё максимум, но без дополнительных усилий.
Эта оптимизация ломает наблюдаемое поведение: в итоге код на более ранних CPU запускаться не сможет. Например, на моей основной машине i7 3930k без AVX2, поэтому от wc без AVX2 или AVX512 толку там нет.
Хм, а какая исходная точка для образцового поведения?
Вы сделали сравнение с wc, предлагаю начать с i486 в 89-году.
Тогда ваш код "ломает поведение", ибо не компилируется из-за отсутствия Haskell ;)
И на e2k ваш код тоже "фатально меняет поведение", ибо не компилируется.
В целом, наличие/отсутствие AVX это локальные плюсы/минусы, как и x86_64.
Ведь если вам свет временно отключат, то остальные не должны тоже сидеть в темноте?
В любом случае, первое "изменение поведения" — это переход на только-ASCII, в второе — отказ от подсчета "печатной" длины строк (ведь без модификации кода нельзя получить все что умеет wc).
Плюс, не могу не отметить интересный факт: вы почему-то считаете нечестным сравнивать хаскелевскую версию с исходной сишной, которая внутри делает больше вычислений (но имеет такой же наблюдаемый результат), но не считаете нечестным одну из версий собирать с -march=native, что наблюдаемый результат таки меняет.
Нет, уж извините.
Во-первых, кто начал весь этот флеш-моб сравнения теплого с мягким и кликбейтом "в 10 раз"?
Во-вторых, я ни разу не сказал что сравнивать SIMD и не-SIMD версии честно.
Собственно я не смотрел на последствия -march и не знал что clang замутил авто-векторизацию, ибо увиденное соотношения производительности было ожидаемым. Выяснять последствия -march я стал по информации в одного из ваших ответов.
Суть же в том, что тут нет и не может быть рационального сравнения, ибо:
- с одной стороны компилятор haskell со специфической оптимизацией map-конструкций (без этого он бы бесполезен), но с march-лоботомией.
- а с другой стороны наивный C-код, но использующий чуть больше возможностей CPU.
Причина разногласий видимо в том, что clang с опциями -Ofast -march=native выполняет (не идеальную, но все же) авто-векторизациюКак насчет пруфов? «видимо», это совершенно недостаточный аргумент.
Кстати, статья была совсем не про скорость, но опустим этот банальный момент.
Их вообще довольно сложно сравнить, т.к. как я понял ghc работает и с LLVM и без. Про компактность никто не спорит, все замечания были именно про сравнения скорости.
С-версии собранные разными компиляторами с разными опциями дают разную скорость.
Хаскель-версии с поддержкой pipe или только с mmap тоже показывают разный результат.
Автор C-реализации утверждает что быстрее всего его C-вариант собранный clang-ом с -march=native.
А у автора хаскель-версии его вариант быстрее чем C-версия без -march=native.
При этом машины разные, с разными CPU.
Каждый может скомпилировать, запустить, увидеть результаты и показать их при желании.
Какие еще пруфы?
Желающим докопаться до сути и составить собственное мнение [...]
Ну вот я пожелал. Мне неинтересно, кто быстрее (в пределах, скажем так, почти порядка). Мне неинтересно, с какими ключами компилятора мне надо пересобрать виртуальную машину эрланга, чтобы победить на конкурсе по измерению бенчмарков. И — внезапно — никакому бизнесу это тоже не интересно. Никто не станет пересобирать штатный wc, чтобы он победил на чемпионате по бессмысленному чтению пробелов из несуществующего файла.
Все это сравнения — они совсем про другое. У меня, например, в escript версии для начала стартует полноценная ErlangVM, но я не стал это вычитать, потому что на берегу условия простые: запустил утилиту, проверил время выполнения. Главное — уверенность в том, что мы не замерзнем на часок, когда упремся в такой вот файл для процессинга. А не наносекунды, и даже не миллисекунды.
Не о чем жалеть, вы все совершенно точно сформулировали "Ниже вы увидите некоторые трюки, которые я использовал… просто хотел убедиться, что на финише мы не отстанем от победителей на круг.".
Своим комментарием я нисколько не хотел задеть вас или придраться к вашей статье.
Тем не менее, достаточно много "бенчмарков" со странными "прорывными" результатами. Строка "Желающим докопаться до сути..." относится именно к ним.
Все прорывные результаты всегда получены в очень специфических, тепличных условиях, в процессе нескоординированного наблюдения в телескоп — пылинки на рукаве соседа.
Даже от машине к машине, и от теста — к тесту, эти бенчмарки разнятся (потому их всегда запускают пачками, кстати).
Имеет смысл смотреть только на порядки величин (кроме очень особенных случаев выполнения на голом железе собранном вот этими руками, из вот этих материалов, при использовании канифоли строго этой марки, но в этих случаях эрланговая VM просто не запустится, а хаскель — вряд ли скомпилируется).
Не, я понимаю, когда люди выпиливают шесть бит из памяти в ассемблерной реализации штуки, которая должна работать в имплантанте внутри глазного яблока дрозофилы. Но тут… Три миллисекунды, или двадцать, оно мне будет считать слова в очередном бложепостике? — Да пофиг. Не минуту — и хорошо, вот это важно.
Три миллисекунды, или двадцать
А вот если три часа или сутки — это уже заметнее разница хотя коэффициент тот же.
Вот примерно на дроздофилах я и зарабатываю. Поэтому "прорывными" (именно в кавычках) называю бенчмарки где хаскель оказывается в 10 раз быстрее С. Но чтобы не было недопонимания гляньте дисклаймер в моем первом комментарии ко всему этому флеш-мобу.
Так что я скачал его и склеил с самим собой десять раз, как и было завещано.
Автор — ненастоящий рубист и эликсирщик, так как склеил файл как-то иначе, чем
$ ruby -e '10.times { `cat part.txt >> test.txt` }'С какого перепугу у меня дома на ноуте будет руби? Кроме того, ваш вызов шелла из руби, вызванного из шелла — это пропуск сразу вон в ту дверь, у нас части легко помещаются.в память, поэтому:
File.write "test.txt", File.read("part.txt") * 10$ ruby -e '10.times { system("cat part.txt >> test.txt") || raise }'
при этом одна половина посчитается как слово в первом чанке
Не посчитается, потому что после него нет ни пробела, ни возврата каретки. Тут есть опасность не посчитать самое последнее слово, оно [полукорректно] обходится за счет того, что я инициализирую счетчик слов в единицу (передрано в хаскель-варианте по ссылке), но можно и явно обработать последние пробелы, это не скажется на производительности вовсе.
Там есть [спасибо вашему вопросу, иначе бы без тестов я и не заметил] еще проблема с leading spaces в самом начале (мой код их посчитает за 1 слово), её тоже легко обойти пост-процессингом, который, опять же, никак не повлияет на общую производительность. Считать 1 байт и вычесть единицу, если что — это какие-то миллиардные доли процента на такого размера файле.
Примерно 20 строк, примерно такие же результаты: wc на Elixir