Optimizing end-to-end performance of an algorithm

[freemin7]

When one has an executable working on some file

./executeable work_file

an obvious means of doing causal benchmarking is to add an progress point before the end of the program and loop the execution of the program via some other mechanism (for example an bash script). For long running programs this means that coz will take longer to learn anything about the program behavior. If the algorithm is of this structure:

m = read(workfile)
for i in 1..n
  m = doSomething(i,m)
end
print(m)
Progress_point++
return

on can insert a progress point in the loop and can accept that with enough samples coz can estimate the importance of speeding up certain components for the complete loop.

m = read(workfile)
for i in 1..n
  m = doSomething(m)
  Progress_point++
end
print(m)
return

The more similar the optimization profiles of doSomething(m) are with the total program and each other the faster it can estimate the optimization profiles. Are there some theory results or benchmarks which verify this?

However there are also programs of this type:

m = read(workfile)
startup_work()
while not_good_enough(m)
   round_start = time()
   while less_than_a_minute_passed(round_start)
          m = chip_on_problem_multi_threaded(m)
   end
   print(m)
end
print(m)
Progress_point++
return 

Moving the progress points into either while loop means the number of progress points per complete run is no longer fixed. Creating "perverse incentives" such as:

• If startup_time is long and having the loop run more often gives more Progress_points per time.
• A progress point in outer while loop shows a profile that tries to trick the timer if possible or have the inner operations to as close to being slightly longer than a minute then possible, leading to saw tooth style profile on further improvement when the actual total time declines
• A progress point in the inner while loop would show a profile which coordinates threads that as little work as possible gets done in an iteration.

How would one go about using coz on a program of the second type?

[emeryberger]

I don't exactly understand the issues, which might be based on a misunderstanding.

Coz works by identifying the effect of any (virtual) speedups on the rate of execution of progress points. There's no "incentive" per se; it just measures the effect of a speedup on the progress point (or, for latency, the time between the start and end progress points). The total number of progress points executed per run is immaterial, except that you'd rather have more than fewer so you don't have to run the code for as long or run it too many times.

[freemin7]

Since i can't get the tooling working i wrote up a simulation of the effect i mean.

function simulation1(speedup)
       snapshots = [0.0];
       N = 10.0
       timer = 0.0
       while N > 0.2
           round_start = timer
           while timer - round_start < 0.5
               N *= 0.95; #work
               timer += 0.3/speedup #takes time
           end
       end
       append!(snapshots, timer) #progress point
       return snapshots
end

For each array of snapshots i process them as such:

average_time  = [ sum(simulation1(s))/length(s) for s in 1.0:0.05:2.9 ];
total_time = [ maximum(simulation1(s)) for s in 1.0:0.05:2.9 ];
max_dif_time = [ maximum([simulation1(s)[i] - simulation1(s)[i-1] for i in 2:length(simulation1(s))]) for s in 1.0:0.05:2.9 ];
min_dif_time = [ minimum([simulation1(s)[i] - simulation1(s)[i-1] for i in 2:length(simulation1(s))]) for s in 1.0:0.05:2.9 ];

It is obvious that since snapshots consists of the start and stop point that the resulting time.

However if i introduce another progress point in the outer while loop

function simulation2(speedup)
       snapshots = [0.0];
       N = 10.0
       timer = 0.0
       while N > 0.2
           round_start = timer
           while timer - round_start < 0.5
               N *= 0.95; #work
               timer += 0.3/speedup #takes time
           end
           append!(snapshots, timer) #progress point 
       end
       return snapshots
end

the same profile now looks like this:

If we analyze the difference of the n-th and n+1-th sample the same behavior reappears.

And if we remove the total time for context and just explore to speedups up to 1.3. Minimizing the differences between two points might lead on to consider 1.2 a good stopping although we know that total program time keep decreasing from all the previous analysis. We've also seen that aggregations such as the max or min over all differences keep being spiky. Randomness sampling of speed up doesn't help either:

Or where do i go wrong?

[emeryberger]

Now that everything is working, please go ahead and try with real code; hopefully it will be clarifying.