Hi,
In a parser project, I was using a class (with a slot for an INPUT
string and another two slots for CURSOR and SIZE variables) to store
parsing state information between calls of parsing routines. (There
are nearly 20-30 functions and they get called upon 700-800 times for
each document.) But the problem was, it took nearly 150-170 seconds to
parse a document for a hundred times. And after replacing related
class with a struct (with INPUT and SIZE slots marked as read-only)
the runtime dropped to 5-6 seconds. (Using SBCL 1.0.6)
I love working with classes and taking advantage of their flexibility
and abstraction. But after this experience, it made me wonder the
reason of related performance impact. (It even made me think that if
classes are getting copied upon every call!) What would you recommend
in such scenarios? What are the known performance deficiencies of
classes? In which particular scenarios someone should avoid using
them?
Actually, AFAIK, same situation applies to generic functions as well,
right? (Because of their dispatching costs.) I'd be appreciated to
hear comments about this too.
Regards.
vy wrote:
> Hi,
>
> In a parser project, I was using a class (with a slot for an INPUT
> string and another two slots for CURSOR and SIZE variables) to store
> parsing state information between calls of parsing routines. (There
> are nearly 20-30 functions and they get called upon 700-800 times for
> each document.) But the problem was, it took nearly 150-170 seconds to
> parse a document for a hundred times. And after replacing related
> class with a struct (with INPUT and SIZE slots marked as read-only)
> the runtime dropped to 5-6 seconds. (Using SBCL 1.0.6)
Could you show us your class and struct definitions for comparison? How
did you access the slots, via slot-value or via accessors?
> I love working with classes and taking advantage of their flexibility
> and abstraction. But after this experience, it made me wonder the
> reason of related performance impact. (It even made me think that if
> classes are getting copied upon every call!) What would you recommend
> in such scenarios? What are the known performance deficiencies of
> classes? In which particular scenarios someone should avoid using
> them?
Classes provide a lot of flexibility. For example, their definitions can
be changed at runtime and this will be reflected in all existing
instances of such changed classes. Such flexibility naturally comes at a
cost. However, the difference between classes and structs seems to be
too steep in your case, so my guess would be that something else is
going wrong here.
> Actually, AFAIK, same situation applies to generic functions as well,
> right? (Because of their dispatching costs.) I'd be appreciated to
> hear comments about this too.
Generic functions are typically quite efficient and the dispatch they
perform is not slower than what you would otherwise implement manually
(cond, case, typecase, etc.). Plain functions can be tweaked in more
fine-grained ways, for example by inlining them. That should matter only
for bottlenocks, though.
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/
On Jul 20, 1:50 am, Pascal Costanza <····@p-cos.net> wrote:
> Could you show us your class and struct definitions for comparison?
(defclass parser-context ()
((data
:initarg :data
:accessor parser-context-data
:documentation "Input data getting parsed.")
(size
:initarg :size
:accessor parser-context-size
:documentation "Size of the input data.")
(cursor
:initarg :cursor
:accessor parser-context-cursor
:documentation "Current location on the input data.")
(checkpoints
:accessor parser-context-checkpoints
:documentation "Reversed list of declared checkpoints.")
(attachment
:initarg :attachment
:accessor parser-context-attachment
:documentation "Attachment to carry with to parser context
object."))
(:documentation "Information about current state of the parsing
process."))
(defstruct parser-context
(data nil :read-only t :type string)
(size nil :read-only t :type unsigned-byte)
(cursor 0 :type unsigned-byte)
(checkpoints
(make-array 8 :element-type 'unsigned-byte :adjustable t :fill-
pointer 0)
:type (vector unsigned-byte *))
attachment)
> How did you access the slots, via slot-value or via accessors?
Via accessors. For instance, in the above case should I have memoized
PARSER-CONTEXT-DATA and PARSER-CONTEXT-SIZE accessors? Might this make
any difference?
> Generic functions are typically quite efficient and the dispatch they
> perform is not slower than what you would otherwise implement manually
> (cond, case, typecase, etc.). Plain functions can be tweaked in more
> fine-grained ways, for example by inlining them. That should matter only
> for bottlenocks, though.
In irc.freenode.org, #lisp channel warned me exactly the same way. I
was trying to inline PEEK-ATOM/READ-ATOM methods (similar to PEEK-CHAR/
READ-CHAR, except former ones operate on strings). And learned that
it's not possible to inline generic methods. (At least, AFAIK, SBCL
doesn't support this yet.)
Regards.
vy wrote:
> On Jul 20, 1:50 am, Pascal Costanza <····@p-cos.net> wrote:
>> Could you show us your class and struct definitions for comparison?
>
> (defclass parser-context ()
> ((data
> :initarg :data
> :accessor parser-context-data
> :documentation "Input data getting parsed.")
> (size
> :initarg :size
> :accessor parser-context-size
> :documentation "Size of the input data.")
> (cursor
> :initarg :cursor
> :accessor parser-context-cursor
> :documentation "Current location on the input data.")
> (checkpoints
> :accessor parser-context-checkpoints
> :documentation "Reversed list of declared checkpoints.")
> (attachment
> :initarg :attachment
> :accessor parser-context-attachment
> :documentation "Attachment to carry with to parser context
> object."))
> (:documentation "Information about current state of the parsing
> process."))
>
> (defstruct parser-context
> (data nil :read-only t :type string)
> (size nil :read-only t :type unsigned-byte)
> (cursor 0 :type unsigned-byte)
> (checkpoints
> (make-array 8 :element-type 'unsigned-byte :adjustable t :fill-
> pointer 0)
> :type (vector unsigned-byte *))
> attachment)
This looks reasonable. The type declarations in the defstruct probably
also buy you some efficiency gain, especially those for size and cursor.
(I am not aware of a CLOS implementation that takes advantage of type
declarations in a similar way.)
I still find the difference too extreme. Are there any metaclasses
defined somewhere in the rest of your program? Maybe they don't
specialize slot-value-using-class correctly. But that's just a wild guess...
>> How did you access the slots, via slot-value or via accessors?
>
> Via accessors. For instance, in the above case should I have memoized
> PARSER-CONTEXT-DATA and PARSER-CONTEXT-SIZE accessors? Might this make
> any difference?
Accessors have a better chance of getting optimized than access via
slot-value. So this looks ok as well.
One option could be to check against CMUCL. It provides ways to tweak
slot-value access. For example, you can specify that a slot is never
unbound, which allows CMUCL to optimize away the check for unboundness.
>> Generic functions are typically quite efficient and the dispatch they
>> perform is not slower than what you would otherwise implement manually
>> (cond, case, typecase, etc.). Plain functions can be tweaked in more
>> fine-grained ways, for example by inlining them. That should matter only
>> for bottlenocks, though.
>
> In irc.freenode.org, #lisp channel warned me exactly the same way. I
> was trying to inline PEEK-ATOM/READ-ATOM methods (similar to PEEK-CHAR/
> READ-CHAR, except former ones operate on strings). And learned that
> it's not possible to inline generic methods. (At least, AFAIK, SBCL
> doesn't support this yet.)
[Sidenote: There is no such thing as a generic method. There are generic
functions and methods.]
There is a conceptual barrier that makes inlining generic functions
hard: In CLOS, you can add and remove methods to and from generic
functions at runtime. So in the general case, the best you can hope for
with current compilation approaches in the Lisp world is that the method
dispatch is inlined, but not the methods themselves. However, inlining
the method dispatch also has the disadvantage that certain optimizations
of method dispatch are not possible anymore. For example, when a generic
function contains only very few methods, it can perform a much better
dispatch than if there are a lot of methods. An inlined method dispatch
would have to assume the general case.
A dynamic compilation approach, like in Self, Strongtalk or Java, would
enable much more interesting inlining of generic functions, but
unfortunately, such optimization techniques have not been explored
enough in the Lisp world yet.
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/
On Jul 20, 3:31 pm, Pascal Costanza <····@p-cos.net> wrote:
> This looks reasonable. The type declarations in the defstruct probably
> also buy you some efficiency gain, especially those for size and cursor.
I think so. Before I replaced the class with struct, (proclaim
(optimize speed)) dumps lots of warnings about cannot be optimized
GENERIC-+ (or GENERIC--) operations due to type uncertainty.
> I still find the difference too extreme. Are there any metaclasses
> defined somewhere in the rest of your program? Maybe they don't
> specialize slot-value-using-class correctly. But that's just a wild guess...
No, there isn't any other metaclasses except T.
> One option could be to check against CMUCL. It provides ways to tweak
> slot-value access. For example, you can specify that a slot is never
> unbound, which allows CMUCL to optimize away the check for unboundness.
I'll try that.
> There is a conceptual barrier that makes inlining generic functions
> hard: In CLOS, you can add and remove methods to and from generic
> functions at runtime. So in the general case, the best you can hope for
> with current compilation approaches in the Lisp world is that the method
> dispatch is inlined, but not the methods themselves. However, inlining
> the method dispatch also has the disadvantage that certain optimizations
> of method dispatch are not possible anymore. For example, when a generic
> function contains only very few methods, it can perform a much better
> dispatch than if there are a lot of methods. An inlined method dispatch
> would have to assume the general case.
>
> A dynamic compilation approach, like in Self, Strongtalk or Java, would
> enable much more interesting inlining of generic functions, but
> unfortunately, such optimization techniques have not been explored
> enough in the Lisp world yet.
Hrm... I didn't know that.
/me warps to wikipedia to check these concepts.
Regards.
In article <···············@mid.individual.net>,
Pascal Costanza <··@p-cos.net> wrote:
> vy wrote:
> > On Jul 20, 1:50 am, Pascal Costanza <····@p-cos.net> wrote:
> >> Could you show us your class and struct definitions for comparison?
> >
> > (defclass parser-context ()
> > ((data
> > :initarg :data
> > :accessor parser-context-data
> > :documentation "Input data getting parsed.")
> > (size
> > :initarg :size
> > :accessor parser-context-size
> > :documentation "Size of the input data.")
> > (cursor
> > :initarg :cursor
> > :accessor parser-context-cursor
> > :documentation "Current location on the input data.")
> > (checkpoints
> > :accessor parser-context-checkpoints
> > :documentation "Reversed list of declared checkpoints.")
> > (attachment
> > :initarg :attachment
> > :accessor parser-context-attachment
> > :documentation "Attachment to carry with to parser context
> > object."))
> > (:documentation "Information about current state of the parsing
> > process."))
> >
> > (defstruct parser-context
> > (data nil :read-only t :type string)
> > (size nil :read-only t :type unsigned-byte)
> > (cursor 0 :type unsigned-byte)
> > (checkpoints
> > (make-array 8 :element-type 'unsigned-byte :adjustable t :fill-
> > pointer 0)
> > :type (vector unsigned-byte *))
> > attachment)
>
> This looks reasonable. The type declarations in the defstruct probably
> also buy you some efficiency gain, especially those for size and cursor.
> (I am not aware of a CLOS implementation that takes advantage of type
> declarations in a similar way.)
The efficiency might be in memory, but not in speed.
...
> There is a conceptual barrier that makes inlining generic functions
> hard: In CLOS, you can add and remove methods to and from generic
> functions at runtime. So in the general case, the best you can hope for
> with current compilation approaches in the Lisp world is that the method
> dispatch is inlined, but not the methods themselves. However, inlining
> the method dispatch also has the disadvantage that certain optimizations
> of method dispatch are not possible anymore. For example, when a generic
> function contains only very few methods, it can perform a much better
> dispatch than if there are a lot of methods. An inlined method dispatch
> would have to assume the general case.
Delivery options might allow you to get some speed back. Like
in Dylan where you can 'seal' things. This is non-portable,
but I think there was at least implementation which
allows things like that.
> A dynamic compilation approach, like in Self, Strongtalk or Java, would
> enable much more interesting inlining of generic functions, but
> unfortunately, such optimization techniques have not been explored
> enough in the Lisp world yet.
>
>
> Pascal
--
http://lispm.dyndns.org
From: Jeronimo Pellegrini
Subject: Re: Struct vs. Class Performance
Date:
Message-ID: <f7q122$vd4$1@aioe.org>
Hi Pascal,
On 2007-07-19, Pascal Costanza <··@p-cos.net> wrote:
> Generic functions are typically quite efficient and the dispatch they
> perform is not slower than what you would otherwise implement manually
> (cond, case, typecase, etc.). Plain functions can be tweaked in more
> fine-grained ways, for example by inlining them. That should matter only
> for bottlenocks, though.
After asking some questions about CLOS and structures, I went up and did
some tests, and it seems like using methods and classes does slow down
things, at least on SBCL and CLisp.
But I'm not sure this is a good test. It's just something I came up with
quickly. I am also no sure about the semantics of using a method on a
structure :-)
Here's the test:
(defstruct (thing-st (:conc-name th-))
name
(value 0))
(defclass thing-cl ()
((name)
(value :initform 0)))
(defun fun-inc-value-class (thing val)
(with-slots (value) thing
(setf value (+ value val))))
(defmethod met-inc-value-class (thing val)
(with-slots (value) thing
(setf value (+ value val))))
(defun fun-sum-value-class (thing sum)
(with-slots (value) thing
(setf sum (+ sum value))))
(defmethod met-sum-value-class (thing sum)
(with-slots (value) thing
(setf sum (+ sum value))))
(defun fun-inc-value-struc (thing val)
(setf (th-value thing) (+ val (th-value thing))))
(defmethod met-inc-value-struc (thing val)
(setf (th-value thing) (+ val (th-value thing))))
(defun fun-sum-value-struc (thing sum)
(setf sum (+ sum (th-value thing))))
(defmethod met-sum-value-struc (thing sum)
(setf sum (+ sum (th-value thing))))
(compile 'fun-inc-value-class)
(compile 'met-inc-value-class)
(compile 'fun-inc-value-struc)
(compile 'met-inc-value-struc)
(defun test (iter)
(let ((obj (make-instance 'thing-cl)))
(print "Function on class")
(time (dotimes (i iter)
(fun-inc-value-class obj 15.101)))
(print "Method on class")
(time (dotimes (i iter)
(met-inc-value-class obj 15.101))))
(let ((obj (make-thing-st)))
(print "Function on structure")
(time (dotimes (i iter)
(fun-inc-value-struc obj 15.101)))
(print "Method on structure")
(time (dotimes (i iter)
(met-inc-value-struc obj 15.101)))))
J.
From: Jeronimo Pellegrini
Subject: Re: Struct vs. Class Performance
Date:
Message-ID: <f7q2nq$5cp$1@aioe.org>
On 2007-07-20, Jeronimo Pellegrini <···@aleph0.info> wrote:
> (defun fun-sum-value-class (thing sum)
> (with-slots (value) thing
> (setf sum (+ sum value))))
> (defmethod met-sum-value-class (thing sum)
> (with-slots (value) thing
> (setf sum (+ sum value))))
>
> (defun fun-sum-value-struc (thing sum)
> (setf sum (+ sum (th-value thing))))
> (defmethod met-sum-value-struc (thing sum)
> (setf sum (+ sum (th-value thing))))
Ah -- the fun-sum-* and met-sum-* stuff isn't used anywhere.
Those are leftover from a previous attempt (sorry!).
J.
Jeronimo Pellegrini wrote:
> Hi Pascal,
>
> On 2007-07-19, Pascal Costanza <··@p-cos.net> wrote:
>> Generic functions are typically quite efficient and the dispatch they
>> perform is not slower than what you would otherwise implement manually
>> (cond, case, typecase, etc.). Plain functions can be tweaked in more
>> fine-grained ways, for example by inlining them. That should matter only
>> for bottlenocks, though.
>
> After asking some questions about CLOS and structures, I went up and did
> some tests, and it seems like using methods and classes does slow down
> things, at least on SBCL and CLisp.
I am not surprised about CLisp here, but I would assume that SBCL can do
much better. In your code, I would try to (a) replace with-slots with
accessors and (b) declare the types of variables containing objects of
your test classes.
Also make sure that your test function is compiled as well.
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/