PWC 049 › LRU Cache

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #2 this week has us build an LRU cache, which is a cache of fixed capacity, whereby when it is full but a new item needs to be added, the item that was least-recently accessed is evicted from the cache.


For example, if a cache of capacity = 3 contains [a b c] (where a was accessed most recently), elements are evicted off the right side of the list. Adding element d, the list would contain [d a b], for example.

Of course, [d a b] are just the keys of the items in the cache. We’ll take an arbitrary scalar (which could itself be a reference) as a value.

High Level Design

At minimum, we need to provide get and set routines. I’ll also provide a constructor, an explicit evict option to manually remove items, and a capacity method to get (or set!) the capacity. As an internal helper, an _expire method will evict as many elements as needed to bring the list down to its capacity (useful when setting capacity to a smaller value). I also provide an exists method, and a length method to return the current length of the cache.

I’ve put all of this into an OO class called Local::LRU.

Implementation

I store the elements in a hash, keyed on whatever key the user provides in set. That hash is also a doubly-linked list, as each element is a hashref that has next and prev references. I also maintain the head and tail of the list to ensure all operations are constant time.

The link to my full implementation is available on Github.

I won’t show the whole listing here, as much of it is relatively uninteresting. set, get, and evict are the most relevant:

# Set item named $key to $val, and promote it to the head of the list
sub set {
    my ($s, $key, $val) = @_;
    $s->evict($key) if $s->exists($key);

    my $elem = { key => $key, val => $val, next => $s->{_head} };
    $s->{_cache}{$key} = $elem;

    $s->{_head} and $s->{_head}{prev} = $elem;
    $s->{_tail} //= $elem;
    $s->{_head} = $elem;
    $s->{_length}++;
    $s->_expire;

    $val;
}

# Get an item named $key, or croak
sub get {
    my ($s, $key) = @_;
    croak "$key does not exist" unless $s->exists($key);
    my $val = $s->{_cache}{$key}{val};
    $s->set($key, $val);
}

# Evict a specific $key from the cache
sub evict {
    my ($s, $key) = @_;
    croak "$key does not exist" unless $s->exists($key);
    my $elem = $s->{_cache}{$key};

    # Re-link next/prev elements in DLL
    $elem->{next} and $elem->{next}{prev} = $elem->{prev};
    $elem->{prev} and $elem->{prev}{next} = $elem->{next};
    delete $s->{_cache}{$key};
    $s->{_tail} = $elem->{prev} if $s->{_tail} == $elem;
    $s->{_head} = $elem->{next} if $s->{_head} == $elem;

   --$s->{_length};
}

These three subs contain the bulk of the logic. Even then, there is nothing very clever about it. If you have ever seen a doubly-linked list, this logic should be easy enough to reproduce.

Head and Tail

In practice, you don’t need to maintain the head and tail of a doubly-linked list as long as you have at least one cursor or other reference into the list. (You can simply start from anywhere and stop once next is undefined, and now you’re at the tail, for example.) But any operation where you need the head (i.e., MRU item) or tail (i.e., LRU item) would then be O(n), but if you do a bit of housekeeping to maintain the head and tail references, all operations are O(1) with a slightly larger constant.

Raku Version

The Raku version is a straight port over to the Raku syntax. I do like the OO syntax of Raku, and in larger Perl projects I typically use something like Mouse, which brings in much of the same syntax and functionality.

Here’s the properties, set method, and note that it isn’t necessary to write a constructor, here:

class LRU {
    has UInt $.capacity is required is rw;
    has      %!cache;
    has      $!head;
    has      $!tail;
    has UInt $!length = 0;

    method length() { $!length }

    #| Set item named $key to $val and promote it to head of the list
    method set( $key, $val ) {
        $.evict($key) if $.exists($key);
        
        my $elem = { key => $key, val => $val, next => $!head };
        %!cache{$key} = $elem;
        $!head and $!head<prev> = $elem;
        $!tail //= $elem;
        $!head = $elem;
        $!length++;
        self!expire;

        $val;
    }

I suppose I could have made a LRU::Element class, which would be better for overrides, but it’s never exposed to the end user, so I decided that it could be done at a later date, if and when required.

I like Raku’s further commitment to Huffman coding. $.evict is cleaner than $s->evict from Perl.

Other Thoughts

A hash + doubly-linked-list implementation is certainly not the only way to tackle this problem, although it is one of the only constant-time (O(1)) implementations. The code would be shorter had I used arrays and some combination of grep and splice to maintain the cache, but at the cost of operations being O(n) instead of O(1). Thus, I chose the more classic, performant version (for sufficiently large n).

Leave a Reply

Your email address will not be published. Required fields are marked *