The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Beginner question: performance problems with a simple program
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 Messages 1 - 25 of 605 Newer >

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Dec 26 2001, 6:28 am
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Wed, 26 Dec 2001 12:26:17 +0100
Local: Wed, Dec 26 2001 6:26 am
Subject: Beginner question: performance problems with a simple program
Hi all,

I've just started learning Common Lisp and as a simple exercise of what I've
learned so far I thought I might write a program that allows one to play around
a bit with Collatz sequences.
I thus produced the following program:

(defun coll-step (n)
(if (= (mod n 2) 0) (/ n 2) (+ 1 (* 3 n))))
(defun coll-max (n)
"Computes the maximum of the collatz sequence starting with its argument"
(coll-max-iter n n n))
(defun coll-max-iter (n a b)
(if (< n a) b (coll-max-iter (coll-step n) a (max b n))))
(defun max-lst (n)
"prints out all n up to its argument which have the property that
coll-max(m)>=coll-max(n) ==> m >= n"
(max-lst-iter 3 n (coll-max 3)))
(defun max-lst-iter (n range mx)
(if (> n range) mx
(max-lst-iter (+ n 4) range (next n (coll-max n) mx))))
(defun next (n am mx)
(if (> am mx) (toscreen n am) mx))
(defun toscreen (n am)
(write (list n am))
am)

The program works fine, except for the fact that I am not feeling well about
its performance speed-wise. Does anyone on this group have any tips to offer
regarding improvements in this respect? (I am working with Allegro Common
Lisp).

Regards,
Janosch.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 26 2001, 10:43 am
Newsgroups: comp.lang.lisp
From: Barry Margolin <bar...@genuity.net>
Date: Wed, 26 Dec 2001 15:43:30 GMT
Local: Wed, Dec 26 2001 10:43 am
Subject: Re: Beginner question: performance problems with a simple program
In article <a0cc4p\$u16\$0...@news.t-online.com>,

Janosch Zwerensky <zweren...@nahoo.de> wrote:
>Hi all,

>I've just started learning Common Lisp and as a simple exercise of what I've
>learned so far I thought I might write a program that allows one to play around
>a bit with Collatz sequences.
>I thus produced the following program:

>(defun coll-step (n)
>  (if (= (mod n 2) 0) (/ n 2) (+ 1 (* 3 n))))

Why not use EVENP here?

>The program works fine, except for the fact that I am not feeling well about
>its performance speed-wise. Does anyone on this group have any tips to offer
>regarding improvements in this respect? (I am working with Allegro Common
>Lisp).

Did you remember to compile it?

--
Barry Margolin, bar...@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 26 2001, 4:46 pm
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Wed, 26 Dec 2001 22:45:48 +0100
Local: Wed, Dec 26 2001 4:45 pm
Subject: Re: Beginner question: performance problems with a simple program
Hi,

>>(defun coll-step (n)
>>  (if (= (mod n 2) 0) (/ n 2) (+ 1 (* 3 n))))

>Why not use EVENP here?

Using evenp here doesn't hurt nor help, performancewise, here. I agree though
that evenp looks more natural.

>Did you remember to compile it?

Of course I did. I might have little experience with lisp so far, but I am not
stupid. Still, the program seems to be around 10 times slower than an
algorithmically equivalent C program, which is a larger speed loss than what I
would have expected just from Lisp doing BigInteger arithmetics vs. the long
long int calculations one does in C.

Regards,
Janosch.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 26 2001, 5:24 pm
Newsgroups: comp.lang.lisp
From: Barry Margolin <bar...@genuity.net>
Date: Wed, 26 Dec 2001 22:23:59 GMT
Local: Wed, Dec 26 2001 5:23 pm
Subject: Re: Beginner question: performance problems with a simple program
In article <a0dgeb\$cga\$0...@news.t-online.com>,

Janosch Zwerensky <zweren...@nahoo.de> wrote:
>Hi,

>>>(defun coll-step (n)
>>>  (if (= (mod n 2) 0) (/ n 2) (+ 1 (* 3 n))))

>>Why not use EVENP here?

>Using evenp here doesn't hurt nor help, performancewise, here. I agree though
>that evenp looks more natural.

I didn't think it would, it was just a style comment.

>>Did you remember to compile it?

>Of course I did. I might have little experience with lisp so far, but I am not
>stupid.

I never said you were.  There have been plenty of times when people posted
questions about performance and it turned out that they weren't compiling,
so most of the problem was in the interpreter's overhead.  It's not
stupidity, just inexperience.

>     Still, the program seems to be around 10 times slower than an
>algorithmically equivalent C program, which is a larger speed loss than what I
>would have expected just from Lisp doing BigInteger arithmetics vs. the long
>long int calculations one does in C.

Declarations can often help with heavily numeric code.  Without them, lots
of runtime type dispatching has to take place.  Although if you can't limit
your numbers to fixnums, it may still have to do type checks to switch
between fixnum and bignum versions of functions.

Try using the TIME macro to see if you're consing alot.  If your Lisp
implementation has a profiling feature, try using that to see where the
bottleneck is.

--
Barry Margolin, bar...@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 26 2001, 9:29 pm
Newsgroups: comp.lang.lisp
Date: Thu, 27 Dec 2001 02:29:13 GMT
Local: Wed, Dec 26 2001 9:29 pm
Subject: Re: Beginner question: performance problems with a simple program
What's the opposite of a flame? Barry Margolin once again demonstrates how
to post respectfully & irenically. Thanks, Barry for your fine example.

Will Fitzgerald

"Barry Margolin" <bar...@genuity.net> wrote in message

news:36sW7.19\$Mv6.41773@burlma1-snr2...

group.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 26 2001, 10:52 pm
Newsgroups: comp.lang.lisp
From: David Sletten <slytob...@home.com>
Date: Thu, 27 Dec 2001 03:52:22 GMT
Local: Wed, Dec 26 2001 10:52 pm
Subject: Re: Beginner question: performance problems with a simple program

Will Fitzgerald wrote:
> What's the opposite of a flame? Barry Margolin once again demonstrates how
> to post respectfully & irenically. Thanks, Barry for your fine example.

> Will Fitzgerald

Would that be a 'douse'? Or is it 'Preparation H' to prevent a
hemorrhoid from flaring up?

David Sletten

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 27 2001, 4:34 am
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Thu, 27 Dec 2001 10:33:58 +0100
Local: Thurs, Dec 27 2001 4:33 am
Subject: Re: Beginner question: performance problems with a simple program
Hi,

>(...) There have been plenty of times when people posted
>questions about performance and it turned out that they weren't compiling,
>so most of the problem was in the interpreter's overhead.

Ok, I didn't know that.
Call it, uhm, inexperience regarding this newsgroup ;).

>>        Still, the program seems to be around 10 times slower than an
>>algorithmically equivalent C program, which is a larger speed loss than what
I
>>would have expected just from Lisp doing BigInteger arithmetics vs. the long
>>long int calculations one does in C.

>Declarations can often help with heavily numeric code.

I know this, since I have done programming in Scheme before.
I assume, then, that I can't do much about the performance of my program if
Lisp doesn't have a number type that suits my problem better than general
bignums (it is my understanding that this was the case in MIT-Scheme)?

>(...)  Although if you can't limit

Exactly my problem :(.

> it may still have to do type checks to switch
>between fixnum and bignum versions of functions.

>Try using the TIME macro to see if you're consing alot.  If your Lisp
>implementation has a profiling feature, try using that to see where the
>bottleneck is.

I think I know where the bottleneck is anyway, but I'll nonetheless follow that

Regards,
Janosch.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 27 2001, 1:57 pm
Newsgroups: comp.lang.lisp
From: cbbro...@acm.org
Date: Thu, 27 Dec 2001 18:56:39 GMT
Local: Thurs, Dec 27 2001 1:56 pm
Subject: Re: Beginner question: performance problems with a simple program

zweren...@nahoo.de (Janosch Zwerensky) writes:
> >>(defun coll-step (n)
> >>  (if (= (mod n 2) 0) (/ n 2) (+ 1 (* 3 n))))

> >Why not use EVENP here?

> Using evenp here doesn't hurt nor help, performancewise, here. I agree though
> that evenp looks more natural.

> >Did you remember to compile it?
> Of course I did. I might have little experience with lisp so far,
> but I am not stupid.

Can you tell a bit more about what you did to accomplish this?  I'm
not usually considered stupid, either, but have made the mistake of
_believing_ I was running a compiled copy, when reality was that I
wasn't...

Some mistakes are regrettably easy to make, and if you think I'm
calling you "stupid," the moniker would have to apply just as much to
myself...

> Still, the program seems to be around 10 times slower than an
> algorithmically equivalent C program, which is a larger speed loss
> than what I would have expected just from Lisp doing BigInteger
> arithmetics vs. the long long int calculations one does in C.

I'd hope for a smaller factor than 10 for this, though I'd not expect
1...
--
(concatenate 'string "cbbrowne" "@acm.org")
http://www.ntlug.org/~cbbrowne/x.html
"It's a pretty rare beginner who isn't clueless.  If beginners weren't
clueless, the infamous Unix learning cliff wouldn't be a problem."
-- david parsons

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 27 2001, 2:48 pm
Newsgroups: comp.lang.lisp
From: Erik Naggum <e...@naggum.net>
Date: Thu, 27 Dec 2001 19:48:17 GMT
Local: Thurs, Dec 27 2001 2:48 pm
Subject: Re: Beginner question: performance problems with a simple program
* Janosch Zwerensky
| The program works fine, except for the fact that I am not feeling well
| about its performance speed-wise.  Does anyone on this group have any
| tips to offer regarding improvements in this respect?  (I am working with
| Allegro Common Lisp).

Evaluate (excl::explain-compiler-settings) and turn on the various
:explain options.  The amount of output even exceeds CMUCL at its worst,
but it can be very helpful in realizing when and how to declare stuff.

What were the types of variables in the C version?  How much time does a
function call usually take?  Do you have an example?

///
--
The past is not more important than the future, despite what your culture
has taught you.  Your future observations, conclusions, and beliefs are
more important to you than those in your past ever will be.  The world is
changing so fast the balance between the past and the future has shifted.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 27 2001, 3:01 pm
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Thu, 27 Dec 2001 21:00:26 +0100
Local: Thurs, Dec 27 2001 3:00 pm
Subject: Re: Beginner question: performance problems with a simple program
Hi,

>Can you tell a bit more about what you did to accomplish this?  I'm
>not usually considered stupid, either, but have made the mistake of
>_believing_ I was running a compiled copy, when reality was that I
>wasn't.

If you're saying here that ACL doesn't necessarily compile a lisp program
when one tells it to do just that, I *might* be guilty of having done such a
mistake. I wouldn't be sad if that were the case, since I'd probably get a
good performance boost then by finally doing a compilation ;).
compiled functions indeed.

..

>Some mistakes are regrettably easy to make, and if you think I'm
>calling you "stupid," the moniker would have to apply just as much to
>myself...

I agree it was stupid of me to use the word "stupid" in that context.

>I'd hope for a smaller factor than 10 for this, though I'd not expect
>1...

The really bad thing is that this factor of ten seems to go up when you
increase the values given to max-lst. Probably I'm doing something badly
wrong thus.. :(

Regards,
Janosch.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 27 2001, 3:13 pm
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Thu, 27 Dec 2001 21:12:04 +0100
Local: Thurs, Dec 27 2001 3:12 pm
Subject: Re: Beginner question: performance problems with a simple program
Hi,

> (...)
>  What were the types of variables in the C version?  How much time does a
>  function call usually take?  Do you have an example?

First, here's the C program I used:

#include <stdio.h>

int main(void)
{   long int nmax=0;

int new_max = 0;
long long a, amax = 0;
scanf("%d",&nmax);

for (int n = 3; n <= nmax; n=n+4)
{
a = n;

while (a >= n)
{
if (a&1)
{
a = 3*a + 1;

if (a > amax)
{
amax = a;

if (!new_max) new_max = 1;
}
}
else
{
a = a >> 1;
}
}

if (new_max)
{
new_max = 0;

printf("%d : %e\n", n, (double) amax);
}

}

return 0;
}

On my machine and compiled with lcc-win32, this takes around 0.6 seconds to do
the equivalent of evaluating max-lst(1000000), which in turn takes just under 6
seconds on my machine under allegro common lisp. The number type I'm using in C
is long long, which happens to go just high enough for this application and
reasonable input values.

Regards,
Janosch.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 27 2001, 3:35 pm
Newsgroups: comp.lang.lisp
From: Barry Margolin <bar...@genuity.net>
Date: Thu, 27 Dec 2001 20:35:14 GMT
Local: Thurs, Dec 27 2001 3:35 pm
Subject: Re: Beginner question: performance problems with a simple program
In article <a0fvaj\$bah\$0...@news.t-online.com>,

Janosch Zwerensky <zweren...@nahoo.de> wrote:
>Hi,

>> (...)
>>  What were the types of variables in the C version?  How much time does a
>>  function call usually take?  Do you have an example?

>First, here's the C program I used:

What happens if you do a more straight-forward translation into Lisp,
i.e. use iteration rather than recursion?  Or what happens if you recode
the C program to use lots of separate functions and recursion, rather than
a single function with iteration?

If the recursion gets very deep, you could be taking more page faults on
the stack.  Iterative solutions don't have this problem.  Are you assuming
tail-recursion elimination in the Lisp version?  Lisp isn't Scheme, and
many Lisp implementations don't do tail-call optimization, or they only do
them with specific optimization settings enabled.

>On my machine and compiled with lcc-win32, this takes around 0.6 seconds to do
>the equivalent of evaluating max-lst(1000000), which in turn takes just under 6
>seconds on my machine under allegro common lisp. The number type I'm using in C
>is long long, which happens to go just high enough for this application and
>reasonable input values.

There's a big difference between C's long-long arithmetic and Lisp's bignum
arithmetic.  Lisp has to be prepared for the values to get arbitrarily
large, so it has to use more general algorithms that can handle any
length.  C can generate much simpler code because it knows exactly how many
bytes the long-long values take up.  It's hard to avoid some extra overhead
from this generality, although a factor of 10 seems unlikely.

What happens if you change both programs to use double-precision floating
point?

Maybe it's a combination of the bignum arithmetic and the recursion
vs. iteration difference.

--
Barry Margolin, bar...@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 27 2001, 4:08 pm
Newsgroups: comp.lang.lisp
From: t...@famine.OCF.Berkeley.EDU (Thomas F. Burdick)
Date: 27 Dec 2001 13:08:27 -0800
Local: Thurs, Dec 27 2001 4:08 pm
Subject: Re: Beginner question: performance problems with a simple program

I don't remember Scheme having declarations.

> I assume, then, that I can't do much about the performance of my program if
> Lisp doesn't have a number type that suits my problem better than general
> bignums (it is my understanding that this was the case in MIT-Scheme)?

> >(...)  Although if you can't limit

> Exactly my problem :(.

If your calculation can be done without using a bignum-like facility
able to do it without bignums.  This is very implementation-dependant,
but then optimizing numerics is in any language.  long long ints are
64-bit integers, right?  Using block compilation, you should be able
to do what you want using CMUCL, I think.  It might need some messing
with the compiler, but I think you should be able to do what you want
without bignums.

--
/|_     .-----------------------.
,'  .\  / | No to Imperialist war |
,--'    _,'   | Wage class war!       |
/       /      `-----------------------'
(   -.  |
|     ) |
(`-.  '--.)
`. )----'

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 27 2001, 4:10 pm
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Thu, 27 Dec 2001 22:09:48 +0100
Local: Thurs, Dec 27 2001 4:09 pm
Subject: Re: Beginner question: performance problems with a simple program
Hi,

>If the recursion gets very deep, you could be taking more page faults on
>the stack.  Iterative solutions don't have this problem.  Are you assuming
>tail-recursion elimination in the Lisp version?

Yes, I did assume that. If lisp doesn't do this here, I indeed ought to have a
problem. I will build a more iterative version of my lisp program and see if
and what happens :).
Thanks anyway for bringing up this point!

>There's a big difference between C's long-long arithmetic and Lisp's bignum
>arithmetic.

I'm aware of that and for that reason alone I wouldn't be surprised if Lisp
would be significantly slower for this problem than C. Still, a factor of ten
seemed (possibly) excessive to me if nothing else went wrong.

>What happens if you change both programs to use double-precision floating
>point?

I already tried it for the Lisp program, and it didn't help much,
performance-wise. Could it be the case that Lisp is converting those doubles to
bignums when doing the evenp test? If so, I could imagine that this might be
time-consuming.
Anyway, I will try to see what happens to the C program if I have it compute
with doubles.
Thanks again for all that input,

Janosch.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 27 2001, 7:10 pm
Newsgroups: comp.lang.lisp
From: t...@famine.OCF.Berkeley.EDU (Thomas F. Burdick)
Date: 27 Dec 2001 16:10:53 -0800
Local: Thurs, Dec 27 2001 7:10 pm
Subject: Re: Beginner question: performance problems with a simple program

I'd expect a Lisp version to run very close to C, so, yes, this is
excessive.

> >What happens if you change both programs to use double-precision floating
> >point?

> I already tried it for the Lisp program, and it didn't help much,
> performance-wise. Could it be the case that Lisp is converting those
> doubles to bignums when doing the evenp test? If so, I could imagine
> that this might be time-consuming.  Anyway, I will try to see what
> happens to the C program if I have it compute with doubles.  Thanks
> again for all that input,

CL's evenp is only defined for integers, for obvious reasons (is
5.999999999 even?).

Anyway, I rewrote your program using LOOP and type declarations:

(defun iterative-max-list (range)
(declare (type (unsigned-byte 64) range))
(flet ((coll-max (a)
(loop for n of-type (unsigned-byte 64) = a
then (if (evenp n) (floor n 2) (1+ (* 3 n)))
for b of-type (unsigned-byte 64) = n then (max b n)
until (< n a)
finally (return (max b n)))))
(loop with max of-type (unsigned-byte 64) = (coll-max 3)
for n of-type (unsigned-byte 64) from 3 to range by 4
for am of-type (unsigned-byte 64) = max then (coll-max n)
when (> am max)
do (princ (list n am))
(setf max am)
finally (return max))))

I compiled both versions in CMUCL with
(optimize (speed 3) (safety 1) (compilation-speed 0) (space 0))
and your C version with gcc.

On my Celeron 500 under linux:

"echo 1000000 | ./max_list", compiled with gcc -O
Min: 0.273s
Max: 0.721s
Mean: 0.48250000000000004s

"echo 1000000 | ./max_list", compiled with gcc -O3
Min: 0.45s
Max: 0.628s
Mean: 0.5326s

(iterative-max-list 1000000)
Min: 0.84s
Max: 0.85s
Mean: 0.85s

(max-lst 1000000)
Min: 2.14s
Max: 2.17s
Mean: 2.17s

Each test was run 11 times, and only counted the last 10 runs.  So,
counting only the best versions in C and Lisp:

Min: 311.11% of C
Max: 118.06% of C
Mean: 177.08% of C

It could be better, but it's not too bad.  And certainly better than
1000% :-).  Also, changing that type declaration to integer instead of
(unsigned-byte 64) runs at 150% of the long-long-equivalent version,
which is an option you don't have in C :-).  Also, be sure to bind
*print-pretty* to nil when you run the Lisp version or it might spend
a lot of time formatting its output.

--
/|_     .-----------------------.
,'  .\  / | No to Imperialist war |
,--'    _,'   | Wage class war!       |
/       /      `-----------------------'
(   -.  |
|     ) |
(`-.  '--.)
`. )----'

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 28 2001, 8:19 am
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Fri, 28 Dec 2001 14:16:58 +0100
Local: Fri, Dec 28 2001 8:16 am
Subject: Re: Beginner question: performance problems with a simple program

>I don't remember Scheme having declarations.

MIT-Scheme allows one to declare a few things, although it isn't comparable to
CL in that respect. It does have, however, specialized operations for fixnums,
the use of which of course leads to big speedups when possible.

Regards,
Janosch

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 28 2001, 8:25 am
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Fri, 28 Dec 2001 14:24:21 +0100
Local: Fri, Dec 28 2001 8:24 am
Subject: Re: Beginner question: performance problems with a simple program
Hi,

I've written my own iterative version of my program in the meantime. It's not
nearly as fast as yours, because I didn't put in the appropriate declarations,
but it is significantly faster than my first try nonetheless.
On my machine and under Allegro Common Lisp, your code seems to be around 3.5
times slower than the C program. I guess the difference to your measurements
can be attributed to me having used another compiler than you; I probably ought
to finally get me Linux and CMUCL ;)...

Greetings,
Janosch Zwerensky.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 28 2001, 1:09 pm
Newsgroups: comp.lang.lisp
From: k...@ashi.footprints.net (Kaz Kylheku)
Date: Fri, 28 Dec 2001 18:08:52 GMT
Local: Fri, Dec 28 2001 1:08 pm
Subject: Re: Beginner question: performance problems with a simple program

In article <a0hrca\$3ku\$0...@news.t-online.com>, Janosch Zwerensky wrote:

>>I don't remember Scheme having declarations.

>MIT-Scheme allows one to declare a few things, although it isn't comparable to
>CL in that respect. It does have, however, specialized operations for fixnums,

MIT Scheme is not comparable to CL because it is an *implementation*,
whereas CL is an internationally standardized programming *language*.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 28 2001, 5:52 pm
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Fri, 28 Dec 2001 23:50:12 +0100
Local: Fri, Dec 28 2001 5:50 pm
Subject: Re: Beginner question: performance problems with a simple program
Hi,

I've done a few minor changes on your program now, which seem to give a speedup
of an additional ten percent on my system :)... :

(defun iterative-max-list (range)
(declare (type (unsigned-byte 64) range))
(flet ((coll-max (a)
(let* ((b a))
(loop for n of-type (unsigned-byte 64) = a
then (if (evenp n) (floor n 2) (progn
(setf x (1+ (* 3
n)))
(setf b (max x b))
(floor x 2)))
for x of-type (unsigned-byte 64) = a
until (< n a)
finally (return (max b n))))))
(loop with max of-type (unsigned-byte 64) = (coll-max 3)
for n of-type (unsigned-byte 64) from 3 to range by 4
for am of-type (unsigned-byte 64) = max then (coll-max n)
when (> am max)
do (princ (list n am))
(setf max am)
finally (return max))))

I don't think that what I did here looks very elegant. If someone has something
better to offer, I'd be glad to see it.

Regards,
Janosch.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 28 2001, 6:07 pm
Newsgroups: comp.lang.lisp
From: e...@agharta.de (Dr. Edmund Weitz)
Date: Sat, 29 Dec 2001 00:07:02 +0100
Local: Fri, Dec 28 2001 6:07 pm
Subject: Re: Beginner question: performance problems with a simple program

I think the (FLOOR X 2) part isn't necessary (or even wrong), so it should be:

(defun iterative-max-list (range)
(declare (type (unsigned-byte 64) range))
(flet ((coll-max (a)
(let* ((b a))
(loop for n of-type (unsigned-byte 64) = a
then (if (evenp n)
(floor n 2)
(prog1
(setf x (1+ (* 3 n)))
(setf b (max x b))))
for x of-type (unsigned-byte 64) = a
until (< n a)
finally (return (max b n))))))
(loop with max of-type (unsigned-byte 64) = (coll-max 3)
for n of-type (unsigned-byte 64) from 3 to range by 4
for am of-type (unsigned-byte 64) = max then (coll-max n)
when (> am max)
do (princ (list n am))
(setf max am)
finally (return max))))

Edi.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 28 2001, 8:23 pm
Newsgroups: comp.lang.lisp
From: e...@agharta.de (Dr. Edmund Weitz)
Date: 29 Dec 2001 02:23:02 +0100
Local: Fri, Dec 28 2001 8:23 pm
Subject: Re: Beginner question: performance problems with a simple program
e...@agharta.de (Dr. Edmund Weitz) writes:

Or maybe

(defun iterative-max-list (range)
(declare (type (unsigned-byte 64) range))
(loop with max of-type (unsigned-byte 64) = 0
for a of-type (unsigned-byte 64) from 3 to range by 4
for am of-type (unsigned-byte 64) = max
then (let ((n a))
(declare (type (unsigned-byte 64) n))
(loop if (evenp n)
do (setq n (floor n 2))
else
maximize (setq n (1+ (* 3 n)))
until (< n a)))
when (> am max)
do (princ (list a
(setf max am)))
finally (return max)))

or, if you're only interested in the maximum value,

(defun iterative-max-list (range)
(declare (type (unsigned-byte 64) range))
(loop for a of-type (unsigned-byte 64) from 3 to range by 4
for am of-type (unsigned-byte 64) = 0
then (let ((n a))
(declare (type (unsigned-byte 64) n))
(loop if (evenp n)
do (setq n (floor n 2))
else
maximize (setq n (1+ (* 3 n)))
until (< n a)))
maximize am))

I have to add that I wasn't able to get ratios as good as Thomas
F. Burdick's on my machine (CMUCL 18c, P3 850, 256 MB RAM, Linux
2.4.10) - even with the same compilation options and with
*PRINT-PRETTY* set to NIL. The C program - compiled with -O3 - was
about 3 times as fast. If I compared the last version with a modified
C program that also only prints the final result it got even worse:
The C program was about 5 to 6 times as fast as CMUCL.

On the other hand, CMUCL was significantly faster than AllegroCL, ECL,
or LispWorks - which didn't surprise me very much...

Edi.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 28 2001, 11:32 pm
Newsgroups: comp.lang.lisp
From: t...@famine.OCF.Berkeley.EDU (Thomas F. Burdick)
Date: 28 Dec 2001 20:32:54 -0800
Local: Fri, Dec 28 2001 11:32 pm
Subject: Re: Beginner question: performance problems with a simple program
e...@agharta.de (Dr. Edmund Weitz) writes:

BTW, when reading this, I just noticed that range and a are both
fixnums.  Of course, that will probably only make a couple percent
difference.

> I have to add that I wasn't able to get ratios as good as Thomas
> F. Burdick's on my machine (CMUCL 18c, P3 850, 256 MB RAM, Linux
> 2.4.10) - even with the same compilation options and with
> *PRINT-PRETTY* set to NIL. The C program - compiled with -O3 - was
> about 3 times as fast. If I compared the last version with a modified
> C program that also only prints the final result it got even worse:
> The C program was about 5 to 6 times as fast as CMUCL.

For whatever reason, CMUCL seems to emit really good code (relative to
gcc) for my Celeron.  I have no idea if CMUCL's code is for whatever
reason especially well optimized for Celerons or if gcc is especially

> On the other hand, CMUCL was significantly faster than AllegroCL, ECL,
> or LispWorks - which didn't surprise me very much...

Yeah, Python really shines when it goes to work on numeric code.  If
it new how to open code a few operations on 64-bit words (say as a
pair of 32-bit words), it could probably do a lot better here.

--
/|_     .-----------------------.
,'  .\  / | No to Imperialist war |
,--'    _,'   | Wage class war!       |
/       /      `-----------------------'
(   -.  |
|     ) |
(`-.  '--.)
`. )----'

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 29 2001, 3:37 am
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Sat, 29 Dec 2001 09:35:14 +0100
Local: Sat, Dec 29 2001 3:35 am
Subject: Re: Beginner question: performance problems with a simple program

>I think the (FLOOR X 2) part isn't necessary (or even wrong), so it should be:

If n isn't even, x:=3n+1 must be an even number. Therefore, in this case I know
that I'm going to divide that number by two in the next step anyway and thus
doing it right away saves me an unnecessary evenp test.
Why do you think that I might have done something wrong here?

Regards,
Janosch.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 29 2001, 3:58 am
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Sat, 29 Dec 2001 09:57:22 +0100
Local: Sat, Dec 29 2001 3:57 am
Subject: Re: Beginner question: performance problems with a simple program
Hi,

>I have to add that I wasn't able to get ratios as good as Thomas
>F. Burdick's on my machine (CMUCL 18c, P3 850, 256 MB RAM, Linux
>2.4.10) - even with the same compilation options and with
>*PRINT-PRETTY* set to NIL. The C program - compiled with -O3 - was

with this version of the C program:

#include <stdio.h>

int main(void)
{   long int nmax=0;

int new_max = 0;
long long a, amax = 0;
nmax=1000000;
// scanf("%d",&nmax);

for (int n = 3; n <= nmax; n=n+4)
{
a = n;

while (a >= n)
{
if (a&1)
{
a = 3*a + 1;

if (a > amax)
{
amax = a;

if (!new_max) new_max = 1;
}
a=a >> 1;         }
else
{
a = a >> 1;
}
}

if (new_max)
{
new_max = 0;

printf("%d : %e\n", n, (double) amax);
}

}

return 0;
}

compiled with lcc-win32, I get a ratio of just under five versus the version of
the lisp program I posted recently (I get a runtime of 0.5 seconds on my
machine for C vs. 2.35 seconds for Lisp).
What do you get here with CMUCL?

Regards,
Janosch.

To post a message you must first join this group.
You do not have the permission required to post.
More options Dec 29 2001, 7:43 am
Newsgroups: comp.lang.lisp
From: zweren...@nahoo.de (Janosch Zwerensky)
Date: Sat, 29 Dec 2001 13:41:03 +0100
Local: Sat, Dec 29 2001 7:41 am
Subject: Re: Beginner question: performance problems with a simple program
Hi again,

I just compared the two programs again, doing the equivalent of evaluating
(iterative-max-list 100000000) in both Lisp and C. I get runtimes of 746
seconds for Lisp versus 33.5 seconds for C, which is a 22:1 disadvantage for
Lisp :(...

Regards,
Janosch.