From: Wang Yin
Subject: How to improve efficiency of LISP program?
Date:
Message-ID: <m33cd9edw8.fsf@wangyin.com>
Hi,
I've rewrited one of my C programs which do computation geometry
algorithms into CL. I compiled the program with CMU CL.
At first it runs rather slowly. It takes 170s to get the results that
can be computed in less than 1s by the C program.
Later I inserted some (declare (type ...)) and (proclaim '(optimize
speed (space 0) (safety 0))) and I use fixnum for the integers and
'(vector double-float) for coordinate numbers in the defstruct's. And
I inlined some functions.
And I improved the program to run in 17s. But with a large input it
still takes about 40 times longer than the C version.
This is not resonable. I hope the LISP program can run only 2 times
slower than C programs. Can anyone suggest some method to improve the
efficiency? I've read some of CMU CL's but it doesn't help much.
I wonder if hash tables in CL cost much time? The C program doesn't
use hash table, but the data structures just got messy without it.
--
Yin Wang,
EDA Lab,
Deparment of Computer Science and Technology,
Tsinghua University,
100084
Beijing China
Wang Yin <··@wangyin.com> writes:
> I've rewrited one of my C programs which do computation geometry
> algorithms into CL. I compiled the program with CMU CL.
>
> At first it runs rather slowly. It takes 170s to get the results that
> can be computed in less than 1s by the C program.
>
> Later I inserted some (declare (type ...)) and (proclaim '(optimize
> speed (space 0) (safety 0))) and I use fixnum for the integers and
> '(vector double-float) for coordinate numbers in the defstruct's. And
> I inlined some functions.
Don't use (safety 0), use (safety 1). Presumably you want Lisp's
traditional behavior of giving you the correct result, right? :)
> This is not resonable. I hope the LISP program can run only 2 times
> slower than C programs. Can anyone suggest some method to improve the
> efficiency? I've read some of CMU CL's but it doesn't help much.
It's reasonable to expect them to be on the same order of magnitude.
If you're willing to write actually equivalent programs, where the
Lisp program has the same restrictions as the C program, you can
generally get them running at the same speed -- but once you have the
choice, everyone wants more flexability than C gives.
> I wonder if hash tables in CL cost much time? The C program doesn't
> use hash table, but the data structures just got messy without it.
You really need to post code, if you want help. But one thing I can
tell you is that if you're hashing on floats, you're consing a lot.
CMUCL can keep floats unboxed in vectors, and often in variables, but
once you put them in a generic container (something that could
potentially hold any type of value), like a hash table, it has to
allocate memory to box the float.
Profile, and send us your code.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> Wang Yin <··@wangyin.com> writes:
>
>> Later I inserted some (declare (type ...)) and (proclaim '(optimize
>> speed (space 0) (safety 0))) and I use fixnum for the integers and
>> '(vector double-float) for coordinate numbers in the defstruct's. And
>> I inlined some functions.
>
> Don't use (safety 0), use (safety 1). Presumably you want Lisp's
> traditional behavior of giving you the correct result, right? :)
Declarations of the form (safety 0) do not give conforming
implementations latitude to return the wrong result in the presence of
only correct type declarations, and otherwise correct code.
Christophe
--
http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)
Christophe Rhodes <·····@cam.ac.uk> writes:
> ···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> > Wang Yin <··@wangyin.com> writes:
> >
> >> Later I inserted some (declare (type ...)) and (proclaim '(optimize
> >> speed (space 0) (safety 0))) and I use fixnum for the integers and
> >> '(vector double-float) for coordinate numbers in the defstruct's. And
> >> I inlined some functions.
> >
> > Don't use (safety 0), use (safety 1). Presumably you want Lisp's
> > traditional behavior of giving you the correct result, right? :)
>
> Declarations of the form (safety 0) do not give conforming
> implementations latitude to return the wrong result in the presence of
> only correct type declarations, and otherwise correct code.
Of course, but people are notorious for declaring types incorrectly.
There's nothing wrong with a local declaraion of (optimize (safety 0))
that applies to carefully scrutinized code, but asking for it globally
is, well, asking for it.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
From: Wang Yin
Subject: Re: How to improve efficiency of LISP program?
Date:
Message-ID: <m3llr0fbap.fsf@wangyin.com>
···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> You really need to post code, if you want help. But one thing I can
> tell you is that if you're hashing on floats, you're consing a lot.
> CMUCL can keep floats unboxed in vectors, and often in variables, but
> once you put them in a generic container (something that could
> potentially hold any type of value), like a hash table, it has to
> allocate memory to box the float.
>
> Profile, and send us your code.
Yes, I'm consing a lot. But I don't know better way do collect the
results. Will a linked list implemented as defstruct's work better
than cons?
I tried to send the code as attachments but Emacs failed to send it
out. So I put it on my home page. The address is:
http://learn.tsinghua.edu.cn/homepage/015450/src/delaunay-lisp.tar.gz
The code is separated into 2 files: delaunay.lisp and nary-tree.lisp.
I don't know why I can't (load "nary-tree.lisp") in delaunay.lisp to work.
I'll take sometime learning how to use package later...
So you first load nary-tree.lisp, then load delaunay.lisp
I hope you can point out what's wrong with (load "nary-tree.lisp") in
delaunay.lisp.
There is 2 data files: n830.xy and n34728.xy
The code process n34728.xy rather slowly.
It takes about 17s. Before I add the type declarations it takes 170s.
The C version finishes in 0.3s
I hope someone can point out what slowed the LISP code down.
Thanks.
>
> --
> /|_ .-----------------------.
> ,' .\ / | No to Imperialist war |
> ,--' _,' | Wage class war! |
> / / `-----------------------'
> ( -. |
> | ) |
> (`-. '--.)
> `. )----'
--
Yin Wang,
EDA Lab,
Deparment of Computer Science and Technology,
Tsinghua University,
100084
Beijing China
Wang Yin <··@wangyin.com> writes:
> ···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> >
> > You really need to post code, if you want help. But one thing I can
> > tell you is that if you're hashing on floats, you're consing a lot.
> > CMUCL can keep floats unboxed in vectors, and often in variables, but
> > once you put them in a generic container (something that could
> > potentially hold any type of value), like a hash table, it has to
> > allocate memory to box the float.
> >
> > Profile, and send us your code.
>
>
> Yes, I'm consing a lot. But I don't know better way do collect the
> results. Will a linked list implemented as defstruct's work better
> than cons?
If you know or if you can compute a more or less close upper bound of
the number of results, you could allocate an array where to store the
collection.
--
__Pascal_Bourguignon__
http://www.informatimago.com/
"Wang Yin" <··@wangyin.com> ha scritto nel messaggio
>
> I hope someone can point out what slowed the LISP code down.
>
> Thanks.
You try to do a test with OpenLisp, it's seems very very fast..
http://christian.jullien.free.fr/
DaveNlp
In article <······················@twister2.libero.it>,
DaveNlp wrote:
>
> You try to do a test with OpenLisp, it's seems very very fast..
> http://christian.jullien.free.fr/
How does ISLISP differ from Common Lisp? I tried downloading the spec,
but the zipped pdf file isn't any good and the URL for the dvi isn't any
good.
The FAQ doesn't really answer any questions about the two languages
either.
--
Kenneth P. Turvey <··@squeakydolphin.com>
Artificial Intelligence Algorithms Wiki
http://ai.squeakydolphin.com
Kenneth P. Turvey wrote:
> In article <······················@twister2.libero.it>,
> DaveNlp wrote:
>
>>You try to do a test with OpenLisp, it's seems very very fast..
>>http://christian.jullien.free.fr/
>
>
> How does ISLISP differ from Common Lisp? I tried downloading the spec,
> but the zipped pdf file isn't any good and the URL for the dvi isn't any
> good.
>
> The FAQ doesn't really answer any questions about the two languages
> either.
Did you check out http://www.islisp.info/ ?
Pascal
In article <············@newsreader2.netcologne.de>,
Pascal Costanza wrote:
>
> Did you check out http://www.islisp.info/ ?
Thanks for the link. I looked over the specification and read the FAQ,
but I didn't leave with any real feel for why one would choose ISLISP
over Common Lisp or Common Lisp over ISLISP. I understand that the
ISLISP language is more compact than Common Lisp (this is probably a
good thing), but it is missing some features of the later.
Are there other reasons that ISLISP might be preferable? Is it capable
of generating more efficient code? Is it more elegant in some respect?
--
Kenneth P. Turvey <··@squeakydolphin.com>
Artificial Intelligence Algorithms Wiki
http://ai.squeakydolphin.com
>>>>> On Sat, 1 Nov 2003 22:09:34 -0600, Kenneth P Turvey ("Kenneth") writes:
Kenneth> In article <············@newsreader2.netcologne.de>,
Kenneth> Pascal Costanza wrote:
>>
>> Did you check out http://www.islisp.info/ ?
Kenneth> Thanks for the link. I looked over the specification
Kenneth> and read the FAQ, but I didn't leave with any real
Kenneth> feel for why one would choose ISLISP over Common Lisp
Kenneth> or Common Lisp over ISLISP.
I didn't think ISLISP was widely used; I thought it was a political
response to Common Lisp, so that a few people in some countries could
possibly use something that wasn't a flithy American (ANSI) standard.
Kenneth P. Turvey wrote:
> In article <············@newsreader2.netcologne.de>,
> Pascal Costanza wrote:
>
>>Did you check out http://www.islisp.info/ ?
>
>
> Thanks for the link. I looked over the specification and read the FAQ,
> but I didn't leave with any real feel for why one would choose ISLISP
> over Common Lisp or Common Lisp over ISLISP. I understand that the
> ISLISP language is more compact than Common Lisp (this is probably a
> good thing), but it is missing some features of the later.
>
> Are there other reasons that ISLISP might be preferable? Is it capable
> of generating more efficient code? Is it more elegant in some respect?
I could imagine that it might be a better educational variant of Common
Lisp. In education, a smaller language works probably better, that's
probably why Scheme is generally preferred over Common Lisp in education.
Furthermore, OpenLisp seems to have a good FFI which might make it very
suitable for same applications.
(But this is all just guesswork, I haven't actually tried it.)
Pascal
"Kenneth P. Turvey" <··@geo.premiumservices.yahoo.com> ha scritto nel
messaggio ······················@geo.premiumservices.yahoo.com...
> In article <······················@twister2.libero.it>,
> DaveNlp wrote:
> >
> > You try to do a test with OpenLisp, it's seems very very fast..
> > http://christian.jullien.free.fr/
>
> How does ISLISP differ from Common Lisp? I tried downloading the
spec,
> but the zipped pdf file isn't any good and the URL for the dvi isn't
any
> good.
>
> The FAQ doesn't really answer any questions about the two languages
> either.
>
first you needs to download a free Word copy of OpenLisp language
from here:
http://christian.jullien.free.fr/openlisp.doc.zip
Greetings
DaveNlp
Wang Yin wrote:
> This is not resonable. I hope the LISP program can run only 2 times
> slower than C programs. Can anyone suggest some method to improve the
> efficiency? I've read some of CMU CL's but it doesn't help much.
>
> I wonder if hash tables in CL cost much time? The C program doesn't
> use hash table, but the data structures just got messy without it.
Did you use the TIME function to see if you were consing a lot, or to
narrow down where the time is being spent? Can you post the code?
kenny
--
http://tilton-technology.com
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
On 31 Oct 2003 21:27:03 +0800, Wang Yin <··@wangyin.com> wrote:
> Can anyone suggest some method to improve the efficiency?
Without showing us the code? Very unlikely.
You might also want to try the CMUCL mailing list.
Edi.
Wang Yin <··@wangyin.com> writes:
> This is not resonable. I hope the LISP program can run only 2 times
> slower than C programs. Can anyone suggest some method to improve the
> efficiency? I've read some of CMU CL's but it doesn't help much.
There is a lot of advanced optimization possible with CMU-CL:
http://cvs2.cons.org/ftp-area/cmucl/doc/cmu-user/
http://cvs2.cons.org/ftp-area/cmucl/doc/cmu-user/compiler-hint.html
--
__Pascal_Bourguignon__
http://www.informatimago.com/
On 8548 day of my life Wang Yin wrote:
> Later I inserted some (declare (type ...)) and (proclaim '(optimize
> speed (space 0) (safety 0))) and I use fixnum for the integers and
> '(vector double-float) for coordinate numbers in the defstruct's. And
> I inlined some functions.
BTW, try (declaim (optimize speed (space 0) (safety 0))) or wrap
DECLAIM with proper EVAL-WHEN.
Under CMU CL, I often use
(declaim
(optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0) (space 0)))
statement. Though it doesn't improve speed very much.
--
Ivan Boldyrev
"Assembly of Japanese bicycle require great peace of mind."
From: Thomas A. Russ
Subject: Re: How to improve efficiency of LISP program?
Date:
Message-ID: <ymiu15kx63k.fsf@sevak.isi.edu>
Wang Yin <··@wangyin.com> writes:
> And I improved the program to run in 17s. But with a large input it
> still takes about 40 times longer than the C version.
I wonder how you are getting the large input data into the system.
There are some potential booby traps with input-output routines in
Lisp. The lisp reader often does a lot more work. It is possible that
you are spending a lot of time in the I/O routines of the system.
--
Thomas A. Russ, USC/Information Sciences Institute