[armedbear-devel] patch: do not call compile for every call of eql-specialized generic functions
Hello.
The attached is a patch to improve performance of eql-specialized generic functions.
I started to investigate this problem because slime fuzzy completion works very slow with ABCL. For example
(time (swank::fuzzy-completions "de" 'cl-user))
takes 1.5 - 2 seconds. That long time is not pleasant for user interface.
Turned out that most of the time is spent in COMPILE.
During SWANK::FUZZY-COMPLETIONS every symbol is processed by SWANK-CLASSIFY-SYMBOL, which uses (DOCUMENTATION s 'TYPE), and every invocation (DOCUMENTATION s 'TYPE) being eql-specialized function leads to COMPILE.
With my patch (time (swank::fuzzy-completions "de" 'cl-user)) takes 0.25 - 0.5 seconds. Not too fast, in CLISP the same takes 0.07 sec, in CCL 0.03 sec. But significantly better than it was.
In the patch method getArgSpecialization could probably be named better. Also I am not sure if you want to keep the wordy javadoc comment; i just decided to put the patch explanation to the sources instead of this email.
Best regards, - Anton
Anton Vodonosov wrote:
Hello.
The attached is a patch to improve performance of eql-specialized generic functions.
Committed as [svn 12042][1].
I'm not totally convinced as to what would happen to the eql-specialization cache in the face of subsequent redefinitions, but can't really come up with a good counter-example. Your understanding of our CLOS implementation seems already greater than mine, your patch does speed up swank's fuzzy completion, and it doesn't seem to break anything that I could find, so we'll go with this behavior for now. If anyone else has objections, please let us know.
[1]: http://trac.common-lisp.net/armedbear/changeset/12042
In the patch method getArgSpecialization could probably be named better. Also I am not sure if you want to keep the wordy javadoc comment; i just decided to put the patch explanation to the sources instead of this email.
Comments, especially long ones, are always welcome.
Thanks for the contribution!
2009/7/13 Mark Evenson evenson@panix.com:
I'm not totally convinced as to what would happen to the eql-specialization cache in the face of subsequent redefinitions, but can't really come up with a good counter-example.
More precisely it's not only eql-specialized method cache, but cache for all the (effective) methods.
When generic function is called, correct code must be executed, according to the passed arguments, taking into account all the methods defined, class precedence lists for argument classes, method combination of the generic function.
Calculation of the correct code is expensive, therefore a cache is used. When we call (FN X Y) first time, effective method is calculated based on X and Y, and stored in cache of the generic function FN.
This mechanism was already in place, but it wasn't used for eql-specialized methods. Instead full clos dispatch was performed every time for every generic function having at least one eql-specialized method. Full CLOS dispatch in ABCL includes generation some lisp code at runtime, and compiling it.
My fix just extends the chaching mechanism to handle eql-specialized methods too.
Redefinitions are handled as before: function FINALIZE-GENERIC-FUNCTION just clears the cache. This function is called every time when new method is added to a generic function (but it seems not to be called when class hierarchy changes, probably that's what was referred by the old ABCL home: "ABCL's CLOS is slow and does not handle on-the-fly redefinition of classes correctly").
Christophe Rhodes in sbcl-help once pointed me to "Efficient Method Dispatch in PCL" by Kiczales and Rodriguez. Maybe you'll find it useful (I personally still haven't worked through this 15 pages doc; but the quick glance i made at that time gave me understanding that CLOS dispatch is optimized by caching and therefore helped to understand the ABCL code now).
Best regards, - Anton
Anton Vodonosov wrote:
2009/7/13 Mark Evenson evenson@panix.com:
I'm not totally convinced as to what would happen to the eql-specialization cache in the face of subsequent redefinitions, but can't really come up with a good counter-example.
More precisely it's not only eql-specialized method cache, but cache for all the (effective) methods.
[…]
Thanks for the more detailed explanation of what's going on here. It gives me a better place to meditate for my understanding.
Christophe Rhodes in sbcl-help once pointed me to "Efficient Method Dispatch in PCL" by Kiczales and Rodriguez. Maybe you'll find it useful (I personally still haven't worked through this 15 pages doc; but the quick glance i made at that time gave me understanding that CLOS dispatch is optimized by caching and therefore helped to understand the ABCL code now).
Further help in this paper ["Efficient Method Dispatch in PCL"][1] is also appreciated.
[1]: http://www2.parc.com/csl/groups/sda/publications/papers/Kiczales-Andreas-PCL...
armedbear-devel@common-lisp.net
-
Anton Vodonosov -
Mark Evenson