Why is counting to a billion in lisp so slow?

Question

(defun billion-test () 
  (setq i 0) 
  (loop while (< i 100) do 
    (setq i (+ i 1)))) 
(billion-test) 
(print "done")

I have the above Lisp code that simply loops to one billion. The problem is it is really
slow. Slower than any trivial program I have ever written. These are the times it took to
run with the intepreters I have(gcl and clisp).

                       Compiled  Uncompiled
GNU Common Lisp(gcl)    270-300s  900-960s
Clisp                   280-300s  960-1647s

I used this Python code to time the time for Clisp and an approximated using the system time
with gcl since you can't run it from the command prompt.

import sys
import time
import os

start=time.time()
os.system(" ".join(sys.argv[1:]))
stop=time.time()

print "\n%.4f seconds\n"%(stop-start)

Here are the comparison with while loops from other languages:

Kawa scheme     220.3350s
Petite chez     112.827s
C#              1.9130s
Ruby            31.045s
Python          116.8600s        113.7090s(optimized)
C               2.8240s          0.0150s(optimized)
lua             84.6970s

My assumption is that loop while <condition> do is the Lisp equivalent of a while
loop. I have some doubts about those 1647s(25+ min), I was watching something at that
time and it might have slowed the execution, but by almost 800s? I don't know.
These results are hard to believe. According to Norvig Lisp
is 3 to 85 times faster than Python. Judging from what I got, the most logical
explanation for such slow execution is that Clisp and gcl in Windows have some kind
of bug that slows down large iterations. How, you ask, I don't know? Sooo, my question is, why so slow?
Is anybody else getting something like this?

UPDATE 1:
I ran Joswigs's program and got these results:

      compiled   uncompiled
gcl    0.8s       12mins
clisp  5mins      18mins

gcl compiled the program fine, clisp however gave this warning:

;; Compiling file C:\mine\.cl\test.cl ...
WARNING: in BILLION-TEST in lines 1..8 : FIXNUM-SAFETY is not a 
valid OPTIMIZE quality.
 0 errors, 1 warning
;; Wrote file C:\mine\.cl\test.fas

     ;; clisp
     [2]> (type-of 1000000000)
     (INTEGER (16777215))

     ;;gcl
     (type-of 1000000000)
      FIXNUM

Guess that could be the reason it took more than a minute.

UPDATE 2:
I thought I would give it another try with another implementation just to confirm
that it's really the bignum comparison that slowing it down. I obtained sbcl
for windows and ran the program again:

 * (print most-positive-fixnum)
   536870911

 * (compile-file "count-to-billion.cl")
   ; compiling file "C:/mine/.cl/count-to-billion.cl"
   (written 09 OCT 2013 04:28:24 PM):
   ; compiling (DEFUN BILLION-TEST ...)
   ; file: C:/mine/.cl/count-to-billion.cl
   ; in: DEFUN BILLION-TEST
   ;     (OPTIMIZE (SPEED 3) (SAFETY 0) (DEBUG 0) (FIXNUM-SAFETY 0))
   ;
   ; caught WARNING:
   ;   Ignoring unknown optimization quality FIXNUM-SAFETY in:
   ;    (OPTIMIZE (SPEED 3) (SAFETY 0) (DEBUG 0) (FIXNUM-SAFETY 0))

 * (load "count-to-billion")

I wish I could tell you how long it took but I never saw the end of it. I waited for
2 hours, watched an episode of Vampire Diaries(hehe) and it still hadn't finished.
I was expecting it to be faster than Clisp since its MOST-POSITIVE-FIXNUM is, well, more
positive. I'm vouching for the slow implementation point because only gcl could pull
off the less than one minute run.

Running Rörd's code with gcl:

(time (loop with i = 0 while (< i 1000000000) do (incf i))) 

gcl with Rords's code:
>(load "count-to-billion.cl")
Loading count-to-billion.cl
real-time : 595.667 secs
run time : 595.667 secs

>(compile-file "count-to-billion.cl")
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling count-to-billion.cl.
#p"count-to-billion.o"

>(load "count-to-billion")
Loading count-to-billion.o
real time : 575.567 secs
run time  : 575.567 secs
start address -T 1020e400 Finished loading count-to-billion.o
48

UPDATE 3:

This is the last one, I promise. I tried Rords other code:

(defun billion-test ()
  (loop with i fixnum = 0
        while (< i 1000000000) do (incf i)))

and suprisingly, it runs as fast Joswig's the difference being the keywords fixnum and with:

gcl's output:

real time : 0.850 secs
run time  : 0.850 secs

sbcl's output(ran for about half a second and spat this out):

debugger invoked on a TYPE-ERROR in thread
#<THREAD "main thread" RUNNING {23FC3A39}>:
  The value 536870912 is not of type FIXNUM.

clisp's output:

Real time: 302.82532 sec.
Run time: 286.35544 sec.
Space: 11798673420 Bytes
GC: 21413, GC time: 64.47521 sec.
NIL

Appreciative

If I search for fixnum-safety in this page, the only occurrence I find of it is in your question; I don't see it in @RainerJoswig's code. Are you sure you took his code as it was written? – Mouth

@Joshua Taylor: I used it in an earlier version. It is LispWorks-only and not needed here. – Errantry

@RainerJoswig Ah, nevermind then. I saw OP's comment, and it didn't make sense. I should have checked the revisions. Sorry, Segfault! – Mouth

I've switched to 64bit some time ago. Maybe your computer/OS is 64bit capable, too? Then you might want to look for a 64bit Lisp implementation for Windows (I'd guess that SBCL or CCL should have those). – Errantry

Answer 1

• start up time
• undeclared variable
• global variable
• no type declarations
• compiler not told to optimize
• on 32bit machines/implementations 1000000000 is possibly not a fixnum, see the variable MOST-POSITIVE-FIXNUM
• possibly < comparison with a bignum on 32bit machines -> better to count to 0
• slow implementation

A 64bit Common Lisp should have larger fixnums and we can use simple fixnum computations.

On a 64bit LispWorks on a MacBook Air laptop with 2 Ghz Intel i7 I get unoptimized code to run in slightly under 2 seconds. If we add declarations, it gets a bit faster.

(defun billion-test ()
  (let ((i 0))
    (declare (fixnum i)
             (optimize (speed 3) (safety 0) (debug 0))
             (inline +))
    (loop while (< i 1000000000) do 
          (setq i (+ i 1)))))


CL-USER 7 > (time (billion-test))
Timing the evaluation of (BILLION-TEST)

User time    =        0.973
System time  =        0.002
Elapsed time =        0.958
Allocation   = 154384 bytes
0 Page faults
NIL

A 64bit SBCL needs 0.3 seconds. So it is even faster.

With GCL you should be able to get better results on a 32bit machine. Here I use GCL on a 32bit ARM processor (Samsung Exynos 5410). A billion is with GCL on the ARM machine still a fixnum.

>(type-of 1000000000)

FIXNUM

>(defun billion-test ()
  (let ((i 0))
    (declare (fixnum i)
             (optimize (speed 3) (safety 0) (debug 0))
             (inline +))
    (loop while (< i 1000000000) do 
          (setq i (+ i 1)))))

BILLION-TEST

>(compile *)

Compiling /tmp/gazonk_23351_0.lsp.
Warning:
The OPTIMIZE quality DEBUG is unknown.
End of Pass 1.  
End of Pass 2.  
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling /tmp/gazonk_23351_0.lsp.
Loading /tmp/gazonk_23351_0.o
start address -T 0x7a36f0 Finished loading /tmp/gazonk_23351_0.o
#<compiled-function BILLION-TEST>
NIL
NIL

Now you can see that GCL is also quite fast, even on a slower ARM processor:

>(time (billion-test))

real time       :      0.639 secs
run-gbc time    :      0.639 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
NIL

Errantry

Care to add some little explanation and how to fix them? – Appreciative

gcl reports MOST-POSITIVE-FIXNUM as 2147483647 while clisp's is 16777215. Are bignum comparisons that slow? Why? – Appreciative

@Segfault: fixnum operations are basically primitive processor instructions. A bignum is much more complicated. – Errantry

Unrelated question, how do you compile from the console using gcl in windows? – Appreciative

@Segfault: I have no idea. If you have an unrelated question, you might want to ask it as an unrelated and new question. – Errantry

SBCL is quite fast about this even without any declarations. (time (loop with i = 0 while (< i 1000000000) do (incf i))) gives Evaluation took: 0.776 seconds of real time ... – Mittel

And a compiled version in GCL (the code was (defun billion-test () (loop with i fixnum = 0 while (< i 1000000000) do (incf i)))) even returns instantly. Apparently the dead code gets eliminated. – Mittel

@Rörd, mine is hardly instantaneous. The only way to make it so is through Joswig's additions. What are your system specs? – Appreciative

@Segfault: Yes, I should have specified that. Since GCL uses the system's C compiler, its optimization behaviour is likely to vary greatly between different configurations. I observed this result on a x86-64 Linux system with GCC 4.73. – Mittel

@Segfault: Also note that the code I used with GCL does have a type hint (with i fixnum). Without that, it doesn't return instantly for me either. I guess, without it GCC's optimizer cannot recognize the dead code. – Mittel

@Rörd, do you mean with i=0? That's a type hint? – Appreciative

@Segfault: The code in my comment on SBCL and my comment on GCL is slightly different. The with clause in the loop is just with i = 0 in the first, but with i fixnum = 0 in the second. That extra fixnum there is the type hint. – Mittel