[Ecls-list] Hopefully some innovation..

[Brian Spilsbury]

> There is also another issue, which is that the cache does not use
> timestamps. When the cache gets full, it is simply emptied and
> everything starts from zero. It would be nice if we could come up with
> a very cheap algorithm to overwrite entries in the cache when this has
> reached the predetermine size. Note however that the cache only grows
> when methods are called with different types of objects. Rather
> complicated programs would be required to test the performance of such
> rewriting algorithm.

Have you considered integrating a Clock-like cache with the hash-table?

In this model each entry has a single bit associated with it, and the
hash-table has a cursor.
When the cache is full, the cursor sweeps incrementally around the
hash-table, looking for
an entry without the bit set and clearing the set bits that it passes.

When it finds an entry without the bit set, it removes it, then adds
the new entry with its bit
set. It's a kind of one bit approximation to LRU.

I think thread-local caching sounds good in that threads are often
quite specialized in terms
of the functions they call. As for invalidation, have you considered
simply setting a bit on each
cache which says "please clear this cache the next time you use it?".
This bit can be set using
a lock-free list traversal and update, so it should be very cheap.
Redefinition is probably rare enough that it's worth lazily flushing
all method caches everywhere when it happens.

Regards,
Brian.