TNish

Recently, I needed to add a simple cache to my application. In particular, I was looking for a way to memo-ize a function, and age out old entries as necessary. There's great cache modules on CPAN that do this, but I needed to accomplish it with only standard modules.

In order to create a very dumb Least-Recently-Used cache, you need a list and a hash. The hash obviously stores mapping from keys to values, and the list keeps the order of items in the most recently-used order. When an existing item is modified or retrieved, its key moves to the end of the list. When an insertion is made that would overflow the size limit of the cache, entries from the front of the list are removed. Note that the implementation below would only work for string keys (and things that are convertible to strings, like intergers, since perl hash keys are stringified), but it shouldn't be too hard to modify to handle arbitrary objects.

Fortunately, there's a standard module called Tie::IxHash which makes this trivial to implement. Tie::IxHash, when tied to an ordinary perl hash, will make its keys ordered! Here's what it looks like:

use v5.10.1;
use strict;
use warnings;
use Data::Dumper;

use Tie::IxHash;

my $size_limit = 10;

# %lru keys are now ordered, so 'each' and 'keys' will return the keys 
# in the order they were added.
tie my %lru, 'Tie::IxHash'; 

sub set {
    my ($lru, $k, $v) = @_;

    if (exists $lru->{$k}) {
        delete $lru->{$k};
    }

    # $k now is the last item.
    $lru->{$k} = $v;

    # note: the 'keys' call in the conditional resets the 'each' iterator
    while (keys %$lru > $size_limit) {
        # in scalar context, each returns the key. for a IxHash, it returns them in order added.
        my $oldest = each %$lru; 
        delete $lru->{$oldest};
    }
}

sub get {
    my ($lru, $k) = @_;

    if (exists $lru->{$k}) {
        my $v = delete $lru->{$k};
        # $k now is the last item.
        $lru->{$k} = $v;
        return $v;
    }
    return;
}

We test it out by setting 10 kv-pairs, filling up the cache.

set \%lru, 1, "one";
set \%lru, 2, "two";
set \%lru, 3, "three";
set \%lru, 4, "four";
set \%lru, 5, "five";
set \%lru, 6, "six";
set \%lru, 7, "seven";
set \%lru, 8, "eight";
set \%lru, 9, "nine";
set \%lru, 10, "ten";

say Dumper \%lru;

# $VAR1 = {
#           '1' => 'one',
#           '2' => 'two',
#           '3' => 'three',
#           '4' => 'four',
#           '5' => 'five',
#           '6' => 'six',
#           '7' => 'seven',
#           '8' => 'eight',
#           '9' => 'nine',
#           '10' => 'ten'
#         };

Note that thanks to Tie::IxHash, Data::Dumper dumps the hash in key-order. Next, we reset some of the keys:

set \%lru, 2, "TWO";
set \%lru, 4, "FOUR";
set \%lru, 4, "FOUR";
set \%lru, 5, "FIVE";
set \%lru, 11, "ELEVEN";

say Dumper \%lru;

# $VAR1 = {
#           '3' => 'three',
#           '6' => 'six',
#           '7' => 'seven',
#           '8' => 'eight',
#           '9' => 'nine',
#           '10' => 'ten',
#           '2' => 'TWO',
#           '4' => 'FOUR',
#           '5' => 'FIVE',
#           '11' => 'ELEVEN',
#         };

Notice that 2, 4, and 5 values have been updated and moved to the end of the key list (the most recently used), and the "1" entry has been removed because it was at the beginning of the list.