Когда мемоизация выполняется автоматически в GHC Haskell?

106

Я не могу понять, почему m1, по-видимому, мемоизирован, а m2 отсутствует в следующем:

m1      = ((filter odd [1..]) !!)

m2 n    = ((filter odd [1..]) !! n)

m1 10000000 занимает около 1,5 секунд при первом вызове и небольшую часть этого времени при последующих вызовах (предположительно, он кэширует список), тогда как m2 10000000 всегда занимает такое же количество времени (перестраивает список при каждом вызове). Есть идеи, что происходит? Есть ли какие-то практические правила относительно того, когда и когда GHC запомнит функцию? Спасибо.

haskell ghc memoization Иордания
источник

Ответы:

112

GHC не запоминает функции.

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

m1' = (!!) (filter odd [1..])              -- NB: See below!
m2' = \n -> (!!) (filter odd [1..]) n

(Примечание: отчет Haskell 98 на самом деле описывает левую секцию оператора (a %)как эквивалент \b -> (%) a b, но GHC обессахаривает ее (%) a. Технически они отличаются, потому что их можно различить по seq. Думаю, я мог бы подать заявку на GHC Trac по этому поводу.)

Учитывая это, вы можете видеть, что in m1', выражение filter odd [1..]не содержится ни в одном лямбда-выражении, поэтому оно будет вычисляться только один раз за запуск вашей программы, в то время как in m2', filter odd [1..]будет вычисляться каждый раз при вводе лямбда-выражения, т. Е. на каждый вызов m2'. Это объясняет разницу во времени, которую вы видите.

Фактически, некоторые версии GHC с определенными параметрами оптимизации будут иметь больше значений, чем указано в приведенном выше описании. В некоторых ситуациях это может быть проблематично. Например, рассмотрим функцию

f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x])

GHC может заметить, что yэто не зависит от xи переписать функцию на

f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x])

В этом случае новая версия намного менее эффективна, потому что ей придется считывать около 1 ГБ из памяти, в которой yона хранится, в то время как исходная версия будет работать в постоянном пространстве и поместиться в кеш-память процессора. Фактически, в GHC 6.12.1 функция fпочти в два раза быстрее при компиляции без оптимизации, чем при компиляции -O2.

Рид Бартон
источник
1
Стоимость вычисления выражения (filter odd [1 ..]) в любом случае близка к нулю - в конце концов, это ленивый список, поэтому реальная стоимость находится в приложении (x !! 10000000), когда список фактически оценивается. Кроме того, как m1, так и m2, похоже, оцениваются только один раз с -O2 и -O1 (на моем ghc 6.12.3), по крайней мере, в рамках следующего теста: (test = m1 10000000 seqm1 10000000). Однако есть разница, когда не указан флаг оптимизации. И оба варианта вашего "f" имеют максимальное размещение 5356 байт независимо от оптимизации, кстати (с меньшим общим распределением при использовании -O2).
Эдька
1
@ Ed'ka: Попробуйте эту тестовую программу, с приведенным выше определением f: main = interact $ unlines . (show . map f . read) . lines; компилировать с или без -O2; тогда echo 1 | ./main. Если вы напишете тест вроде main = print (f 5), тогда yможно будет собирать мусор по мере его использования, и нет никакой разницы между двумя fs.
Рид Бартон
эээ, так должно быть map (show . f . read), конечно. И теперь, когда я загрузил GHC 6.12.3, я вижу те же результаты, что и в GHC 6.12.1. И да, вы правы насчет оригинала m1и m2: версии GHC, которые выполняют такой подъем с включенной оптимизацией, будут преобразованы m2в m1.
Рид Бартон
Да, теперь я вижу разницу (-O2 определенно медленнее). Спасибо за этот пример!
Эдька
29

m1 вычисляется только один раз, потому что это постоянная заявочная форма, в то время как m2 не является CAF, и поэтому вычисляется для каждой оценки.

См. Вики GHC по CAF: http://www.haskell.org/haskellwiki/Constant_applicative_form

sclv
источник
1
Объяснение «m1 вычисляется только один раз, потому что это постоянная заявочная форма» для меня не имеет смысла. Поскольку предположительно и m1, и m2 являются переменными верхнего уровня, я думаю, что эти функции вычисляются только один раз, независимо от того, являются они CAF или нет. Разница заключается в том [1 ..], вычисляется ли список только один раз во время выполнения программы или один раз для каждого приложения функции, но связано ли это с CAF?
Цуёси Ито
1
На связанной странице: «CAF ... может быть скомпилирован в часть графика, который будет использоваться всеми пользователями, или в некоторый общий код, который перезапишет себя каким-то графом при первой оценке». Поскольку m1это CAF, второй применяется и filter odd [1..](не только [1..]!) Вычисляется только один раз. GHC может также отметить, что это m2относится к filter odd [1..]тому же преобразователю, который используется, и разместить ссылку на него m1, но это будет плохой идеей: в некоторых ситуациях это может привести к большим утечкам памяти.
Алексей Романов
@Alexey: Спасибо за поправку по поводу [1..]и filter odd [1..]. В остальном я все еще не убежден. Если я не ошибаюсь, CAF имеет значение только тогда, когда мы хотим утверждать, что компилятор может заменить filter odd [1..]in m2глобальным преобразователем (который может быть даже тем же преобразователем, что и используемый в m1). Но в ситуации, когда задает вопрос , компилятор не сделал эту «оптимизацию», и я не вижу ее отношения к вопросу.
Цуёси Ито
2
Уместно , что он может заменить его в m1 , и это делает.
Алексей Романов
13

Между двумя формами есть принципиальное различие: ограничение мономорфизма применяется к m1, но не к m2, потому что m2 явно указал аргументы. Итак, тип m2 является общим, а тип m1 - специфическим. Им присваиваются следующие типы:

m1 :: Int -> Integer
m2 :: (Integral a) => Int -> a

Большинство компиляторов и интерпретаторов Haskell (все, что я знаю на самом деле) не запоминают полиморфные структуры, поэтому внутренний список m2 воссоздается каждый раз, когда он вызывается, а m1 - нет.

мокус
источник
1
Играя с ними в GHCi, кажется, что это также зависит от преобразования let-Floating (один из проходов оптимизации GHC, который не используется в GHCi). И, конечно же, при компиляции этих простых функций оптимизатор в любом случае может заставить их вести себя одинаково (в соответствии с некоторыми критериями, которые я все равно проводил, с функциями в отдельном модуле и отмеченными прагмами NOINLINE). Предположительно, это потому, что генерация списков и индексация в любом случае сливаются в очень плотный цикл.
mokus
1

Я не уверен, потому что сам новичок в Haskell, но похоже, что это потому, что вторая функция параметризована, а первая - нет. Природа функции такова, что ее результат зависит от входного значения, а в функциональной парадигме, особенно, зависит ТОЛЬКО от входа. Очевидно, подразумевается, что функция без параметров всегда возвращает одно и то же значение снова и снова, несмотря ни на что.

По сути, в компиляторе GHC есть механизм оптимизации, который использует этот факт для вычисления значения такой функции только один раз за все время выполнения программы. Конечно, делает это лениво, но, тем не менее, делает. Я сам это заметил, когда писал такую ​​функцию:

primes = filter isPrime [2..]
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n]
        where f `divides` n = (n `mod` f) == 0

Затем , чтобы проверить это, я вошел в GHCI и написал: primes !! 1000. Прошло несколько секунд, но в конце концов я получил ответ: 7927. Тогда я позвонил primes !! 1001и сразу получил ответ. Точно так же в одно мгновение я получил результат take 1000 primes, потому что Haskell должен был вычислить весь список из тысячи элементов, чтобы вернуть 1001-й элемент раньше.

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

Свентимир
источник