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

[Neil Cerutti]

On 2007-09-11, Robert Brown <bbrown at speakeasy.net> wrote:
> 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))))

That's pretty cool. Thanks for the example.

-- 
Neil Cerutti