Caching Algorithm

The cache behaves as though it contains a collection of blocks of elements. Each cached element is counted as one object and each cached block of elements is also counted as an object. As a result, a block of four elements are counted as five objects, one object for each element and a fifth object for the block. However, if the same element occurs on several blocks it is counted only once. This is because the element cache shares elements between blocks.

The cache uses the "least recently used" algorithm on blocks of elements. That is, when the cache is full, it discards the blocks of elements that have been in the cache for the longest time without any requests for the blocks. Individual elements, which are shared between blocks, are discarded when all the blocks that contain the elements have been discarded. Finding the blocks to discard is a relatively expensive operation. Hence, the cache discards one quarter of its contents each time it reaches the maximum number of allowed objects.