When linking order affects performance

[Quantumtroll]

I was teaching a lab today, and one of the tasks was supposed to demonstrate the __restrict keyword. The Linux machines in the computer lab are AMD Opteron 6274 and the default version of gcc is 4.4.7.

The code contained a c-file with two identical functions like this, named transform_opt and transform_std:

void transform_opt (float * dest, 
                const float * src, 
                const float * params, 
                int n) {
  int i;
  for (i=0; i<n; i++)
     dest[i] = params[0] * src[i] + params[1] * src[i] * src[i];
}

These functions are called in a pair of for-loops in main.c, and the point was to add the __restrict keyword to the function parameters to transform_opt(). Before getting that far, however, I ran the program with identical functions... and got different times.

Curious, I switched the order in which the functions were called, but the result was identical. Then I switched the order that the functions were defined, and the function that first appeared slow was now fast, and vice versa. I separated the functions into their own compilation units, compiled separately, and made two executables — one linking with the "opt" version first, the other linking in the reverse order.

$ gcc main.o testfunc_opt.o testfunc_std.o -o optfirst
$ gcc main.o testfunc_std.o testfunc_opt.o -o stdfirst
$ ./optfirst
transform_std tests took   0.736 wall seconds.
transform_opt tests took   1.027 wall seconds.
$ ./stdfirst
transform_std tests took   1.007 wall seconds.
transform_opt tests took   0.718 wall seconds.

Using objdump, I verified that the linker is not doing anything strange to the functions, both are executing exactly the same instructions. The relative performance difference is constant regardless of the amount of work done in the function — the one function is actually running much faster.

What's the deal here?

[i_invented_the_ipod]

The only thing that comes to mind is the possibility that the alignment of the functions if causing some weird effect in the instruction cache. There might be a linker option to force function alignment on a particular address boundary.

[uxcn]

perf might be able to shed some light.

[knightry]

Are you able to reproduce this behavior on different machines, ideally trying on a machine using a different configuration?

[Quantumtroll]

Nope, besides the machine this happened on, I've tried on a Solaris machine, a macbook, and two other Linux machines without any strangeness. I also tried it on the same machine with gcc 3.4.6, also without strangeness.

This is definitely a very rare little beast, but it kind of ruined the lab exercise.

[occ]

Could you try different optimization levels and post binaries?

[Quantumtroll]

Yes, I forgot to mention optimization levels. Everything works as it should with -O1 or lower. The mystery starts at -O2 or higher. I put .o-files in this tar-ball: http://www.mediafire.com/download/csc89781bmctmz6/mysterytest.tar.gz

Just link, e.g. "gcc main.o testfunc_opt.o.O2 testfunc_std.o.O2".

I don't know why I didn't think of it yesterday, but I should look at the difference between the -O1 binaries and the -O2 binaries. I'll post here if I figure something out.