Первоначально задача возникла в https://t.me/haskellru и формулировалась примерно так: почему следующий код на Haskell
main :: IO ()
main = do
interact processAll
processAll = concat . process . unzip . map toPairs . lines
process (l1, l2) = [format e1 e2 | e1 <- l1, e2 <- l2]
toPairs line = (el1, tail el2)
where (el1, el2) = break (==' ') line
format a b = a ++ b ++ "\n"работает в разы медленнее, чем код на Python:
#!/usr/bin/env pypy
import sys
w = [l.split(' ', 1) for l in sys.stdin]
pref = [x[0] for x in w]
suff = [x[1].rstrip() for x in w]
for p in pref:
print "\n".join([(p + s) for s in suff])
(на самом деле, это уже оптимизированная версия на Python, и запускается при помощи pypy, а не обычным образом).
Если сформулировать словами, то программа должна быстро читать из stdin
поток лексем вида
prefix <space> suffix <endline>
считывать пары (prefix, suffix) и кормить stdout
всеми возможными сочетаниями prefix и suffix
Довольно быстро возникло понимание, что
- Как всегда, виноваты строки
- И ввод-вывод
Довольно быстро пришли к всё еще идеоматичной версии на Haskell:
module Main where
import Data.Monoid
import Data.List
import qualified Data.ByteString.Char8 as BS
import Data.List.Split
import qualified Data.Vector as V
import Control.Monad
import qualified Data.ByteString.FastBuilder as B
import System.IO
main = do
ls <- V.fromList . BS.words <$> BS.hGetContents stdin
let p = V.ifilter (\i _ -> even i) ls
let s = V.ifilter (\i _ -> odd i) ls
let wtf = V.map (\pref -> foldMap (mkb pref) s) p
mapM_ (B.hPutBuilder stdout) wtf
where
mkb s1 s2 = B.byteString s1 <> B.byteString s2 <> B.char7 '\n'для которой, на самом деле, есть не слишком медленная версия без хаков с векторами, т.е с честным парсингом через (примерно)
(p,s) <- unzip . fmap (\[a,b] -> (a,b) . words)
. BS.lines <$> BS.getContents stdinНаиболее экстремальная хаскельная версия by @qnikst использует vector stream fusion и выглядит примерно так:
{-# Language OverloadedStrings #-}
{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}
module Main where
import qualified Data.ByteString.Char8 as BS8
import qualified Data.ByteString.Lazy as BSL
import qualified Data.ByteString.FastBuilder as Builder
import Data.ByteString.Char8 (ByteString)
import Data.Monoid ((<>))
import qualified Data.Vector as V
import GHC.Exts
import System.IO
main :: IO ()
main = do
ws <- BS8.lines <$> BS8.getContents
let s = V.map (\v -> case BS8.words v of
(a:_) -> a)
$ V.fromList ws
BSL.hPutStr stdout
$ Builder.toLazyByteStringWith 110000 110000
$ foldMap (\suff ->
V.foldr (\pref nx -> Builder.byteString suff
<> Builder.byteString pref
<> Builder.char8 '\n'
<> nx) mempty (mkP ws)) s
{-# NOINLINE mkP #-}
mkP = V.map (\v -> case BS8.words v of
(_:b:_) -> b)
. V.fromListИтого, "всё-еще-идеоматичная" версия выигрывает у pypy где-то раза в два, "экстремальная" - раза в четыре и ведёт себя примерно, как Си.
Разумеется, оптимизация микробенчмарков затягивает, как алкоголь и азартные игры, поэтому версии на C, C++, C# и Rust ждать себя не заставили.
С "энтерпрайзной" версией на Си можно ознакомиться здесь:
https://github.com/voidlizard/bsfuck-c
Она использует кое-какие библиотеки, честно парсит входной поток чем-то, что похоже на парсер-комбинаторы, сохраняет результаты в связных списках, не делает предположений про размер ввода, копирует память ну и вообще субоптимально. Показывает результаты, примерно как "экстремальная" хаскельная версия. Память в конце не чистит, потому, что лень, но утечек там всего два массива и список токенов, они на виду лежат, если что.
Самая быстрая (из имеющихся) узкоспециализированная версия на Си:
https://gist.github.com/voidlizard/dddf9ef4fbfa860da1ea2ebc030b6935
Уже быстрее хаскелла.
Текущий победитель - версия на Rust:
https://github.com/mersinvald/rust-vs-haskell-special-olimpiade
Участвовали еще версии на C++ и C#, но они 1) сильно медленнее 2) не выполняют условия теста - т.е md5sum от выхлопа не совпадает с версией на pypy, которая взята за основу.
Какую-то мораль, кроме "используйте байтстроки и FastBuilder, смотрите на настройки IO и буферизуйте вручную, если нужен быстрый вывод на Haskell" я пока сформулировать затрудняюсь.
Узким местом почти на всех языках стал ввод-вывод, а именно, большое количество syscalls при выводе результатов.
Почти везде помогла правильно сделанная буферизация, которую нельзя делать тупо, так как размер вывода примерно квадратичен от размера входа.
Еще стоит отметить, что по метрике "скорость работы первого пришедшего в голову кода" победил, наверное python.
Первая пришедшая мне в голову версия на Haskell просто сожрала всю память и вызвала kernel panic.
Вторая ("всё-еще-идеоматичная") версия на Haskell работала уже в два раза быстрее референса, но всё равно, pypy поразил.
Все остальные версии либо жрут всю память, либо работают долго (C++, С#).
Код на C# неожиданно хорошо читаем, как и C++. Но оба медленные.
Код на C писать мучительно, как и ожидалось. При том, что Rust в итоге быстрее C. Так что для задач, когда надо производительность любой ценой --- надо внимательно посмотреть на Rust, он уже работает, как замена C.
Код на Python, "идеоматичном" Haskell, С++ и C# написался за минуты. Написание, отладка, оптимизация кода C и Rust заняла часы.
Первый взбредший в голову С работает, в лучшем случае, как Python (но пишется много дольше).
Ссылка на входной файл
md5sum правильного выхлопа (за основу - версия на pypy) -
$ ./v-stream < ./49zGQ6Zt.txt | md5sum
eb8d32c8d260d240b351dfadd42cb5e5 -
Продолжение следует.
UPD
Победил C, после копирования памяти блоками фиксированного размера:
static inline void dump_chunk(struct chunk *c) {
const size_t len = c->h.len;
char *src = chunk_cstr(c);
if( dump_avail() < len ) {
dump_fflush();
}
if( __builtin_expect(!!(len>8), 0) ) {
memcpy(out_p, src, len);
} else {
memcpy(out_p, src, 8); // <- ЗДЕСЬ
}
src += len;
out_p += len;
}Разница с лучшей версией на Rust - почти в четыре раза (см. fixchunks.c и последний код от @qnikst).
Дальнейшие соревнования видятся бессмысленными.
UPD.
- Java/Scala: https://gist.github.com/optician/830cb8fe1212eae055ec9fdfb1cd78a8
- Очередной С от @qnikst, побивает Rust https://paste.pound-python.org/show/ghuOtpbzd4KN0R7oc7At/
- Go лучше pypy spol.go
- Go c буферизацией чуть хуже идеоматичного хаскела
- Пока что самая быстрая версия на C fixchunk
- Версия от @qnikst, еще чуть быстрее
- OCaml быстрее идеоматичного хаскела, медленнее v-stream
- SML - говорят, медленнее v-stream раза в полтора
все без оптимизаций -
stack buildиocamlbuild