Generic memoize function in Swift

Question

I need to perform some expensive calculation, such as determining a Fibonacci number:

/// Calculate the Nth Fibonacci number (inefficiently)
func fib(n: Int) -> Int {
 n > 1 ? fib(n: n-1) + fib(n: n-2) : n
}

My project contains a number value types that need to perform calculations like fib based on their properties:

struct Fibber : Hashable {
 /// The index in the sequence
 var n: Int
 /// The calculated Fibonacci number at _n_
 var fibcalc: Int { fib(n: n) }
}

It works fine. But it is slow!

class FibberTests: XCTestCase {
 func testFibCalc() {
 measure { // average: 1.291, relative standard deviation: 1.5%
 var fibber = Fibber(n: 1)
 XCTAssertEqual(1, fibber.fibcalc)
 fibber.n = 25
 XCTAssertEqual(75_025, fibber.fibcalc)
 fibber.n = 39
 XCTAssertEqual(63_245_986, fibber.fibcalc)
 }
 }
}

So I make a single global dictionary that is keyed on source code location, and contains a map from a Hashable instance to the result of some arbitrary calculation:

/// Singleton global memoization cache, keyed on source code location and input hashable
private var memoized = Dictionary<String, Dictionary<AnyHashable, Any>>()

The cache key will be something like: "function:fibcalc file:Fibber.swift line:47".

Any Hashable instance can utilize this function to perform and memoize a calculation based on the key type, and return that cached value on subsequent invocations of the same call:

extension Hashable {
 /// Caches and returns the result of the `calculation` function.
 public func memoize<T>(function: StaticString = #function, file: StaticString = #file, line: Int = #line, _ calculation: (Self) -> T) -> T {
 let cacheKey = "function:\(function) file:\(file) line:\(line)"
 let hashKey = AnyHashable(self)
 if let cached = memoized[cacheKey]?[hashKey] as? T { return cached }
 if memoized[cacheKey] == nil { memoized[cacheKey] = Dictionary() }
 let calculated = calculation(self)
 memoized[cacheKey]?[hashKey] = calculated
 return calculated
 }
}

Memoizing these expensive calculations is now very simple:

extension Fibber {
 /// The cached fib. Repeated calls on the same source instance will return the memoized result for this instance.
 var fibmemo: Int { memoize(\.fibcalc) }
}

And we get an order-of-magnitude speedup!

extension FibberTests {
 func testFibMemo() {
 measure { // average: 0.132, relative standard deviation: 299.9%
 var fibber = Fibber(n: 1)
 XCTAssertEqual(1, fibber.fibmemo)
 fibber.n = 25
 XCTAssertEqual(75_025, fibber.fibmemo)
 fibber.n = 39
 XCTAssertEqual(63_245_986, fibber.fibmemo)
 }
 }
}

Assumptions:

• the Hashable key will always be a value type (this isn't currently enforceable in Swift)

Non-Issues:

• Thread-safety: locking can be added to the cache later
• Unbounded memory growth: memoized Dictionary will be converted to an NSCache

Valid Issues:

• Duck typing: the keys are AnyHashable and the values are Any, so runtime type conversion is used (yuck)

My main question is: is this a good idea? Are there any issues with the cache key using the source location?

Answer 1

It sounds like you're on the right track, but the cache key needn't be so specific. Unless you're storing to the same cache/dictionary as other code is using, there won't be collisions.

Since Fibonacci numbers build on the previous 2 numbers, recursion is a natural solution, but obviously gets slower for larger numbers. This post details a recursive memoization approach that seems like exactly what you're looking for:

https://www.hackingwithswift.com/plus/high-performance-apps/using-memoization-to-speed-up-slow-functions

• Mast: Welcome to Code Review! Could you elaborate on the memoization? After all, the basis for it is already mentioned in the question itself. Links can rot and your link specifically links to a subscription service.