generic way to evaluate a function cost at compile time

Question

I am currently working on the implementation of a multidimensional array iterator. Considering the iteration over two contiguous ranges (for std::equal, std::copy purposes) that represent compatible data with different alignements (row vs col major in 2D), I would like to find the stride order for each iterator giving the fastest execution time.

For example:

row of vector components = A -> m elements
row of vectors =           B -> n elements
2D plan of vectors =       C -> 3 elements
row of plan of vectors =   D -> 10 elements

given the datas ordered by ascending strides:
first array:   B | A | C | D
second array:  B | A | D | C

 Obviously, we can iterate over both iterators by bunches of m*n elements. Then:

 If we choose the first array convention, the first iterator is contiguous and the second one 
 will perform (3 - 1)*(10 - 1) jumps forward with a stride of 10 and (10 - 1) jumps backward.

 If we choose the second array convention, the second iterator is contiguous and the first one will 
 perform (10 - 1)*(3 - 1) jumps forward with a stride of 3 and (3 - 1) jumps backward.

=> The second convention is better at everything in this example.

Since I have to take a lot of factors to take into account like the memory back and forth, the contiguity and the iterator implementation itself (which is not trivial), I want to perform an experimental plan. But I also know everything at compile time (the sizes and the strides) so it would be cool to perform the experimental plan at compile time for each template instantiation. My question is:

Is it possible to evaluate the runtime cost of some instructions at compile time, when everything is known at compile time except the memory address of the input array ?

user_241013 · Answer

No. Your question is based on bad assumptions.

Some of the bad assumptions (there might be others):

The function is used as it is: The compiler might inline it in many places or decide you are better-off having it in a separate function because the code size improves. Since you can get slightly different behavior by the surrounding code you might see different performance.
There is a cost for an instructions: Processors run instructions out of order in many cases or they parallelize instructions. Something that might take a long time like a division might be hidden if it's surrounded by other memory access and gets it's costs amortized.
Performance is independent of the processor. The compiler doesn't know which specific processor you're going to run on, how big the caches or the cache lines are, how fast the main memory is or how good/bad branch prediction will be. All these have a huge impact on performance.

What you can do is profile and measure. Profile the application using this function and see if you actually need to fix it. Measure the performance you're getting and experiment with the different options.

generic way to evaluate a function cost at compile time

1 Answers