From: Pillsy
Subject: Sealed generic functions in CLOS?
Date: 
Message-ID: <1163547445.880883.295190@b28g2000cwb.googlegroups.com>
AIUI, a major reasons that generic functions can not be optimized as
aggressively as regular functions is that they have to allow for the
possibility of adding methods dynamically at pretty much any time.
Thus, presumably getting rid of that ability allow for speed increases.
Of course, this isn't something you'd want to do in general, because
adding new defmethods later is useful, but is there a way to do it on a
GF-by-GF basis?

I know that it's not in ANSI CL, but do any of the CL implementations
allow a declaration or something equivalent? Or maybe there's a way of
automagically converting a GF into a something like defun with a
typecase in it?

Am I crazy to even want this?

TIA,
Matt

From: bradb
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <1163548332.382239.175750@f16g2000cwb.googlegroups.com>
On Nov 14, 3:37 pm, "Pillsy" <·········@gmail.com> wrote:
> AIUI, a major reasons that generic functions can not be optimized as
> aggressively as regular functions is that they have to allow for the
> possibility of adding methods dynamically at pretty much any time.

Is that really true?  Imagine the case where you have a single GF that
takes one argument that is not specialized.  It could in theory be
exactly the same code as a regular function.  When you add a
specialization to that GF, it needs to do some type checking and call
one specialization or the other, so I can see the overhead of needing
to dynamically determine the type at runtime.  I would expect the call
overhead for GFs to be based on the number of arguments they specialise
on and how many specialized functions there actually are.
Given a sufficiently smart and sufficiently well informed compiler, it
should also be possible to statically determine which specific method
needs to be called from the call site - though it sounds hard to me.  I
don't see why you'd get a win from "sealing" the GF, after all you have
a complier in the image, if need be you can recompile whatever you need
to when you add a method.

Am I completely off track with my thoughts here?

Cheers
Brad
From: Thomas A. Russ
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <ymi4pt0poq4.fsf@sevak.isi.edu>
"bradb" <··············@gmail.com> writes:

> Given a sufficiently smart and sufficiently well informed compiler, it
> should also be possible to statically determine which specific method
> needs to be called from the call site - though it sounds hard to me.

Well, the real problem lies in the ability to dynamically add the new
methods.  The static analysis done during compilation may no longer be
valid if you change (by adding or deleting) a method from the generic
function. 

>  I
> don't see why you'd get a win from "sealing" the GF, after all you have
> a complier in the image, if need be you can recompile whatever you need
> to when you add a method.

Well, the issue is how to do this recompilation.  In effect that is what
often happens (sort of) below the surface of most high performance CLOS
implementations.  But instead of recompiling the calling code what
happens is that the call form itself does some sort of caching of the
methods.

-- 
Thomas A. Russ,  USC/Information Sciences Institute
From: Didier Verna
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <muxzmasxu1n.fsf@uzeb.lrde.epita.fr>
"bradb" <··············@gmail.com> wrote:

> I don't see why you'd get a win from "sealing" the GF

        Sometimes you want to retain the ability to modify your program at
run-time, but sometimes you don't need that, or you need to sacrifice that to
get better performance. Of course you can reinvent a new object system to do
that, but the real power is to be able to express everything in the same
context (in CLOS ideally). Also, apart from the question of homogeneity, it's
easy to imagine a situation in which during program development, you prefer to
keep everything dynamic, but once the program is stabilized, you know you can
freeze some parts of it.

There is a particularly interesting case where sealing a GF would be useful:
it would make it possible to inline the calls, just the way a standard
function can be inlined. This is especially nice for performance when your
methods happen to be small but called very often (hence, the dynamic dispatch
is costly compared to the actual time needed to execute the function). This
happens a lot in image processing for instance.


-- 
Check out my new jazz CD on http://www.didierverna.com/ !

Didier Verna	EPITA / LRDE, 14-16 rue Voltaire   Tel.+33 (1) 44 08 01 85
             	94276 Le Kremlin-Bic�tre, France   Fax.+33 (1) 53 14 59 22
From: Pascal Bourguignon
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <871wo5ftdj.fsf@thalassa.informatimago.com>
"Pillsy" <·········@gmail.com> writes:

> AIUI, a major reasons that generic functions can not be optimized as
> aggressively as regular functions is that they have to allow for the
> possibility of adding methods dynamically at pretty much any time.
> Thus, presumably getting rid of that ability allow for speed increases.
> Of course, this isn't something you'd want to do in general, because
> adding new defmethods later is useful, but is there a way to do it on a
> GF-by-GF basis?
>
> I know that it's not in ANSI CL, but do any of the CL implementations
> allow a declaration or something equivalent? Or maybe there's a way of
> automagically converting a GF into a something like defun with a
> typecase in it?
>
> Am I crazy to even want this?

So you have a function and you have a predetermined set of types?

Why do you want a generic function? 
Just use an normal function and typecase!


If in addition you want to be able to write the code of the various
cases in different places, you can easily write some macrology to do
it, and collect the bodies at the end to build the defun.



-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
From: Pillsy
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <1163551764.249456.281820@h48g2000cwc.googlegroups.com>
Pascal Bourguignon wrote:

> So you have a function and you have a predetermined set of types?

> Why do you want a generic function?
> Just use an normal function and typecase!

Because (hypothetically) when I started writing my program, I didn't
know what my predetermined set of types and methods would be. But when
I finished writing my program, I know all of that, but now have a
performance issue with method dispatch.

I can do (and less hypothetically, have done) the conversion myself,
but it's kinda tedious, repetitive, and error-prone---exactly the sort
of thing I bought my computer to do for me.

Cheers,
Matt
From: Pascal Bourguignon
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <87wt5xe9se.fsf@thalassa.informatimago.com>
"Pillsy" <·········@gmail.com> writes:

> Pascal Bourguignon wrote:
>
>> So you have a function and you have a predetermined set of types?
>
>> Why do you want a generic function?
>> Just use an normal function and typecase!
>
> Because (hypothetically) when I started writing my program, I didn't
> know what my predetermined set of types and methods would be. But when
> I finished writing my program, I know all of that, but now have a
> performance issue with method dispatch.
>
> I can do (and less hypothetically, have done) the conversion myself,
> but it's kinda tedious, repetitive, and error-prone---exactly the sort
> of thing I bought my computer to do for me.

So you are wanting what I described in the cut out part.

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter *partial-functions* (make-hash-table)))

(defmacro define-partial-function
     (name ((arg type) &rest other-arguments) &body body)
  (let ((partial-name (intern (format nil "~A-~A" name type))))
    (push (list partial-name type (cons arg other-arguments))
          (gethash name *partial-functions* '()))
   `(progn
     ;; we use a function to get the lexical environment.
     (defun ,partial-name ,(cons arg other-arguments)
        (block ,name ,@body))
     ',name)))

(defun generate-partial-functions ()
  (maphash
     (lambda (k v)
        (compile
          (eval 
            `(defun ,k ,(third (first v))
               (etypecase ,(first (third (first v)))
                 ,@(mapcar (lambda (e)
                            `(,(second e) (,(first e) ,@(third (first v)))))
                         (reverse v)))))))
     *partial-functions*))

(let ((z 0))
  (define-partial-function f ((x integer) y) (+ x y (incf z))))

(let ((z ""))
  (define-partial-function f ((x string) y)
    (setf z (concatenate 'string z "!"))
    (concatenate 'string x (format nil "~A" y) z)))

(eval-when (:compile-toplevel :load-toplevel :execute)
  (generate-partial-functions))



[107]> (function-lambda-expression 'f-integer)
(LAMBDA (X Y) (DECLARE (SYSTEM::IN-DEFUN F-INTEGER))
 (BLOCK F-INTEGER (BLOCK F (+ X Y (INCF Z))))) ;
#(#(Z 0 NIL) NIL NIL NIL
  ((DECLARATION XLIB::CLX-VALUES VALUES OPTIMIZE DECLARATION))) ;
F-INTEGER
[108]> (function-lambda-expression 'f-string)
(LAMBDA (X Y) (DECLARE (SYSTEM::IN-DEFUN F-STRING))
 (BLOCK F-STRING
  (BLOCK F (SETF Z (CONCATENATE 'STRING Z "!"))
   (CONCATENATE 'STRING X (FORMAT NIL "~A" Y) Z)))) ;
#(#(Z "" NIL) NIL NIL NIL
  ((DECLARATION XLIB::CLX-VALUES VALUES OPTIMIZE DECLARATION))) ;
F-STRING
[109]> (function-lambda-expression 'f)
(LAMBDA #1=(X Y) (DECLARE (SYSTEM::IN-DEFUN F))
 (BLOCK F
  (ETYPECASE X (INTEGER (F-INTEGER . #1#)) (STRING (F-STRING . #1#))
   (INTEGER (F-INTEGER . #1#)) (STRING (F-STRING . #1#))))) ;
#(NIL NIL NIL NIL ((DECLARATION XLIB::CLX-VALUES VALUES OPTIMIZE DECLARATION))) ;
F
[110]> (f 4 5)
10
[111]> (f 4 5)
11
[112]> (f "4" 5)
"45!"
[113]> (f "4" 5)
"45!!"
[114]> (f 4.5 6)

*** - The value of X must be of one of the types INTEGER, STRING, INTEGER,
      STRING
      The value is: 4.5


Of course you can also dispatch on multiple arguments, and process
better the lambda lists (you can use my
COM.INFORMATIMAGO.COMMON-LISP.SOURCE package to parse the lambda
list).


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

The world will now reboot.  don't bother saving your artefacts.
From: Pillsy
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <1163557061.392605.56270@m73g2000cwd.googlegroups.com>
Pascal Bourguignon wrote:
> "Pillsy" <·········@gmail.com> writes:
[...]
> > I can do (and less hypothetically, have done) the conversion myself,
> > but it's kinda tedious, repetitive, and error-prone---exactly the sort
> > of thing I bought my computer to do for me.

> So you are wanting what I described in the cut out part.

I didn't think I did, but seeing it close up, it looks pretty good.

Thanks,
Matt
From: Ari Johnson
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <m2lkmdtl6v.fsf@hermes.theari.com>
Pascal Bourguignon <···@informatimago.com> writes:

> "Pillsy" <·········@gmail.com> writes:
>
>> AIUI, a major reasons that generic functions can not be optimized as
>> aggressively as regular functions is that they have to allow for the
>> possibility of adding methods dynamically at pretty much any time.
>> Thus, presumably getting rid of that ability allow for speed increases.
>> Of course, this isn't something you'd want to do in general, because
>> adding new defmethods later is useful, but is there a way to do it on a
>> GF-by-GF basis?
>>
>> I know that it's not in ANSI CL, but do any of the CL implementations
>> allow a declaration or something equivalent? Or maybe there's a way of
>> automagically converting a GF into a something like defun with a
>> typecase in it?
>>
>> Am I crazy to even want this?
>
> So you have a function and you have a predetermined set of types?
>
> Why do you want a generic function? 
> Just use an normal function and typecase!
>
>
> If in addition you want to be able to write the code of the various
> cases in different places, you can easily write some macrology to do
> it, and collect the bodies at the end to build the defun.

This is essentially my suggestion.  Write your own generic function
system that allows for this.  Then you have the benefit of writing
code in defmethod style while you develop and just adding a
post-compile optimize-generic-functions call to finalize them when you
are ready to deploy.
From: Juho Snellman
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <slrnelkvra.i3s.jsnell@sbz-30.cs.Helsinki.FI>
Pascal Bourguignon <···@informatimago.com> wrote:
> So you have a function and you have a predetermined set of types?
>
> Why do you want a generic function? 
> Just use an normal function and typecase!

In many (if not most) implementations generic function dispatch for
CLOS instances will be significantly faster than using a typecase.

-- 
Juho Snellman
From: Pillsy
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <1163570395.331041.60600@f16g2000cwb.googlegroups.com>
Juho Snellman wrote:

> In many (if not most) implementations generic function dispatch for
> CLOS instances will be significantly faster than using a typecase.

With SBCL, I got significant speed-ups from that sort of change.
Specifically, when I changed this...

(defgeneric get-tracked-move (move)
  (declare (optimize (speed 3) (safety 1) (debug 0)))
  (:method ((move remove-pair-move))
    (remover (entry-by-pair (removed-pair move))))
  (:method ((move add-pair-move))
    (adder (entry-by-pair (added-pair move))))
  (:method ((move swap-pair-move))
    (swapper-from-entry (removed-base move)
			(entry-by-pair (added-pair move)))))

to this...

(defun get-tracked-move (move)
  "Rind MOVE in the tracker, and return NIL if move isn't present."
  (declare (optimize (speed 3) (safety 1) (debug 0)))
  (etypecase move
    (swap-pair-move
     (swapper-from-entry (removed-base move) (entry-by-pair
					      (added-pair move))))
    (add-pair-move
     (adder (entry-by-pair (added-pair move))))
    (remove-pair-move
     (remover (entry-by-pair (removed-pair move))))))

The former (according to my profiling) took about 5e-6 sec/call and
consed a few hundred bytes each call; the latter took 1e-6 sec/call or
less, and consed nothing. I haven't tried it with another
implementation yet. In both cases, add-pair-move et al. are CLOS
classes.

Cheers,
Matt
From: Juho Snellman
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <slrnelmeoq.acm.jsnell@sbz-30.cs.Helsinki.FI>
Pillsy <·········@gmail.com> wrote:
> Juho Snellman wrote:
>
>> In many (if not most) implementations generic function dispatch for
>> CLOS instances will be significantly faster than using a typecase.
>
> With SBCL, I got significant speed-ups from that sort of change.

Colour me surprised, if your *-PAIR-MOVE are standard-classes and not
structures. FWIW, here are some test results from several CL
implementations which show the opposite.

        null generic etypecase
clisp   0.53    1.12       1.6
cmucl   0.08    0.20       0.5      
ecl     0.14    1.71      14.4
gcl     0.02    1.06      12.4
sbcl    0.07    0.15       1.5

;; The code

(declaim (optimize speed))

(defclass a () ())
(defclass b () ())
(defclass c () ())
(defclass d () ())

(defgeneric test-generic (object)
  (:method ((object a)) 1)
  (:method ((object b)) 2)
  (:method ((object c)) 3)
  (:method ((object d)) 4))

(defun test-etypecase (object)
  (etypecase object
    (a 1)
    (b 2)
    (c 3)
    (d 4)))

(defun test-null (object)
  (declare (ignore object))
  nil)

(defun run (&optional (iterations (expt 2 22)))
  (let ((objects (list (make-instance 'd)
                       (make-instance 'a)
                       (make-instance 'b)
                       (make-instance 'c))))
    (setf (cdr (last objects)) objects)
    (time
      (dotimes (i iterations)
        (setf objects (cdr objects))
        (test-null (car objects))))
    (time
      (dotimes (i iterations)
        (setf objects (cdr objects))
        (test-generic (car objects))))
    (time
      (dotimes (i iterations)
        (setf objects (cdr objects))
        (test-etypecase (car objects))))))


-- 
Juho Snellman
From: Pillsy
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <1163611322.643012.226240@m7g2000cwm.googlegroups.com>
Juho Snellman wrote:

> Pillsy <·········@gmail.com> wrote:

> > Juho Snellman wrote:

> >> In many (if not most) implementations generic function dispatch for
> >> CLOS instances will be significantly faster than using a typecase.

> > With SBCL, I got significant speed-ups from that sort of change.

> Colour me surprised, if your *-PAIR-MOVE are standard-classes and not
> structures.

I ran your test, and got a similar result.

FWIW, I have no idea what the slow-down is. Certainly, it's very large
compared to the cost of either the etypecase or the method dispatch in
your example (both take ~1e-8 seconds). The other function calls (for
adder, remover and such) are also GFs, and there's multiple inheritance
going on:

(defclass pair-move () [...slots...])

(defclass add-pair-move (pair-move) [...more slots...])

(defclass remove-pair-move (pair-move) [...still more slots...])

(defclass swap-pair-move (remove-pair-move add-pair-move) ())

However, doing a similar test with b and c inheriting from d, and a
inheriting from both b and c, does not substantially change things WRT
to speed. I have a vague sense that the compiler is able to optimize
the typecased version much more aggressively, but I couldn't say
why[1].

Cheers,
Matt

[1] You might say that it was silly to start the thread off with such a
specific question about optimization if I've got so little experience
with it, and if you did say that, you would be right.
From: Raffael Cavallaro
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <2006111511364150878-raffaelcavallaro@pasdespamsilvousplaitmaccom>
On 2006-11-15 11:06:50 -0500, Juho Snellman <······@iki.fi> said:

> 
>         null generic etypecase
> clisp   0.53    1.12       1.6
> cmucl   0.08    0.20       0.5      ecl     0.14    1.71      14.4
> gcl     0.02    1.06      12.4
> sbcl    0.07    0.15       1.5

and true for lispworks on mac intel (core-duo 2.0 GHz):

lwm-intel 0.49    0.65      1.57
From: Pascal Costanza
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <4sbapuFtuv57U1@mid.individual.net>
Pillsy wrote:
> Juho Snellman wrote:
> 
>> In many (if not most) implementations generic function dispatch for
>> CLOS instances will be significantly faster than using a typecase.
> 
> With SBCL, I got significant speed-ups from that sort of change.
> Specifically, when I changed this...
> 
> (defgeneric get-tracked-move (move)
>   (declare (optimize (speed 3) (safety 1) (debug 0)))
>   (:method ((move remove-pair-move))
>     (remover (entry-by-pair (removed-pair move))))
>   (:method ((move add-pair-move))
>     (adder (entry-by-pair (added-pair move))))
>   (:method ((move swap-pair-move))
>     (swapper-from-entry (removed-base move)
> 			(entry-by-pair (added-pair move)))))
> 
> to this...
> 
> (defun get-tracked-move (move)
>   "Rind MOVE in the tracker, and return NIL if move isn't present."
>   (declare (optimize (speed 3) (safety 1) (debug 0)))
>   (etypecase move
>     (swap-pair-move
>      (swapper-from-entry (removed-base move) (entry-by-pair
> 					      (added-pair move))))
>     (add-pair-move
>      (adder (entry-by-pair (added-pair move))))
>     (remove-pair-move
>      (remover (entry-by-pair (removed-pair move))))))
> 
> The former (according to my profiling) took about 5e-6 sec/call and
> consed a few hundred bytes each call; the latter took 1e-6 sec/call or
> less, and consed nothing. I haven't tried it with another
> implementation yet. In both cases, add-pair-move et al. are CLOS
> classes.

It matters how you perform the benchmark. Whenever a generic function is 
called with a specific set of argument types for the first time, it 
creates cache entries, so this probably explains the consing. In the 
long run, a generic function shouldn't cons anymore (unless you change 
its definition on the fly).

In my experience, it also makes a difference whether you say this:

(time
   (loop repeat +number-of-calls+
         do (get-tracked-move)))

or that:

(defun test ()
   (loop repeat +number-of-calls+
         do (get-tracked-move)))

(time (test))

In the latter case, generic function seem to be perform better.

This probably also depends on the concrete generic function, the 
concrete class hierachy, etc. To get a better overall picture, you 
probably need a much more comprehensive suite of benchmarks.

On top of that, even if generic functions are somewhat slower than plain 
functions, they are so close that it most probably doesn't really 
matter. In the general case, only 20% of the code is executed 80% of the 
time (or so). Furthermore, only 20% of the time, the code runs the 
instructions that are necessary for performing function invocations. The 
rest of the time, code actually _does_ something. ;)

Such things are hard to reflect in benchmarks.


Pascal

-- 
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Pillsy
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <1163959214.799657.116080@b28g2000cwb.googlegroups.com>
Pascal Costanza wrote:
> Pillsy wrote:
> > Juho Snellman wrote:
> >
> >> In many (if not most) implementations generic function dispatch for
> >> CLOS instances will be significantly faster than using a typecase.
> >
> > With SBCL, I got significant speed-ups from that sort of change.
> > Specifically, when I changed this...
> >
> > (defgeneric get-tracked-move (move)
> >   (declare (optimize (speed 3) (safety 1) (debug 0)))
> >   (:method ((move remove-pair-move))
> >     (remover (entry-by-pair (removed-pair move))))
> >   (:method ((move add-pair-move))
> >     (adder (entry-by-pair (added-pair move))))
> >   (:method ((move swap-pair-move))
> >     (swapper-from-entry (removed-base move)
> > 			(entry-by-pair (added-pair move)))))
> >
> > to this...
> >
> > (defun get-tracked-move (move)
> >   "Rind MOVE in the tracker, and return NIL if move isn't present."
> >   (declare (optimize (speed 3) (safety 1) (debug 0)))
> >   (etypecase move
> >     (swap-pair-move
> >      (swapper-from-entry (removed-base move) (entry-by-pair
> > 					      (added-pair move))))
> >     (add-pair-move
> >      (adder (entry-by-pair (added-pair move))))
> >     (remove-pair-move
> >      (remover (entry-by-pair (removed-pair move))))))
> >
> > The former (according to my profiling) took about 5e-6 sec/call and
> > consed a few hundred bytes each call; the latter took 1e-6 sec/call or
> > less, and consed nothing. I haven't tried it with another
> > implementation yet. In both cases, add-pair-move et al. are CLOS
> > classes.

> It matters how you perform the benchmark.

Well, I was mostly profiling runs of my simulation with the SBCL
profiler. It wasn't until after I saw the responses here that I
realized (time (loop repeat ... )) might be helpful. :-/

> Whenever a generic function is  called with a specific set of argument
> types for the first time, it creates cache entries, so this probably
> explains the consing. In the  long run, a generic function shouldn't cons
> anymore (unless you change its definition on the fly).

Interesting. What ultimately gave me the best performance[1] was
defining each method body as its own plain function (with optimization
and type declarations), and then having each method of the generic
function call the appropriate plain function. I don't know *why* this
helps at all, though, and it feels like I'm really doing cargo cult
development. It slows things down in other places.

At least its not hard to do it automatically in macros, if I end up
doing a lot of it.

[1] http://paste.lisp.org/display/30223

> On top of that, even if generic functions are somewhat slower than plain
> functions, they are so close that it most probably doesn't really
> matter. In the general case, only 20% of the code is executed 80% of the
> time (or so). Furthermore, only 20% of the time, the code runs the
> instructions that are necessary for performing function invocations. The
> rest of the time, code actually _does_ something. ;)

Yes, this is actually what prompted me to start in on this:
get-tracked-move was far from 80% of the code, but it was taking close
to 80% of the time. Now it isn't any more, but I still have plenty of
other performance bottlenecks to deal with. I think the next big one
has to do with lousy data-structure design on my part, though.

Thanks for the informative posts.

Cheers, 
Matt
From: Pascal Costanza
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <4sc5pbFu86vvU1@mid.individual.net>
Pillsy wrote:
> Pascal Costanza wrote:

>> It matters how you perform the benchmark.
> 
> Well, I was mostly profiling runs of my simulation with the SBCL
> profiler. It wasn't until after I saw the responses here that I
> realized (time (loop repeat ... )) might be helpful. :-/
> 
>> Whenever a generic function is  called with a specific set of argument
>> types for the first time, it creates cache entries, so this probably
>> explains the consing. In the  long run, a generic function shouldn't cons
>> anymore (unless you change its definition on the fly).
> 
> Interesting. What ultimately gave me the best performance[1] was
> defining each method body as its own plain function (with optimization
> and type declarations), and then having each method of the generic
> function call the appropriate plain function. I don't know *why* this
> helps at all, though, and it feels like I'm really doing cargo cult
> development. It slows things down in other places.

OK, since you are using SBCL, what could be happening here is this: The 
CLOS implementation in SBCL is derived from PCL (Portable Common Loops), 
an implementation of CLOS that was used as a testbed for CLOS itself and 
its MOP before and during the specification process. As the name 
suggests, it is implemented in (mostly) portable Common Lisp.

Apparently, PCL tried to implement a number of optimizations of method 
bodies without using the constructs in Common Lisp that are natural for 
doing this, but actually doing (many / some?) things with its own code 
walker. I recall reading somewhere that at least in the case of CMUCL 
and SBCL (which use the same CL compiler), this has counterproductive 
effects because it inhibits, or at least hampers some of their 
optimization strategies.

I am only retelling this from hearsay, so take this with a big bag of 
salt. However, it sounds as if this could indeed explain your observations.


Pascal

-- 
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Ken Tilton
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <kMH6h.21$G15.6@newsfe08.lga>
Pascal Bourguignon wrote:
> "Pillsy" <·········@gmail.com> writes:
> 
> 
>>AIUI, a major reasons that generic functions can not be optimized as
>>aggressively as regular functions is that they have to allow for the
>>possibility of adding methods dynamically at pretty much any time.
>>Thus, presumably getting rid of that ability allow for speed increases.
>>Of course, this isn't something you'd want to do in general, because
>>adding new defmethods later is useful, but is there a way to do it on a
>>GF-by-GF basis?
>>
>>I know that it's not in ANSI CL, but do any of the CL implementations
>>allow a declaration or something equivalent? Or maybe there's a way of
>>automagically converting a GF into a something like defun with a
>>typecase in it?
>>
>>Am I crazy to even want this?
> 
> 
> So you have a function and you have a predetermined set of types?
> 
> Why do you want a generic function? 
> Just use an normal function and typecase!

That (typecase) was slower in one unscientific benchmark I did under ACL.

kt

-- 
Cells: http://common-lisp.net/project/cells/

"I'll say I'm losing my grip, and it feels terrific."
    -- Smiling husband to scowling wife, New Yorker cartoon
From: Wade Humeniuk
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <wpu6h.3689$b07.2391@clgrps13>
Pillsy wrote:
> AIUI, a major reasons that generic functions can not be optimized as
> aggressively as regular functions is that they have to allow for the
> possibility of adding methods dynamically at pretty much any time.
> Thus, presumably getting rid of that ability allow for speed increases.
> Of course, this isn't something you'd want to do in general, because
> adding new defmethods later is useful, but is there a way to do it on a
> GF-by-GF basis?
> 
> I know that it's not in ANSI CL, but do any of the CL implementations
> allow a declaration or something equivalent? Or maybe there's a way of
> automagically converting a GF into a something like defun with a
> typecase in it?
> 

Yes.  LispWorks has that ability for "compress" generics and such during
delivery.  See ...

http://www.lispworks.com/documentation/lw50/DV/html/deluser-103.htm#pgfId-108781
http://www.lispworks.com/documentation/lw50/DV/html/deluser-94.htm#pgfId-91919

Wade
From: rydis (Martin Rydstr|m) @CD.Chalmers.SE
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <w4clkmdo0rn.fsf@rackham.cd.chalmers.se>
"Pillsy" <·········@gmail.com> writes:
> I know that it's not in ANSI CL, but do any of the CL implementations
> allow a declaration or something equivalent? Or maybe there's a way of
> automagically converting a GF into a something like defun with a
> typecase in it?

CMUCL has sealing, at least.
http://common-lisp.net/project/cmucl/doc/cmu-user/extensions.html#toc81

',mr
-- 
rydis (Martin Rydstr�m) @CD.Chalmers.SE             http://www.rydis.se

[Emacs] is written in Lisp, which is the only computer language that is
beautiful.  -- Neal Stephenson, _In the Beginning was the Command Line_
From: Raffael Cavallaro
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <2006111511521337709-raffaelcavallaro@pasdespamsilvousplaitmaccom>
On 2006-11-14 18:37:25 -0500, "Pillsy" <·········@gmail.com> said:

> Am I crazy to even want this?

Not necessarily - this was promoted as one of the selling points of 
Dylan - dynamism where you need it but with the ability to optimize 
dispatch speed via sealing.
From: Pascal Costanza
Subject: Re: Sealed generic functions in CLOS?
Date: 
Message-ID: <4sba43FunkiuU1@mid.individual.net>
Pillsy wrote:
> AIUI, a major reasons that generic functions can not be optimized as
> aggressively as regular functions is that they have to allow for the
> possibility of adding methods dynamically at pretty much any time.
> Thus, presumably getting rid of that ability allow for speed increases.

That's incorrect. The ability to change the methods of a generic 
function doesn't affect their efficiency. The internal protocol for 
changing methods is designed in a way such that after changes have been 
made, a generic function can inspect the methods associated with it and 
then perform ad-hoc optimizations / partial evaluation based on that 
knowledge. Sealing generic function isn't likely to have a substantial 
effect in this regard.

What affects efficiency is the fact that generic functions are typically 
not inlined. Implementations of other programming languages, like Self, 
Smalltalk and Java, show that inlining creates substantial speedups and, 
even more importantly, that inlining doesn't interfere with updates of 
function / method definitions.

Inlining provides substantial speedups because a compiler can analyse 
the call site and, for example, determine that some argument types are 
never passed to a function, or unlikely to be passed. This allows 
reducing the overhead of tests that have to be performed at runtime. 
Inlining doesn't interfere with changes of function / method definitions 
when / because the call site can be recompiled at runtime.

ANSI Common Lisp is specified in a way that inlining of plain functions 
is straightforward in the general case. Unfortunately, CLOS and more 
specifically its MOP are specified in a way that inlining is not 
possible (or not straightforward) in the general case.

See http://people.csail.mit.edu/jrb/Projects/partial-dispatch.htm for an 
approach that combines generic functions with inlineability. It would be 
interesting to redesign CLOS and the CLOS MOP to enable such inlinings, 
but that's probably a lot of work, especially when backwards 
compatibility should be achieved as well.

Still, as a bottom line, sealing is probably not very useful for 
optimization purposes, but only for controlling method (re)definition.


Pascal

-- 
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/