LRUCacheDoc.tioga
Created by: Christian Jacobi, August 15, 1986 1:17:29 pm PDT
Last Edited by: Christian Jacobi, August 18, 1986 10:40:08 am PDT
LRUCache
CEDAR 6.1 — FOR INTERNAL XEROX USE ONLY
LRUCache
Christian Jacobi
© Copyright 1986 Xerox Corporation. All rights reserved.
Abstract: Definitions for least recently used cache abstraction.
Created by: Christian Jacobi
Maintained by: Christian Jacobi <Jacobi.pa>
Keywords: lru, cache
XEROX Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304
For Internal Xerox Use Only
LRUCache
Definitions for least recently used cache abstraction.
The definition
LRUCache: CEDAR DEFINITIONS...
Handle:
TYPE = ...
A handle represents a least recently used cache.
HashProc: TYPE = PROC [REF] RETURNS [CARDINAL];
EqualProc: TYPE = PROC [REF, REF] RETURNS [BOOL];
Create:
PROC [size:
NAT, hash: HashProc←
NIL, equal: EqualProc←
NIL]
RETURNS [Handle];
Creates a new empty lru cache of given size.
The following relations for hash and equal are imposed:
-hash returns always the same value given the same argument.
-2 equal values (equal returns TRUE on them) must have the same hash key.
Defaults for hash and equal are:
hash: a [low quality] [fast] rope hash.
equal: Rope equality with case mattering.
Include:
PROC [h: Handle, value:
REF]
RETURNS [index:
NAT, insert:
BOOL, used:
REF];
Includes value into a lru cache
Returns
index: "index" of new inserted or re-used value in lru cache; 0<=index<size.
insert: value has been inserted into table [otherwise: old value re-used].
used: the "equal" val found in table, or value again, if insert=TRUE.
Constant time, independent of size of lru-cache.
If two lru-caches of same size, with same hash and equal procedures are used on
the same values in the same order, they will return the same numbers for index.
Fetch:
PROC [h: Handle, index:
NAT]
RETURNS [used:
REF];
Fetches a value from a lru cache.
index must have been previously returned with Include.
Considers the returned value to be used.
Reset:
PROC [h: Handle];
Empties a lru cache again.
Usage
start package:
use the load file LRUCache.load
LRU-caches are completely garbage collected when they are no more used
The module HashTable provides some hash and equal procs, these procedures fullfill LRUCache's requirements.
Rational
LRU caches have been used in ChipNDale for two purposes:
Compaction of output files:
Atoms are entered into a lru-cache before output. If the atom was found, only its index into the lru-cache was written. The reading routine builds an array with aequvalent entries! (For robustness: Not anoyther lru cache is used; the reader does not need to know the cache size)
Reduce of memory usage:
Immutable objects are entered into a lru-cache on creation. This allows to re-use already created objects without caching all objects: The objects are still subject to the garbage collector.