Numerical code efficiency

I've been reacquainting myself with Lisp for the last few weeks, having not 
used it for about twenty years. I'm doing it partly for fun and general 
edification, but I'm also evaluating its suitability for the sort of number 
crunching one might find in a Newtonian physics simulator. I've been using 
Corman Lisp 2.5 for my investigations.

I just did a few investigations into performance for a very simple function 
to sum floating point numbers. I'd like to find out if my approach to 
optimizing a little subroutine like this is appropriate, and if my results 
are typical for Lisps in general.

Here's the entire test file:
(declaim
      (optimize
         (speed 3)
         (compilation-speed 0)
         (safety 0)
         (debug 0)))

(defun sum-reduce (v)
     (reduce #'+ v))

(defun sum-reduce-df (v)
     (declare (type (vector double-float 10) v))
     (the double-float (reduce #'+ v)))

(defun sum-loop (v)
     (let ((acc (svref v 0))
           (len (length v)))
         (do ((i 1 (1+ i)))
             ((eq i len) acc)
             (setq acc (+ acc (svref v i))))))

(defun sum-loop-df (v)
     (declare (type (vector double-float 10) v))
     (let ((acc (svref v 0))
           (len (length v)))
         (declare (type double-float acc))
         (do ((i 1 (1+ i)))
             ((eq i len) acc)
             (declare (type fixnum i))
             (setq acc (+ acc (svref v i))))))

(defun test-sum (label f)
     (format t "~&~A:~%" label)
     (let ((v #(1.0d0 2.0d0 3.0d0 4.0d0 5.0d0 6.0d0 7.0d0 8.0d0 9.0d0 10.0d0)))
         (gc)
         (time
             (dotimes (i 1000000)
                 (declare (type fixnum i))
                 (funcall f v))))
     (values))

(test-sum "Lambda reduce-plus" #'(lambda (x) (reduce #'+ x)))
(test-sum "SUM-REDUCE"    #'sum-reduce)
(test-sum "SUM-REDUCE-DF" #'sum-reduce-df)
(test-sum "SUM-LOOP"      #'sum-loop)
(test-sum "SUM-LOOP-DF"   #'sum-loop-df)
:DONE


And here's some typical output from executing this file:

T
SUM-REDUCE
SUM-REDUCE-DF
SUM-LOOP
SUM-LOOP-DF
TEST-SUM
Lambda reduce-plus:
Total Execution time: 6.169552 seconds
Time spent garbage collecting: 0.416621 seconds
SUM-REDUCE:
Total Execution time: 6.105878 seconds
Time spent garbage collecting: 0.400325 seconds
SUM-REDUCE-DF:
Total Execution time: 6.104992 seconds
Time spent garbage collecting: 0.441325 seconds
SUM-LOOP:
Total Execution time: 2.698069 seconds
Time spent garbage collecting: 0.31516 seconds
SUM-LOOP-DF:
Total Execution time: 2.706086 seconds
Time spent garbage collecting: 0.317234 seconds
:DONE



The lambda form, sum-reduce, and sum-reduce-df all consistently execute in 
about the same time. The fact that a hand-coded loop is faster didn't 
surprise me much, based on what I'd read in Paul Graham's ANSI Common Lisp. 
But two things did surprise me:

1. Adding type declarations didn't seem to improve matters. Am I using them 
appropriately? I tried single-float instead of double-float, but there was 
no discernible difference. Also, the declamation of i in the loop made no 
difference.

2. Looking at the disassembled functions, i noticed that svref results in 
an actual function call, as does the call to #'+. Is there any way around 
this? Declaiming these inline doesn't work; I get a warning that the source 
isn't accessible.

Assuming I'm not doing anything wrong: Is this typical for Lisps in 
general? The generated code makes me suspect that writing low-level matrix 
and vector manipulation functions in Lisp would lead to mediocre results 
for a production-quality program. That's not necessarily a big problem; 
it's certainly the sort of thing that one might expect to hand-optimize 
using assembler or by calling a third-party library. I'm just curious about 
how far straight Lisp programming can be stretched for math-intensive 
programming. Although using multiple languages is common, it's certainly 
nicer when you don't have to mess with crossing the boundaries.

Thanks in advance for your comments.



Dan Muller
[email protected]

Some people believe in absolutes. Others aren't so sure.



---
avast! Antivirus: Outbound message clean.
Virus Database (VPS): 10/9/2003
Tested on: 10/12/2003 11:17:23 AM
avast! is copyright (c) 2000-2003 ALWIL Software.
http://www.avast.com




------------------------ Yahoo! Groups Sponsor ---------------------~-->
Buy Ink Cartridges or Refill Kits for your HP, Epson, Canon or Lexmark
Printer at MyInks.com. Free s/h on orders $50 or more to the US & Canada.
http://www.c1tracking.com/l.asp?cid=5511
http://us.click.yahoo.com/mOAaAA/3exGAA/qnsNAA/SyjtlB/TM
---------------------------------------------------------------------~->

To unsubscribe from this group, send an email to:
[email protected]

 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/