Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

 "картинка для привлечения внимания"

О специальной олимпиаде Haskell vs Python (pypy) vs всё остальное

Первоначально задача возникла в 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

Довольно быстро возникло понимание, что

  1. Как всегда, виноваты строки
  2. И ввод-вывод

Довольно быстро пришли к всё еще идеоматичной версии на 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.

@optician
Copy link

optician commented Oct 24, 2017

#!/bin/bash

declare -a arr1 arr2
time while IFS=" " read -r c1 c2;
do   
	arr1+=("$c1");   
	arr2+=("$c2"); 
done < 49zGQ6Zt.txt

time eval echo {"${arr1[*]}"}{"${arr2[*]}"} > /dev/null

Just for fun. С переносами в выводе забил уже разбираться. В cygwin инфернально жрет память (намного больше чем выхлоп по размеру) и у меня работает порядка 12 минут.

Loading

@Abbath
Copy link

Abbath commented Oct 24, 2017

#include <iostream>
#include <algorithm>
#include <list>
#include <deque>
using namespace std;

int main(){
  string a, b;   
  deque<string> as, bs;
  while (cin){
    cin >> a >> b;
    as.push_back(a);
    bs.push_back(b);
  }
  string megastring;
  const int max = 1000000 * a.size() * 2;
  megastring.reserve(max);
  const string e = "\n";
  auto iter = begin(megastring);
  for(const auto& a : as) {
    for(const auto& b : bs){
      const string elem{a+b+e};
      copy(begin(elem), end(elem), iter);
      if(megastring.size() >= max){
        cout << megastring;
        iter = megastring.begin();
      }
    }
  }
  return 0;
}

С++ 2.12s

Loading

@NightBlues
Copy link

NightBlues commented Oct 24, 2017

OCaml: https://gist.github.com/NightBlues/ff0eb61480e5deed83db902fcdf42f0a

real	0m1.803s
user	0m1.800s
sys	0m0.000s

на этой же машине версия "хаскельная версия by @qnikst использует vector stream fusion":

real	0m2.106s
user	0m2.484s
sys	0m0.360s

Loading

@voidlizard
Copy link
Author

voidlizard commented Oct 24, 2017

хаскель без оптимизаций, поди. у меня результат обратный в этом тесте. хотя, еще версия ghc влияет

Loading

@NightBlues
Copy link

NightBlues commented Oct 24, 2017

хаскель без оптимизаций, поди. у меня результат обратный в этом тесте. хотя, еще версия ghc влияет

все без оптимизаций - stack build и ocamlbuild

Loading

@voidlizard
Copy link
Author

voidlizard commented Oct 24, 2017

хаскель без оптимизаций смысла не имеет

Loading

@enomado
Copy link

enomado commented Oct 26, 2017

Феерический пример подмен и манипуляций.

В задаче есть два источника ботлнеков - вывод и генерация перестановок. Ботлнек вывода в том что print делает flush после каждой строки и легко чинится буферизацией. Генерация перестановок это CPU-bound и говорит уже о непосредственной оптимизации языка/структур данных/попадания в кеш/бранчпредиктор/пайплайн.

Само по себе соревнование макроассемблера и макроассемблера с типизацией бессмысленно потому что в итоге соревнуются подходы а не то как и что скомпилирует код, хотя наверное соревнование go, pypy и v8 во времени отдачи портов вордпресса под каждую платформу имело бы смысл.

Хронология событий:

  • сравнение небуферизированного вывода с худо-бедно буферизированым - мм окей, "достойно внимания".

  • сделали кое-какую буферизацию и ботлнек ушел в перестановки - делаем какието "выводы".

  • кто-то понял что буферизация одинаковыми кусками быстрее и написал её на расте (попутно обмазав код хинтами для бранч-предиктора). Изза этого финта раст ОБЬЯВЛЯЕТСЯ победителем.

  • то же самое пишется на сях и си изи в четыре раза быстрее раста но выводы уже сделаны.

  • теоретического предела т.е. времени вывода не представлено.
    $ yes | pv > /dev/null например выдает 2.44GiB/s. Мне лень разбираться много это или мало но это имеет смысл.

Короче как обычно бенчмаркнули скорость копирование памяти о чем тут конечно забыли написать

Loading

@voidlizard
Copy link
Author

voidlizard commented Oct 27, 2017

Ну, конечно постфактум язвительным специалистам из интернета всё видно сразу, без написания
кода. О том, где какие ботлнеки разобрались уже в процессе, но довльно быстро, о чём и написано.

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

Ваша хронология фактически неточна, так как на расте копирование одинаковыми кусками ничего не даёт,
как и хинты likely/unlikely/ Т.е вы не в курсе. Предположу, что вы топите за сиплюсплюс, и от происходящего
у вас бомбануло.

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

Rust был объявлен текущим победителем, потому что документ писался в реальном времени, и на момент написания абзаца код на расте был самым быстрым, а продолжать никто вроде не собирался. Но уже несколькими абзацами ниже идет про версию на Си, которая быстрее раста, и на момент написания вашего комментария этот абзац уже был. И это написано и в заключении, на которое вы ссылаетесь, и даже на референсное копирование нулей в /dev/null там упоминается, и скорость этого процесса относительно финальной версии.

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

В итоге олимпиада практически полезна, потому что по её итогам в Haskell пропатчат FastBuilder и он будет работать в пару раз быстрее, сократив отрыв на этой задаче от Си. А haters как обычно gonna hate.

Loading

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