[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: CLOS Speed

With regard to the method vs. procedure call numbers, I presume this
is a method with a single specialized parameter, inheritance
is not involved, and you've taken no measures to defeat the generic function
caching, correct? If so, then the numbers you've presented are
about the same in Lucid Common Lisp on a Sun 3/110. With the stock
PCL implementation from PARC, I'm typically seeing a factor of 3 
difference between function calling and method invocation when the
method function is cached. By modifying the caching dispatching function
to heavily declare everything, that can be reduced to about a factor
of 2. A factor of 2 difference between a function call and a method 
invocation is pretty good, about what you get in Objective-C, somewhat
slower than C++ (three to 5 instructions). Polymorphic operations
don't come free, unfortunately. It might be possible to reduce dispatch
time even further by assembly coding the dispatch functions, but I
have no data for Lucid Lisp. I did something similar in HP Lisp and
the result was fast enough to program graphics applications.

If a cache miss occurs, then you really pay. The default algorithm is
linear in the number of methods defined on the generic function. I
replaced the default algorithm with a hash table and am getting times
which are about 9 times a function call, with no variation in the number
of methods on the generic function. Again, this is for single

For multiple dispatching, the cost of doing the CLASS-OF operation 
rapidly comes to dominate the cache hit calculation as the number
of parameters discriminated on increases. If a cache miss occurs,
a similar kind of linear dependency on the number of methods
defined on the generic function is observed. I have implemented an
algorithm which is logarithmic in the number of methods, but have
not finished measuring it yet.

Before you decide not to use CLOS, I urgue you to code up tests using
DEFSTRUCTs and functions with TYPECASE or COND having the same number
of branches as methods on the generic function. I think you'll find
that there will be some number of "methods" at which the TYPECASE
or COND versions will start to exceed the generic function/method

As to slot access, since most compilers can optimize slot access for
DEFSTRUCTs to one or two instructions, this comparison is not suprising.
I believe Gregor is working on some code to significantly improve
slot access in PCL. Slot access in CLOS will probably always be one
instruction longer than for DEFSTRUCTs because of the need to support
class redefinition, but there is still considerable room for improvement.
Since generic functions should ultimately be definable on DEFSTRUCTs as
well, you can define methods on DEFSTRUCTs if you still find slot access
to be too slow.