Automated software optimization and tuning

Question

I'm writing code that uses a lot of graph operations; many higher-level algorithms iterate over all the graph edges and do some processing on them. There's an iterator method that returns a batch of edges, like so:

G.get_edges(edges,iterator,num_edges);
for (k = 0; k < num_edges; k++) {
    i = edges[k,0];
    j = edges[k,1];
    // Do something to (i,j)
}

Elsewhere in the program, there's a parameter called batch_size which is the standard number of edges to operate on whenever this algorithm is called. Currently, I have have batch_size hard-coded to 64, figuring that a cache line can hold 128 integers on my computer.

What's a sane way to automatically tune the batch size? I'd like to do something akin to how ATLAS chooses the block size without having to read the ATLAS source code.

My best guess for how this should work:

1. Compile an initial version of the code where the batch size is chosen at run-time

2. Run a test suite several times with different batch sizes.

3. Pick the batch size b for which the test suite ran fastest.

4. Generate a new .h file containing a pre-processor directive that sets the batch size to be b.

5. Compile the rest of the code, for which the batch size is now known at compile time.

Answer 1

You could just write an edit, compile, run loop in shell or Python that does it directly in the .h file if you think hard-coding this value is likely to give the compiler an advantage. If the runs are short enough, it ought to be straightforward to iterate over all values of batch_size in a reasonable range.

Answer 2

I think it's rather uncommon these days to run an auto-tuning build, but not out of the question. Looking at your code sample, I don't actually see any cache reuse, so I'm not sure what your anticipated benefit here is.

As Bill alludes, you should probably make the batch size a run-time parameter unless you've got evidence that your compiler is behaving inefficiently without it statically compiled in.