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

Question

Две функции 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 будет работать во второй функции, а также в первой, и не понимаю, почему это не так.

Answer 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. См. When is memoization automatic in GHC Haskell?

Answer 2

Нет, это не имеет никакого отношения к встраиванию. Разница в том, что 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), поэтому ∈ mfibO (2 ^п).

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