A Simple LRU Cache Implementation in Swift 5

With generics and protocols.

A Least Recently Used Cache retains a sorted and finite amount of data where the data being sorted is sorted in descending order by the number of times it’s been accessed. When the LRU Cache becomes full, the least recently used object of data is bumped out to make room for the new object of data.

The LRU cache that we’ll be creating today will be similar to the NSCache provided as a Collection in Foundation.
I’ve created a small sample of how to use NSCache here.

Caching comes in handy when you’d like to keep data that is being accessed/copied a lot readily accessible for other pieces of your code to use. An LRU Cache especially comes in handy when you don’t know how many times each piece of data is going to be accessed, but would still like to prioritize data that is accessed more frequently.

Examples of what you might consider a cache for:

• Caching images to maybe not have to transfer URL to Data and to UIImage type. to prevent multiple data transfer calls from being generated for obtaining an image that doesn’t change. i.e. URL -> Data -> UIImage which is time consuming.
• Caching network responses that don’t change their response data given a specific status code. This prevents extraneous HTTP requests from being made.

⚠️ Quick FYI: The function dataWithContentsOfURL:(NSURL *)url is synchronous which means if you call network based URLs, it shouldn’t be done on the main thread as it will result in latency. Often times, I’d see this call when creating a UIImage type from an image URL which isn’t handled on the background thread. This can be looked across as you may think it’s done asynchronously - which it isn’t!
Read further on dataWithContentsOfURL:(NSURL *)url on Apple Docs
We want to make sure that there’s never an synchronous call on the main thread as it will cause a short latency or long app freeze depending on the task and user's network.

LRU cache visual representation

Key Components

Referencing the image displayed above, let’s discuss the key components that make up the LRU cache.

• Doubly linked list
• Dictionary

Doubly Linked List

This data structure will store important information of each element in the cache where keeping a priority of the most accessed elements at the head, and least accessed item at the tail, and as the cache is going to exceed it’s capacity, removing the tail in order to add a new element.
The policy here is to move the recently used element to the head of the linked list and as the cache will exceed its limit, the tail will be reassigned to the previous node, with adding the new element as the head. You can see how if we used an array, and added items in, it would steadily increase the run time proportional to the number of items in the array, i.e. cache.

Want to read this story later? Save it in Journal.

Dictionary

This data structure will store important information of retrieving data.

Take a moment to think exactly what type each collection — linked list, dictionary — should store in order to make adding and retrieving elements O(1) time complexity.

Key Functionality

main key functionality of LRU caches are:

• setObject: adding the element to the LRU cache.
• retrieveObject: retrieving the element from the LRU cache.

Now these will be the two high level functions, or at least what would be accessible from the cache. There may be more underlying functionality that will help achieve and maintain a valid LRU cache state.

Let’s see what exactly each data structure will store.

• The doubly linked list will contain its general node properties; containing a previous and next node, and an additionalPayload type.
  The Payload will contain the key and value, this way, we can map the key to its value in the dictionary.
• The dictionary will contain the value of the node type associated to the specified key.

Implementation

Doubly Linked List

Since each node will contain a payload, let’s go ahead and create that first

Now that we have that protocol, we’re going to create a CachePayload that will conform to Payload.

Our cache payload will be generic since we want our LRU cache to be able to store any type of value associated to its key. And we know that our CachePayloads key must be hashable — conform to the Hashable protocol — as that’s what’s required to map values to it’s key.

Now that we have the CachePayload that the node will store, let’s write out the Node.

You might notice how the Node here is a class instead of struct type. Because we’re putting the node into a linked list and dictionary, we can take advantage of reference semantics in order to avoid duplication, which would doubly the memory footprint of the cache. Granted, Swift does a good job of avoiding that duplication for you, you never solely want to depend on the implicit parts of a language like that. Because we’re holding onto a reference, we’re assured that the node will never hold on to an older version of node, since any changes will be reflected on every instance.

The node must store a payload contain information of the key and value.

I won’t go into linked lists here because their implementation is out of scope for this article, but see the full implementation here which also includes unit tests.

Now, we’re going to build the LRU cache class utilizing the doubly linked list and dictionary.

1. LRUCache has a generic type T which conforms to Hashable, and U which doesn’t have any requirements — It doesn’t have to conform to anything.
   Read more on generics here.
   This way, the LRU cache can be used for many types.
2. An instance variable, capacity which is of type UInt (unsigned integer) because the capacity cannot be negative.
3. A private(set) linkedList as the LRUCache can only be the source to modify it through the functions on the class. The type is DoublyLinkedList<CachePayload<T, U>>()
4. A private(set) dictionary as the LRUCache can only be the source to modify it through the functions on the class. The type is [T: Node<CachePayload<T, U>>]
5. A required initializer where there must be a capacity. This can however be modified this to have a default capacity.

Continuing on to setObject(for key: T, value: U) function:

1. We create a Payload object that stores the key and value
2. Create a check wether there’s an existing object in the cache, if there is, we move that up to the head and update the existing value, if there isn’t we create a node and add it into the linked list while making sure to remove the tail if it’s about to exceed capacity. And making sure to update the dictionary for both cases.

Lastly, for the retrieveObject(at key: T) -> U? function:

1. Simply access the dictionary and return the value associated to the node’s payload property. This will return nil if there’s no value in the payload.

You can find the full LRU Cache implementation here which also includes unit tests.

If you found this useful to you in some way, you might find this GitHub repo that I’ve been cultivating knowledge through my experience as an iOS engineer — computer-science-with-ios — useful as well!

⭐️ Thanks for studying with me! You can support me by giving some claps, up to 50X! 👏
📌 Find me on LinkedIn and GitHub.

Thanks to Vincenzo Marcella and Adrian Castillejos for the valuable feedback!

See every link mentioned in this article: