Hi *,
I have written an interpreter for my little esoteric toy language[0].
Using SBCL on GNU/Linux the naive common lisp implementation is
reasonable fast with one big exception:
I'm using an (two dimensional) array which in some cases has to be
dynamically extended. Here is the relevant code:
(defparameter *code/data* (make-array '(40 80)
:element-type '(signed-byte 32)
:adjustable t)
"The two dimensional code/data array, as described in the spec.")
[...]
(defun grow-code/data-array ()
"Grow code/data array by 40 rows."
(setf *code/data*
(adjust-array *code/data*
(list (+ (array-dimension *code/data* 0)
40)
80)
:element-type '(signed-byte 32))))
If it is used my interpreter nearly spends all its time[1] in
grow-code/data-array with each call taking about 0.05 seconds[2].
Interestingly enough: if i grow the array by bigger chunks (say 400
rows) it takes nearly the same time, so this is a lame way to speed
things up but I think its the wrong way to go.
In the C implementation I'm using realloc and its no noticeable
bottleneck.
So the questions are:
- Why does adjust-array take so long?
- and: How can I make it faster?
I'm already using (declaim (optimize (speed 3) (safety 0) (debug 0))).
cheers
sascha
[0] shameless plug: Its called Argh! and can be found in the official
mercurial repository: http://hg.intevation.org/argh/ and on my
german homepage: http://www.sha-bang.de/eso.html
[1] Profiler output:
measuring PROFILE overhead..done
seconds | consed | calls | sec/call | name
----------------------------------------------------------
3.050 | 22,643,664 | 58 | 0.052585 | ARGH::GROW-CODE/DATA-ARRAY
0.161 | 2,359,560 | 379,872 | 0.0000004 | ARGH:INTERPRET-CODE-AT-IP
0.030 | 0 | 66,936 | 0.0000004 | ARGH::GROW-CODE/DATA-ARRAY-MAYBE
----------------------------------------------------------
3.241 | 25,003,224 | 446,866 | | Total
estimated total profiling overhead: 1.46 seconds
overhead estimation parameters:
4.8e-8s/call, 3.272e-6s total profiling, 1.272e-6s internal profiling
[2] on my old 800MHz Athlon, but anyway.
--
Sascha Wilde
Nothing is fool-proof to a sufficiently talented fool.
Sascha Wilde <·····@sha-bang.de> writes:
> Hi *,
>
> I have written an interpreter for my little esoteric toy language[0].
> Using SBCL on GNU/Linux the naive common lisp implementation is
> reasonable fast with one big exception:
>
> I'm using an (two dimensional) array which in some cases has to be
> dynamically extended. Here is the relevant code:
>
> (defparameter *code/data* (make-array '(40 80)
> :element-type '(signed-byte 32)
> :adjustable t)
> "The two dimensional code/data array, as described in the spec.")
>
> [...]
>
> (defun grow-code/data-array ()
> "Grow code/data array by 40 rows."
> (setf *code/data*
> (adjust-array *code/data*
> (list (+ (array-dimension *code/data* 0)
> 40)
> 80)
> :element-type '(signed-byte 32))))
I guess it would be faster to grow it by columns.
At least, in clisp it is:
C/USER[482]> (defun grow-code/data-array ()
"Grow code/data array by 40 columns."
(setf *code/data*
(adjust-array *code/data*
(list 80 (+ (array-dimension *code/data* 0)
40))
:element-type '(signed-byte 32))))
GROW-CODE/DATA-ARRAY
C/USER[483]> (progn (defparameter *code/data* (make-array '(80 0) :element-type '(signed-byte 32))) (time (loop repeat 200 do (grow-code/data-array))))
Real time: 0.039001 sec.
Run time: 0.039998 sec.
Space: 15571712 Bytes
GC: 2, GC time: 0.016666 sec.
NIL
C/USER[484]> (defun grow-code/data-array ()
"Grow code/data array by 40 rows."
(setf *code/data*
(adjust-array *code/data*
(list (+ (array-dimension *code/data* 0)
40)
80)
:element-type '(signed-byte 32))))
GROW-CODE/DATA-ARRAY
C/USER[485]> (progn (defparameter *code/data* (make-array '(0 80) :element-type '(signed-byte 32))) (time (loop repeat 200 do (grow-code/data-array))))
Real time: 1.636093 sec.
Run time: 1.629894 sec.
Space: 514771712 Bytes
GC: 81, GC time: 1.066602 sec.
NIL
C/USER[486]>
The time complexity is very different from one case to the other.
> So the questions are:
> - Why does adjust-array take so long?
Because you adjusted the wrong dimension.
> - and: How can I make it faster?
By adjusting the right dimension.
--
__Pascal Bourguignon__
Hello Pascal,
thanks for your reply,
···@informatimago.com (Pascal J. Bourguignon) wrote:
> Sascha Wilde <·····@sha-bang.de> writes:
>> I'm using an (two dimensional) array which in some cases has to be
>> dynamically extended. Here is the relevant code:
>>
>> (defparameter *code/data* (make-array '(40 80)
>> :element-type '(signed-byte 32)
>> :adjustable t)
>> "The two dimensional code/data array, as described in the spec.")
>>
>> [...]
>>
>> (defun grow-code/data-array ()
>> "Grow code/data array by 40 rows."
>> (setf *code/data*
>> (adjust-array *code/data*
>> (list (+ (array-dimension *code/data* 0)
>> 40)
>> 80)
>> :element-type '(signed-byte 32))))
>
> I guess it would be faster to grow it by columns.
While this is an convincing theory, the sad truth is, that the speedup
in your example is only caused by an error in the code, causing it to
actually grow the array only once:
> At least, in clisp it is:
>
> C/USER[482]> (defun grow-code/data-array ()
> "Grow code/data array by 40 columns."
> (setf *code/data*
> (adjust-array *code/data*
> (list 80 (+ (array-dimension *code/data* 0)
> 40))
; This must be:
; (list 80 (+ (array-dimension *code/data* 1)
; 40))
> :element-type '(signed-byte 32))))
With this change the timings for both variations are nearly the same, at
least with sbcl. Any other Ideas?
In the mean time it turns out that growing an one dimensional array like
this:
(defun grow-code/data-array ()
"Grow code/data array by 40 columns."
(setf *code/data*
(adjust-array *code/data*
(+ (array-dimension *code/data* 0)
#.(* 40 80))
:element-type '(signed-byte 32))))
(progn (defparameter *code/data* (make-array 80 :element-type '(signed-byte 32))) (time (loop repeat 200 do (grow-code/data-array))))
is about 3.5 times faster, which is better but still somewhat
disappointing.
cheers
sascha
--
Sascha Wilde : "There are 10 types of people in the world.
: Those who understand binary and those who don't."
Sascha Wilde <·····@sha-bang.de> writes:
> Hello Pascal,
>
> thanks for your reply,
>
> ···@informatimago.com (Pascal J. Bourguignon) wrote:
>> Sascha Wilde <·····@sha-bang.de> writes:
>>> I'm using an (two dimensional) array which in some cases has to be
>>> dynamically extended. Here is the relevant code:
>>>
>>> (defparameter *code/data* (make-array '(40 80)
>>> :element-type '(signed-byte 32)
>>> :adjustable t)
>>> "The two dimensional code/data array, as described in the spec.")
>>>
>>> [...]
>>>
>>> (defun grow-code/data-array ()
>>> "Grow code/data array by 40 rows."
>>> (setf *code/data*
>>> (adjust-array *code/data*
>>> (list (+ (array-dimension *code/data* 0)
>>> 40)
>>> 80)
>>> :element-type '(signed-byte 32))))
>>
>> I guess it would be faster to grow it by columns.
>
> While this is an convincing theory, the sad truth is, that the speedup
> in your example is only caused by an error in the code, causing it to
> actually grow the array only once:
Oops, sorry! <*^.^*>
> In the mean time it turns out that growing an one dimensional array like
> this:
> [...]
> is about 3.5 times faster, which is better but still somewhat
> disappointing.
> On the other hand, the C implementation shows, that reallocating per se
> is not the problem, what I really want is a way to hint the common lisp
> compiler that it can (re)allocate memory merely in the same simple and
> stupid way the C implementation does.
The difference is that with realloc, "newly allocated memory will be
uninitialized." This is something lisp cannot do.
------------------------------------------------------------------------
(defstruct (atable (:constructor %make-atable))
width height height-increment
element-type
initial-element
data)
(defmethod print-object ((self atable) stream)
(print-unreadable-object (self stream :identity t :type t)
(format stream ":width ~A :height ~A :height-increment ~A :element-type ~S :initial-element ~S"
(atable-width self)
(atable-height self)
(atable-height-increment self)
(atable-element-type self)
(atable-initial-element self)))
self)
(defun make-atable (width height
&key (height-increment height) (element-type 't)
(initial-element 'nil))
(multiple-value-bind (count rest) (truncate height height-increment)
(assert (zerop rest))
(loop
:with table = (%make-atable :width width :height height
:height-increment height-increment
:element-type element-type
:initial-element initial-element
:data (make-array (list 8)
:adjustable t
:fill-pointer 0))
:repeat count
:do (atable-grow table)
:finally (return table))))
(defun atable-ref (table i j)
(multiple-value-bind (s r) (truncate j (atable-height-increment table))
(aref (aref (atable-data table) s) i r)))
(defun (setf atable-ref) (new-value table i j)
(multiple-value-bind (s r) (truncate j (atable-height-increment table))
(setf (aref (aref (atable-data table) s) i r) new-value)))
(defun atable-grow (table)
(vector-push-extend
(make-array (list (atable-width table)
(atable-height-increment table))
:element-type (atable-element-type table)
:initial-element (atable-initial-element table))
(atable-data table))
(incf (atable-height table) (atable-height-increment table))
table)
(defparameter *code/data* (make-atable 80 40
:element-type '(signed-byte 32)
:initial-element 0))
(time (loop
:repeat 1000
:do (atable-grow *code/data*)))
(print *code/data*)
------------------------------------------------------------------------
C/USER[509]> (load"~/src/lisp/encours/atable.lisp")
;; Loading file /home/pjb/src/lisp/encours/atable.lisp ...
Real time: 0.157815 sec.
Run time: 0.156657 sec.
Space: 26297008 Bytes
GC: 2, GC time: 0.093327 sec.
#<ATABLE :width 80 :height 40080 :height-increment 40 :element-type (SIGNED-BYTE 32) :initial-element 0 #x00033759B1D0>
;; Loaded file /home/pjb/src/lisp/encours/atable.lisp
T
C/USER[510]> (atable-ref *code/data* 1 100)
0
C/USER[511]> (incf (atable-ref *code/data* 1 100))
1
C/USER[512]> (incf (atable-ref *code/data* 1 100))
2
--
__Pascal Bourguignon__
···@informatimago.com (Pascal J. Bourguignon) wrote:
> (defstruct (atable (:constructor %make-atable))
[...]
Thanks for the promising idea and the example code -- I'll have a closer
look at it this weekend...
cheers
sascha
--
Sascha Wilde
Programmer - A red-eyed, mumbling mammal capable of conversing with
inanimate objects.
Sascha Wilde <·····@sha-bang.de> wrote:
> ···@informatimago.com (Pascal J. Bourguignon) wrote:
>> (defstruct (atable (:constructor %make-atable))
> [...]
>
> Thanks for the promising idea and the example code -- I'll have a closer
> look at it this weekend...
Ok, fwiw, I did some testing:
Your code works well[0] and probably is the best generic solution. But
it turned out that a rather simple hash-table based solution is equally
fast -- even a little bit faster -- for my actual application.[1]
The code looks like this:
(defstruct (cell-array (:constructor %make-cell-array))
width
hash-table)
(defun make-cell-array (width)
(%make-cell-array :width width
:hash-table (make-hash-table)))
(defmacro getcell (cell-array x y)
`(gethash (+ ,x (* ,y (cell-array-width ,cell-array)))
(cell-array-hash-table ,cell-array)))
which is not only rather short but "auto growing", too. Actually it can
be reduced to:
(defun make-cell-array ()
(make-hash-table))
(defmacro getcell (cell-array x y)
`(gethash (+ ,x (* ,y 80)) ,cell-array))
as the Argh! spec allows for no other widths than 80 to squeeze out
even some more milliseconds...
(admittedly, some error checking needs to be added)
cheers
sascha
[0] After fixing a minor bug: in make-atable :height initially must set
to 0 as it gets incremented by the later call to atable-grow in the
same function.
[1] At least with all actual Argh! programs I know of which is a rather
small test set I must admit... ;-)
--
Sascha Wilde
Life's too short to read boring signatures
P� Sun, 20 Jul 2008 21:58:57 +0200, skrev Sascha Wilde <·····@sha-bang.de>:
>
> (defmacro getcell (cell-array x y)
> `(gethash (+ ,x (* ,y 80)) ,cell-array))
>
This should be a function, not a macro.
Note that you are expaning cell-array, x and y directly into the code
before evaluating them which can give unexpected side effects.
(see the macro once-only .. or rebinding in LW for a fix for this class of
problem.)
You can still get the function inlined by writing (declaim inline
getcell), but now variables are evaluated first and applied later.
--------------
John Thingstad
"John Thingstad" <·······@online.no> wrote:
> P� Sun, 20 Jul 2008 21:58:57 +0200, skrev Sascha Wilde <·····@sha-bang.de>:
>
>>
>> (defmacro getcell (cell-array x y)
>> `(gethash (+ ,x (* ,y 80)) ,cell-array))
>>
>
> This should be a function, not a macro.
I have to admit, that I was a little lazy: it would need an function and
an setf-function.
> Note that you are expaning cell-array, x and y directly into the code
> before evaluating them which can give unexpected side effects.
Can you elaborate on this? I rally don't see the problem here...
> (see the macro once-only .. or rebinding in LW for a fix for this
> class of problem.)
Sorry, I don't use LW.
cheers
sascha
--
Sascha Wilde
"Gimme about 10 seconds to think for a minute..."
P� Mon, 21 Jul 2008 12:10:49 +0200, skrev Sascha Wilde <·····@sha-bang.de>:
> "John Thingstad" <·······@online.no> wrote:
>
>> P� Sun, 20 Jul 2008 21:58:57 +0200, skrev Sascha Wilde
>> <·····@sha-bang.de>:
>>
>>>
>>> (defmacro getcell (cell-array x y)
>>> `(gethash (+ ,x (* ,y 80)) ,cell-array))
>>>
>>
>> This should be a function, not a macro.
>
> I have to admit, that I was a little lazy: it would need an function and
> an setf-function.
>
>> Note that you are expaning cell-array, x and y directly into the code
>> before evaluating them which can give unexpected side effects.
>
> Can you elaborate on this? I rally don't see the problem here...
>
The problem is that cell-array, x and y are lisp expressions.
When you evaluate functions the parameters are evaluated first.
In macroes the contents of a parameter is verbatimly substituded inn.
Now consider the case where x and y are not values but expressions.
Now side effects come into play.
>> (see the macro once-only .. or rebinding in LW for a fix for this
>> class of problem.)
>
> Sorry, I don't use LW.
>
Use once-only then. ("Practical Common Lisp by Peter Seibel"
http://www.gigamonkeys.com/book)
> cheers
> sascha
--
--------------
John Thingstad
Sascha Wilde <·····@sha-bang.de> writes:
> "John Thingstad" <·······@online.no> wrote:
>
>> P� Sun, 20 Jul 2008 21:58:57 +0200, skrev Sascha Wilde <·····@sha-bang.de>:
>>
>>>
>>> (defmacro getcell (cell-array x y)
>>> `(gethash (+ ,x (* ,y 80)) ,cell-array))
>>>
>>
>> This should be a function, not a macro.
>
> I have to admit, that I was a little lazy: it would need an function and
> an setf-function.
>
>> Note that you are expaning cell-array, x and y directly into the code
>> before evaluating them which can give unexpected side effects.
>
> Can you elaborate on this? I rally don't see the problem here...
(let ((i 0))
(getcell (aref my-arrays (incf i)) (incf i) (incf i)))
with the 'standard' evaluation rules, we would expect to get the same
as:
(getcell (aref my-arrays 1) 2 3)
that is:
(gethash (+ 2 (* 3 80)) (aref my-arrays 1))
but since the expansion contains the argument in different orders, we get:
(gethash (+ 1 (* 2 80)) (aref my-cell 3))
It could be even worse, if the same expression was used in several
places in the expansion:
(defmacro very-wrong-incf (i incremnent)
`(setf (gethash ,i *table*) (+ ,increment (gethash ,i *table*))))
then:
(let ((i 0))
(very-wrong-incf (incf i) (incf i)))
which one would expect to be equivalent to:
(very-wrong-incf 1 2)
that is:
(setf (gethash 1 *table*) (+ 2 (gethash 1 *table*)))
would actually be:
(setf (gethash 1 *table*) (+ 2 (gethash 3 *table*)))
So, unless there's a good and well documented reason not to, macros
should take care of evaluating the expressions they evaluate:
- exactly once,
- in the textual order.
(defmacro getcell (cell-array x y)
;; at macro expansion time,
;; make up variable names to hold the values of the expressions:
(let ((vcell (gensym))
(vx (gensym))
(vy (gensym)))
;; at run time,
;; bind the value of the expression, in the order they're passed as parameter,
;; the these made-up variables:
`(let ((,vcell ,cell-array)
(,vx ,x)
(,vy ,y))
;; use the values from these variables; now the order doesn't matter anymore:
(gethash (+ ,vx (* ,vy 80)) ,vcell))))
Eventually, by the LET <=> LAMBDA:
((lambda (vcell vx vy) (gethash (+ vx (* vy 80)) vcell))
cell-array x y)
you can see that your macro doesn't do anything more than a function
call, so you should just write it as a function (or a pair of
functions, if you need the setter).
Sometimes it's not possible to write it as a function, then you have
to write use GET-SETF-EXPANSION, but this is rare.
--
__Pascal Bourguignon__
···@informatimago.com (Pascal J. Bourguignon) wrote:
> Sascha Wilde <·····@sha-bang.de> writes:
>> "John Thingstad" <·······@online.no> wrote:
[...]
>>> Note that you are expaning cell-array, x and y directly into the code
>>> before evaluating them which can give unexpected side effects.
>>
>> Can you elaborate on this? I rally don't see the problem here...
[...]
> So, unless there's a good and well documented reason not to, macros
> should take care of evaluating the expressions they evaluate:
> - exactly once,
> - in the textual order.
The second is the one I missed -- thanks for pointing it out.
> you can see that your macro doesn't do anything more than a function
> call, so you should just write it as a function (or a pair of
> functions, if you need the setter).
I know, as admitted before, I was just lazy... No good style, though.
cheers
sascha
--
Sascha Wilde
- no sig today... sorry!
P� Fri, 18 Jul 2008 11:02:28 +0200, skrev Sascha Wilde <·····@sha-bang.de>:
> So the questions are:
> - Why does adjust-array take so long?
> - and: How can I make it faster?
>
I haven't looked at your program. But what immediately appears to me is
the following.
Reallocating is expensive. Sometimes it means creating a new array and
copying the content to a new location.
So ask yourself this.
What is the average size of the elements you collect?
For the ones that are bigger just how much bigger are they?
Set a reasonable starting size that avoids the need for reallocation most
of the time.
If the max size is predictable and small enough it might not need to be
adjusted.
Fill pointer can still be set and push-new will work.
If that is not possible look at the function which calculates of the
adjustment size.
A good scheme in many cases is to double the size of the array each time.
The idea is if it is bigger it is often a lot bigger. This could cut the
number of reallocations logarithimically.
Once you know the size you could always make a array exactly big enough
and copy the contents if space is a issue.
(I am assuming it is impossible to know the size ahead of time.)
Moral is get some statisics on your allocation pattern and minimize (or
eliminate) the number of reallocations.
Also be careful optimizing for speed here. Check what your compiler does
with the setting. Sometimes space is a better choice.
--------------
John Thingstad
"John Thingstad" <·······@online.no> writes:
> P� Fri, 18 Jul 2008 11:02:28 +0200, skrev Sascha Wilde <·····@sha-bang.de>:
>
>
>> So the questions are:
>> - Why does adjust-array take so long?
>> - and: How can I make it faster?
>>
>
> I haven't looked at your program. But what immediately appears to me
> is the following.
> Reallocating is expensive. Sometimes it means creating a new array and
> copying the content to a new location.
> So ask yourself this.
> What is the average size of the elements you collect?
> For the ones that are bigger just how much bigger are they?
>
> Set a reasonable starting size that avoids the need for reallocation
> most of the time.
> If the max size is predictable and small enough it might not need to
> be adjusted.
> Fill pointer can still be set and push-new will work.
> If that is not possible look at the function which calculates of the
> adjustment size.
> A good scheme in many cases is to double the size of the array each time.
> The idea is if it is bigger it is often a lot bigger. This could cut
> the number of reallocations logarithimically.
> Once you know the size you could always make a array exactly big
> enough and copy the contents if space is a issue.
> (I am assuming it is impossible to know the size ahead of time.)
>
> Moral is get some statisics on your allocation pattern and minimize
> (or eliminate) the number of reallocations.
> Also be careful optimizing for speed here. Check what your compiler
> does with the setting. Sometimes space is a better choice.
Also, since the increment is constant, you can easily avoid any
reallocation adding one level of indirection, a vector of fixed sized
arrays. When you want to extend, you only have to add an array with
vector-push-extend, and for indexing, you use TRUNCATE to get the
vector slot and the array index.
--
__Pascal Bourguignon__
"John Thingstad" <·······@online.no> wrote:
> P� Fri, 18 Jul 2008 11:02:28 +0200, skrev Sascha Wilde <·····@sha-bang.de>:
>
>> So the questions are:
>> - Why does adjust-array take so long?
>> - and: How can I make it faster?
>>
>
> I haven't looked at your program. But what immediately appears to me
> is the following.
> Reallocating is expensive. Sometimes it means creating a new array and
> copying the content to a new location.
[short: try to reallocate less often]
Thanks for the reply, but this strategy is not an option for my
application. If and how much extra memory must be allocated depends
solely on the interpreted code, so the interpreter can't make any
reasonable assumptions on that.
On the other hand, the C implementation shows, that reallocating per se
is not the problem, what I really want is a way to hint the common lisp
compiler that it can (re)allocate memory merely in the same simple and
stupid way the C implementation does.
cheers
sascha
--
Sascha Wilde
Hauptfunktion einer GUI ist es IMHO, die dadurch verlorene Zeit durch
einen h�heren Spa�-Faktor zu kompensieren. Essentiell ein
Computerspiel. -- Rainer Weikusat in d.c.o.u.d
On 2008-07-18, Sascha Wilde <·····@sha-bang.de> wrote:
> On the other hand, the C implementation shows, that reallocating per se
> is not the problem, what I really want is a way to hint the common lisp
> compiler that it can (re)allocate memory merely in the same simple and
> stupid way the C implementation does.
You could try this: (may be a somewhat ugly solution, but it may work)
Create an implementation-specific way to get what you want by patching
SBCL and including an :itialize option to adjust-array. The semantics
would be his:
- T by default
- When :initialize is NIL, do not initialize the
contents of the array otherwise it will be ignored.
You could add extra restrictions, such as "it will only have any
effect if the array holds unboxed data (characters or numbers),
but *will* initialize the array if it holds boxed data/references to
Lisp objects".
Then convince the SBCL developers that this is a good idea.
And finally, modify your code to use the :initialize argument only if it
is running on SBCL (or another implementation that supports it, if you
also modify others).
J.
From: Richard M Kreuter
Subject: Re: speeding up adjust-array?
Date:
Message-ID: <87bq0vuimj.fsf@progn.net>
Sascha Wilde <·····@sha-bang.de> writes:
> In the C implementation I'm using realloc and its no noticeable
> bottleneck.
By light inspection, it looks as though the realloc() on my system
often returns its argument when no allocation has happened since the
initial malloc() or previous realloc() of that memory, and rarely does
so when another allocation has occurred in that interval. Presumably,
my realloc() is sometimes able "just" to change some pointer into free
space, and not actually reallocate anything.
> So the questions are:
> - Why does adjust-array take so long?
Because it's actually allocating a new array and then copying your
existing data into the new array.
> - and: How can I make it faster?
If you mean SBCL's ADJUST-ARRAY, it would take work at a couple levels
of SBCL to make it possible for ADJUST-ARRAY to ever avoid allocating
a new array.
If you mean your program, one option might be to grow your array
exponentially, rather than linearly. If that still doesn't help,
change over to a manually-managed structure that doesn't require
reallocation.
--
RmK