Pull to refresh

Comments 29

Очередная демонизация Хаскеля, аплодирую стоя.
UFO just landed and posted this here
UFO just landed and posted this here
> что он предлагает услуги по F#-консалтингу.

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

Особенно примечательно использование словосочетания «изуродованный алгоритм», так как вышеприведенный код на Хаскеле не читаемый в принципе, ни типов, имена переменных x xcv df sdf lj ahf as;dfh as;kldfh a;sdfj a'sdfj, какой то набор символов. Я вот одного не пойму, вот человек был нормальным писал на императивных языках но как только он взял в руки Хаскель то у него появляется неудержимое желание сделать спагетти совершенно неясного кода, а с переменные превратить в разбросанные куски различных сочетаний двух-трех букв испорченного генератора паролей.
Спрашивается, ну вот почему ты в своем C# так не пишешь? Почему? Ужас какой то. Ну не въехал ты в Хаскель, ничего страшного, занимайся другими языками, но такие статьи похожи на бессильную злобу.
UFO just landed and posted this here
При всём при этом, у меня есть личные конкретные баттхёрты от 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 не нужно, т.к. он выставляется динамически).
UFO just landed and posted this here
MUT это время работы «мутатора», т.е. самой программы, чем оно больше — тем лучше.
UFO just landed and posted this here
Автор действительно предлагает услуги по F# консалтингу, но его аргументы обычно очень адекватные.

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

Справедливости ради, весь код (кроме первого из двух строчек) взят из постов и комментов людей, которые пытались реализовать эту параллельную быструю сортировку. В статье есть ссылки, они все до сих пор рабочие. То есть там вообще нет кода автора. А люди эти вроде как апологеты Хаскеля (в отличие от автора, да).
UFO just landed and posted this here
UFO just landed and posted this here
Просто, Haskell по факту не является языком общего назначения. Глупо, к примеру, требовать того же от SQL.
UFO just landed and posted this here
Справедливости ради, SQL невероятно мощный язык, после очень долгого туториала по Postgres'у кажется, что там в десятки раз больше всяческих типов, конструкций, чем в любом другом. Что-то, а сортировку на SQL точно сделать проще =)
UFO just landed and posted this here
Харроп то ладно, он всегда был жирным троллем, который не умеет цитировать даже собственные reddit треды, в чем легко можно убедиться пройдя по ссылкам в его посте, но он хотя бы полезный, т.к. пару раз (не преувеличение) после поднятого хайпа интересные вещи в компилятр допиливали.

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

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

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


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

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


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

Тем не менее, если я правильно понимаю, правильное решето Эратосфена без 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 ещё нет. И главное я не знаю зачем нужно пиать полностью функциональную версию в чисто императивном алгоритме, если в языке есть прекрасная поддержка императивности и локализуемой изменяемости.
Не параллельный уже написали:

https://hackage.haskell.org/package/vector-algorithms-0.7.0.1/docs/Data-Vector-Algorithms-Tim.html
За всё надо платить. То что, например, системы реального времени медленнее систем общего назначения никого не удивляет. А то что иммутабельность порождает сложности в некоторых алгоритмах это прямо трагедия. К тому же автор слукавил, параллельность пока
UFO just landed and posted this here
UFO just landed and posted this here
А у вас есть пример алгоритма, который не ложится на императивный стиль?
UFO just landed and posted this here
UFO just landed and posted this here
Если ограничиться заголовком статьи, то вот накопал у себя в архивах с личными экспериментами:
{-# 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
UFO just landed and posted this here
Sign up to leave a comment.

Articles