[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) = 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.
----
[Arts and crafts of Tcl-Tk programming]