[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

optimization question

This may be a silly question, but please bear with me. I am
trying to speed up a time critical routine in my program.
The routine itself is highly recursive, and originally was
written somehow like this:

(defun a ()
  (case (which-case)
    (c1 b)
    (c2 c)
    (cn q)))

(defun b () ... (a) ...)
(defun c () ... (c) ... (c) ... (a) ...)
(defun d () ... (d) ... (a) ...)


i.e., a called a bunch of other functions, which are
recursive plus call a again. (Note that this is just an
example, a, b, c, etc. do have plenty of arguments.)

Since a is called very often, I thought that maybe removing
some of the function call overhead might be worth trying. So
I tried the following things:

(1) original version
(2) rewrite the functions so that no function is
self-recursive. Instead, there is only mutual recursion
between a and the other functions b, c, etc.
(3) like (2), but define b, c, etc. via define-inline-function
(4) like (2), but make b, c, etc. macros

I tried to time the different versions (unfortunately, the
routines themselves take quite some time, so I tried only
about 500 iterations in a loop for each experiment).

Basically, the result was that all four versions took about
the same amount of time. 

These are the numbers (compiled code):

            (4)     (2)     (3)     (1)
gc before  1047    2715    4684    6054
real time    60      55      55      56
run time     48.5    45.1    46.1    45.5
gc after   1378    2876    4858    6226

What I don't quite understand is that the version using
macros is actually slower than any other, and must do more
garbage collection. Even version (1), where nothing is done
to the call structure is faster than the macro version,
which I thought would have been the fastest.

Can anybody explain why above is the case. Is this just a
freak accident, or does it mean that the akcl compiler is so
smart, or does it mean that the akcl compiler is not so
smart, or ...

Any hints are appreciated.

Thomas Weigert

| Thomas Weigert                 |                                 |
| Suiron-kenkyuu-shitsu          | weigert@{mcs.anl.gov,etl.go.jp} |
| Electrotechnical Laboratory    | +81-298-58-5918 (phone+fax)     |