Когда оценивать строго в Haskell?

Ответ 1

В ваших примерах шаблоны ударов перемещаются по окончательному вычислению среднего или, скорее, его ингредиентов:

where (!len, !acc)   = V.foldl' f (0,0) xs :: (Int, Double)
where !(len, acc)   = V.foldl' f (0,0) xs :: (Int, Double)

но (с одним очевидным исключением), а не вторым элементом, самой функцией складывания:

       f (len, acc) x = (len+1, acc+x)

Но это f есть действие. В ваших примерах различные способы, с помощью которых вы комментируете (len,acc), как представляется, запускают компилятор, чтобы использовать тонко разные представления о том, что делать с f. Вот почему все кажется слегка оккультным. Дело в том, что это напрямую связано с f.

Основная точка с хлебом и маслом заключается в том, что в левой складке или накопительной петле все аккумулированные материалы должны оцениваться строго. В противном случае вы просто создаете большое выражение с помощью foldl', а затем просите его свернуться, когда придете, наконец, что-то сделать с накопленным вами материалом - здесь, с окончательным вычислением среднего значения.

В ваших примерах, однако, foldl' никогда не дается явно строгая функция, чтобы сбрасывать: накопленные len и acc попадают в ловушку регулярного ленивого набора Haskell.

Проблема строгости возникает здесь, потому что вы накапливаете больше, чем одно, но нужно связать их вместе в один аргумент для операции f, которую вы переходите на foldl'. Это типичный случай для написания строгих типов или записей для накопления; это занимает одну короткую строку

data P = P !Int !Double

тогда вы можете написать

mean0 xs = acc / fromIntegral len
    where P len acc    = V.foldl' f (P 0 0) xs 
          f (P len acc) !x = P (len+1) (acc+x)

Обратите внимание, что я не отмечаю (P len acc) ударом, так как он явно находится в слабой нормальной форме головы - вы можете видеть P и не нужно просить компилятор найти его с помощью! /seq - и, следовательно, f строго в первом аргументе. То же самое верно в том случае, когда вы добавляете строгость к f

          f !(len, acc) x = (len+1, acc+x)

Но функция

          f (len, acc) x = (len+1, acc+x)

был уже строгим в первом аргументе, пара, так как вы можете увидеть внешний конструктор (,) и не нуждаетесь в аннотации строгости (которая в основном просто сообщает компилятору его найти). Но конструктор просто конструирует ленивый кортеж, поэтому он не был (явно) строгим в len и acc

$ time ./foldstrict
5.00000000067109e8
real    0m1.495s

тогда как на моей машине лучше всего:

$ time ./foldstrict
5.00000000067109e8
real    0m1.963s

Ответ 2

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

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

Рекомендации по эффективности Johan Tibell лучше всего указывают на тонкости: http://johantibell.com/files/haskell-performance-patterns.html#(1). Обратите внимание, что последние GHC автоматически выполняют небольшую строчную распаковку без необходимости комментировать. Также см. Strict прагмы.

О том, когда вводить строгие поля: делайте это правильно с самого начала, так как это гораздо труднее закрепить его ретроспективно. Вы все еще можете использовать ленивые поля, но только тогда, когда вы их явно хотите.

Примечание: [] является ленивым и больше используется в качестве структуры управления, которая, как ожидается, будет встроена, а не как контейнер. Используйте vector и т.д. Для последнего.

Примечание 2: существуют специализированные библиотеки, позволяющие вам иметь дело со строгим сгибанием (см. foldl) или с потоковыми вычислениями (conduit, pipes).

Update

Немного о разработке обоснования, так что 1) вы знаете, что это не только для резиновой утки с неба 2) знать, когда/почему отклоняться.

Зачем оценивать строго?

Один случай строгое накопление, как указано в вопросе. Это происходит и в менее очевидных формах - например, подсчет некоторых событий, происходящих в состоянии приложения. Если вы не храните строгий счет, вы можете получить длинную цепочку из +1 thunks build up, которая не требует большой памяти без уважительной причины (вместо сохранения только обновленного счета).

Выше называется memory leak неофициально, даже если это не технически утечка (память не потеряна, она просто удерживается дольше, чем требуется).

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

Путь решения для этого использует NFData из deepseq. Но представьте, что у вас есть окончательная структура данных, слоистая A (B (C)), где каждый уровень вычисляется отдельным потоком, глубоко заставляя структуру перед возвратом. Теперь C сильно затухает (по сути, перемещается в памяти) три раза, B два раза. Если C - это глубокая/большая структура, это отходы. На этом этапе вы можете либо добавить один раз трюк, либо просто использовать строгую строгую структуру данных, где делает мелкое принуждение к WHNF (а не к глубокому NF) имеет тот же эффект глубокого форсирования, но так называемый "трюк" укомплектован компилятором.

Теперь, если вы согласны и осведомлены, вы можете нормально работать с deepseq + Once.

Примечание: очень простая совпадение с одновременной оценкой является однопоточной оценкой в ​​страшном случае чистых ошибок, таких как undefined и error. Они идеально не используются, но если есть, способы атаки на проблему очень похожи на описанные выше (см., Например, spoon).