Оптимизация GHC

Две функции Haskell ниже, по-видимому, различаются только тем, является ли индексная переменная неявной или явной, но разница в производительности на два порядка.

Эта функция занимает около 0,03 секунды для вычисления mfib 30:

let mfib = (map fib [0..] !!)
  where
    fib 0 = 0
    fib 1 = 1
    fib x = mfib (x-1) + mfib (x-2)

Эта функция занимает около 3 секунд для mfib 30:

let mfib i = map fib [0..] !! i
  where
    fib 0 = 0
    fib 1 = 1
    fib x = mfib (x-1) + mfib (x-2)

Я предполагаю, что это связано с встроенными правилами GHC и пытались добавить inline/noinline pragmas, чтобы получить соответствующую производительность.

EDIT: Я понимаю, как поиск в ленивом списке можно использовать для memoize функции fib и почему традиционное определение fib очень медленное. Я ожидал, что memoization будет работать во второй функции, а также в первой, и не понимаю, почему это не так.

Ответы

Ответ 1

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

let mfib = let fib 0 = 0
               fib 1 = 1
               fib x = mfib (x-1) + mfib (x-2)
           in (!!) (map fib [0..])

против

let mfib = \i ->
               let fib 0 = 0
                   fib 1 = 1
                   fib x = mfib (x-1) + mfib (x-2)
               in map fib [0..] !! i

Обратите внимание, что во второй программе выражение map fib [0..] появляется внутри \i -> ..., поэтому оно (как правило, без оптимизации) оценивается для каждого значения i. См. Когда автоматическая запись в GHC Haskell?

Ответ 2

Нет, это не имеет никакого отношения к inlining. Разница в том, что mfib = (map fib [0..] !!) не имеет аргументов. Это все еще функция, конечно, но оценка этой функции не требует передачи каких-либо аргументов. В частности, оценка этого mfib будет генерировать список fib таким образом, чтобы его можно было повторно использовать для всех индексов.

OTOH, mfib i = map fib [0..] !! i означает, что весь блок where будет рассматриваться только тогда, когда вы фактически передаете аргумент i.

Эти два варианта отличаются друг от друга, если вы многократно оцениваете функцию много раз. К сожалению, для второй версии функции собственной рекурсии уже называет ее снова и снова! Поэтому mfib (x-1) + mfib (x-2) необходимо выполнить всю работу mfib (x-1), а затем снова всю работу mfib (x-2). Таким образом, mfib n берет более чем в два раза вычислительную стоимость mfib (n-1), поэтому mfib ∈ O (2 n).

Это невероятно расточительно, потому что большинство терминов в mfib (x-2) также уже находятся в mfib (x-1) и могут быть просто повторно использованы. Ну, именно то, что делает ваша первая версия, потому что она вычисляет список fib один раз и для всех индексов, поэтому оценка mfib (x-1) будет уже выполнять большую часть работы, которую затем можно просто перечитать с помощью mfib (x-2), уменьшая сложность полинома.