RFD: profile standard deviation of # of loop iterations?

[Dale Johannesen]

On Mar 16, 2004, at 4:34 AM, Joern Rennecke wrote:
> We currently seem to assume that the probability for a loop to end is 
> equal
> at each iteration.  I think this is a rather unrealistic assumption.
> And it does not only matter in getting probabilities right after 
> unrolling,
> but also in deciding what unrolling factor is best to start with.

> The current profile-arcs framework gives us the number of executions 
> for
> the loop header and for the loop body, which allows us to just 
> calculate
> the average number of iterations.

Yes.   There are a number of loops in SPEC which are executed the same
small number of iterations every time, although you can't tell that at 
compile time.
If the profile data indicates this possibility, it is right overall to 
unroll the
loop that number of times, even if it's a number that you wouldn't 
ordinarily
unroll by, like 3 or 5.   And unexecuted or very infrequently executed
loops should not be unrolled at all; that comes up too.

> To be able to calculate the standard deviation, we'd have to keep track
> of the sum of the squares of loop iterations.
> One way to do this would entail to keep track of the total number of 
> loop
> iterations at the finish of the last loop, which would be initialized 
> to zero.
> After the end of a loop, we subtract the previous total iterations from
> current total iterations, square the difference, and add the result to
> the sum of squares of loop iterations.  Then we copy the current total
> number of loop iterations to the previous number of loop iterations.
>
> The instrumentation point for this need not necessarily be after the 
> loop;
> we could also do this before the loop, and in addition to that at 
> function
> or program end to capture the last loop run.

What would you do with the standard deviation after you got it?
I don't see how that would let you decide unrolling any better than the 
average.

I agree more info would be useful.  One other interesting case is when 
the loop is
executed with a fairly small set of different numbers of iterations 
(say 2x or 3x on
different occasions); then you could make multiple copies of the loop,
unrolled different numbers of times.  I haven't seen that one in SPEC, 
though.
Another case that does occur in SPEC is when the loop header is executed
more frequently than the loop body (i.e. the loop is executed 0 
iterations a
large amount of the time).  I haven't yet come up with a good heuristic 
for
that one; more data would certainly help.

I was thinking along the lines of keeping a small number of 'buckets' 
for each
loop, to remember how often they're executed in practice (i.e. remember 
several
different iteration counts, it that's what happens).  I haven't done 
anything about
it, though.