Re: Reordering of functions

Tim Frink <plfriko@yahoo.de> writes:


> I've a question about the influence of compiler optimizations that
> reorder functions on the system performance.
>
> Assume a modern processor with all state-of-the art features like
> prefetching, branch prediction and a superscalar pipeline. Further
> assume that all caches are disabled. Will the program runtime change
> when just the order of functions is changed (without any other code
> transformation)?
>
> I'm of the opinion that a reordering of function should have little
> influence on the program execution, maybe due to some prefetch effects
> but thes should be marginal. Of course, with caches this situation
> would look different.


Maybe. You've set up a straw-man where you have tried to deny all
ways that changing the order of function calls might affect
preformance and then asked will performance remain unchanged.
However, even in your denial you have left holes open, what about
machines the execute a limited number of instructions out-of-order and
use register renaming. That's a cache-like effect (just like
pre-fetching, and branch prediction are). Reordering the function
calls can influence all of those. They may all be little effects in
isolation, but they may be larger in total than you expect (or they
may remain small even in combination).


More importantly, in rearranging the functions are you allowed to pull
them out-of-loops (in particular, loops caused by recursive
invocations). That's a very significant question.


To understand why consider quicksort. If you do the recursive calls
in the correct order (attacking the larger half non-recursively, and
pushing only the smaller half on the stack), you significantly change
the algorithm form O(n**2) to O(n*log(n)). If your function
reordering causes an effect like that, it will significantly affect
performance, even if no other optimizations are applied.


So, yes, there is a model where rearranging functions has little or no
effect on application performance. However, it doesn't model all the
real world accurately, and it isn't just random luck that function
reordering can improve performance--the reasons for improved
performance can be profound (yielding deep insight into the problem).


Now, I'm curious why you ask the question. What influence does
whether function reordering influences performance (or not) have on
some decision you have to make, or point you need to prove?


BTW, I presumed that you were talking about the rearrangement of the
order in which functions were executed. Changing the location of the
functions in memory, but not their execution order probably has a more
limited effect on performance, since you can't pull a function
out-of-a-loop that way.


Finally, some of the effects are hard to quantify and/or predict.
When I was working on the Alpha optimizer, there were some
optimizations we specifically turned on (and off) in specific orders
because they had an unfortunate interaction on one of the benchmarks
we were measuring against. The right combination of optimizations
yielded a fortuitous alignment of a critical loop, that was lost if we
did (a little) more optimization until we got significantly more
optimizations enabled and could remove enough code that the loop was
always aligned.


Hope this helps,
-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

Return to the comp.compilers page.
Search the comp.compilers archives again.