title: Why is counting to a billion in lisp so slow?
body: <pre><code>(defun billion-test () 
    (setq i 0) 
    (loop while (&lt; i 100) do 
      (setq i (+ i 1)))) 
  (billion-test) 
  (print "done")
  </code></pre>
  
  <p>I have the above <code>Lisp</code> code that simply loops to one billion. The problem is it is really<br>
  slow. Slower than any trivial program I have ever written. These are the times it took to<br>
  run with the intepreters I have(gcl and clisp).  </p>
  
  <pre><code>                       Compiled  Uncompiled
  GNU Common Lisp(gcl)    270-300s  900-960s
  Clisp                   280-300s  960-1647s
  </code></pre>
  
  <p>I used this Python code to time the time for <code>Clisp</code> and an approximated using the system time<br>
  with <code>gcl</code> since you can't run it from the command prompt.  </p>
  
  <pre><code>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)
  </code></pre>
  
  <p>Here are the comparison with while loops from other languages:  </p>
  
  <pre><code>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
  </code></pre>
  
  <p>My assumption is that <code>loop while &lt;condition&gt; do</code> is the <code>Lisp</code> equivalent of a <code>while</code><br>
  loop. I have some doubts about those <code>1647s(25+ min)</code>, I was watching something at that<br>
  time and it might have slowed the execution, but by almost <code>800s</code>? I don't know.<br>
  These results are hard to believe. According to <a href="http://norvig.com/python-lisp.html" rel="nofollow">Norvig</a> <code>Lisp</code><br>
  is 3 to 85 times faster than <code>Python</code>. Judging from what I got, the most logical<br>
  explanation for such slow execution is that <code>Clisp</code> and <code>gcl</code> in <code>Windows</code> have some kind<br>
  of bug that slows down large iterations. How, you ask, I don't know?
  Sooo, my question is, <strong>why so slow</strong>?<br>
  <strong>Is anybody else getting something like this?</strong></p>
  
  <p><strong>UPDATE 1:</strong><br>
  I ran Joswigs's program and got these results:  </p>
  
  <pre><code>      compiled   uncompiled
  gcl    0.8s       12mins
  clisp  5mins      18mins
  </code></pre>
  
  <p><code>gcl</code> compiled the program fine, <code>clisp</code> however gave this warning:  </p>
  
  <pre><code>;; 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]&gt; (type-of 1000000000)
       (INTEGER (16777215))
  
       ;;gcl
       (type-of 1000000000)
        FIXNUM
  </code></pre>
  
  <p>Guess that could be the reason it took more than a minute.</p>
  
  <p><strong>UPDATE 2:</strong><br>
  I thought I would give it another try with another implementation just to confirm<br>
  that it's really the <code>bignum</code> comparison that slowing it down. I obtained <code>sbcl</code><br>
  for windows and ran the program again:  </p>
  
  <pre><code> * (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")
  </code></pre>
  
  <p>I wish I could tell you how long it took but I never saw the end of it. I waited for<br>
  2 hours, watched an episode of Vampire Diaries(hehe) and it still hadn't finished.<br>
  I was expecting it to be faster than <code>Clisp</code> since its <code>MOST-POSITIVE-FIXNUM</code> is, well, more<br>
  positive. I'm vouching for the slow implementation point because only <code>gcl</code> could pull<br>
  off the less than one minute run.</p>
  
  <p>Running Rörd's code with <code>gcl</code>:</p>
  
  <pre><code>(time (loop with i = 0 while (&lt; i 1000000000) do (incf i))) 
  
  gcl with Rords's code:
  &gt;(load "count-to-billion.cl")
  Loading count-to-billion.cl
  real-time : 595.667 secs
  run time : 595.667 secs
  
  &gt;(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"
  
  &gt;(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
  </code></pre>
  
  <p><strong>UPDATE 3:</strong></p>
  
  <p>This is the last one, I promise. I tried Rords other code:</p>
  
  <pre><code>(defun billion-test ()
    (loop with i fixnum = 0
          while (&lt; i 1000000000) do (incf i)))
  </code></pre>
  
  <p>and suprisingly, it runs as fast Joswig's the difference being the keywords <code>fixnum</code> and
  <code>with</code>:</p>
  
  <p><code>gcl</code>'s output:</p>
  
  <pre><code>real time : 0.850 secs
  run time  : 0.850 secs
  </code></pre>
  
  <p><code>sbcl</code>'s output(ran for about half a second and spat this out):</p>
  
  <pre><code>debugger invoked on a TYPE-ERROR in thread
  #&lt;THREAD "main thread" RUNNING {23FC3A39}&gt;:
    The value 536870912 is not of type FIXNUM.
  </code></pre>
  
  <p><code>clisp</code>'s output:</p>
  
  <pre><code>Real time: 302.82532 sec.
  Run time: 286.35544 sec.
  Space: 11798673420 Bytes
  GC: 21413, GC time: 64.47521 sec.
  NIL
  </code></pre>