Newbie performance question

dgiaimo

unread,

Nov 9, 2010, 1:34:58 PM11/9/10

to

Hi all,

I am fairly new to Lisp programming and am trying to get a sense of
how to write code performantly. Are there good references online for
general tips in this regard? Also, for a particular example, can
someone tell me why the Lisp code below is so much slower than the C
code that follows it? They are both implementations of the sieve of
Eratosthenes. As far as I understand, they should be doing the same
thing, but the C code runs in around 30 seconds without any
optimization set on the compiler whereas the Lisp code takes half a
day. Is this just due to the fact that the Lisp is interpreted, or am
I missing something important?

;;; Lisp CODE

(format t "Finding primes.~%")

(defvar *memo* (make-array 1000000001 :element-type 'bit :initial-
element 0))

(setf (aref *memo* 0) 1
(aref *memo* 1) 1)

(loop for i from 2 to (sqrt 1000000000)
when (= (aref *memo* i) 0)
do (loop for j from (* i i) to 1000000000 by i
do (setf (aref *memo* j) 1
)
)
)

// C CODE

#include <ctype.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char** argv)
{
int max = 1000000000;

char* nums = malloc(max + 1);

memset(nums, 0, max+1);

nums[0] = 1;
nums[1] = 1;

printf("Finding primes.\n");

for(int i=2; i<=sqrt(max); i++)
{
if(!nums[i])
{
for(int64_t j=((int64_t)i)*((int64_t)i); j<=max; j+=i)
{
nums[j] = 1;
}
}
}

return EXIT_SUCCESS;
}

Thanks,
Dan Giaimo

jos...@lisp.de

unread,

Nov 9, 2010, 2:12:15 PM11/9/10

to

* you need to compile the code

* you need to use a Lisp that compiles to fast code, means usually
that it generates native code

* some implementations can't handle such large arrays
see the variable ARRAY-TOTAL-SIZE-LIMIT

* the Lisp code does not the same as the C code.
Arithmetic in Lisp and C may look similar: (+ a b) and a + b
But in reality these are very different operations.
Lisp arithmetic is generic with automatic overflow to bignums.
It also supports ratios and complex numbers.
If you want to get limited arithmetic, you need to declare that
and in many cases the compiler will generate the same
unsafe code (with silent overflows, etc.) as in C.

Zach Beane

unread,

Nov 9, 2010, 2:14:13 PM11/9/10

to

dgiaimo <dgi...@gmail.com> writes:

> Hi all,
>
> I am fairly new to Lisp programming and am trying to get a sense of
> how to write code performantly. Are there good references online for
> general tips in this regard? Also, for a particular example, can
> someone tell me why the Lisp code below is so much slower than the C
> code that follows it? They are both implementations of the sieve of
> Eratosthenes. As far as I understand, they should be doing the same
> thing, but the C code runs in around 30 seconds without any
> optimization set on the compiler whereas the Lisp code takes half a
> day. Is this just due to the fact that the Lisp is interpreted, or am
> I missing something important?

Special variable access can be slower than lexical variable access. And
compiling the code usually makes it run much faster. I timed this
variation of your code:

(defun primes ()

(format t "Finding primes.~%")

(let ((memo (make-array 1000000001 :element-type 'bit
:initial-element 0)))
(setf (sbit memo 0) 1
(sbit memo 1) 1)

(loop for i from 2 to (sqrt 1000000000)

when (= (sbit memo i) 0)

do (loop for j from (* i i) to 1000000000 by i

do (setf (sbit memo j) 1))))
t)

It runs in about 45 seconds on my laptop with SBCL. SBCL compiles
everything by default, and produces pretty efficient bit-vector code.

Zach

dgiaimo

unread,

Nov 9, 2010, 2:25:45 PM11/9/10

to

On Nov 9, 2:14 pm, Zach Beane <x...@xach.com> wrote:

Using sbcl, even on the code I wrote unchanged helped a lot. I had
been using clisp before. I guess it must not compile the code by
default. Thanks for the pointers.

Thanks a lot,
Dan Giaimo

Thomas A. Russ

unread,

Nov 9, 2010, 6:31:16 PM11/9/10

to

dgiaimo <dgi...@gmail.com> writes:

Compiling often makes a huge difference. Fortunately this is easy to
do, since with a function like PRIMES, you can just do

(compile 'primes)

and then you have compiled code that you can invoke right from the
interactive lisp interface.

Trying this on my machine I get the following. I am using a 64 bit
version of SBCL and CCL, so this all fits in fixnums.

SBCL: Finding primes.
Evaluation took:
33.194 seconds of real time
29.314178 seconds of total run time
(28.651712 user, 0.662466 system)

CLISP: Exceeded fixnum size / array limit size. (24 bits)

CCL: Finding primes.
(PRIMES) took 33.612617 seconds to run
with 2 available CPU cores.
During that period, 29.648820 seconds in user mode
0.695922 seconds in system mode
0.004193 seconds was spent in GC.

These were done with a slightly modified version of Zach's code, adding
type declarations to the loop variables and compiler optimization
settings of (speed 3) (safety 0) (debug 0) (space 0). Interestingly,
this only helped a little in SBCL (5% faster) but made a big difference
for CCL twice as fast.

--
Thomas A. Russ, USC/Information Sciences Institute

Andy Venikov

unread,

Nov 10, 2010, 9:19:06 AM11/10/10

to

On 11/9/2010 6:31 PM, Thomas A. Russ wrote:

> These were done with a slightly modified version of Zach's code, adding
> type declarations to the loop variables and compiler optimization
> settings of (speed 3) (safety 0) (debug 0) (space 0).

Could you post the complete code?
I'm also coming from performance critical point of view and sometimes
worry about Lisp performance. I'd like to learn when and how to add the
type declarations to make things run faster.

Thanks,
Andy.

Thomas A. Russ

unread,

Nov 10, 2010, 1:30:05 PM11/10/10

to

Andy Venikov <swojch...@gmail.com> writes:

(defun primes ()
(declare (optimize (speed 3) (safety 0) (debug 0) (space 0)))

(format t "Finding primes.~%")
(let ((memo (make-array 1000000001 :element-type 'bit
:initial-element 0)))
(setf (sbit memo 0) 1
(sbit memo 1) 1)

(loop for i fixnum from 2 to (isqrt 1000000000)

when (= (sbit memo i) 0)

do (loop for j fixnum from (the fixnum (* i i)) to 1000000000 by i

do (setf (sbit memo j) 1)))

;; Note, this should probably return MEMO, but for
;; algorithm performance testing, we return T to
;; avoid having the REPL print a big array.
t))