From: Jean-Hugues ROBERT <jean_hugues_robert@...>
Date: 2002-04-05T17:12:04+09:00
Subject: Re: About efficiency

Hello,

This msg is about the Ruby C interpreter, not about using Ruby itself.

About caching in an OO interpreter like Ruby. Speeding access to an object's
instance variable can be done in two complementary ways. This involve some
caching. In both cases the cached data is invalidated if the structure of the
object changes, either because some method is added/deleted/changed or
because something similar happened to the instances variables. However, the
caches work because most objects have a fairly stable structure.

1) Caching access to an instance variable
The problem is that the cache is not 100% valid because the structure of
objects can change. Hence, the cache is just a "hint", not a definitive
answer. Algo:
   1) get cached_data from cache(obj.type, inst_var_name)
   2) get variable based on cached_data (if available, else skip to step 5)
   3) check that variable is expected one (true in most cases)
   4) If true then return, it's been fast
   5) If false, use previous "slow" access method
   6) update cache entry for cache( obj.type, inst_var_name)
The cache beeing just a "hint", if for any reason it is not a good hint,
we simply fallback to the slower access.

2) Caching access to an accessor (either getter or setter)
We have the same type of problem here. The cache can get invalidated if the
accessor's definition change. Algo:
At runtime:
   1) When about to call a method, first check if it is an accessor
   2) If so, don't call it, directly access the instance variable
   3) Else, use previous "slow" access method
At compile time
   1) Detect if method is an accessor (setter or getter).
   2) Age the global cache (making it totally invalid, i.e. clearing it).

Nota: clearing the global method cache is done by "aging" it. That is:
when caching a method access in cache( obj.type, method_name), save a
"generation" counter in addition to the method. When using the cached data,
first check that it is still "valid", i.e. that the "generation" is equal
to the "current generation". Increment "current generation" whenever a new
"def" is done (or a method is deleted).

Please note that both cache do *not* require any help from the Ruby
developer. More aggressive caching can be implemented if the developer is
OK to provide "hints" to the compiler. Similar to "final" or "const" is
some language (such "hints" would tell the compiler that either a whole
class or some method will never be modified, subclassed, removed, etc...

I don't know if these caching technics are applicable to the Ruby C interp,
maybe they are already implemented, or maybe something better exists. I did
a quick search in the mailing list archive, but I am not 100% efficient
with it. Sorry if this msg is a repeat.

Jean-Hugues


---------------------------------------------------------------------------
Web:  http://hdl.handle.net/1030.37/1.1
Phone: +33 (0) 4 92 27 74 17