Charlie, have a look on ClassInfo and around in Groovy. May be it is what you need or similar.
Alex On Wed, Oct 1, 2008 at 1:11 AM, Charles Oliver Nutter < [EMAIL PROTECTED]> wrote: > > 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 -~----------~----~----~----~------~----~------~--~---
