Можно ли дублировать дублирование для повышения производительности памяти?

Одна из моих проблем с ленивой оценкой в Haskell - это сложность рассуждений об использовании памяти. Я думаю, что способность дублировать thunk сделает это намного легче для меня. Вот пример.

Создайте действительно большой список:

let xs = [1..10000000]

Теперь создадим плохую функцию:

bad = do
    print $ foldl1' (+) xs
    print $ length xs

Без оптимизаций это поглощает несколько десятков МБ оперативной памяти. Сборщик мусора не может освободить xs во время сгиба, потому что он понадобится для вычисления длины позже.

Можно ли переопределить эту функцию примерно так:

good = do
    (xs1,xs2) <- copyThunk xs
    print $ foldl1' (+) xs1
    print $ length xs2

Теперь xs1 и xs2 будут представлять одно и то же значение, но также могут быть независимы друг от друга в памяти, поэтому сборщик мусора может освободиться во время сброса памяти, предотвращающей память. (Я думаю, что это немного увеличит вычислительную стоимость?)

Очевидно, что в этом тривиальном примере рефакторинг кода может легко решить эту проблему, но, похоже, не всегда очевидно, как рефакторировать. Или иногда рефакторинг значительно снижает ясность кода.

Ответ 1

Мне было интересно то же самое еще некоторое время назад и создала прототипную реализацию такой функции дублирования звука. Вы можете прочитать о результатах в моем препринте " dup - Явный un-sharing в haskell" и увидеть код в http://darcs.nomeata.de/ghc-dup. К сожалению, в этом году этот документ не был принят для симпозиума Haskell и семинара мастеров Haskell.

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

Ответ 2

Интересный вопрос. Я не знаю, как реализовать copyThunk. Но есть что-то еще, что вы можете сделать (извините, если вы уже это знали):

xsFunction :: () -> [Int]
xsFunction = const [1..10000000]

better = do
  print $ foldl1' (+) $ xsFunction ()
  print $ length $ xsFunction ()

Здесь он определенно не будет помещать выражение xsFunction () в thunk, он будет вычисляться дважды, таким образом не делая раздувания памяти.

Интересным продолжением этого является:

Можно ли реализовать copyThunk?
Должен ли программист haskell когда-либо возиться с этой относительно низкой степенью оптимизации? Не можем ли мы предположить, что ghc перехитрил нас на этом?

Ответ 3

Поверните xs в функцию. Это может быть уродливым, но работает, потому что он предотвращает совместное использование:

let xs () = [1..1000000]

good = do
    print $ foldl1' (+) (xs ())
    print $ length (xs ())