A size-bounded cache

Richard Suchenwirth 2004-11-17 - When time-consuming operations occur more than once on the same input (and giving the same result), it is faster to cache such results for future use in an array keyed with the input (see Result caching). However, if a long-running process uses a cache, it will grow unbounded - less politely expressed, a kind of "leak". So here's a caching code that keeps a list of least-recently-used (LRU) elements (in the "" key - think minimal... assuming that "" is not a valid data key), and deletes the least recently used one once the maximum size is reached:

 proc cached {arrName key args} {
    upvar #0 $arrName arr
    if {![info exists arr($key)]} {
        set arr($key) [eval $args]
        if {[llength $arr()]>=$arr(maxSize)} {
            unset arr([lindex $arr() 0])
            set   arr() [lrange $arr() 1 end]
        }
    } else {
        set pos   [lsearch $arr() $key]
        set arr() [lreplace $arr() $pos $pos]
    }
    lappend arr() $key ;# LRU list
    set     arr($key)
 }

Testing: initialize a cache, fill with some data

 % array set Cache {maxSize 4 {} {}}
 % cached Cache a clock seconds
 1100702390
 % cached Cache b clock seconds
 1100702440
 % cached Cache c clock seconds
 1100702443
 % cached Cache d clock seconds
 1100702445
 % parray Cache
 Cache()        = a b c d
 Cache(a)       = 1100702390
 Cache(b)       = 1100702440
 Cache(c)       = 1100702443
 Cache(d)       = 1100702445
 Cache(maxSize) = 4

Ask for the element "a" again (moves it to end of LRU list):

 % cached Cache a clock seconds
 1100702390
 % parray Cache
 Cache()        = b c d a
 Cache(a)       = 1100702390
 Cache(b)       = 1100702440
 Cache(c)       = 1100702443
 Cache(d)       = 1100702445
 Cache(maxSize) = 4
 % cached Cache c clock seconds
 1100702443
 % parray Cache
 Cache()        = b d a c
 Cache(a)       = 1100702390
 Cache(b)       = 1100702440
 Cache(c)       = 1100702443
 Cache(d)       = 1100702445
 Cache(maxSize) = 4

As maxSize is reached, the least-recently-used "b" will be decached:

 % cached Cache x clock seconds
 1100704105
 % parray Cache
 Cache()        = d a c x
 Cache(a)       = 1100702390
 Cache(c)       = 1100702443
 Cache(d)       = 1100702445
 Cache(maxSize) = 4
 Cache(x)       = 1100704105

TV (17 Nov 04) The cache of the processor chip involved in these test is hard to put in the same beginning state to actually test these kinds of scenarios. Maybe except starting the the machine up again in the same sequence.