< Back to Latest Articles

# Using memoization to speed up slow functions

In this article you’ll learn how memoization can dramatically boost the performance of slow functions, and how easy Swift makes it thanks to its generics and closures.

Watch the video here, or read the article below

Memoization allows us to speed up function calls by caching the return value for a particular piece of input. The technique is startlingly simple in Swift, and can deliver huge performance boosts in all kinds of apps and games.

Tip: I’ve had folks email me trying correct my spelling here, so just to be clear it is called “memoization” and not “memorization” – they both come from the same root Latin word, memoro, meaning “to remember.”

## What’s the problem?

Memoization lets us cache the values of slow functions. For example, if you were building a game and wanted to keep a high frame rate while also performing slow operations such as calculating square roots or sine values, memoization is perfect for the job.

In fact, memoization is used extensively in functional programming, because if you have a pure function – a function that always returns identical output for given input because it relies on no external state and has no side effects – then there’s not much of a reason why the result shouldn’t be cached.

The example project I’ve given you is trivial: it has a `UITableViewController` with 40 rows. Inside each row is being shown the Fibonacci number equivalent for that row’s index path, so if you run the app you’ll see 0, 1, 1, 2, 3, 5, 8, 13, and so on. Each sequence is calculated by starting with 0 and 1, then calculating each new number by adding the previous two.

You’ll see the code calculates the correct output for any given input like this:

``````func fibonacci(_ number: Int) -> Int {
number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2)
}``````

So, for the 0th and 1st items we just send back 0 and 1 directly, but for everything else the function recursively calls itself to add the previous numbers together.

If you try using the app you’ll see it has a problem: scrolling gets worse the lower you go, and in fact if you go towards the bottom you’ll see your device completely freeze up. It doesn’t matter how powerful your device is, this is extremely slow and you just won’t get even close to smooth scrolling.

The problem is that our simple-looking function is recursive, so it generates huge amount of work in just one line of code. For example, if we want to calculate the 50th value in the Fibonacci sequence:

• We need to calculate the 49th value of the sequence, `number - 1`. That needs to calculate the 48th value, which needs to calculate the 47th value, and the 46th, the 45th, and so on.
• We also need to calculate the 48th value of the sequence, `number - 2`, which needs to do all the same work.

What actually happens is that end up repeating vast amounts of work, because every single number in the sequence tries to calculate every single number before it and the single number before that.

You can see the problem in action by changing the function to be more explicit:

``````func fibonacci(_ number: Int) -> Int {
print("Calculating \(number)")
return number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2)
}``````

When the app runs you’ll see a huge wall of `print()` statements – well past 10,000 and probably even past 20,000 depending on which device you’re using.

One way to address this problem is to calculate the sequence up front, then read values from that cache.

So, you could add a property to `ViewController` like this:

``let numbers = Array(0...40).map(fibonacci)``

And now you can change `cellForRowAt` to read values from that cache, like this:

``cell.textLabel?.text = String(numbers[indexPath.row])``

If you run the app again, you’ll see it now scrolls smoothly. However, our fast runtime performance has come at a cost: our app now launches significantly slower, because it’s doing all the calculation up front.

You might then try using a lazy map, like this:

``let numbers = Array(0...40).lazy.map(fibonacci)``

But unlike lazy properties, lazy maps don’t store their results – our app will now launch faster, but we’re back to the same terrible scrolling performance.

We can do better than this, and that’s where memoization comes in.

Before you continue, please revert your code back to use the `fibonacci()` function directly. That means removing the `numbers` property and using `String(fibonacci(indexPath.row))` for the cell’s text label

## Manual memoization

Our app has two problems: scrolling around is slow because we have to calculate complex values, and even after we calculate a value as soon as we scroll away that value gets discarded and needs to be recalculate every time. Memoization can help us solve both those problems.

Remember, memoization is the process of caching returned values from a function for particular in input. In its most raw state, that would mean adding a global dictionary variable to store input and outputs for our function. Place this outside the `ViewController` class, so it’s a global variable:

``var fibonacciCache = [Int: Int]()``

And now we can modify our `fibonacci()` function so that it starts by attempting to read the cache for the provided input. If we get a cache hit (we found the result for that input) then we send it back immediately, but if not we calculate it as before then store that value in the cache. So, the cache will start off empty, but fill up as the function runs repeatedly.

Here’s how that looks:

``````func fibonacci(_ number: Int) -> Int {
if let value = fibonacciCache[number] {
return value
}

let newValue = number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2)
fibonacciCache[number] = newValue
return newValue
}``````

If you run the app now you’ll see it works perfectly: it launches instantly, scrolling is smooth all the way to the bottom, and if you scroll up and down then it doesn’t need to recalculate values – it’s all cached.

Before you continue, please revert your code so that we don’t cache values. That means removing the `fibonacciCache` dictionary and putting the `fibonacci()` function back to this:

``````func fibonacci(_ number: Int) -> Int {
number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2)
}``````

If you want, you can keep the caching `fibonacci()` function around but commented out – we’ll be looking at it again later.

## Automatic memoization

Global functions are common, but global variables are usually a bad idea. What we really want is for that cache dictionary to be stored inside the function, so we don’t make a mess in our code. Even worse, if we have several things we want to memoize then we’ll create an even bigger mess!

To fix this, we’re going to create a new function called `memoize()` that will be able to memoize any function that accepts a single value and returns a single value.

This needs some careful thinking:

1. If we’re going to be able to memoize anything, then we can’t just have a single global variable any more – we need that storage be inside the memoizing function.
2. To memoize any kind of data we need to use generics: a generic input and a generic output.
3. We can’t memoize absolutely everything, because dictionaries can only store keys that conform to the `Hashable` protocol.

The reason this is all possible in Swift is because it supports closures – anonymous functions that we can pass around as data. In this instance, that means our `memoize()` function will accept some sort of function (the work to do, e.g. `fibonacci()`, then send back a new function that wraps it in a cache. Because that function parameter will be saved, we need to mark it as `@escaping` so Swift will keep it alive.

Add this function below `fibonacci()`:

``````// work with any sort of input and output as long as the input is hashable, accept a function that takes Input and returns Output, and send back a function that accepts Input and returns Output
func memoize<Input: Hashable, Output>(_ function: @escaping (Input) -> Output) -> (Input) -> Output {
// our item cache
var storage = [Input: Output]()

// send back a new closure that does our calculation
return { input in
if let cached = storage[input] {
return cached
}

let result = function(input)
storage[input] = result
return result
}
}``````

The magic happens there because we’re returning a closure that will capture the `storage` cache. Inside that closure we’re calling the function that was passed in (`fibonacci()`) and storing it in the cache.

When it comes to using that `memoize()` function, you first add it as a property to `ViewController`, like this:

``let memoizedFibonacci = memoize(fibonacci)``

And now update `cellForRowAt` to call that memoized version, like this:

``cell.textLabel?.text = String(memoizedFibonacci(indexPath.row))``

That’s it! Remember, our `memoize()` function accepts as its parameter some sort of function. Importantly, `memoize()` matches the signature as the function it accepts, so if the function accepts an `Int` and returns a `String` then so does `memoize() – that’s why we can use it directly with our table view cell.

If you run the app now you’ll see it kind of works: our scrolling is slow at first, but then when you scroll away and come back it’s fast. This means we’ve only solved half the problem: our values aren’t being recalculated, but we’re still stuck with them being slow the first time they are being calculated.

So, what happened? How come our awesome generic function was much slower than the specialized function?

## Why the slow down?

First, let’s take a look at the specialized caching `fibonacci()` function we wrote earlier:

``````func fibonacci(_ number: Int) -> Int {
if let value = fibonacciCache[number] {
return value
}

let newValue = number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2)
fibonacciCache[number] = newValue
return newValue
}``````

That attempts to find a value in the cache, but if it fails it will call itself to calculate the value.

Now look at our generic function again:

``````func memoize<Input: Hashable, Output>(_ function: @escaping (Input) -> Output) -> (Input) -> Output {
// our item cache
var storage = [Input: Output]()

// send back a new closure that does our calculation
return { input in
if let cached = storage[input] {
return cached
}

let result = function(input)
storage[input] = result
return result
}
}``````

That attempts to find a value in the cache, but if it fails it will call the original function to calculate the value.

The difference might seem small, but it accounts for the massive performance difference: in the specialized function the cache was inside the function, so when the function called itself it would benefit from all previous cached values; but in the generic function the cache was only used for the original input value, with all other values going through the uncached original function directly.

For small examples like the above this isn’t a problem, but if you wanted the 40th item in the sequence then you’re doing thousands of times more work than necessary – every item has to be calculated again and again because it isn’t in the cache. When it finishes, Swift will remember the return value of `fibonacci(40)` and make that one specific function call faster, but if you then asked for `fibonacci(41)` then it will do everything from scratch.

Fixing this is hard. I mean, really hard. If I explain it here and you think “Paul finds this easy,” you should know that I first saw this technique used six years ago at WWDC – I’ve had six years to come to terms with this!

And you know, a lot of time you don’t need the solution I’m about to present. If you’re doing slow work that you want to cache but that isn’t recursive – any function that needs to call itself, such as the Fibonacci sequence or factorials – then you can stop here and our simple `memoize()` function is enough.

But if you do have memoization needs that involve recursive functions, or if you have a morbid fascination for just how hard this is going to be, read on…

## Recursive memoization

We need to update our `memoize()` function so that rather than calling its input function it inside calls the caching closure that gets returned.

Having both forms of `memoize()` is helpful, so rather than change your existing function I suggest you take a copy of it that we can modify, calling the new version `recursiveMemoize()`.

First, we need to change the parameter that our copy accepts. Right now it’s `(Input) -> Output`, which means it will take something in and send back something – an `Int` coming in and an `Int` going out, for the Fibonacci sequence.

We need to change that so we accept a function that accepts some input and returns some output, as well as the input it’s working with. So, the parameter becomes this: `(Input) -> Output, Input) -> Output`.

In isolation that isn’t easy, but it gets even more complex when viewed in light of the whole function signature:

``func recursiveMemoize<Input: Hashable, Output>(_ function: @escaping ((Input) -> Output, Input) -> Output) -> (Input) -> Output {``

That means:

• `recursiveMemoize()` accepts a function as its parameter.
• That function itself accepts a function, which must be able to accept our input and send back our output.

So we now have a function `recursiveMemoize()` that accepts a function as its parameter, and that function accepts it own function as a parameter. See, I told you it was hard?

Now, when it comes to the code inside `recursiveMemoize()` we need to make a few changes.

You see, the closure we return needs to able to call itself, which means it needs to have a name.

So, change the closure to this:

``let memo = { input in``

Now add `return memo` to the end of the function.

Next, inside that closure we’re calling our calculation function like this:

``let result = function(input)``

That worked fine when our function was `(Input) -> Output`, but now the function is `((Input) -> Output, Input) -> Output` – it returns the same output value ultimately, but it needs an `(Input) -> Output` function as its first parameter.

Fortunately, that’s exactly what our memoization function does, so we can use that:

``let result = function(memo, input)``

And now we have a new problem: we’re using the `memo()` closure inside its own definition – we haven’t even finished creating it before we’re using it. Swift really doesn’t like this, so we need to make a change: we need to define the closure before we create it, like this:

``````var memo: ((Input) -> Output)!

memo = { input in``````

And that’s it: our new memoization function is ready. Again, this is complex Swift code so don’t feel bad if you need to go over it many times to really understand how it works.

However, if you thought that was hard wait until you see how we use it.

First, change the `memoizedFibonacci` property so that it starts a closure that accepts two parameters, a function, and an input:

``let memoizedFibonacci = recursiveMemoize { fibonacci, number in``

Now copy in the body of the existing `fibonacci()` function, like this:

``````let memoizedFibonacci = recursiveMemoize { fibonacci, number in
number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2)
}``````

Yes, that closure now calls as a function one of the parameters it gets passed in – it’s recursive! That means it’s no longer using the global `fibonacci()` function we made earlier, but is instead calling itself.

This seems like it ought to be impossible, but it really isn’t: eventually the function call will resolve in number` being less than 2 so it will stop calling itself.

If you run the app now you should see we get smooth scrolling. So, we finally solved our problem fully, while also making it generic so that we can use it with any other kind of similar function.

## What now?

Our original, simpler generic memoization function is useful in many places, and it’s the kind of thing you’ll find yourself using in any place where you have a complex, repeatable transformation being applied.

Like I said at the beginning, you could memoize square root calculations:

``let memoizedSqrt = memoize(sqrt)``

You could also memorize calculating the sine of numbers, although because there are several different forms of `sine()` you should be clear which one you mean:

``let memoizedSin: (Double) -> Double = memoize(sin)``

Notice how I’m using the original function name, just prefixed with `memoized` – that makes it easy to understand at a glance what’s happening when you come across the code elsewhere.

Before I’m doing, I want to add two important notes to this technique.

First, memoization is a time-space tradeoff: we save some time in exchange for chewing up a little extra memory to store all our cached data. If you have lots of spare CPU time and little spare memory, memoization might not be for you.

Second, recursive memoization allows us to do some tasks extremely quickly, but it’s not magic – recursive functions can still cause a stack overflow, where one function calls itself so much that the computer can’t handle it any more.

With great power comes great responsibility! And speed. Responsibility and speed. And power. Responsibility, speed, and power!

And flexibility.

Oh, you get the point…

## Challenges

I have one question for you to think about, and one coding challenge. The question is this: if we had an app that uses Core Image filters with a slider to control filter strength, why would that make a poor choice for memoization?

Have a think about that before I answer. In the meantime, here’s the coding challenge: write a memoized factorial function, then benchmark how much faster it is with and without recursive memoization. You should use `CFAbsoluteTimeGetCurrent()` to measure timings.

As for the Core Image question, the problem with caching images is that they are big – they’ll chew up a lot of memory, which means our dictionary cache will fill up extremely quickly. It’s best to use memoization for simple data, such as `String`, `Int`, and `Double`.

## If you liked this, you'd love Hacking with Swift+…

Here's just a sample of the other tutorials, with each one coming as an article to read and as a 4K Ultra HD video.

6:52

### FREE: Functional programming in Swift: Introduction

Before you dive in to the first article in this course, I want to give you a brief overview of our goals, how the content is structured, as well as a rough idea of what you can expect to find.

42:32

### FREE: Transforming data with map()

In this article we’re going to look at the `map()` function, which transforms one thing into another thing. Along the way we’ll also be exploring some core concepts of functional programming, so if you read no other articles in this course at least read this one!

27:33

### FREE: Understanding assertions

Assertions allow us to have Swift silently check the state of our program at runtime, but if you want to get them right you need to understand some intricacies. In this article I’ll walk you through the five ways we can make assertions in Swift, and provide clear advice on which to use and when.

14:26

### FREE: User-friendly network access

Anyone can write Swift code to fetch network data, but much harder is knowing how to write code to do it respectfully. In this article we’ll look at building a considerate network stack, taking into account the user’s connection, preferences, and more.

32:08

### FREE: Creating a WaveView to draw smooth waveforms

In this article I’m going to walk you through building a `WaveView` with SwiftUI, allowing us to create beautiful waveform-like effects to bring your user interface to life.

23:07

### FREE: Making the most of optionals

Swift’s optionals are implemented as simple enums, with just a little compiler magic sprinkled around as syntactic sugar. However, they do much more than people realize, and in this article I’m going to demonstrate some of their power features that can really help you write better code – and blow your mind along the way.

11:03

### FREE: Ultimate Portfolio App: Introduction

UPDATED: While I’m sure you’re keen to get started programming immediately, please give me a few minutes to outline the goals of this course and explain why it’s different from other courses I’ve written.

24:11

### FREE: How to use phantom types in Swift

Phantom types are a powerful way to give the Swift compiler extra information about our code so that it can stop us from making mistakes. In this article I’m going to explain how they work and why you’d want them, as well as providing lots of hands-on examples you can try.

31:55

### FREE: Trees

Trees are an extraordinarily simple, extraordinarily useful data type, and in this article we’ll make a complete tree data type using Swift in just a few minutes. But rather than just stop there, we’re going to do something quite beautiful that I hope will blow your mind while teaching you something useful.

14:20

### FREE: Creating a custom property wrapper using DynamicProperty

It’s not hard to make a basic property wrapper, but if you want one that automatically updates the `body` property like `@State` you need to do some extra work. In this article I’ll show you exactly how it’s done, as we build a property wrapper capable of reading and writing documents from our app’s container.

20:01

### FREE: Understanding generics – part 1

Generics are one of the most powerful features of Swift, allowing us to write code once and reuse it in many ways. In this article we’ll explore how they work, why adding constraints actually helps us write more code, and how generics help solve one of the biggest problems in Swift.

3:54

### FREE: Interview questions: Introduction

Getting ready for a job interview is tough work, so I’ve prepared a whole bunch of common questions and answers to help give you a jump start. But before you get into them, let me explain the plan in more detail…

19:50

###### SWIFTUI SPECIAL EFFECTS

SwiftUI gives us a modifier to make simple shadows, but if you want something more advanced such as inner shadows or glows, you need to do extra work. In this article I’ll show you how to get both those effects and more in a customizable, flexible way.

14:46

### Creating a RemoteImage to load images from the web

Just like UIKit before it, SwiftUI doesn’t come with built-in support for loading remote images, which makes it hard to get data from the internet. In this article I’ll show you how you can build a custom view that can fetch image from the internet, while also showing other images for different states.

52:27

### Simple SwiftUI, part 2: SimpleNews

In this article we’re going to build another simple SwiftUI project to continue the Simple SwiftUI series. This time our goal is to build a news reader built through fetching a remote API.

1:46:18

### Ping Pong

How can you be first in line when a website announces important changes? Simple: make your computer watch for changes automatically! In this article we’ll build a macOS app that can watch an arbitrary list of URLs for changes, and will notify us when something changes…

1:45:22

### Simple SwiftUI, part 1: SimpleToDo and SimpleScores

In this article we’re going to build two simple SwiftUI projects back to back, as part of a new initiative to create easily accessible sample projects for learners.

2:04

### What is the purpose of size classes?

Whether you use UIKit or SwiftUI, size classes are Apple’s broad-stroked approach to providing information about the available space for our UI.

7:30

### Layout and Geometry

This challenge asks you make views fade out, scale down, and change their color, all synchronized with the movement in our `ScrollView`. Let’s tackle it now…

2:05:15

### Fireworks

In this article we’re going to build a tool that designs particle systems for SwiftUI apps, all built on top of the `TimelineView` and `Canvas` that were added in SwiftUI. I think you’ll really be amazed how fast this comes together!

You are not logged in