Параллельная быстрая сортировка на Хаскеле и как нелегко её оказалось написать

[rikert]

Очередная демонизация Хаскеля, аплодирую стоя.

[rikert]

> что он предлагает услуги по F#-консалтингу.

Вот на это очень похоже, потому что только из-за слов "Правильное решение оказалось в 10 раз длиннее, чем намного более простое решение на F# и в целых 100 раз длиннее, чем оригинальный изуродованный алгоритм на Хаскеле." можно сделать однозначный вывод, что автор до конца не разбирается в технической реализации Хаскеля, так как от F# он отличается кардинально, общее у них разве что функциональный принцип, с таким же успехом можно сказать что например на Scala это делается ещё проще, что то в этом роде.

Особенно примечательно использование словосочетания «изуродованный алгоритм», так как вышеприведенный код на Хаскеле не читаемый в принципе, ни типов, имена переменных x xcv df sdf lj ahf as;dfh as;kldfh a;sdfj a'sdfj, какой то набор символов. Я вот одного не пойму, вот человек был нормальным писал на императивных языках но как только он взял в руки Хаскель то у него появляется неудержимое желание сделать спагетти совершенно неясного кода, а с переменные превратить в разбросанные куски различных сочетаний двух-трех букв испорченного генератора паролей.
Спрашивается, ну вот почему ты в своем C# так не пишешь? Почему? Ужас какой то. Ну не въехал ты в Хаскель, ничего страшного, занимайся другими языками, но такие статьи похожи на бессильную злобу.

[qnikst]

При всём при этом, у меня есть личные конкретные баттхёрты от quality of implementation в случае конкретного ghc — в сколь угодно нетривиальных параллельных программах GC начинает жрать непомерно много времени, потому что GC там хоть и параллельный, но не конкурентный, привет stop-the-world, если даже всего один HEC выжрал свой и соседние allocation area. Но это не свойство языка, впрочем. Либо, не отрицаю, я просто не умею писать многопоточные программы на хаскеле.

Проблема тут не в quality of implementation, а в tradeoff между throughput и latency и предсказуемости того, сколько памяти может отжирать программа на пустом месте. Если важна latency и пофиг на память, то можно идти путём go. Если не важен sharing структур между потоками, то можно делать как Erlang.
В целом ветка non-blocking-gc есть, но те тесты, что были показали, что в большинстве случаев усложнение реализации не окупается. Ну и важно помнить, что до ghc 8.0 очень неудачные RTS опции по умолчанию. Так +RTS -A254m -qb0 -ki{size-of-l1-cache} зачастую очень сильно улучшает поведение (после 8.0 -qb0 не нужно, т.к. он выставляется динамически).

[qnikst]

MUT это время работы «мутатора», т.е. самой программы, чем оно больше — тем лучше.

[Bas1l]

Автор действительно предлагает услуги по F# консалтингу, но его аргументы обычно очень адекватные.

Алгоритм на Хаскеле «изуродованный» (bastardized в оригинале), потому что это не решето Эратосфена, а совсем другой алгоритм. В упомянутой научной статье его называют поэтому кодовым именем «unfaithful sieve». Оказывается, он даже хуже, чем реализация «в лоб» на императивном языке («trial division»). В лоб—это для каждого числа искать все его делители. В статье есть и анализ сложности. У нормального решета Θ(n log log n) (почти линейная, можно сказать). У unfaithful sieve—Θ(n^2/(log n)^2). У решения в лоб—Θ(n^(3/2)/(log n)^2). А на F# можно легко написать нормальный алгоритм, потому что в нем есть изменяемое состояние.

Справедливости ради, весь код (кроме первого из двух строчек) взят из постов и комментов людей, которые пытались реализовать эту параллельную быструю сортировку. В статье есть ссылки, они все до сих пор рабочие. То есть там вообще нет кода автора. А люди эти вроде как апологеты Хаскеля (в отличие от автора, да).

[ababo]

Просто, Haskell по факту не является языком общего назначения. Глупо, к примеру, требовать того же от SQL.

[Romaboy]

Справедливости ради, SQL невероятно мощный язык, после очень долгого туториала по Postgres'у кажется, что там в десятки раз больше всяческих типов, конструкций, чем в любом другом. Что-то, а сортировку на SQL точно сделать проще =)

[qnikst]

Харроп то ладно, он всегда был жирным троллем, который не умеет цитировать даже собственные reddit треды, в чем легко можно убедиться пройдя по ссылкам в его посте, но он хотя бы полезный, т.к. пару раз (не преувеличение) после поднятого хайпа интересные вещи в компилятр допиливали.

Но тут интереснее спросить у автора, а насколько у него глубокий уровень экспертизы в Haskell для того, чтобы оставлять подобные
[quote]Прим. перев.: Это перевод истории о том, как нелегко оказалось написать параллельную быструю сортировку (quicksort) на Хаскеле. Оригинал статьи написан в 2010 году, но, мне кажется, он до сих пор поучительный и во многом актуальный.[/quote]

Если охота потроллить haskell советую взять более современные посты, например, про hashtable и поспрашивать у haskell-истов почему они тормозят. Это гораздо полезнее интереснее и ближе к реальности.

[Bas1l]

Мой пост, мне хочется верить, тоже полезный, потому что дает возможность сформировать более взвешенное мнение о чисто функциональных языках и их ограничениях. А так же о том, как осторожно надо относиться к хайпу по поводу какой бы то ни было технологии.

Я на Хаскеле не пишу. Тем не менее, если я правильно понимаю, правильное решето Эратосфена без priority queue в нем, скорее всего, до сих реализовать нельзя. И занимает оно все равно больше строчек, чем решето на любом императивном языке.

[qnikst]

Мой пост, мне хочется верить, тоже полезный, потому что дает возможность сформировать более взвешенное мнение о чисто функциональных языках и их ограничениях.

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

А так же о том, как осторожно надо относиться к хайпу по поводу какой бы то ни было технологии.

Вот с этим согласен, в т.ч. и про функциональные языки и там не все идеально.

Тем не менее, если я правильно понимаю, правильное решето Эратосфена без priority queue в нем, скорее всего, до сих реализовать нельзя.

Более-менее осмысленное императивное (а решето эратосфена это императивный алгоритм) решение можно было получить, когда появились массивы (array), библиотека от 2007 года, статью искать лень. С появлением пакета vector 2008 год, но не входит в стандарт, стало ещё проще. Учитывая, что ST уже было, то можно даже изолировать алгоритм и получить чистый результат как er n = V.toList $ runST $ do { x <- new 0; run x ; return $ unsafeFreeze x }.

При этом строчек будет столько же или меньше, вот некоторые будут выглядеть хуже, т.к. вместо привычного всем a[i] = 0 будет unsafeWrite a i, в случае не возникающего в задаче a[i] = b[j] будет ещё хуже unsafeWrite a i =<< unsafeRead b j. Для меня учитывая количество получаемых плюсов этот синтаксис большой проблемой не является.

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

[Akon32]

Лучше бы TimSort написали.

[qnikst]

Не параллельный уже написали:

https://hackage.haskell.org/package/vector-algorithms-0.7.0.1/docs/Data-Vector-Algorithms-Tim.html

[koldyr]

За всё надо платить. То что, например, системы реального времени медленнее систем общего назначения никого не удивляет. А то что иммутабельность порождает сложности в некоторых алгоритмах это прямо трагедия. К тому же автор слукавил, параллельность пока

[Bas1l]

А у вас есть пример алгоритма, который не ложится на императивный стиль?

[unclechu]

Если ограничиться заголовком статьи, то вот накопал у себя в архивах с личными экспериментами:

{-# LANGUAGE ScopedTypeVariables #-}

import Control.Parallel (par, pseq)
import System.Random (randomRIO)

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
  greater `par` lesser `par` lesser ++ x : greater
  where lesser  = quicksort [y | y <- xs, y <= x]
        greater = quicksort [y | y <- xs, y >  x]

main :: IO ()
main = do
  (randoms :: [Int]) <- mapM (const $ randomRIO (1, 9)) $ take 50000 $ repeat 1
  print $ quicksort randoms