Skip to content

Instantly share code, notes, and snippets.

@voidlizard
Last active November 6, 2017 03:37
Show Gist options
  • Save voidlizard/a27799d66ee8de424e911e7632c80c73 to your computer and use it in GitHub Desktop.
Save voidlizard/a27799d66ee8de424e911e7632c80c73 to your computer and use it in GitHub Desktop.
Специальная олимпиада имени memcpy: послесловие

Надеюсь, что теперь эта специальная олимпиада затихнет, потому что код-победитель только на ~20% уступает простой записи нулей в /dev/null.

При ближайшем рассмотрении, задача оказалась на скорость вывода в stdout, т.е. так как вход у неё довольно маленький (~10K элементов), то парсить практически всё равно как -- на любом языке из использовавшихся.

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

Сишный код победил за счёт того, что удалось свести задачу к копированиям кусков памяти фиксированного размера при заполнении выходного буфера, и компилятор смог подставить специализированную реализацию memcpy, подходящую к данному размеру блока. Это привело к драматичному росту скорости, который не оставил шансов остальным языкам.

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

Дальше будет субъективное впечатление об используемых тут языках:

0.3 - 2 секунды

C Си как всегда. Плохо читаемо, плохо поддерживаемо, периодически пытается выстрелить вам в ногу или голову. Мы привыкли и не обращаем внимания.

Rust на вид довольно сложен. Даже у тех, кто им владеет, реализация и профилирование задачи заняло довольно много времени, видимо, дольше писать только на Си (несмотря на то, кто итоговый код в разы меньше). Профит от его использования по сравнению с Haskell не столь весом, что бы всё бросить и перейти. Но цене входа Rust выглядит дороже (сложнее), чем идеоматичный Haskell. Странноватый и излишне подробный синтаксис, необходимость всё время думать о владении и вообще размещении в памяти данных --- думать об этом бы не хотелось, кроме клинических случаев. Лучше бы, компилятор выводил это сам, как было в MLTon с регионами, но не взлетело. При этом всём, все привычные возможности функцинальных языков (ладно - конкретно Haskell) наверняка окажутся более анемичными. К сахару для монад и самим монадам, сложным типам и прочему быстро привыкаешь. Но хороший тулинг, нет проблем с кросс-компиляцией с другой стороны.

Haskell крайне страдает от отсутствия хорошей, продуманной стандартной библиотеки, по крайней мере в части ввода-вывода. Строки, файлы, сокеты --- вот это всё. Вместо этого множество разных пакетов и необходимость каждый раз над этим думать. Так же требуется навязываемая партией политика обработки ошибок --- просто признать волевым решением какой-то подход их обработки основным. А прочие подходы --- для особых ценителей. Насаждать подобное можно разными способами, лучший - стандартная библиотека. Перескакивать с Haskell на Rust пока что повода я не увидел, кроме отдельных задач (кросс-компиляция, странные целевые устройства, которые ghc не будут поддерживаться толком никогда). Всё это может быть решено даже без заметных изменений языка, просто кто-то авторитетный должен сделать хорошую Prelude, и потом её поддерживать, взвешенно добавляя в неё новое. Нужны какие-то простые, но удобные подходы к IO с корректным освобождением ресурсов и гарантированно фиксированные по памяти.

2 - 5 секунд

Python оказался очень неплох для подобных "однострочников" и соотношению прибыль / издержки. 6 строк, 4 секунды (только при использовании pypy). Как и положено скриптовому языку, прямо единство формы и содержания. Реально работает политика "один способ что-то сделать" --- в используемом коде мы видим 1 (прописью: один) импорт из библиотеки, и его достаточно, что бы решить задачу. Более того, сокращение числа возможных способов решить типовые задачи приводят к тому, что эти самые способы работают сразу очень неплохо --- потому, что меньше людей со своим особым видением (lazy strings, iteretees, pipes, conduits, machines, streams в Haskell) и усилия коммьюнити сфокусированы. Мне же только надо быстро прочитать и обработать файл любого размера за фиксированную память, какого чёрта ж в самом деле у меня должно быть 9000 способов это сделать?

Go Ничем не поразил, но быстро достигается результат, лучший по производительности, чем в Python. Такой себе квадратно-гнездовой военный язык для программирования взводами и батальонами. Подход имеет право на жизнь.

OCaml как обычно

SML едва ли можно считать живым, но всё же

5 секунд и дальше

C++ Ну, C++ как всегда. Вероятно, у него есть где-то область, в которой он очень хорош и лучше всех остальных. На стыке мутабельности, векторизации и параллелизации. Просто потому, что в других языках для этого пока ничего нет.

C#, Java, Ada, CL и остальные C# хорошо читаем, говорят, еще можно ускорить, но его адепты быстро сдаются. Про остальных сказать нечего - писать сложно, работает медленно, адепты недостаточно упорны и упороты.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment