If one wants to work with a large number of large objects which require some time to prepare and one does not know beforehand, how often one will need each one, it makes sense to work with some sort of cache. A cache is a data structure to keep some of the objects already produced but not too many of them to waste a lot of memory. That is, objects which have not been used for some time can automatically be removed from the cache, whereas the objects which are used more frequently stay in the cache. This chapter describes an implementation of this idea used in the orbit-by-suborbit algorithms.
A cache is created using the following operation:
‣ LinkedListCache( memorylimit ) | ( operation ) |
Returns: A new cache object
This operation creates a new linked list cache that uses at most memorylimit bytes to store its entries. The cache is organised as a linked list, newly cached objects are appended at the beginning of the list, when the used memory grows over the limit, old objects are removed at the end of this list automatically.
New objects are entered into the hash with the following function:
‣ CacheObject( c, ob, mem ) | ( operation ) |
Returns: A new node in the linked list cache
This operation enters the object ob into the cache c. The argument mem is an integer with the memory usage of the object ob. The object is prepended to the linked list cache and enough objects at the end are removed to enforce the memory usage limit.
‣ ClearCache( c ) | ( operation ) |
Returns: Nothing
Completely clears the cache c removing all nodes.
A linked list cache is used as follows: Whenever you compute one of the objects you store it in the cache using CacheObject (5.2-2) and retain the linked list node that is returned. The usual place to retain it would be in a weak pointer object, such that this reference does not prevent the object to be garbage collected. When you next need this object, you check its corresponding position in the weak pointer object, if the reference is still there, you just use it and tell the cache that it was used again by calling UseCacheObject (5.2-4), otherwise you create it anew and store it in the cache again.
As long as the object stays in the cache it is not garbage collected and the weak pointer object will still have its reference. As soon as the object is thrown out of the cache, the only reference to its node is the weak pointer object, thus if a garbage collection happens, it can be garbage collected. Note that before that garbage collection happens, the object might still be accessible via the weak pointer object. In this way, the available main memory in the workspace is used very efficiently and can be freed immediately when needed.
‣ UseCacheObject( c, r ) | ( operation ) |
Returns: Nothing
The argument c must be a cache object and r a node for such a cache. The object is either moved to the front of the linked list (if it is still in the cache) or it is re-cached. If necessary, objects at the end are removed from the cache to enforce the memory usage limit.
generated by GAPDoc2HTML