Why is this loop heavy code so slow in Python? Possible Project Euler spoilers

[Robert Brown]

Neil Cerutti <horpner at yahoo.com> writes:

> On 2007-09-02, Steven D'Aprano
> <steve at REMOVE-THIS-cybersource.com.au> wrote:
>> A big question mark in my mind is Lisp, which according to
>> aficionados is just as dynamic as Python, but has native
>> compilers that generate code running as fast as highly
>> optimized C.

> Lisp, as far as I know, requires type declarations, discipline,
> deep knowledge of Lisp, and more than passing knowledge of your
> Lisp implementation in order to generate code that's competitive
> with C.

On my Mac Mini, the original Python code runs in 6 minutes 37 seconds using
Python 2.3.5.  The Common Lisp code below, a straightforward translation,
containing *no* type declarations, runs in 27 seconds on the same Mini using
SBCL.

When the commented out optimization declaration is included in the code, the
run time drops to 3.3 seconds.  For comparison, run times with GCC on the C
version posted earlier are 3.5 seconds unoptimized and 0.58 seconds with
optimization flag "-O3".

So for this example, deep knowledge of the Lisp implementation and type
declarations are not required to get speed equivalent to unoptimized C code.
Approaching the speed of optimized C code does require more work.

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

(defun doit ()
;;  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (let ((solutions (make-array 1001 :initial-element 0)))
    (loop for a upfrom 1 below 10000
          do (loop for b upfrom 1 below (- 1000 a)
                   do (loop for c upfrom 1 below (- 1000 a b)
                            do (let ((p (+ a b c)))
                                 (when (and (< p 1000)
                                            (= (+ (* a a) (* b b)) (* c c)))
                                   (incf (aref solutions p)))))))
    (loop with max-index = 0
          with max = 0
          for solution across solutions
          for index upfrom 0
          do (when (> solution max)
               (setf max solution)
               (setf max-index index))
          finally (print max-index))))