A "fast" memoization generic in Swift

gistfile1.txt

Promised speed:

0.1s https://dl.dropboxusercontent.com/s/bpgountdjrbs17n/2014-06-09%20at%2019.00.png

Actual speed:

575s https://dl.dropboxusercontent.com/s/2kbn5p1g4t03fvl/2014-06-09%20at%2019.00%20%281%29.png

With optimizations:

$ time xcrun swift -i -Ofast memoize.swift
1.61803398874989
      608.42 real       304.25 user       144.19 sys

memoize.swift

func memoize<T: Hashable, U>( body: ( (T)->U, T )->U ) -> (T)->U {
    var memo = Dictionary<T, U>()
    var result: ((T)->U)!
    result = { x in
        if let q = memo[x] { return q }
        let r = body(result, x)
        memo[x] = r
        return r
    }
    return result
}

let fibonacci = memoize {
    fibonacci, n in
    n < 2 ? Double(n) : fibonacci(n-1) + fibonacci(n-2)
}

println(fibonacci(45)/fibonacci(44))

I'm new to Swift and I'm trying to understand why this is slow, do you have an explanation?

Closures are nice though.

Hi, the problem isn't Apple giving you "fake" fast memoization, but it's your code, because your fibonacci function is wrong.
It should be like this:

let fibonacci: (Int ->  Double) = memoize {
    fibonacci, n in
    return (n < 2) ? Double(n) : fibonacci(n - 1) + fibonacci(n - 2)
}

And just to test how actually fast it is I computed fibonacci(20)/fibonacci(19) before with a slow (recursive non-memoized) function and then with the function I provided...
The results? Well my computer took 64.1283450126648 seconds to compute the slow one and just 0.135640025138855 seconds to compute the memoized one.

Please, check your code before before post anything!

Hey just wrote an in depth post this, might be interested read for you random googles :) https://medium.com/@mvxlr/swift-memoize-walk-through-c5224a558194#.sl4bfon3k