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

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