On Sep 30, 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?
>
Yes, my recommendation is that the representation of the entire
'mutable' hierarchy be a single immutable (tree-like) value. 'Changes'
to the hierarchy will create a completely new version and swap it in
atomically (using synchronized or a CAS). Caches can simply use the
hierarchy value itself as a has-been-modified flag, no numbering
needed. Different hierarchy from cached means recalc - staleness test
is ==. Your cache can be an optimized copy of and/or calculated from
anything in the hierarchy.
The presumption is that hierarchy changes are infrequent and blowing
all caches every mod is ok. If not, you can still number nodes (then
cache the root and the number, different root _and_ different number
mean recalc cache), but stick with the immutable tree.
Clojure does this for its ad hoc hierarchies and it is simple and
fast.
Rich
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "JVM
Languages" group.
To post to this group, send email to [email protected]
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
-~----------~----~----~----~------~----~------~--~---
