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 -~----------~----~----~----~------~----~------~--~---
