From: John S. Rodrigues
Subject: Benchmark LISP vs Python
Date: 
Message-ID: <A1ED890F394E0D9F.AB275346BFA93105.96BB5832DC95BBAF@lp.airnews.net>
Lisp code : (CLISP 2.29)

(defmacro isPrime(num)
        '(and (not (= 0 (mod ,num 2)))
              (not (= 0 (mod ,num 3)))))

(defun listPrimes(limit)
        (do ((primesList nil)
             (i 1 (+ i 1)))
            ((> i limit) (values primesList (length primesList)))
          (if (isPrime i)
            (setf primesList (append primesList
                                     (cons i '()))))))

******************************

Python Code : (Python 2.2)

def isPrime (num) :
	return num%2 != 0 and num%3 != 0


def listPrimes(limit) :
	primesList = []
	for i in range(limit) :
		if(isPrime(i)) :
			primesList.append(i)
	print primesList, len(primesList)


=====================================================================

(listPrimes 100000)

findPrimes(100000)

Very significant difference. Python is much faster. How can I optimize 
my lisp code to run faster/just as fast.

Thanks,
John

From: Carl Shapiro
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <ouyn0q6h837.fsf@panix3.panix.com>
"John S. Rodrigues" <········@airmail.net> writes:

> Very significant difference. Python is much faster. How can I optimize
> my lisp code to run faster/just as fast.

For starters, you can't make comparisons against broken code.  You'll
first need something which actually works.

  (defmacro primep (x)
    (let ((n (gensym)))
      `(let ((,n ,x))
         (and (not (zerop (mod ,n 2)))
              (not (zerop (mod ,n 3)))))))

  (defun find-primes (limit)
    (do ((acc '())
         (len 0)
         (i 0 (1+ i)))
        ((> i limit) (values acc len))
      (when (primep i)
        (push i acc)
        (incf len))))

  (find-primes 100000)

You may also wish to rewrite your Python code to behave similarly to
your Lisp code.

  def isPrime (num) :
    return num%2 != 0 and num%3 != 0

  def listPrimes(limit) :
    primesList = []
    primesLength = 0
    for i in range(limit) :
      if(isPrime(i)) :
        primesList.append(i)
        primesLength = primesLength + 1
    return primesList, primesLength

  listPrimes(100000)

Now for the silly microbenchmarks.

$ time clisp prime.lisp

real    0m0.650s
user    0m0.547s
sys     0m0.018s
$ clisp

[1]> (compile-file "prime.lisp")

Compiling file /u1/home/css/prime.lisp ...

Compilation of file /u1/home/css/prime.lisp is finished.
0 errors, 0 warnings
#P"/u1/home/css/prime.fas" ;
NIL ;
NIL
[2]> (quit)
$ time clisp prime.fas

real    0m0.101s
user    0m0.016s
sys     0m0.002s
$ time python2.2 prime.py

real    0m0.408s
user    0m0.386s
sys     0m0.017s
From: Joseph Dale
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <CIck9.786$Kb3.52659532@newssvr13.news.prodigy.com>
John S. Rodrigues wrote:
> Lisp code : (CLISP 2.29)
> 
> (defmacro isPrime(num)
>        '(and (not (= 0 (mod ,num 2)))
>              (not (= 0 (mod ,num 3)))))
> 
> (defun listPrimes(limit)
>        (do ((primesList nil)
>             (i 1 (+ i 1)))
>            ((> i limit) (values primesList (length primesList)))
>          (if (isPrime i)
>            (setf primesList (append primesList
>                                     (cons i '()))))))
[snip]
> 
> Very significant difference. Python is much faster. How can I optimize 
> my lisp code to run faster/just as fast.

The most obvious change would be not to use append to append the values 
to the end of the list. First of all, append does not destructively 
modify the list, so every time you append something to the end of a 
list, it must make a copy of the entire list to append to. This puts the 
running time of your algorithm at O(n^2), and requires O(n^2) memory to 
be consed and garbage collected (since you are throwing away the old 
list that you copied every time).

On my computer, using nconc instead of append to destructively append to 
the end of the list gets the Lisp version down to using about ten times 
the CPU time of the Python version. However, if I understand correctly, 
nconc must still traverse the entire list every time you want to append 
something to it -- still O(n^2) time, but now you aren't using and 
throwing away O(n^2) memory. We can fix this by simply pushing values 
onto the front of the list in the loop and then (destructively) 
reversing the list before returning it:

(defun listPrimes(limit)
   (do ((primesList nil)
        (i 1 (+ i 1)))
       ((> i limit) (values (nreverse primesList) (length primesList)))
     (if (isPrime i)
	(push i primesList))))

This version takes only about 1 and a half times the CPU time of the 
Python version. I'm using the CLISP implementation, and so far I haven't 
compiled the code. After I do that, the Lisp version uses about 
one-fourth the CPU time of the Python version. And CLISP only compiles 
to bytecode, so this would probably be even faster when compiled to 
native code. I also tried to compile the Python code using the 
py_compile.compile function, but this did not seem to have any effect on 
the speed. Did you try compiling the Python code?


Joe
From: Tibor Simko
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <873crw6gof.fsf@pcdh91.cern.ch>
On Wed, 25 Sep 2002, Joseph Dale wrote:
> I also tried to compile the Python code using the py_compile.compile
> function, but this did not seem to have any effect on the speed. 

You may try using Psyco, as I wrote in another thread.  For the Python
program from Carl Shapiro, Psyco improved the speed by a factor of 5.
But it's still about 5x slower than CLISP, though.

T.
From: Raffael Cavallaro
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <aeb7ff58.0209250604.653648a7@posting.google.com>
"John S. Rodrigues" <········@airmail.net> wrote in message news:<··················································@lp.airnews.net>...

> Very significant difference. Python is much faster. How can I optimize 
> my lisp code to run faster/just as fast.
> 
> Thanks,
> John

You've posted a slow (and as another poster has pointed out,
incorrect) implementation of the prime sieve benchmark.

Roger Corman provides the fastest common lisp prime sieve I've come
across as an example file in his Corman Common Lisp. I've renamed the
function, but otherwise, it's the same as his last version (he
provides several). Note that this function is Copyright Roger Corman
so far as I know, and you need to consult him as to copying, use in
any software, etc. I believe I am within my fair use rights to post a
single defun out of a single file, out of the millions of lines of
code provided with Corman Common Lisp, much as one might legally quote
a sentence or two from a book in instructional materials, etc.


(defun primes (n)
	(declare (fixnum n)(optimize (speed 3)(safety 0)))
	(let* ((a (make-array n :element-type 'bit :initial-element 0))
		   (result (list 2))
		   (root (isqrt n)))
		(declare (fixnum root))
		(do ((i 3 (the fixnum (+ i 2))))
			((>= i n)(nreverse result))
			(declare (fixnum i))
			(progn
				(when (= (sbit a i) 0)
					(push i result)
					(if (< i root)
						(do* ((inc (+ i i))
							  (j (* i i) (the fixnum (+ j inc))))
							 ((>= j n))
							(declare (fixnum j inc))
							(setf (sbit a j) 1))))))))


If you compile this version, I believe you'll see an order of
magnitude better run times than Python. Remember, it's pretty
meaningless to compare short runs - i.e., less than (primes 1000000) 
and include the  time to launch the lisp image. Start the lisp image
first. Compile the defun above,  then try (time (primes 1000000)) and
you'll be very favorably impressed.

If this vesion looks complicated to you, that's because when you're
concerned primarily with speed, you often need to consider bit
twiddling optimizations. Note that the actual "work" of this function
operates on a bit vector, which is a common lisp type that lets you
fiddle with individual bits in memory. Many implementations can
optimize operations on vectors for speed of access and writing. Lisp
lets you get down to that level, but only if you want to or need to.
From: Michael Hudson
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <lky99mutzx.fsf@pc150.maths.bris.ac.uk>
·······@mediaone.net (Raffael Cavallaro) writes:

> If this vesion looks complicated to you, that's because when you're
> concerned primarily with speed, you often need to consider bit
> twiddling optimizations. 

Of course, the posted Python implementation was pretty dumb, too.

I like this one, due to Tim Peters:

def sieve(n):
    if n < 2:
        return []
    limit = int(math.sqrt(n))
    primes = range(1, n+1, 2)
    primes[0] = 0
    n = len(primes)
    for p in primes:
        if not p: continue
        if p <= limit:
            # note that p*p is odd, so no need to subtract 1
            # before shifting right -- same thing in the end
            for i in xrange((p*p)>>1, n, p):
                primes[i] = 0
            continue
        break
    primes[0] = 2
    return primes

(I know of a slightly faster implementation, but it's completely
insane).

It ain't gonna match the lisp one for speed, I'd have thought.

Cheers,
M.

-- 
  BUGS   Never use this function.  This function modifies its first
         argument.   The  identity  of  the delimiting character is
         lost.  This function cannot be used on constant strings.
                                    -- the glibc manpage for strtok(3)
From: Marco Antoniotti
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <y6c65wquk5j.fsf@octagon.valis.nyu.edu>
Michael Hudson <···@python.net> writes:

> ·······@mediaone.net (Raffael Cavallaro) writes:
> 
> > If this vesion looks complicated to you, that's because when you're
> > concerned primarily with speed, you often need to consider bit
> > twiddling optimizations. 
> 
> Of course, the posted Python implementation was pretty dumb, too.
> 
> I like this one, due to Tim Peters:
> 
> def sieve(n):
>     if n < 2:
>         return []
>     limit = int(math.sqrt(n))
>     primes = range(1, n+1, 2)
>     primes[0] = 0
>     n = len(primes)
>     for p in primes:
>         if not p: continue
>         if p <= limit:
>             # note that p*p is odd, so no need to subtract 1
>             # before shifting right -- same thing in the end
>             for i in xrange((p*p)>>1, n, p):
>                 primes[i] = 0
>             continue
>         break
>     primes[0] = 2
>     return primes
> 
> (I know of a slightly faster implementation, but it's completely
> insane).
> 
> It ain't gonna match the lisp one for speed, I'd have thought.

What about this Common Lisp implementation?  :)

;;; -*- Mode: Lisp -*-

(in-package "SETL-USER")

(defun primes (max)
  [n in (range 3 max 2)
     / (not (exist m in (range 3 (min (1- n) (+ 2 (sqrt n))) 2)
                   / (= (mod n m) 0)))])

;;; end of file -- primes-setl.lisp --

It expands into loops and then it is compiled to native code.

I admit I do not know the SERIES package: does anybody have an example
using it?

Cheers

-- 
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group        tel. +1 - 212 - 998 3488
715 Broadway 10th Floor                 fax  +1 - 212 - 995 4122
New York, NY 10003, USA                 http://bioinformatics.cat.nyu.edu
                    "Hello New York! We'll do what we can!"
                           Bill Murray in `Ghostbusters'.
From: Michael Hudson
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <lkr8fbvpaw.fsf@pc150.maths.bris.ac.uk>
Marco Antoniotti <·······@cs.nyu.edu> writes:

> What about this Common Lisp implementation?  :)

Given that googling for your setl code only finds you bragging about
it, it's hard to come up with any sensible comments...

> ;;; -*- Mode: Lisp -*-
> 
> (in-package "SETL-USER")
> 
> (defun primes (max)
>   [n in (range 3 max 2)
>      / (not (exist m in (range 3 (min (1- n) (+ 2 (sqrt n))) 2)
>                    / (= (mod n m) 0)))])
> 
> ;;; end of file -- primes-setl.lisp --
> 
> It expands into loops and then it is compiled to native code.

But, unless your macros are unexpectedly clever, it looks like a
fairly naive algorithm to me.

Cheers,
M.

-- 
  If a train station is a place where a train stops, what's a
  workstation?                            -- unknown (to me, at least)
From: Marco Antoniotti
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <y6c4rc73791.fsf@octagon.valis.nyu.edu>
Michael Hudson <···@python.net> writes:

> Marco Antoniotti <·······@cs.nyu.edu> writes:
> 
> > What about this Common Lisp implementation?  :)
> 
> Given that googling for your setl code only finds you bragging about
> it, it's hard to come up with any sensible comments...

The piece of code essentially shows that you can change the syntax of
Common Lisp in interesting ways.   SetL is an interesting language
with a lot more to it than surface syntax.

> > ;;; -*- Mode: Lisp -*-
> > 
> > (in-package "SETL-USER")
> > 
> > (defun primes (max)
> >   [n in (range 3 max 2)
> >      / (not (exist m in (range 3 (min (1- n) (+ 2 (sqrt n))) 2)
> >                    / (= (mod n m) 0)))])
> > 
> > ;;; end of file -- primes-setl.lisp --
> > 
> > It expands into loops and then it is compiled to native code.
> 
> But, unless your macros are unexpectedly clever, it looks like a
> fairly naive algorithm to me.

Of course the algorithm is naive as it it stated.  As I said, I do not
know SERIES well enough to attempt an implementation.  My
understanding of it is that the intertwined calls of macros would, in
that case, yield something more efficient that the simply algorithm I
gave.


Cheers


-- 
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group        tel. +1 - 212 - 998 3488
715 Broadway 10th Floor                 fax  +1 - 212 - 995 4122
New York, NY 10003, USA                 http://bioinformatics.cat.nyu.edu
                    "Hello New York! We'll do what we can!"
                           Bill Murray in `Ghostbusters'.
From: Bernd Beuster
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <3D914E8F.3040403@epost.de>
John S. Rodrigues schrieb:


> Very significant difference. Python is much faster. How can I optimize 
> my lisp code to run faster/just as fast.

Did you *compile* the Lisp code?

What about CMUCL or other (commercial) native code Lisps?



-- 
Bernd
From: Tim Bradshaw
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <ey3ofam1jz8.fsf@cley.com>
* John S Rodrigues wrote:
> Lisp code : (CLISP 2.29)
> (defmacro isPrime(num)
>         '(and (not (= 0 (mod ,num 2)))
>               (not (= 0 (mod ,num 3)))))

> (defun listPrimes(limit)
>         (do ((primesList nil)
>              (i 1 (+ i 1)))
>             ((> i limit) (values primesList (length primesList)))
>           (if (isPrime i)
>             (setf primesList (append primesList
>                                      (cons i '()))))))

Something like this is probably much faster:

    (declaim (inline isPrime))
    (defun isPrime(num)
      ;; this doesn't actually tell you if NUM is prime
      (declare (type (integer 0 *) num))
      (and (not (= 0 (mod num 2)))
           (not (= 0 (mod num 3)))))

    (defun listPrimes(limit)
      (declare (type (integer 0 *) limit))
      (loop with n = 0
            for i from 1 to limit
            when (isPrime i)
            collect i into primes
            and do (incf n)
            finally (return (values primes n))))

Remember to compile the code.  If you can replace the integer
declarations with fixnum ones you may well do much better.

--tim
From: Petr Swedock
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <86k7lajeof.fsf@blade-runner.mit.edu>
"John S. Rodrigues" <········@airmail.net> writes:

> Lisp code : (CLISP 2.29)
> 
> (defmacro isPrime(num)
>         '(and (not (= 0 (mod ,num 2)))
>               (not (= 0 (mod ,num 3)))))

This is going to miss the first two prime numbers,
2 and 3... and admit numbers that are not prime.

For instance 

 (isprime 25)

T

(isprime 35)

T



Peace,

Petr
From: Bruce Hoult
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <bruce-9E8FE6.19283825092002@copper.ipg.tsnz.net>
In article 
<··················································@lp.airnews.net>,
 "John S. Rodrigues" <········@airmail.net> wrote:

> Lisp code : (CLISP 2.29)
> 
> (defmacro isPrime(num)
>         '(and (not (= 0 (mod ,num 2)))
>               (not (= 0 (mod ,num 3)))))
> 
> (defun listPrimes(limit)
>         (do ((primesList nil)
>              (i 1 (+ i 1)))
>             ((> i limit) (values primesList (length primesList)))
>           (if (isPrime i)
>             (setf primesList (append primesList
>                                      (cons i '()))))))

Change this to:

 (defun listPrimes(limit)
         (do ((primesList nil)
              (i 1 (+ i 1)))
             ((> i limit) (values (nreverse primesList)
                                  (length primesList)))
           (if (isPrime i)
             (setf primesList (cons i primesList)))))

append creates a whole new list every time, so you end up creating 
5,000,000,000 cons cells which need garbage collecting.

This takes 7.7 seconds in CMUCL on my Athlon 700.
After (compile 'listPrimes) it takes 0.03 seconds

Python used 0.8 seconds.

-- Bruce

p.s. I had to fix errors in both the Lisp and the Python
From: Paul Foley
Subject: Re: Benchmark LISP vs Python
Date: 
Message-ID: <m23cry5vf8.fsf@mycroft.actrix.gen.nz>
On Tue, 24 Sep 2002 23:57:20 -0500, John S Rodrigues wrote:

> Lisp code : (CLISP 2.29)
> (defmacro isPrime(num)
>         '(and (not (= 0 (mod ,num 2)))
>               (not (= 0 (mod ,num 3)))))

This only works for numbers between 4 and 24.  [And only if you
replace the quote with a backquote]

But why is it a macro?

> (defun listPrimes(limit)
>         (do ((primesList nil)
>              (i 1 (+ i 1)))
>             ((> i limit) (values primesList (length primesList)))
>           (if (isPrime i)
>             (setf primesList (append primesList
>                                      (cons i '()))))))

> ******************************

> Python Code : (Python 2.2)

> def isPrime (num) :
> 	return num%2 != 0 and num%3 != 0


> def listPrimes(limit) :
> 	primesList = []
> 	for i in range(limit) :
> 		if(isPrime(i)) :
> 			primesList.append(i)
> 	print primesList, len(primesList)


> =====================================================================

> (listPrimes 100000)

> findPrimes(100000)

> Very significant difference. Python is much faster. How can I optimize 
> my lisp code to run faster/just as fast.

What Python calls a "list" is an adjustable vector.  Your Lisp code
has to walk over the result list repeatedly as it keeps appending
things.  A literal translation of your Python code into Lisp (other
than putting a newline between the two values it prints) is

  (defun list-primes (limit)
    (let ((primes-list (make-array 20 :adjustable t :fill-pointer 0)))
      (dotimes (i limit)
        (when (is-prime i)
          (vector-push-extend i primes-list)))
      (print primes-list)
      (print (length primes-list))))

which runs well over a hundred times faster than your Python code,
here.


Using lists, you could write

  (loop for i below limit
     when (is-prime i) collect i)

or

  (do ((primes '())
       (i 1 (1+ i)))
      ((> i limit) (nreverse primes))
    (when (is-prime i)
      (push i primes)))

or whatever; the main cause of slowness in your code is the repeated
list traversal.

-- 
If that makes any sense to you, you have a big problem.
                                      -- C. Durance, Computer Science 234
(setq reply-to
  (concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))