That's certainly one solution; and it's probably one we'll explore on our own. I'm hoping to find some papers or empirical evidence or existing implementations that do this, especially in the presence of multiple threads.
For the most part I keep coming to a serial number on each node of the hierarchy that represents a point in time for it and all ancestors. Any change in the ancestors them propagates serial number changes to all descendants, and the cache has a passive guard that compares the cached serial number with the incoming serial number. Ideally a way to eliminate the guard at the cache site itself would be ideal, but I haven't been able to think through an efficient and thread-safe way to do that active cache site flushing without a "stop the world" approach that would probably be too costly. I have a working implementation of a serial number-based per-node cache that appears to work reasonably well, but it does not propagate changes down the hierarchy. As a result, each guard has to walk all ancestors and calculate an aggregate serial number every time; this increases the cost of invalidating data cached out of a single-element hierarchy (probably more than I'm comfortable with) but works extremely well for reducing the cost of caching data out of a deep hierarchy (the deeper, the more savings, since the ancestor walk and serial number calculation is ultimately far cheaper than an ancestor walk plus a hash hit at each node). Matt Fowles wrote: > Charlie~ > > Why not simply have all the nodes of the tree cache their value and > put invalidate hooks that propagate mutation upwards. Then when any > node changes, it simply tells it dependent nodes that they must > invalidate their caches. This allows you to invalidate an entire > branch at touch, but doesn't require you to throw away everything. > > Matt > > On Tue, Sep 30, 2008 at 4:54 PM, Charles Oliver Nutter > <[EMAIL PROTECTED]> wrote: >> I'm looking for papers, references, descriptions of methodologies for >> caching data out of a mutable hierarchy. Anyone got some pointers? >> >> Basically in JRuby we have lots of untapped caching opportunities, for >> methods, "constants", class variables, and so on. All these caching >> opportunities tend to be stymied by the high mutability of Ruby's >> hierarchy. So I'm trying to boil the problem down to a more general space: >> >> 1. We wish to cache arbitrary data elements out of a hierarchy >> 2. The data elements in each node of the hierarchy are mutable, with >> mutations "affecting" all downstream nodes (in other words, the cached >> data is always looked up from the leaves to the trunk) >> 3. The structure of the hierarchy can be changed, adding single elements >> at arbitrary points (i.e. at any time new nodes can be inserted >> immediately between the current node and its "super" node). >> 4. The cache should be as fast as possible for access, with the >> acceptable tradeoff being a higher mutation cost. >> 5. The hierarchy could be bi-directional, but ideally that would not be >> a requirement. A secondary bi-dir hierarchy could be layered atop the >> original to avoid overt parent-to-child references. >> >> There has to be some prior work in this area, or a simple data structure >> I've overlooked. Finding such a structure would help caching efforts for >> most dynamic languages, but especially help Ruby. >> >> Any thoughts or pointers? >> >> - Charlie >> > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "JVM Languages" group. To post to this group, send email to jvm-languages@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/jvm-languages?hl=en -~----------~----~----~----~------~----~------~--~---
