Strange Compile Results
- To: mathgroup at smc.vnet.net
- Subject: [mg6829] Strange Compile Results
- From: Michael Giddings <giddings at whitewater.chem.wisc.edu>
- Date: Mon, 21 Apr 1997 02:03:37 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Using MMA 3.0/Nextstep/Intel:
I am trying to compile a function that operates on a long data list (all
real values) to find the next maxima, given a certain starting point (it is a
function that is called many times by another function). To speed it up, I
have been attempting to compile it, and have had some strange results. Here
is the function:
Findnextmax = Compile[{{list, _Real, 1}, {startpoint, _Integer}},
Module[{i=0, total=0 ,start=0,end=0},
{total = Length[list]-1;
If[startpoint >= total, Return[startpoint]];
i = startpoint;
While[(i < (total) && (Part[list, i] >= Part[list, i+1])), i += 1];
While[(i < (total) && (Part[list,i] < Part[list, i+1])), i += 1];
If[Part[list,i]==Part[list,i+1],
start = i;
While[(i < total) && (Part[list,i] == Part[list,i+1]), i+=1];
end = i;
i = Round[(start + end)/2]]; i],
{{Round[_], _Integer}}]
(The function basically does this: go downhill if possible, then uphill
until the next maxima is reached. If it is flat on top, return the midpoint
of the flat section.)
Now, given a long linear array of real values, I compare timings on 100
calls of this function versus 100 calls of the same function uncompiled(using
Timing[Do[Findnextmax[data, 14], {100}]]). I get:
Compiled 1.09s
Uncompiled: 0.37s
This was surprising. So I played with commenting out various parts of the
function to see which was responsible for the slowdown. Surprisingly, a big
factor was the very last assigment statement (which originally used Floor
instead of Round). I played with it. The only thing that worked to speed it
up was Changing the '=' to ':=', which almost doubles the speed of the
compiled function!!! The new timing for the compiled function: 0.68s.
Stranger yet, if I change a different assignment, say "total :=
Length[list]-1" from '=' to ':=', I get a big slowdown again! So it appears
to be inconsistent. There seems to be something going on with assignments
and compilation that I don't fully understand here.
The other thing to be noticed is that even with the speedup provided by the
"correct" use of '=' and ':=', the compiled function is still almost 2x
slower in 100 calls. To see whether this was due to parameter passing
overhead, I moved the 100 loops inside the function. Now if I compare the
compiled to the uncompiled function, I get:
Compiled: 0.01s
Uncompiled: 0.15s
So, the remaining speed difference was due to something in function
call/parameter passing. The only guess I had is there is some overhead
involved in converting this list into the appropriate form for use by
compiled functions.
To test this, I compiled the external loop which calls the function, i.e.:
test = Compile[{{mydata, _Real, 1}, {loops, _Integer}},
Do[Findnextmax[mydata,14], {loops}], {{Findnextmax[_], _Integer}}]
Results using this compiled function to call compiled vs. uncompiled
versions of Findnextmax using 100 loops(e.g. Timing[a[data, 100];]):
Compiled: 0.73 s
Uncompiled: 0.38 s
So compiling the calling function to first get the list into appropriate
form before iterating the call has virtually no speedup effect.
After all of this I can't think of anything else to make it run faster,
except putting it inline and compiling the whole calling function. The
problem is, the calling code is already large and messy, so that really isn't
a viable option.
Can anyone explain the following two strange effects I have observed?:
1) 2x overhead calling a compiled function versus uncompiled
2) location dependence of compiled function speed on use of '=' and ':=' in
assigment
I just recently subscribed to the group and haven't recieved confirmation
yet, so please cc: me at giddings at whitewater.chem.wisc.edu.
Thanks
---
Michael Giddings
giddings at whitewater.chem.wisc.edu
giddings at barbarian.com
(608)258-1699 or (608) 692-2851
http://smithlab.chem.wisc.edu/PersonalPages/giddings/giddings.html
http://www.barbarian.com