После недавних статей (№10xd34df00d, №2chapuza, №3picul) сравнивающих скорость работы реализаций упрощенной утилиты wc у меня оставался только один вопрос — Как простая реализация на Haskell оказалась быстрее простой реализации на C ?!
Рубрика «бессмысленные бенчмарки»
Побеждая C двадцатью строками Haskell: пишем свой wc
2020-02-20 в 15:15, admin, рубрики: haskell, бессмысленные бенчмарки, Программирование, функциональное программированиеПривет.
На днях Siemargl предложил мне перевести любопытную статью о победе над юниксовым wc при помощи хаскеля. Переводить её я, конечно же, не буду, и по нескольким причинам:
- автор выжал из однопоточной версии далеко не всё, и однопоточная версия была существенно медленнее
wc, - в той статье для победы потребовалось воспользоваться многопоточностью (что само по себе немного читерство и победа скорее над здравым смыслом, а не над
wc), - для этого автору пришлось углубляться в
трихомонады и моноиды — не, это отличная иллюстрация прелестей моноидального мышления, но ИМХО немного перебор для такой задачи, тем более, что из-за этого - код получился излишне объёмным,
- да и вообще, соревноваться с
wc, которая имеет кучу опций и фич, реализуя её ну очень игрушечный аналог, вообще как-то странно и даже немного глуповато.
Тем не менее, заниматься странными делами — дело хорошее, поэтому сегодня мы попробуем исправить первый из пунктов выше и улучшим результат Криса (так звать автора исходной статьи).
Опять же, как мы выяснили в прошлый раз, код на C я писать не умею, так что писать его и не буду, а в качестве конкурента хаскель-реализации у меня (как и у Криса) выступает сишный wc из GNU Coreutils. Те чуваки уж точно на C писать умеют, коду этому не один десяток лет, да и о производительности они позаботились, судя по таким кусочкам:
/* If the average line length in the block is >= 15, then use
memchr for the next block, where system specific optimizations
may outweigh function call overhead.
FIXME: This line length was determined in 2015, on both
x86_64 and ppc64, but it's worth re-evaluating in future with
newer compilers, CPUs, or memchr() implementations etc. */Спойлер: мы обгоним сишный wc примерно на порядок без всяких проблем, получив вполне идиоматичный код и потратив менее получаса на изменения и оптимизацию оригинального кода.
Быстрее, чем C++; медленнее, чем PHP
2020-01-14 в 12:57, admin, рубрики: haskell, бенчмарки слооожна, бессмысленные бенчмарки, Программирование, функциональное программированиеПривет.
У меня тут случайно код на хаскеле получился быстрее аналогичного кода на C++. Иногда — на 40%.
(время работы, меньше — лучше, C++ снизу)
Что самое смешное — я собирал хаскель-код через LLVM-бекенд, но при этом сравнивал с GCC. Если сравнивать с clang (что вроде как логичнее), то всё становится ещё хуже для плюсов: почему-то на этой задаче clang проигрывает GCC в пару раз, и разница становится не 40%, а этак раза три. Впрочем, одна маленькая модификация C++-кода это поменяет.
Началось всё с того, что для одного моего проекта (который, естественно, делается на хаскеле, и о котором я тоже скоро напишу) нужно было быстро и эффективно считать расстояние Левенштейна между двумя строками. Расстояние Левенштейна — это такая метрика, которая говорит, сколько символов нужно удалить, добавить или заменить в одной строке, чтобы она стала равна другой строке. Я считал расстояния между довольно большими строками (масштаба десятков тысяч символов), поэтому эффективность была действительно важна.
А потом мне стало интересно, насколько быстро я вообще могу это расстояние считать (потратив разумное время на оптимизацию, конечно), так что я набросал вариант на С++ и взял его время работы за этакий идеал, к которому стоит стремиться. Впрочем, как уже понятно, идеал оказался превзойдён.
Посмотрим, как этого можно достичь?
В качестве бонуса — сравнение с некоторыми другими языками. Спойлеры:
- Nim медленнее компилятора C двадцатилетней давности.
- C# в пять раз медленнее Java, которая оказывается вполне на уровне Rust.
- Go вровень с C.
- PHP быстрее питона (что оправдывает вторую часть заголовка).