# Automated software optimization and tuning

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.

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.