How To Implement Cache LRU With Swift

/implement-cache-lru-swift/featured-image.webp

How To Implement Cache LRU With Swift

02 Oct 2017 1879 words 9 minutes

Contents

Algorithms and Data Structures. It’s the basis of computer science and a very huge topic. In this article, we are going to cover only a little piece: Cache LRU.

Introduction

A cache LRU (Least Recently Used) is similar to a dictionary. It stores data associated to a key. The difference between a dictionary and a Cache is that the latter has a limited capacity. Every time we reach the capacity, the Cache deletes the least recently used element.

In this article, we are going to see how to implement a Cache LRU with Swift.

Happy Reading!

Getting Started

First of all, we must understand what data structures we should use to implement our Cache LRU. There are different ways to implement it. In this version, we will use:

Doubly Linked List: This is the core of our implementation. We need this list to store the elements of our cache. We don’t use an Array because it would be slower. The Cache LRU policy is to move the elements recently used in the head very often. If we move an element in the head—at the index 0—in an array, we should perform a shift to right for all the other elements.
Dictionary<Key, ListNode>: The problem of using a doubly linked list is that its lookup complexity is O(n). We can solve this bottleneck using a dictionary—which has a lookup complexity of O(1). We’ll use this dictionary to store the nodes of our list.

In the next section, we are going to see how to implement the doubly linked list. If you already know it, feel free to jump at the section Cache LRU.

Doubly Linked List

For this article, we don’t need a complete doubly linked list implementation. For this reason, we’ll implement only the methods used in the Cache.

The first step is to create a new class DoublyLinkedList which accepts a generic value T to store inside the nodes:

1
2
final class DoublyLinkedList<T> {   
}

Then, we must create a class for the nodes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
final class DoublyLinkedList<T> {
    
    final class Node<T> {
        var payload: T
        var previous: Node<T>?
        var next: Node<T>?
        
        init(payload: T) {
            self.payload = payload
        }
    }
}

In this implementation, we use a nested Node class. If you use a Swift version older than 3.1, you must create this class outside DoublyLinkedList. Nested classes with generic values are supported from Swift 3.1.

Then, we must provide the information of how many elements are stored in the list:

1
private(set) var count: Int = 0

The operations on a linked list may be sometimes complex to implement. For this reason, we can store the first and last elements to keep our life easier:

1
2
private var head: Node<T>?
private var tail: Node<T>?

Now, we can start implementing the list methods:

addHead

We need a method to add a new element in the list. We add it in the head to be compliant with the Cache LRU policy—a new element is the recently used:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func addHead(_ payload: T) -> Node<T> {
    let node = Node(payload: payload)
    defer {
        head = node
        count += 1
    }
    
    guard let head = head else {
        tail = node
        return node
    }
    
    head.previous = node
    
    node.previous = nil
    node.next = head
    
    return node
}

moveToHead

The concept of a Cache LRU is keeping the recently element used at the beginning of our list. For this reason, we need a method to move a node at the head:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func moveToHead(_ node: Node<T>) {
    guard node !== head else { return }
    let previous = node.previous
    let next = node.next
    
    previous?.next = next
    next?.previous = previous
    
    node.next = head
    node.previous = nil
    
    if node === tail {
        tail = previous
    }
    
    self.head = node
}

removeLast

When our Cache is full, we need a method to remove the last element—which is the least recently used:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func removeLast() -> Node<T>? {
    guard let tail = self.tail else { return nil }
    
    let previous = tail.previous
    previous?.next = nil
    self.tail = previous
    
    if count == 1 {
        head = nil
    }
    
    count -= 1
    
    // 1
    return tail
}

The value of this tail is not the same of self.tail. It’s the value of the old tail which comes from the optional binding in the guard at the beginning of this method.

Finally, we can add a typealias for our Node type to use in the Cache implementation:

1
typealias DoublyLinkedListNode<T> = DoublyLinkedList<T>.Node<T>

The final version of our list implementation should be like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
typealias DoublyLinkedListNode<T> = DoublyLinkedList<T>.Node<T>

final class DoublyLinkedList<T> {
    final class Node<T> {
        var payload: T
        var previous: Node<T>?
        var next: Node<T>?
        
        init(payload: T) {
            self.payload = payload
        }
    }
    
    private(set) var count: Int = 0
    
    private var head: Node<T>?
    private var tail: Node<T>?
    
    func addHead(_ payload: T) -> Node<T> {
        let node = Node(payload: payload)
        defer {
            head = node
            count += 1
        }
        
        guard let head = head else {
            tail = node
            return node
        }
        
        head.previous = node
        
        node.previous = nil
        node.next = head
        
        return node
    }
    
    func moveToHead(_ node: Node<T>) {
        guard node !== head else { return }
        let previous = node.previous
        let next = node.next
        
        previous?.next = next
        next?.previous = previous
        
        node.next = head
        node.previous = nil
        
        if node === tail {
            tail = previous
        }
        
        self.head = node
    }
    
    func removeLast() -> Node<T>? {
        guard let tail = self.tail else { return nil }
        
        let previous = tail.previous
        previous?.next = nil
        self.tail = previous
        
        if count == 1 {
            head = nil
        }
        
        count -= 1
        
        return tail
    }
}

Cache LRU

It’s time to implement our Cache. We can start creating a new CacheLRU class:

1
final class CacheLRU<Key: Hashable, Value> {

The generic value Key must be Hashable since it’s the key of the value stored in the doubly linked list.

A Cache stores data associated to keys like a dictionary. Unfortunately, our doubly linked list accepts only a value payload and not also a key. To solve this problem, we can create a struct which wraps the value and its key. In this way, our list nodes will store the object CachePayload which contains both value and key:

1
2
3
4
5
6
7
final class CacheLRU<Key: Hashable, Value> {
    
    private struct CachePayload {
        let key: Key
        let value: Value
    }
}

Then, we should add the two data structures—a doubly linked list and a dictionary:

1
2
private let list = DoublyLinkedList<CachePayload>()
private var nodesDict = [Key: DoublyLinkedListNode<CachePayload>]()

As we saw in Introduction, Cache LRU has a limited capacity. We can inject this capacity in the init method and store it in a private property:

1
2
3
4
5
private let capacity: Int
    
init(capacity: Int) {
    self.capacity = max(0, capacity)
}

We use the method max to avoid invalid capacity values less than zero.

Now, we can implement the two Cache methods to get and set the elements:

setValue

With the method set, we can add/update an element for a specific key. The value is always moved at the beginning of the list as recently used element:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func setValue(_ value: Value, for key: Key) {
    // 1
    let payload = CachePayload(key: key, value: value)
    
    // 2
    if let node = nodesDict[key] {
        node.payload = payload
        list.moveToHead(node)
    } else {
        let node = list.addHead(payload)
        nodesDict[key] = node
    }
    
    // 3
    if list.count > capacity {
        let nodeRemoved = list.removeLast()
        if let key = nodeRemoved?.payload.key {
            nodesDict[key] = nil
        }
    }
}

Create a payload object to wrap key and value to be stored in the list.
If the list already stores an element for that specific key, we update the value and move it at the beginning of the list. Otherwise, we create a new node and add it as head of the list.
If we exceeded the capacity of the cache adding the new element, we remove the last element of the list.

getValue

With the method get, we can retrieve an element for a specific key. Every time we retrieve an element, it is moved at the beginning of the list as recently used element:

1
2
3
4
5
6
7
func getValue(for key: Key) -> Value? {
    guard let node = nodesDict[key] else { return nil }
    
    list.moveToHead(node)
    
    return node.payload.value
}

The final version of our Cache implementation should be this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
final class CacheLRU<Key: Hashable, Value> {
    
    private struct CachePayload {
        let key: Key
        let value: Value
    }
    
    private let capacity: Int
    private let list = DoublyLinkedList<CachePayload>()
    private var nodesDict = [Key: DoublyLinkedListNode<CachePayload>]()
    
    init(capacity: Int) {
        self.capacity = max(0, capacity)
    }
    
    func setValue(_ value: Value, for key: Key) {
        let payload = CachePayload(key: key, value: value)
        
        if let node = nodesDict[key] {
            node.payload = payload
            list.moveToHead(node)
        } else {
            let node = list.addHead(payload)
            nodesDict[key] = node
        }
        
        if list.count > capacity {
            let nodeRemoved = list.removeLast()
            if let key = nodeRemoved?.payload.key {
                nodesDict[key] = nil
            }
        }
    }
    
    func getValue(for key: Key) -> Value? {
        guard let node = nodesDict[key] else { return nil }
        
        list.moveToHead(node)
        
        return node.payload.value
    }
}

We can use this cache like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
let cache = CacheLRU<Int, String>(capacity: 2)

cache.getValue(for: 5) // nil
    
cache.setValue("One", for: 1)
cache.setValue("Eleven", for: 11)
cache.setValue("Twenty", for: 20)

cache.getValue(for: 1) // nil. We exceeded the capacity with the previous `setValue`  and `1` was the last element.
cache.getValue(for: 11) // Eleven

You can find a Gist with the Cache LRU implementation here.

Conclusion

That’s all for our Cache LRU.

Nowadays, we have a lot of memory available for our Apps. Despite this, we may need a Cache with a limited capacity to save memory space. For example, when we have to cache objects which are space-consuming like the images.

Update

I’ve figured out that Array is faster than linked list. Since the pure version of Cache LRU uses a doubly linked list, I leave the current implementation. But, keep in mind that with a Swift Array we would have a faster implementation.

You can watch an interesting video about Array and linked list here:

Contents