I'm learning CL (yes I bought a copy of PCL and am glad I did). One of my little exercises is to
implement an L-System evaluator. See
http://en.wikipedia.org/wiki/L-system
My naive attempt is as follows:
(defun run-l-system (rules state count)
(declare (optimize (speed 3) (safety 0)))
(let ((rule-table (make-hash-table)))
(dolist (rule rules)
(setf (gethash (car rule) rule-table) (cdr rule)))
(dotimes (i count)
(let (new-state)
(dolist (a-symbol state)
(setf new-state (append new-state (gethash a-symbol rule-table))))
(setf state new-state)))
state))
This obviously doesn't specifically handle constants, do any error checking,
yadda yadda, it's just an experiment. An example invocation (using the Algae rule set):
CL-USER 9 > (run-l-system (list (cons 'A '(A B)) (cons 'B '(A))) '(A) 3)
(A B A A B)
All well and good, but obviously could be better. What I'm particularly interested
in is how to speed this up (and learn some better CL idioms). I've loaded and compiled
this function on three different implementations, and gotten the following (time) results
when running the same rule set with a count of 20 instead of 3:
LispWorks Personal Edition 4.3.7
user time = 57.875
system time = 0.000
Elapsed time = 0:00:57
Allocation = 1800 bytes standard / 1725022871 bytes conses
0 Page faults
Calls to %EVAL 42
Allegro Trial Edition 6.2 Release 25
; cpu time (non-gc) 816 msec user, 0 msec system
; cpu time (gc) 8,419 msec user, 0 msec system
; cpu time (total) 9,235 msec user, 0 msec system
; real time 9,235 msec
; space allocation:
; 156,820,003 cons cells, 9,488 other bytes, 0 static bytes
GCL 2.6.6
real time : 3.560 secs
run-gbc time : 2.250 secs
child run time : 0.000 secs
gbc time : 1.310 secs
These are all from the same WinXP SP2 P4 3.4GHz 1Gig PC. BTW this is not meant
as a benchmark to compare Lisp vendors, I'm just trying to learn how to write better
code and so I'm trying different implementations.
The big obvious red flag is the ungodly amount of cons'ing. Any suggestions you
might have would be appreciated.
--
Jack
Jack wrote:
> CL-USER 9 > (run-l-system (list (cons 'A '(A B)) (cons 'B '(A))) '(A) 3)
> (A B A A B)
please read again PCL :-) and then write it like this:
(run-l-system '((a a b) (b a)) '(a) 20)
> These are all from the same WinXP SP2 P4 3.4GHz 1Gig PC. BTW this is not meant
> as a benchmark to compare Lisp vendors, I'm just trying to learn how to write better
> code and so I'm trying different implementations.
the append is very time consuming, because it has to run through the whole
list before it can append just some symbols. You can speed it up a lot with
this:
(defun run-l-system (rules state count)
(let ((rule-table (make-hash-table)))
(dolist (rule rules)
(setf (gethash (car rule) rule-table) (cdr rule)))
(dotimes (i count)
(let (new-state)
(dolist (a-symbol state)
(let ((found (gethash a-symbol rule-table)))
(dolist (a-symbol found) (push a-symbol new-state))))
(setf state (nreverse new-state))))
state))
A (time (run-l-system '((a a b) (b a)) '(a) 20)) needs 0 seconds :-)
And just in case you want some Postscript output and rules, which can have
more than one char as the lookup value:
http://groups.google.de/group/comp.lang.lisp/browse_frm/thread/05631fa93379bca8/248b67466ca2aa7d
But it is not a good example in Lisp programming, because I'm learning CL,
too.
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Jack <·······@example.org> writes:
> I'm learning CL (yes I bought a copy of PCL and am glad I did). One of my little exercises is to
> implement an L-System evaluator. See
>
> http://en.wikipedia.org/wiki/L-system
>
> My naive attempt is as follows:
>
> (defun run-l-system (rules state count)
> (declare (optimize (speed 3) (safety 0)))
> (let ((rule-table (make-hash-table)))
> (dolist (rule rules)
> (setf (gethash (car rule) rule-table) (cdr rule)))
> (dotimes (i count)
> (let (new-state)
> (dolist (a-symbol state)
> (setf new-state (append new-state (gethash a-symbol rule-table))))
> (setf state new-state)))
> state))
>
> This obviously doesn't specifically handle constants, do any error
> checking, yadda yadda, it's just an experiment. An example
> invocation (using the Algae rule set):
>
> CL-USER 9 > (run-l-system (list (cons 'A '(A B)) (cons 'B '(A))) '(A) 3)
> (A B A A B)
>
> All well and good, but obviously could be better. What I'm
> particularly interested in is how to speed this up (and learn some
> better CL idioms).
If you must work on lists, it's faster to use them as stack rather
than queues (use push and pop ie. cons, and reverse) instead of append.
push+reverse --> O(N)
append --> O(N�)
Once you've changed the algorithm to reduce its time or space
complexity, you can micro-optimize including in your function a
compiler. Here, we compile the states into functions to do prepend
the successors, and we use these functions to do the job instead.
Here it may not be worthwile, but for example in case of state
machines, you could generate the state machine into an efficient
compiled tagbody/go form.
(defun run-l-system-c (rules sstring repeat)
(let ((rule-table (make-hash-table)))
(dolist (rule rules)
(setf (gethash (car rule) rule-table)
(compile nil `(lambda (sstring)
,(let ((expr 'sstring))
(dolist (sym (reverse (cdr rule)) expr)
(setf expr `(cons ',sym ,expr))))))))
(dotimes (i repeat sstring)
(let ((nstring))
(dolist (sym (nreverse sstring))
(setf nstring (funcall (gethash sym rule-table) nstring)))
(setf sstring nstring)))))
In clisp:
[136]> (prog1 (values)
(time (run-l-system '((a . (a b)) (b . (a))) '(A) 20)))
Real time: 97.17531 sec.
Run time: 82.46 sec.
Space: 1254559912 Bytes
GC: 744, GC time: 71.79 sec.
NIL
[168]> (prog1 (values)
(time (run-l-system-c '((a . (a b)) (b . (a))) '(A) 20)))
Real time: 0.139404 sec.
Run time: 0.14 sec.
Space: 376872 Bytes
NIL
Here, the run-l-system-c function is interpreted, let's improve this:
[169]> (compile 'run-l-system-c)
RUN-L-SYSTEM-C ;
NIL ;
NIL
[170]> (prog1 (values)
(time (run-l-system-c '((a . (a b)) (b . (a))) '(A) 20)))
Real time: 0.016306 sec.
Run time: 0.02 sec.
Space: 376672 Bytes
NIL
[173]> (prog1 (values)
(time (run-l-system-c '((a . (a b)) (b . (a))) '(A) 30)))
Real time: 4.714221 sec.
Run time: 4.69 sec.
Space: 45628824 Bytes
GC: 3, GC time: 2.54 sec.
NIL
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
Jack <·······@example.org> writes:
> This obviously doesn't specifically handle constants, do any error
> checking, yadda yadda, it's just an experiment. An example
> invocation (using the Algae rule set):
On the contrary, it handles constants perfectly well:
[7]> (run-l-system-c '((f . (f + f - f - f + f)) (+ +) (- -)) '(f) 2)
(F + F - F - F + F + F + F - F - F + F - F + F - F - F + F - F + F - F - F + F +
F + F - F - F + F)
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
Jack <·······@example.org> wrote
> One of my little exercises is to
> implement an L-System evaluator.
The most obvious way for expressing the list processing that I can
think of is this:
(loop repeat count
for s = state then (proc s)
finally (return (proc s))))))
Where proc is the processing function, which looks like this:
(defun proc (list)
(apply #'append
(loop for elem in list
collect (gethash elem rule-table))))
My variant of run-l-system would look like this:
(defun f2b (rules state count)
(declare (optimize (speed 3) (safety 0)))
(let ((rule-table (make-hash-table)))
(dolist (rule rules)
(setf (gethash (car rule) rule-table) (cdr rule)))
(flet ((proc (list)
(apply #'append
(loop for elem in list
collect (gethash elem rule-table)))))
(loop repeat count
for s = state then (proc s)
finally (return (proc s))))))
On my system, your run-l-system times like this:
; cpu time (non-gc) 10,409 msec user, 270 msec system
; cpu time (gc) 23,069 msec user, 521 msec system
; cpu time (total) 33,478 msec user, 791 msec system
; real time 34,559 msec
; space allocation:
; 157,652,788 cons cells, 3,441,152 other bytes, 3,576 static bytes
and f2b above times like this:
; cpu time (non-gc) 1,121 msec user, 0 msec system
; cpu time (gc) 301 msec user, 0 msec system
; cpu time (total) 1,422 msec user, 0 msec system
; real time 1,432 msec
; space allocation:
; 1,054,469 cons cells, 5,058,304 other bytes, 0 static bytes
Still it can be improved. If the processing loop is rewritten as a
mapping instead;
(defun f2c (rules state count)
(declare (optimize (speed 3) (safety 0)))
(let ((rule-table (make-hash-table)))
(dolist (rule rules)
(setf (gethash (car rule) rule-table) (cdr rule)))
(flet ((proc (list)
(apply #'append
(mapcar (lambda (elem)
(gethash elem rule-table)) list))))
(loop repeat count
for s = state then (proc s)
finally (return (proc s))))))
It times like:
; cpu time (non-gc) 451 msec user, 10 msec system
; cpu time (gc) 150 msec user, 0 msec system
; cpu time (total) 601 msec user, 10 msec system
; real time 611 msec
; space allocation:
; 391,743 cons cells, 2,323,112 other bytes, 0 static bytes
That's better. But is the hash table really necessary? The code can
be simplified without it:
(defun f3b (rules state count)
(declare (optimize (speed 3) (safety 0)))
(flet ((proc (list)
(apply #'append
(mapcar (lambda (elem)
(rest (assoc elem rules))) list))))
(loop repeat count
for s = state then (proc s)
finally (return (proc s)))))
Times like this:
; cpu time (non-gc) 461 msec user, 0 msec system
; cpu time (gc) 170 msec user, 0 msec system
; cpu time (total) 631 msec user, 0 msec system
; real time 641 msec
; space allocation:
; 420,219 cons cells, 2,321,392 other bytes, 0 static bytes
OK, it's slightly simpler, but somewhat slower and conses some more.
I'd still prefer it to the other variants.
·············@swipnet.se (Peter Lewerin) wrote
> (defun proc (list)
> (apply #'append
> (loop for elem in list
> collect (gethash elem rule-table))))
The apply/append wrapper isn't strictly necessary here; the loop can
instead be written as:
(defun proc (list)
(loop for elem in list
append (gethash elem rule-table)))
This is more readable, but actually a bit slower and conses more.
Jack wrote:
> I'm learning CL (yes I bought a copy of PCL and am glad I did). One of my little exercises is to
> implement an L-System evaluator. See
>
> http://en.wikipedia.org/wiki/L-system
>
> My naive attempt is as follows:
>
> (defun run-l-system (rules state count)
> (declare (optimize (speed 3) (safety 0)))
> (let ((rule-table (make-hash-table)))
> (dolist (rule rules)
> (setf (gethash (car rule) rule-table) (cdr rule)))
> (dotimes (i count)
> (let (new-state)
> (dolist (a-symbol state)
> (setf new-state (append new-state (gethash a-symbol rule-table))))
> (setf state new-state)))
> state))
>
>
(defun run-l-system (rules state count)
(loop repeat count do
(setf state
(loop for rule in state
appending (cdr (assoc rule rules))))
finally (return state)))
ON LW 4.3.7. Using the appending collection method in loop
is as efficient as it comes.
CL-USER 7 > (time (run-l-system '((a a b) (b a)) '(a) 20))
Timing the evaluation of (RUN-L-SYSTEM (QUOTE ((A A B) (B A))) (QUOTE (A)) 20)
user time = 0.030
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 510235 bytes conses
0 Page faults
Calls to %EVAL 36
(A B A A B A B A A B A A B A B A A B
On Fri, 27 May 2005 13:48:39 GMT, Wade Humeniuk <··················@telus.net> wrote:
>
>(defun run-l-system (rules state count)
> (loop repeat count do
> (setf state
> (loop for rule in state
> appending (cdr (assoc rule rules))))
> finally (return state)))
>
Thanks to everyone for your comments!
--
Jack
In article <··································@4ax.com>,
Jack <·······@example.org> wrote:
> I'm learning CL (yes I bought a copy of PCL and am glad I did). One of my little exercises is to
> implement an L-System evaluator. See
>
> http://en.wikipedia.org/wiki/L-system
>
> My naive attempt is as follows:
>
> (defun run-l-system (rules state count)
> (declare (optimize (speed 3) (safety 0)))
> (let ((rule-table (make-hash-table)))
> (dolist (rule rules)
> (setf (gethash (car rule) rule-table) (cdr rule)))
> (dotimes (i count)
> (let (new-state)
> (dolist (a-symbol state)
> (setf new-state (append new-state (gethash a-symbol rule-table))))
> (setf state new-state)))
> state))
>
> This obviously doesn't specifically handle constants, do any error checking,
> yadda yadda, it's just an experiment. An example invocation (using the Algae rule set):
>
> CL-USER 9 > (run-l-system (list (cons 'A '(A B)) (cons 'B '(A))) '(A) 3)
> (A B A A B)
>
> All well and good, but obviously could be better. What I'm particularly interested
> in is how to speed this up (and learn some better CL idioms). I've loaded and compiled
> this function on three different implementations, and gotten the following (time) results
> when running the same rule set with a count of 20 instead of 3:
>
> LispWorks Personal Edition 4.3.7
> user time = 57.875
> system time = 0.000
> Elapsed time = 0:00:57
> Allocation = 1800 bytes standard / 1725022871 bytes conses
> 0 Page faults
> Calls to %EVAL 42
Others have helped you with the code. One question: did you
compile the function? 57 seconds seems to be quite slow. My
LispWorks on my Mac runs your code compiled in 8 seconds.
If you type to the listener, make sure you do this:
CL-USER 1 > (defun run-l-system (rules state count)
(declare (optimize (speed 3) (safety 0)))
(let ((rule-table (make-hash-table)))
(dolist (rule rules)
(setf (gethash (car rule) rule-table) (cdr rule)))
(dotimes (i count)
(let (new-state)
(dolist (a-symbol state)
(setf new-state (append new-state (gethash a-symbol rule-table))))
(setf state new-state)))
state))
RUN-L-SYSTEM
CL-USER 2 > (compile *)
RUN-L-SYSTEM
NIL
NIL
The variable * holds the last value, so (compile *) is here the same as (compile 'run-l-system) .
If you use the LispWorks editor, you can compile your code with a keychord: control-shift-c .
>
> Allegro Trial Edition 6.2 Release 25
> ; cpu time (non-gc) 816 msec user, 0 msec system
> ; cpu time (gc) 8,419 msec user, 0 msec system
> ; cpu time (total) 9,235 msec user, 0 msec system
> ; real time 9,235 msec
> ; space allocation:
> ; 156,820,003 cons cells, 9,488 other bytes, 0 static bytes
>
> GCL 2.6.6
> real time : 3.560 secs
> run-gbc time : 2.250 secs
> child run time : 0.000 secs
> gbc time : 1.310 secs
>
> These are all from the same WinXP SP2 P4 3.4GHz 1Gig PC. BTW this is not meant
> as a benchmark to compare Lisp vendors, I'm just trying to learn how to write better
> code and so I'm trying different implementations.
>
> The big obvious red flag is the ungodly amount of cons'ing. Any suggestions you
> might have would be appreciated.
On Sun, 29 May 2005 17:59:08 +0200, Rainer Joswig <······@lisp.de> wrote:
>
> Others have helped you with the code. One question: did you
> compile the function? 57 seconds seems to be quite slow. My
> LispWorks on my Mac runs your code compiled in 8 seconds.
I thought that I had, but I just now re-ran my original version several
times on LispWorks (after compiling it) and I got results that ranged
from 20 to 30 secs of user time.
I haven't delved into whether there is any sort of tuning that is possible;
I'm just running LispWorks (and the others that I tried) in the default
configuration.
> The variable * holds the last value, so (compile *) is here the same as (compile 'run-l-system) .
>
> If you use the LispWorks editor, you can compile your code with a keychord: control-shift-c .
Thanks for the info!
--
Jack