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 further use (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 elements, and deletes 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) = 4Ask 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