Re: goops and memoization

From: Mikael Djurfeldt <mdj@kvast.blakulla.net>
Cc: djurfeldt@nada.kth.se,
	 Dirk Herrmann <dirk@sallust.ida.ing.tu-bs.de>,
	guile-devel@gnu.org
Subject: Re: goops and memoization
Date: Thu, 21 Nov 2002 19:49:18 -0500	[thread overview]
Message-ID: <xy7of8i2zu9.fsf@linnaeus.i-did-not-set--mail-host-address--so-tickle-me> (raw)
In-Reply-To: <m3u1ia8y17.fsf@laruns.ossau.uklinux.net> (Neil Jerram's message of "21 Nov 2002 20:31:48 +0000")

Neil Jerram <neil@ossau.uklinux.net> writes:

>     Mikael> Benchmarks show that GOOPS method dispatch is
>     Mikael> negligible and a GOOPS generic function nearly as
>     Mikael> efficient as an ordinary closure.
>
> Are those benchmarks available?

Checkout the guile/guile-modules/benchmarks CVS module at
subversions.gnu.org.  There should be a benchmark goops.scm.  You run
it with (type-dispatch-run).

> If I do change the code, it would be good to check that the changes
> don't hurt performance.

Yes.  I would like to be able to continue using GF:s in the inner
loops of my applications.

>     Mikael> Currently, compile-method only makes sure the method has a
>     Mikael> local next-method binding (specific to this method cache
>     Mikael> entry) if that is needed.  However, there are plans to let
>     Mikael> it make powerful optimizations of the code, with great
>     Mikael> potential of reducing overhead.
>
> Do you mean IOR ?

Some of the optimizations mentioned in the IOR text can be done in
current GOOPS.

> If so, couldn't most IOR optimizations be made when the method is
> first defined?

No.  They are dependent on the actual argument types in the
application, not the possible ones.

BTW, maybe I should add something I didn't mention about GOOPS type
dispatch: The method cache uses hashing if the number of methods goes
above a small threshold.  This hashing scheme uses an optimization
which allows for direct hits of the correct entry in the majority of
lookups.

Method cache hash optimization scheme
-------------------------------------

The basic idea is to compute a hash code from the actual arguments of
an application and reduce this code to a hash index in the cache.

The type of each argument is represented by a class object.  Each
class object has 8 hash values.  (Hash values # 1 of all classes in
the system constitutes "hash set 1" etc.)  When building the method
cache, all hash sets are tried, and the one which gives most direct
hits is chosen.  Information about which hash set is used is stored in
the GF object.

Apart from optimizing dispatch this also results in compact
representations of the method caches.

_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel