Re: Optimizing for fast floating-point numerical code

I just realized that there wasn't a direct response to this post.

David A. Ventimiglia wrote:
"Thomas M. Hermann" <tmh.public@xxxxxxxxx> writes:

You are using MAP and REDUCE throughout the code. This is a good
approach for prototyping things, but generally not a performance
oriented approach.

I used mapping functions and `reduce' partly because they seemed like
the closest analogs to Fortran 95's very fast vectorized operations.
Not that a Lisp implementation has to ape a Fortran implementation, but
I often find (as I did in this case) that mapping and reduction
operations conceptually offer a better abstraction than looping, so I was
pleased see support for them in both languages. Would it be fair to
say, however, that in Lisp they don't compete well with looping? On the
other hand, it hadn't occurred to me to use the loop macro, which is
itself a nice abstraction.

In any event, I adopted your suggestions and it now runs in half the
time (the code is included below). One question, if I put the nested
`dotimes' into a function declared with flet, where do I declare that
function to be inline? Does that declaration go inside the flet?

The declaration goes between the function forms and the body forms. Here is an example taken from the hyperspec:

(defun example (y l)
(flet ((attach (x)
(setq l (append l (list x)))))
(declare (inline attach))
(dolist (x y)
(unless (null (cdr x))
(attach x)))
l))


Another thing you should be careful of when making the comparison of
your lisp code with Fortran is that the difference in the
implementations of RANDOM can be significant since you are calling it
inside your loop. On one hand, it is valid to evaluate this difference
because implementing your own random number generation function would
be pretty annoying. On the other hand, if generating random numbers is
a critical part of your algorithm, it may be worth your time to
research how it is accomplished in the respective languages and
implement a version that better meets your requirements.

This point is interesting to me. Evidently, it'd be unsurprising for an
intrinsic function like `random' in a given Lisp implementation to be
suboptimal, perhaps very much so. How does one know ahead of time that
an intrinsic function should be a candidate for avoidance (like with
`map' and `reduce') or for reimplementation (like with `random')?

My coding philosophy is to apply the most specific approach for the information at hand. In the case of MAP and REDUCE, those are functions that operate on sequences, so they work in a very general sense and handle general conditions. They are great for prototyping and for situations where you want to handle lists, vectors and arrays with a single interface. There is a cost for that general behavior, though. So, if you know that your function is only going to accept simple-arrays, then use functions specific to simple-arrays.

There has already been plenty said about RANDOM. I would just like to emphasize that the issue with RANDOM is not unique to common lisp. I also think RANDOM is the most susceptible to being reimplemented. I use the transcendental trig functions frequently and have never had motivation to implement my own versions.


Good luck with your investigation of lisp. The numeric performance can
be made comparable with other languages, but the advantage of using
lisp over Fortran is that lisp has a much better development
environment, not the raw numeric performance. Don't focus on the
numeric performance during the initial development of your code, focus
instead on developing your ideas and getting working code. There is no
reason to focus on the performance of the code until execution of your
programs is impeding the progress of your research or work. When the
execution performance does become an impediment to progress, start by
profiling to correct algorithmic bottlenecks. Only after you have
corrected your algorithmic bottlenecks should you focus on using
declarations. Finally, only use the bare minimum of declarations.

Hope that helps,

Tom H.

It does, thanks. Unfortunately, the real body of code I'm working with
is very from the initial development phase in Fortran, and in Fortran
it's very fast. To solve a real problem on a real machine, it takes
about an hour, which is great, but if it took 25 hours in Lisp my
adviser would consider that to be unacceptable. I think he also would
question my judgment if I told him I had to reimplement some of the
language's intrinsic functions to make it run faster. On the other
hand, the changes you suggested weren't that onerous and with them I
halved the execution time. More work might get it in the ball-park of
Fortran.

Best,
David



------------------------------------------------------------------------

(defun mc ()
(* (/ 3.0d0 4.0d0) (integrate #'sphere #(-1.0d0 -1.0d0 -1.0d0) #(1.0d0 1.0d0 1.0d0) 10000000)))

(defun integrate (fn ll ul N)
(flet ((make-r (r l d)
(dotimes (index l)
(setf (aref r index)
(+ (aref ll index)
(* (random 1.0d0)
(aref d index)))))))
(let* ((l (array-dimension ll 0))
(r (make-array l :element-type 'double-float))
(d (map 'vector #'- ul ll))
(V (reduce #'* d))
(sum 0.0d0))
(dotimes (k N (* V (/ sum N)))
(make-r r l d)
(setf sum (+ sum (funcall fn r)))))))

(defun sphere (r)
(if (< (loop for x across r sum (* x x)) 1.0d0)
1.0d0
0.0d0))



------------------------------------------------------------------------



.

Relevant Pages

  • Re: What do you LISPers think of Haskell?
    ... "Lisp is as fast as Fortran for scientific computing" claims economics ... His published software includes a sparse matrix library written in Lisp ...
    (comp.lang.lisp)
  • Lisp as a tool for the mind
    ... "Lisp is as fast as Fortran for scientific computing" claims economics ... His published software includes a sparse matrix library written in Lisp ...
    (comp.lang.lisp)
  • Re: idiomatic Lisp style
    ... Unlike C, or Perl, where you can declare a variable without assigning ... behavior of special and lexical variables, ... In fact, since the behavior is so different, Lisp coding style has ...
    (comp.lang.lisp)
  • Re: Freepascal rocks!
    ... I've been experimenting with a few programming languages lately: Assembler, Lisp, Forth, Smalltalk. ... A language powerful enough to simply implement another language is damn powerful. ... The other day I joked to my colleagues that we should be writing more stuff in FORTRAN; my contention being that FORTRAN doesn't really do much, so you *have* to keep things simple. ... CurRow, CurCol: Integer; ...
    (comp.lang.pascal.misc)
  • Re: Function declarations - why are they needed?
    ... >> For example in Python functions are defined once and never declared ... The same holds in Fortran where you need not declare ... Fortran is typically used for large MLOC programs and there is *no* ... else) which require the called routine to have an 'explicit interface' ...
    (comp.lang.c)