I performed the following test using CMUCL 18d:
(Debian package version 3.1.4, if it makes a difference)
(defgeneric meth1 (o))
(defvar *n* 100)
(time
(dotimes (i *n*)
(let ((xx (intern (format nil "sub~4,'0D" i))))
(eval `(defclass ,xx ()))
(eval `(defmethod meth1 ((o ,xx)) nil)))))
(quit)
This tests the cost of creating many classes, and one specialization of
the function METH1 for each class.
I got the following times:
*n* = 100 --> 6 sec
*n* = 150 --> 19 sec
*n* = 200 --> 43 sec
*n* = 250 --> 78 sec
*n* = 300 --> 136 sec
which means that the execution time is about O(n^3)
(actually O(n^2.8), go figure)
Naturally I ran each test in a fresh lisp process.
To make sure my benchmark wasn't faulty, I ran this other test:
(dotimes (i *n*)
(let ((xx (intern (format nil "sub~4,'0D" i))))
(eval `(defclass ,xx ()))
(eval `(defmethod ,xx ((o ,xx)) nil)))))
That is, create *n* different generic functions. This test ran in 3
seconds for *n*=300, which shows that the expensive operation is creating
a method on a GF that already has many specializations.
I also tested defclass alone, which seems to run close to O(n).
Obviously this has practical implications for an application with many
classes that share a common protocol (let's say each class needs its own
INITIALIZE-INSTANCE, PRINT-OBJECT, you name it): the application's load
time may be prohibitve. Also if methods are to be added dynamically the
runtime performace will suffer.
Has anyone noticed similar effects on other Lisp implementations?
Is there anything I missed? If defmethid is indeed slow, are there
workarounds?
--
Eric Daniel
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
Eric Daniel wrote:
> I performed the following test using CMUCL 18d:
> (Debian package version 3.1.4, if it makes a difference)
>
>
> (defgeneric meth1 (o))
> (defvar *n* 100)
> (time
> (dotimes (i *n*)
> (let ((xx (intern (format nil "sub~4,'0D" i))))
> (eval `(defclass ,xx ()))
> (eval `(defmethod meth1 ((o ,xx)) nil)))))
> (quit)
>
>
> This tests the cost of creating many classes, and one specialization of
> the function METH1 for each class.
>
> I got the following times:
> *n* = 100 --> 6 sec
> *n* = 150 --> 19 sec
> *n* = 200 --> 43 sec
> *n* = 250 --> 78 sec
> *n* = 300 --> 136 sec
>
> which means that the execution time is about O(n^3)
> (actually O(n^2.8), go figure)
> Naturally I ran each test in a fresh lisp process.
>
> To make sure my benchmark wasn't faulty...
I am not saying your benchmark is wrong, but are you sure this
artificial way of generating many methods on the same GF works the same
as loading compiled FASLs which happen to contain as many methods? Or
are you anticipating in fact defining classes and methods at run-time?
If not the later, could you write the eval'ed code out to a .LISP file,
compile and load it? Then I would start to trust the benchmark.
Back to the peanut gallery, I otherwise have no knowledge of CMUCL and I
happen never to have defined many dozens of methods on the same GF.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Everything is a cell." -- Alan Kay
In article <··············@nyc.rr.com>, Kenny Tilton wrote:
>
>
> Eric Daniel wrote:
> > I performed the following test using CMUCL 18d:
> > (Debian package version 3.1.4, if it makes a difference)
> >
> >
> > (defgeneric meth1 (o))
> > (defvar *n* 100)
> > (time
> > (dotimes (i *n*)
> > (let ((xx (intern (format nil "sub~4,'0D" i))))
> > (eval `(defclass ,xx ()))
> > (eval `(defmethod meth1 ((o ,xx)) nil)))))
> > (quit)
> >
> >
> > This tests the cost of creating many classes, and one specialization of
> > the function METH1 for each class.
> >
> > I got the following times:
> > *n* = 100 --> 6 sec
> > *n* = 150 --> 19 sec
> > *n* = 200 --> 43 sec
> > *n* = 250 --> 78 sec
> > *n* = 300 --> 136 sec
> >
> > which means that the execution time is about O(n^3)
> > (actually O(n^2.8), go figure)
> > Naturally I ran each test in a fresh lisp process.
> >
> > To make sure my benchmark wasn't faulty...
>
> I am not saying your benchmark is wrong, but are you sure this
> artificial way of generating many methods on the same GF works the same
> as loading compiled FASLs which happen to contain as many methods? Or
> are you anticipating in fact defining classes and methods at run-time?
As far as defining methods at run time, I don't know yet, this is why
I ran this benchmark, to see it it was feasible.
> If not the later, could you write the eval'ed code out to a .LISP file,
> compile and load it? Then I would start to trust the benchmark.
I forgot to mention it. Yes, I did compile and load a file
of the form:
(defclass sub0001 () ()) (defmethod meth1 ((o sub0001)) nil)
(defclass sub0002 () ()) (defmethod meth1 ((o sub0002)) nil)
(defclass sub0003 () ()) (defmethod meth1 ((o sub0003)) nil)
(defclass sub0004 () ()) (defmethod meth1 ((o sub0004)) nil)
....
Same results. The load times are the same whether I load the source
file or the FASL. I also tried to dump a lisp image with 200 methods
on METH1, and loading that. The new image loads fine, but defining more
methods on METH1 after that is still slow.
> Back to the peanut gallery, I otherwise have no knowledge of CMUCL and I
> happen never to have defined many dozens of methods on the same GF.
I'm sure most people haven't, it's a lot of typing :-)
Here's what I am up to by the way. I'm trying to prove that Common Lisp,
and CLOS in particular, are ideal for writing MUDs. Modern MUDs typically
implement their own language, that vaguely resembles a prototype-based
C++, if you can picture that. But CLOS is perfect to demonstrate the
usefulness of multiple dispatch, multiple inheritance, changing an
object's class at runtime, etc. Now the trick is to find a good mapping
between game objects and CLOS objects. One possibility is one CLOS class
per game object (because typically each game object has unique
properties). But if I can't expect more than 200-300 methods per generic
function I will look for another mapping, or somehow limit the number of
methods.
Anyway now I'm curious, and I would appreciate if people who have access
to other implementations could run my benchmark.
--
Eric Daniel
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
Eric Daniel wrote:
> Here's what I am up to by the way. I'm trying to prove that Common Lisp,
> and CLOS in particular, are ideal for writing MUDs. Modern MUDs typically
> implement their own language, that vaguely resembles a prototype-based
> C++, if you can picture that. But CLOS is perfect to demonstrate the
> usefulness of multiple dispatch, multiple inheritance, changing an
> object's class at runtime, etc. Now the trick is to find a good mapping
> between game objects and CLOS objects. One possibility is one CLOS class
> per game object (because typically each game object has unique
> properties). But if I can't expect more than 200-300 methods per generic
> function I will look for another mapping, or somehow limit the number of
> methods.
Whoa, major coincidence: I happen to have a little project called Cells
that can be looked at from one standpoint as supporting
instance-oriented programming, by which I mean multiple instances of the
same class can be given different behaviors via custom rules (closures)
as definers of a slot's value. I wager this will tax CMUCL a lot less
(but it's just a wager).
What you would be doing is saying that the outcome currently decided by
a method specialized on a brand new class would be expressed as a slot
value, itself the returned value of an instance-specific function on the
instance. This is feasible simply by having the rule itself find the
information passed to it in its method incarnation by searching global
state space for the same information. This turns out to be easy to
arrange. And slots are "active" in that an echo function can be supplied
for a slot which will get kicked off any time the slot changes value.
The downside is that it is hard to be "a little bit" Cell-ish, so you
would really be committing to the dataflow model Cells support. But it's
a good model. See some stuff at the url below for more details, or email
me. I happen also to be developing a universal (ha!) CL Gui built atop
Cells, and that will use OpenGL for imaging, so a MUD would be that
much more approachable.
You might be able to offer a prototype as your proof. :)
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Everything is a cell." -- Alan Kay
Eric Daniel <···········@barberic.vancouver.wa.us> writes:
>
> I got the following times:
> *n* = 100 --> 6 sec
> *n* = 150 --> 19 sec
> *n* = 200 --> 43 sec
> *n* = 250 --> 78 sec
> *n* = 300 --> 136 sec
With CLISP or emacs, it's much faster than with SBCL or CMUCL (these
later have to compile the methods!):
[······@thalassa tmp]$ ./defmethod-benchmark
CLISP 100
Real time: 0.111309 sec.
Run time: 0.09 sec.
Space: 610764 Bytes
GC: 1, GC time: 0.03 sec.
CLISP 150
Real time: 0.17243 sec.
Run time: 0.13 sec.
Space: 916568 Bytes
GC: 1, GC time: 0.03 sec.
CLISP 200
Real time: 0.393314 sec.
Run time: 0.26 sec.
Space: 1222604 Bytes
GC: 2, GC time: 0.07 sec.
CLISP 250
Real time: 0.36639 sec.
Run time: 0.28 sec.
Space: 1528100 Bytes
GC: 2, GC time: 0.07 sec.
CLISP 300
Real time: 0.516122 sec.
Run time: 0.35 sec.
Space: 1835300 Bytes
GC: 2, GC time: 0.06 sec.
EMACS 100
Took 0.103771 seconds.
EMACS 150
Took 0.171461 seconds.
EMACS 200
Took 0.347938 seconds.
EMACS 250
Took 0.491594 seconds.
EMACS 300
Took 0.552917 seconds.
SBCL 100
Evaluation took:
8.453 seconds of real time
5.95 seconds of user run time
0.24 seconds of system run time
[Run times include 0.91 seconds GC run time.]
777 page faults and
79880048 bytes consed.
SBCL 150
Evaluation took:
15.699 seconds of real time
11.27 seconds of user run time
0.26 seconds of system run time
[Run times include 1.72 seconds GC run time.]
782 page faults and
162776232 bytes consed.
SBCL 200
Evaluation took:
27.865 seconds of real time
19.85 seconds of user run time
0.51 seconds of system run time
[Run times include 3.51 seconds GC run time.]
784 page faults and
296258960 bytes consed.
SBCL 250
Evaluation took:
44.72 seconds of real time
31.99 seconds of user run time
1.1 seconds of system run time
[Run times include 6.05 seconds GC run time.]
786 page faults and
497448968 bytes consed.
SBCL 300
Evaluation took:
70.279 seconds of real time
50.08 seconds of user run time
1.56 seconds of system run time
[Run times include 10.25 seconds GC run time.]
786 page faults and
781804312 bytes consed.
------------------------------------------------------------------------
#!/bin/bash
for n in 100 150 200 250 300 ; do
echo ''
echo -n CLISP $n
clisp -q -norc -x "(progn
(defgeneric meth1 (o))
(defvar *n* $n)
(time
(dotimes (i *n*)
(let ((xx (intern (format nil \"sub~4,'0D\" i))))
(eval \`(defclass ,xx () ()))
(eval \`(defmethod meth1 ((o ,xx)) nil)))))
(quit))
"
done
for n in 100 150 200 250 300 ; do
echo ''
echo EMACS $n
emacs -no-site-file -q -batch -eval "(progn (require 'eieio)
(defun emacs-time-to-seconds (et)
(+ (let ((h (nth 0 et))) (if (< h 1024) (* h 65536) (* h 65536.0)))
(nth 1 et)
(let ((us (nth 2 et))) (if (= 0 us) 0 (/ us 1000000.0)))))
(defmacro time (&rest body)
\`(let* ( (start (current-time))
(result (progn ,@body))
(stop (current-time)) )
(message \"Took %f seconds.\" (- (emacs-time-to-seconds stop)
(emacs-time-to-seconds start))) ))
(defgeneric meth1 (o))
(defvar *n* $n)
(time
(dotimes (i *n*)
(let ((xx (intern (format \"sub%04d\" i))))
(eval \`(defclass ,xx () ()))
(eval \`(defmethod meth1 ((o ,xx)) nil)))))
(kill-emacs))
"
done
for n in 100 150 200 250 300 ; do
echo ''
echo SBCL $n
sbcl --noinform --sysinit /dev/null --userinit /dev/null --eval "(progn
(defgeneric meth1 (o))
(defvar *n* $n)
(time
(dotimes (i *n*)
(let ((xx (intern (format nil \"sub~4,'0D\" i))))
(eval \`(defclass ,xx () ()))
(eval \`(defmethod meth1 ((o ,xx)) nil)))))
(quit))
"
done
#### defmethod-benchmark -- 2003-05-19 01:57:58 -- pascal ####
------------------------------------------------------------------------
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.
In article <··············@thalassa.informatimago.com>, Pascal Bourguignon wrote:
> Eric Daniel <···········@barberic.vancouver.wa.us> writes:
> >
> > I got the following times:
> > *n* = 100 --> 6 sec
> > *n* = 150 --> 19 sec
> > *n* = 200 --> 43 sec
> > *n* = 250 --> 78 sec
> > *n* = 300 --> 136 sec
>
> With CLISP or emacs, it's much faster than with SBCL or CMUCL (these
> later have to compile the methods!):
>
also from what I read these don't implement the MOP, which is where
all the complexity is
>
>
>
> [······@thalassa tmp]$ ./defmethod-benchmark
>
> CLISP 100
> Real time: 0.111309 sec.
> Run time: 0.09 sec.
> Space: 610764 Bytes
[...]
Thank you to all who replied. It seems that it is a PCL-only issue.
I better take this to the CMUCL mailing list, if I think I can contribute
some improvements. Otherwise I'll just live with it.
--
Eric Daniel
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
In article <··········@corp.newsgroups.com>,
Eric Daniel <···········@barberic.vancouver.wa.us> wrote:
> I performed the following test using CMUCL 18d:
> (Debian package version 3.1.4, if it makes a difference)
>
>
> (defgeneric meth1 (o))
> (defvar *n* 100)
> (time
> (dotimes (i *n*)
> (let ((xx (intern (format nil "sub~4,'0D" i))))
> (eval `(defclass ,xx ()))
> (eval `(defmethod meth1 ((o ,xx)) nil)))))
> (quit)
>
>
> This tests the cost of creating many classes, and one specialization of
> the function METH1 for each class.
>
> I got the following times:
> *n* = 100 --> 6 sec
> *n* = 150 --> 19 sec
> *n* = 200 --> 43 sec
> *n* = 250 --> 78 sec
> *n* = 300 --> 136 sec
>
> which means that the execution time is about O(n^3)
> (actually O(n^2.8), go figure)
> Naturally I ran each test in a fresh lisp process.
>
> To make sure my benchmark wasn't faulty, I ran this other test:
>
> (dotimes (i *n*)
> (let ((xx (intern (format nil "sub~4,'0D" i))))
> (eval `(defclass ,xx ()))
> (eval `(defmethod ,xx ((o ,xx)) nil)))))
>
> That is, create *n* different generic functions. This test ran in 3
> seconds for *n*=300, which shows that the expensive operation is creating
> a method on a GF that already has many specializations.
>
> I also tested defclass alone, which seems to run close to O(n).
>
> Obviously this has practical implications for an application with many
> classes that share a common protocol (let's say each class needs its own
> INITIALIZE-INSTANCE, PRINT-OBJECT, you name it): the application's load
> time may be prohibitve. Also if methods are to be added dynamically the
> runtime performace will suffer.
>
> Has anyone noticed similar effects on other Lisp implementations?
> Is there anything I missed? If defmethid is indeed slow, are there
> workarounds?
MCL and LispWorks are much faster in this case. LispWorks
needs on my Laptop 0.5 seconds for *n* = 300.
>>>>> "ed" == Eric Daniel <···········@barberic.vancouver.wa.us> writes:
ed> Obviously this has practical implications for an application
ed> with many classes that share a common protocol (let's say each
ed> class needs its own INITIALIZE-INSTANCE, PRINT-OBJECT, you name
ed> it): the application's load time may be prohibitve. Also if
ed> methods are to be added dynamically the runtime performace will
ed> suffer.
the PCL implementation of CLOS used in CMUCL does quite a lot of work
when a class or a method is defined: it compiles quite a lot of code
for each class/method, and attempts to generate optimized constructors
and accessors etc. If you benchmark very simple DEFXXX code against
other implementations that do less analysis, you may find PCL to be
slower. On more realistic uses of CLOS, however, you will find PCL's
performance to be quite good (and much better in future versions of
CMUCL, thanks to great work by Gerd Moellman).
If your class hierarchy and methods are known at compile-time (which
is often the case), PCL is able to do all this work at compile time; your
compiled code should load very quickly. You can achieve this by adding
a form
#+pcl (pcl::precompile-random-code-segments)
at the top level of the source file.
--
Eric Marsden <URL:http://www.laas.fr/~emarsden/>
In article <···············@melbourne.laas.fr>, Eric Marsden wrote:
> >>>>> "ed" == Eric Daniel <···········@barberic.vancouver.wa.us> writes:
>
> ed> Obviously this has practical implications for an application
> ed> with many classes that share a common protocol (let's say each
> ed> class needs its own INITIALIZE-INSTANCE, PRINT-OBJECT, you name
> ed> it): the application's load time may be prohibitve. Also if
> ed> methods are to be added dynamically the runtime performace will
> ed> suffer.
>
> the PCL implementation of CLOS used in CMUCL does quite a lot of work
> when a class or a method is defined: it compiles quite a lot of code
> for each class/method, and attempts to generate optimized constructors
> and accessors etc. If you benchmark very simple DEFXXX code against
> other implementations that do less analysis, you may find PCL to be
> slower. On more realistic uses of CLOS, however, you will find PCL's
> performance to be quite good (and much better in future versions of
> CMUCL, thanks to great work by Gerd Moellman).
>
> If your class hierarchy and methods are known at compile-time (which
> is often the case), PCL is able to do all this work at compile time; your
> compiled code should load very quickly. You can achieve this by adding
> a form
>
> #+pcl (pcl::precompile-random-code-segments)
>
> at the top level of the source file.
>
Thanks for the information, I will try that
By the way If you look at Pascal Bourguignon's result for SBCL, you will
see that defmethod seems to take O(n) time, if n is the number of methods
already defined. In my tests with CMUCL it takes O(n^2) time. I know that
SBCL is derived from CMUCL, but how far apart are their respective PCL
implementations? Maybe some O(n^2) operation was recently introduced in
CMUCL's implementation?
--
Eric Daniel
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
>>>>> "ed" == Eric Daniel <···········@barberic.vancouver.wa.us> writes:
ed> By the way If you look at Pascal Bourguignon's result for SBCL,
ed> you will see that defmethod seems to take O(n) time, if n is the
ed> number of methods already defined. In my tests with CMUCL it
ed> takes O(n^2) time. I know that SBCL is derived from CMUCL, but
ed> how far apart are their respective PCL implementations? Maybe
ed> some O(n^2) operation was recently introduced in CMUCL's
ed> implementation?
that depends considerably on the versions that you are comparing.
CMUCL 18d had a mostly-"classic" PCL implementation, that was largely
similar to the 1992 PCL release from Xerox. CMUCL 18e introduced a
large number of performance improvements and ANSI-compliance fixes in
the PCL code. Further performance improvements (including work on
declaring classes to be sealed, which allows slot access to be as fast
as for structures), and more ANSI and AMOP compliance fixes, are in
the current CMUCL CVS, which will eventually be released as 19a.
The SBCL developers have been pulling in changes from CMUCL to their
version of PCL, as well as doing independent work. SBCL has more
frequent releases than CMUCL, so expect behaviour somewhere along the
18d -> 18e -> 19a CMUCL-epochs.
I don't have any specific information on O(n�) operations in PCL,
sorry.
--
Eric Marsden <URL:http://www.laas.fr/~emarsden/>
Eric Marsden <········@laas.fr> writes:
> Further performance improvements (including work on
> declaring classes to be sealed, which allows slot access to be as fast
> as for structures) ...
Is there some discussion group that I can get in on for this? I view
sealing as the most major contribution from Dylan, and CL needs at least
breakable seals, but we should add this extension as carefully as possible.
It would be a shame to add such an important feature to various CLs only to
find that it interacts poorly with the MOP implementation in one of them...
How can I find concepts and get in on conversations about the sealing
work the CMUCL team has done? Doc urls anywhere, etc?
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
>>>>> "Duane" == Duane Rettig <·····@franz.com> writes:
Duane> Eric Marsden <········@laas.fr> writes:
>> Further performance improvements (including work on
>> declaring classes to be sealed, which allows slot access to be as fast
>> as for structures) ...
Duane> Is there some discussion group that I can get in on for this? I view
Duane> sealing as the most major contribution from Dylan, and CL needs at least
Duane> breakable seals, but we should add this extension as carefully as possible.
Duane> It would be a shame to add such an important feature to various CLs only to
Duane> find that it interacts poorly with the MOP implementation in one of them...
Duane> How can I find concepts and get in on conversations about the sealing
Duane> work the CMUCL team has done? Doc urls anywhere, etc?
I don't think there's a whole lot done on sealing yet, but the
discussions, if any[1], are on the cmucl-imp and/or sbcl-devel mailing
lists. These are also available from gmane.org. (Sorry, I don't have
the links to gmane.org here.)
Footnotes:
[1] Most of the work is being done by Gerd Moellmann by himself, I
think.
Duane Rettig <·····@franz.com> writes:
> How can I find concepts and get in on conversations about the sealing
> work the CMUCL team has done? Doc urls anywhere, etc?
Try asking on the cmucl-imp mailling list. I'm sure someone on there
would know if they've been doing any work with that.
--
burton samograd
······@kruhft.dyndns.org
http://kruhftwerk.dyndns.org
Duane Rettig <·····@franz.com> writes:
> How can I find concepts and get in on conversations about the sealing
> work the CMUCL team has done? Doc urls anywhere, etc?
You could check out CMUCL from CVS (see www.cons.org); documentation
is in src/docs/cmu-user/extensions.tex. I can send you that file via
email, if you like.
The mentioned performance improvement, which I'm calling "inline"
access is completely orthogonal to sealing. It's controlled by
declarations and doesn't require anything from MOP. (Another
declaration that's interesting in this context is EXT:AUTO-COMPILE,
for automatically re-compiling methods using inline slot access
when classes change.)