Jochen Theodorou wrote: > Charles Oliver Nutter schrieb: >> Hello again friends! >> >> I'm looking to start a discussion about caching strategies for dynamic >> languages. Probably focused mostly around inline caches, but also >> mechanisms for per-class or global caches to supplement the inline cache. >> >> A description of Ruby's class structure may help frame the discussion: >> >> * Ruby's classes are all mutable. Therefore any cache needs to be >> invalidated either actively or passively in response to changes anywhere >> in the class hierarchy. We obviously desire to localize such effects as >> narrowly as possible. >> * Ruby supports mixin inheritance, where at any time a given class may >> mix in a "module" containing methods. The module as a pseudo-class in >> between the current class and its superclass, becoming a virtual >> superclass. So these mixins must also effect cache validation. >> * Modules themselves are also open, meaning mutation of an included >> module needs to be considered as well. >> * Modules can mix in modules. >> * Ruby also supports creating per-object "singleton classes", which act >> as a new anonymous class for a given object, immediately below its >> original class. Singleton classes act like any other classes, other than >> their frequently being very short-lived. > > when you want to start a discussion about caching strategies it would > help to know what exactly your problem is. Even if it is just a general > problem we need to focus the problems I think.
Yes, I think I missed one word in there...I was hoping to talk about method caching strategies. But I guess the rest of the email made that pretty clear. > anyway, the basic problem I see is: you cached a method and now you want > to know if it is still the right method to call. Basically we have the > same problem in Groovy and my "idea" was to have version counter. So the > method has a reference to the class, the class knows its version. If a > class is mutated, then the version counter must be increased. As a > result the cached method becomes invalid. Now of course there is a > problem as I don't know what kind of cache you have. JRuby has had an inline cache for over a year, and *actively* flushes call sites. We keep references to them in a JRuby-runtime-global map, and when changes happen to the hierarchies from which they came we tell all sites known to have cached that method to flush themselves. This works very well so far, but there's a very small chance that under high concurrent load, if a method is simultaneously being called by one thread and redefined by another a cache could get stuck with a stale entry and potentially never flushed. I have not been able to produce this effect experimentally and it has never been reported, so we have not made substantial efforts to replace the active flushing logic. Are you using a version number now? We have attempted to install a version number but it's complicated by several factors: Given class X from which we cached the method: - A change anywhere in X or its superclasses must trigger X's version to increment. - A change anywhere in any modules included into X or any of its superclasses must trigger X's version to increment. These two combined mean we have to have both downreferences from parent to child (necessarily weak references) as well as backreferences from included modules to the pseudoclasses used to mix them in. An alternative, which I implemented as an experiment, is to instead calculate the version each time, compositing version information recursively through the hierarchy. If the per-class cost is low enough, this does improve performance slightly over a raw search for the method in all superclasses' method maps. But it doesn't appear to help enough to warrant the complexity. > For example in a call site cache, you can throw the method out, as soon > as you revisit the cache. If the method is cached in a memory sensitive > way, then there is no need to do that more early I think. If your cache > happens to be in the class itself, then invalidating the cache as soon > as the class is mutated might be an idea. If you have some kind of > inline cache, then you usually have something based on method names and > the cache has some kind of structure that reacts to what class is in > use.Well... I would say that once you found your case you have to check > the version again. The benefit of throwing it out early is reducing the guard cost at the site itself. If we can actively clean out sites there's no need to re-check anything other than incoming object type == previously cached object type. We have been looking at various strategies, including per-class caches, global caches, class serial/version numbers, and so far have been thwarted trying to implement them due to the extreme mutability of Ruby's class hierarchy. > What is bad about the version idea? In a multi threaded environment you > have the problem, that each time you ask for the class version you have > to access synchronized data... There are possible ways around it if you > have thread locals that get informed about class changes in a event like > system. A bit lame probably ;) I think a volatile version number would be sufficient, and only updating the version number would need to be synchronized. There's no reason accessing the version number would have to be synchronized since field access is an atomic operation. - 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 -~----------~----~----~----~------~----~------~--~---
