Всегда гарантируемый порядок вычисления `seq` (со странным поведением`pseq` дополнительно)

Question

Документация seq Функция говорит следующее:

Примечание о порядке оценки: выражение seq a b не гарантирует, что a будет оцениваться раньше b, Единственная гарантия, предоставленная seq является то, что оба a а также b будет оцениваться раньше seq возвращает значение В частности, это означает, что b может быть оценена раньше a, Если вам нужно гарантировать определенный порядок оценки, вы должны использовать функцию pseq из "параллельного" пакета.

Поэтому у меня ленивая версия sum функция с аккумулятором:

sum :: Num a => [a] -> a
sum = go 0
  where
    go acc []     = acc
    go acc (x:xs) = go (x + acc) xs

Очевидно, это очень медленно в больших списках. Сейчас я переписываю эту функцию, используя seq:

sum :: Num a => [a] -> a
sum = go 0
  where
    go acc []     = acc
    go acc (x:xs) = let acc' = x + acc
                    in acc' `seq` go acc' xs

И я вижу огромный рост производительности! Но мне интересно, насколько это надежно? Я получил это по счастливой случайности? Потому что GHC может сначала оценить рекурсивный вызов (согласно документации) и все же накапливать громадины. Похоже, мне нужно использовать pseq чтобы убедиться, что acc' всегда оценивается перед рекурсивным вызовом. Но с pseq Я вижу снижение производительности по сравнению с seq версия. Числа на моей машине (для расчета sum [1 .. 10^7]:

• наивный: 2.6s
• seq: 0.2s
• pseq: 0.5s

Я использую GHC-8.2.2 и компилирую с stack ghc -- File.hs команда.

После того, как я попытался скомпилировать с stack ghc -- -O File.hs командный разрыв между seq а также pseq ушел Теперь они оба бегут в 0.2s,

Так моя реализация демонстрирует свойства, которые я хочу? Или у GHC есть какая-то особенность реализации? Почему pseq помедленнее? Существует ли какой-то пример, где seq a b имеет разные результаты в зависимости от порядка оценки (один и тот же код, но разные флаги компилятора / разные компиляторы / и т. д.)?

Answer 1

Ответы до сих пор были сосредоточены на seq против pseq проблемы с производительностью, но я думаю, что вы изначально хотели знать, какой из двух вы должны использовать.

Короткий ответ таков: хотя оба должны генерировать практически идентично работающий код на практике (по крайней мере, когда включены надлежащие флаги оптимизации), примитив seq, и не pseqявляется правильным выбором для вашей ситуации. С помощью pseq не является идиоматичным, сбивающим с толку и потенциально контрпродуктивным с точки зрения производительности, и ваша причина его использования основана на ошибочном понимании того, что означает его гарантия порядка оценки и что она подразумевает в отношении производительности. Хотя нет никаких гарантий относительно производительности для разных наборов флагов компилятора (а тем более для других компиляторов), если вы когда-нибудь столкнетесь с ситуацией, когда seq версия приведенного выше кода работает значительно медленнее, чем pseq версия, использующая флаги оптимизации "качество продукции" с компилятором GHC, вы должны считать это ошибкой GHC и подать отчет об ошибке.

Длинный ответ, конечно, длиннее...

Во-первых, давайте проясним, что seq а также pseq семантически идентичны в том смысле, что они оба удовлетворяют уравнениям:

seq _|_ b = _|_
seq a b = b -- if a is not _|_
pseq _|_ b = _|_
pseq a b = b -- if a is not _|_

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

Кроме того, в вашем конкретном seqверсия функции на основе sumнетрудно увидеть, что нет ситуации, в которой seq вызывается с неопределенным первым аргументом, но с заданным вторым аргументом (при условии использования стандартного числового типа), поэтому вы даже не используете семантические свойства seq, Вы могли бы переопределить seq как seq a b = b и имеют точно такую ​​же семантику. Конечно, вы знаете это - вот почему ваша первая версия не использовала seq, Вместо этого вы используете seq для побочного побочного эффекта производительности, так что мы находимся за пределами семантических гарантий и возвращаемся в область конкретных реализаций и характеристик производительности компилятора GHC (где на самом деле нет никаких гарантий, о которых можно было бы говорить).

Во-вторых, это подводит нас к намеченной цели seq, Он редко используется для своих семантических свойств, потому что эти свойства не очень полезны. Кто хотел бы вычисления seq a b возвращать b за исключением того, что оно не должно завершаться, если какое-то несвязанное выражение a не может завершиться? (Исключения - без каламбура - это такие вещи, как обработка исключений, где вы можете использовать seq или же deepSeq который основан на seq заставить оценку не заканчивающегося выражения неконтролируемым или контролируемым образом, прежде чем начинать оценку другого выражения.)

Вместо, seq a b предназначен для принудительной оценки a слабой голове нормальной формы, прежде чем вернуть результат b предотвратить накопление глыб. Идея в том, если у вас есть выражение b который создает thunk, который потенциально может накапливаться поверх другого неоцененного thunk, представленного aВы можете предотвратить это накопление, используя seq a b, "Гарантия" слабая: GHC гарантирует, что понимает, что вы не хотите a оставаться неоцененным seq a bценность востребована. Технически это не гарантирует, что a будет "оцениваться раньше" bчто бы это ни значило, но вам не нужна эта гарантия. Когда вы беспокоитесь о том, что без этой гарантии GHC может сначала оценить рекурсивный вызов и при этом накопить громадный поток, это так же смешно, как и беспокоиться о том, что pseq a b может оценить свой первый аргумент, затем подождать 15 минут (просто чтобы убедиться, что первый аргумент был оценен!), прежде чем оценивать его второй.

Это ситуация, когда вы должны доверять GHC, чтобы поступать правильно. Вам может показаться, что единственный способ реализовать выигрыш в производительности seq a b для a быть оцененным в WHNF перед оценкой b запускается, но вполне возможно, что в этой или других ситуациях существуют оптимизации, которые технически начинают оценивать b (или даже полностью оценить b к WHNF), оставляя a в течение короткого времени не оценивалось для повышения производительности при сохранении семантики seq a b, Используя pseq вместо этого вы можете запретить GHC такую ​​оптимизацию. (В вашем sum В программной ситуации такой оптимизации, несомненно, нет, но при более сложном использовании seq, Там может быть.)

В-третьих, важно понимать, что pseq на самом деле для. Впервые он был описан в Marlow 2009 в контексте параллельного программирования. Предположим, мы хотим распараллелить два дорогих вычисления. foo а также bar а затем объединить (скажем, добавить) свои результаты:

foo `par` (bar `seq` foo+bar)  -- parens redundant but included for clarity

Намерение здесь состоит в том, что - когда значение этого выражения востребовано - оно создает искру для вычисления foo параллельно, а затем, через seq выражение, начинает оценивать bar до WHNF (т. е. это числовое значение, скажем), прежде чем окончательно оценить foo+bar который будет ждать на искру foo перед добавлением и возвратом результатов.

Здесь возможно, что GHC распознает это для определенного числового типа, (1) foo+bar автоматически не завершается, если bar удовлетворяет формальную семантическую гарантию seq; и (2) оценка foo+bar чтобы WHNF автоматически форсирует оценку bar WHNF, предотвращая любое накопление thunk и таким образом удовлетворяя неформальную гарантию реализации seq, В этой ситуации GHC может не стесняться оптимизировать seq прочь, чтобы дать:

foo `par` foo+bar

особенно если он считает, что было бы целесообразнее начать оценку foo+bar до окончания оценки bar на WHNF.

Что GHC не достаточно умен, чтобы понять, что - если оценка foo в foo+bar начинается до foo Искра запланирована, искра будет вспыхивать, и параллельное выполнение не произойдет.

Это действительно только в этом случае, когда вам нужно явно отложить запрос значения вспыхнувшего выражения, чтобы дать возможность запланировать его до того, как основной поток "догонит", что вам нужна дополнительная гарантия pseq и хотят, чтобы GHC отказался от дополнительных возможностей оптимизации, допускаемых более слабой гарантией seq:

foo `par` (bar `pseq` foo+bar)

Вот, pseq не позволит GHC внедрить любую оптимизацию, которая могла бы foo+bar начать оценку (потенциально foo искра) раньше bar находится в WHNF (что, мы надеемся, позволяет достаточно времени для планирования зажигания).

В результате, если вы используете pseq для чего-то другого, кроме параллельного программирования, вы используете это неправильно. (Ну, может быть, есть какие-то странные ситуации, но...) Если все, что вы хотите сделать, это принудительно выполнить строгую оценку и / или оценку thunk, чтобы повысить производительность в непараллельном коде, используя seq (или же $! который определяется с точки зрения seq или строгие типы данных Haskell, которые определяются с точки зрения $!) это правильный подход.

(Или, если верить тестам @Kindaro, правильный подход - беспощадный бенчмаркинг с конкретными версиями и флагами компилятора.)

Answer 2

Я вижу только такую ​​разницу с отключенными оптимизациями. С ghc -O и то и другое pseq а также seq выполнить то же самое.

Расслабленная семантика seq разрешить преобразования, приводящие к более медленному коду. Я не могу вспомнить ситуацию, когда это действительно происходит. Мы просто предполагаем, что GHC делает правильные вещи. К сожалению, у нас нет способа выразить это поведение в терминах высокоуровневой семантики для Haskell.

Почему pseq медленнее?

pseq x y = x `seq` lazy y

pseq таким образом, реализуется с помощью seq, Наблюдаемые накладные расходы связаны с дополнительным косвенным вызовом pseq,

Даже если они в конечном итоге будут оптимизированы, это не обязательно будет хорошей идеей для использования pseq вместо seq, В то время как более строгая семантика упорядочения, кажется, подразумевает предполагаемый эффект (что go не накапливает Thunk), это может отключить некоторые дальнейшие оптимизации: возможно, оценка x и оценивая y может быть разложен на операции низкого уровня, некоторые из которых мы не прочь бы пересечь pseq граница.

Существует ли какой-нибудь пример, в котором seq a b имеет разные результаты в зависимости от порядка вычисления (один и тот же код, но разные флаги компилятора / разные компиляторы / и т. Д.)?

Это может бросить либо "a" или же "b",

seq (error "a") (error "b")

Я предполагаю, что в статье объясняется обоснование исключений в Haskell, A Семантика для неточных исключений.

Answer 3

Редактировать: моя теория провалилась, так как время, которое я наблюдал, было сильно искажено влиянием самого профилирования; с профилированием данные идут вразрез с теорией. Более того, время между версиями GHC несколько различается. Я собираю более точные наблюдения даже сейчас, и буду дорабатывать этот ответ, когда подойду к заключительному вопросу.

---

По поводу вопроса "почему pseq медленнее ", у меня есть теория.

1. • Давайте перефразируем acc' `seq` go acc' xs как strict (go (strict acc') xs),
   • Так же, acc' `pseq` go acc' xs перефразируется как lazy (go (strict acc') xs),
2. • Теперь давайте перефразируем go acc (x:xs) = let ... in ... в go acc (x:xs) = strict (go (x + acc) xs) в случае seq,
   • И к go acc (x:xs) = lazy (go (x + acc) xs) в случае pseq,

Теперь легко увидеть, что в случае pseq, go получает ленивый Thunk, который будет оценен в какой-то момент позже. В определении sum, go никогда не появляется слева от pseqи, таким образом, во время пробега sumЭвакуация вообще не будет принудительной. Более того, это происходит для каждого рекурсивного вызова goвот так скопы накапливаются.

Это теория, построенная из ничего, но у меня есть частичное доказательство. В частности, я узнал, что go выделяет линейную память в pseq случай, но не в случае seq, Вы можете убедиться сами, запустив следующие команды оболочки:

for file in SumNaive.hs SumPseq.hs SumSeq.hs 
do
    stack ghc                \
        --library-profiling  \
        --package parallel   \
        --                   \
        $file                \
        -main-is ${file%.hs} \
        -o ${file%.hs}       \
        -prof                \
        -fprof-auto
done

for file in SumNaive.hs SumSeq.hs SumPseq.hs
do
    time ./${file%.hs} +RTS -P
done

- И сравните распределение памяти go центр затрат.

COST CENTRE             ...  ticks     bytes
SumNaive.prof:sum.go    ...    782 559999984
SumPseq.prof:sum.go     ...    669 800000016
SumSeq.prof:sum.go      ...    161         0

---

пост скриптум

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

SumNaive.hs

module SumNaive where

import Prelude hiding (sum)

sum :: Num a => [a] -> a
sum = go 0
  where
    go acc []     = acc
    go acc (x:xs) = go (x + acc) xs

main = print $ sum [1..10^7]

SumSeq.hs

module SumSeq where

import Prelude hiding (sum)

sum :: Num a => [a] -> a
sum = go 0
  where
    go acc []     = acc
    go acc (x:xs) = let acc' = x + acc
                    in acc' `seq` go acc' xs

main = print $ sum [1..10^7]

SumPseq.hs

module SumPseq where

import Prelude hiding (sum)
import Control.Parallel (pseq)

sum :: Num a => [a] -> a
sum = go 0
  where
    go acc []     = acc
    go acc (x:xs) = let acc' = x + acc
                    in acc' `pseq` go acc' xs

main = print $ sum [1..10^7]

Время без оптимизаций:

./SumNaive +RTS -P  4.72s user 0.53s system 99% cpu 5.254 total
./SumSeq +RTS -P  0.84s user 0.00s system 99% cpu 0.843 total
./SumPseq +RTS -P  2.19s user 0.22s system 99% cpu 2.408 total

Время с -O:

./SumNaive +RTS -P  0.58s user 0.00s system 99% cpu 0.584 total
./SumSeq +RTS -P  0.60s user 0.00s system 99% cpu 0.605 total
./SumPseq +RTS -P  1.91s user 0.24s system 99% cpu 2.147 total

Время с -O2:

./SumNaive +RTS -P  0.57s user 0.00s system 99% cpu 0.570 total
./SumSeq +RTS -P  0.61s user 0.01s system 99% cpu 0.621 total
./SumPseq +RTS -P  1.92s user 0.22s system 99% cpu 2.137 total

Может быть видно, что:

• Наивный вариант имеет низкую производительность без оптимизации, но отличную производительность при любом -O или же -O2 - в той степени, в которой он превосходит все остальные.

• seq Вариант имеет хорошую производительность, которая очень мало улучшается оптимизацией, так что с -O или же -O2 Наивный вариант превосходит его.

• pseq вариант имеет стабильно низкую производительность, примерно в два раза лучше, чем наивный вариант без оптимизации, и в четыре раза хуже, чем другие -O или же -O2, Оптимизация влияет на это примерно так же, как seq вариант.