Re: About efficiency

On Tue, 2002-04-02 at 20:16, [e-mail] wrote:
> Hi,
> 
> At Wed, 3 Apr 2002 08:51:31 +0900,
> Jean-Hugues ROBERT wrote:
> > I have been enjoying Ruby for 2 weeks now. I am very impressed. It is
> > my understanding that currently the interpreter directly executes the
> > parse tree versus going thru some bytecode generation phase (the later
> > is what I did for some interpreter I wrote years ago, while at the
> > same time a friend of mine was going the ruby way, hence we had
> > opportunities to compare).
> 
> Ruby VM is planned.

VM's make things a *lot* faster.  I'm experimenting with Scriptix, and
taking it from the Ruby-ish nodes to a byte-code language improved the
speed by 1.5-3 times, depending on the test (I'm no profressional
benchmark writer, mind you).

> 
> Perhaps, for backward compatibility, and maybe to deal with Regexp.
> 
> > 2) "xxx" versus 'xxx', which is more efficient ?
> > Equivalent according to Matz's recent comment. Well... I guess that when xxx does not include any special
> > construction, one of the two *has* to be faster than the other one, either at compile time (parse tree constuction
> > time I mean) or at runtime, right ? Which one ? I am used to using "xxx" but if 'xxx' is more efficient, I can use it
> > instead (when both are semantically equivalent).
> 
> 'xxx' is faster a bit at parse, just an int comparison per
> byte.  It's not significant.

Well, it could make a difference if you are re-parsing a script over and
over many times (i.e., CGI script or somesuch that's under very heavy
load).  Timing it, with a good amount of strings, can shave off a nice
number of milliseconds (hey people, there's only a thousand of those per
second! ~,^)

> 
> > 3) closure
> > I suspect that holding a closure means at least that the stack frame where the closure was created is referenced (and
> > not garbage collected until the closure disappears) (I hope that the caller stack frames aren't referenced, are they
> > ?). This may have big memory impacts, specially if the stack frame also holds references to large object. For sure it
> > does not hurt to do some xxx=nil when xxx is not usefull anymore.
> 
> Proc doesn't hold each stack, Thread does.  About an orphan
> Proc from dead Thread, the stack may be discardable.
> 
> > 3) type induction
> > One day the "dynamic typing" versus "static typing" language war will be over. That day, you will have the ability to
> > switch smoothly from dynamic to static, during the optimization phase of your project. No need for C++ style templates
> > then. All you will have to do is give hints to the compiler/interpreter about the domain/type/range of variables so
> > that the compiler/interpreter can take advantage of that knowledge to optimize the code. I have seen that being
> > applied years ago in Turbo Prolog to some extend, with incredible results. Any plan for Ruby about that ?
> 
> It's been discussed some times, but not implemented yet.

Hmm, how would that work with loadable modules?  Either you'd have to
store a lot of meta information, or modules that try to access a
variable in the wrong way from another module would cause a crash or
some other bad side-effect.

> 
> > 4) String
> > For a String intensive language like Ruby, there is an optimization that could be worth implementing. It is an
> > optimization where a String is actually made of a reference to some potentially shared string representation, +
> > an_offset, + a_size. That means that many operations then do not need to copy the string anymore (you update
> > 'an_offset' and/or 'a_size' instead, still referencing the same 'string_representation'). Has such an optimization
> > been evaluated (it has almost no impacts on the external interface) ? I think this is a type of "Copy On Write"
> > optimization.
> 
> Shugo Maeda had made a patch, but it's left yet due to the
> impact on the external interface mainly.

Wow, that's a nice one.  Will have to try that in Scriptix and see what
kind of performance and memory gain I can get (I'm more interested in
performance - less memory allocations is nice for that.)

> 
> > 5) Cache.
> > Reading the books about the implementation of Smalltalk gives some hints on how much efficient such caches can
> > be. Candidates are: caching (a_class,a_method_name)=>a_method. This cache alone doubled the speed of the smalltalk
> > interpreter !
> 
> Method cache is implemented already.

You know, one cache I found useful in Scriptix (dunno if Ruby uses it)
is a name cache.  I.e., if you have a small loop that references the
same small number of variables/members/etc., the code has a string to
find the name against.  Well, comparing pointers is faster than
comparing a whole string.  So, the compiler caches the last 20 (or
whatever number) names is encountered, so the byte-code (or node tree)
can just have multiple copies of the same string in memory.  This
reduces memory usage for variable name lookups, plus makes the lookups
faster by reducing the complexity of the name comparisons.  This
optimization had a nice effect in Scriptix, so if Ruby doesn't use it
now, it might make a big difference if it did.

> 
> > Another one is for (a_class,an_instance_variable_name)=>an_index. Assuming an object has a value (i.e. has some set of
> > instance variables) and if accessing that set directly is an option (with an index, i.e. versus sequentially or some
> > other less efficient method) then again this can speed things up a lot (in the most common cases, where objects have
> > instance variables layed out in the same order).
> 
> You can add instance variables on the fly, the last assumption
> may not be correct.  I considered it too, but had no good idea.

Hmm.  if you stored them all in a dynamically allocated array, that
might make it work (only appending entries).  The problem I see is
getting the interpreter to know what to cache when.  Doing it at run
time would just add over-head to the current member search, wouldn't
it?  (Maybe I'm just not seeing how this optimization works.)

> 
> > A less trivial cache is for inlining small methods. This is specially efficient for accessors. I think it is described
> > too in the books about the implementation of Smalltalk 80.
> 
> Maybe, but it may prohibit/restrict forward reference, or gain
> compile time cost much.

That's something I've been toying with.  A powerful optimizer can make
the runtime code a *lot* faster, but significantly slow down the
compiler.  If you load a script once and let it run for a very long time
(i.e., a full-scale application, or large mathematical computations), or
if you run a small script repeatedly (using scripts as callbacks in
triggers in an embedding application), then the greatly increased
compile time could well be worth it.

I've not looked much at the Ruby compiler, but perhaps two separate
compilers would be possible?  A simpler, lighter one that compiles
quickly and runs at moderate speed, and a complex one that may take many
seconds to compile a smaller app/script, but run at lightning speeds?

Also, a more complex compiler may be useful if Ruby let you save to some
form of bytecode (hell, even an binary or XML representation of the
current node tree scheme), then load that back in.  You could do like
you would with C - spend a lot of time compiling, but get applications
much much faster than a fully interpreted language.

> 
> -- 
> Nobu Nakada