Why is my program performing differently based only on the order I give source file operands to Clang?

user_9340893 0
Viewed 85

I have a Brainfuck interpreter project with two source files, altering the order that the source files are given as operands to Clang, and nothing else, results in consistent performance differences.

I am using Clang, with the following arguments:

  • clang -I../ext -D VERSION=\"1.0.0\" main.c lex.c
  • clang -I../ext -D VERSION=\"1.0.0\" lex.c main.c

Performance differences are seen regardless of optimisation level.

Benchmark results:

  • -O0 lex before main: 13.68s, main before lex: 13.02s
  • -01 lex before main: 6.91s, main before lex: 6.65s
  • -O2 lex before main: 7.58s, main before lex: 7.50s
  • -O3 lex before main: 6.25s, main before lex: 7.40s

Which order performs worse is not always consistent between the optimisation levels, but for each level, the same operand order always performs worse than the other.

Notes:

  • Source code can be found here.
  • The mandelbrot benchmark that I am using with the interpreter can be found here.

Edits:

  • The executable files for each optimisation level are exactly the same size, but are structured differently.
  • Object files are identical with either operand order.
  • The I/O and parsing process is indistinguishably quick regardless of operand order, even running a 500 MiB random file through it results in no variation, thus performance variation is occurring in the run loop.
  • Upon comparing the objdump of each executable, it appears to me that the primary, if not the only, difference is the order of the sections (, , etc), and the memory addresses that have changed because of this.
  • The objdumps can be found here.
clang linker scope c
1 Answers

I don't have a complete answer. But I think I know what's causing the differences between linkage ordering.

First, I got the similar results. I'm using gcc on cygwin. Some sample runs:

Building like this:

$ gcc -I../ext -D VERSION=\"1.0.0\" main.c lex.c -O3 -o mainlex
$ gcc -I../ext -D VERSION=\"1.0.0\" lex.c main.c -O3 -o lexmain

Then running (multiple times to confirm, but here's a sample run)

$ time ./mainlex.exe input.txt > /dev/null

real    0m7.377s
user    0m7.359s
sys     0m0.015s

$ time ./lexmain.exe input.txt > /dev/null

real    0m6.945s
user    0m6.921s
sys     0m0.000s

Then I noticed these declarations:

static char arr[30000] = { 0 }, *ptr = arr;
static tok_t **dat; static size_t cap, top;

And that caused me to recognize that 30K of a zero byte array is getting inserted into the linkage of the program. That might introduce a page load hit. And the linkage ordering might influence if code in main is within the same page as the functions in lex. Or just accessing array means jumping between a page that isn't in the cache anymore. Or some combination thereof. It was just a hypothesis, not a theory.

So I moved the declarations of these global directly into main and dropped the static declaration. Kept the zero-init on the variables.

int main(int argc, char *argv[]) {
    char arr[30000] = { 0 }, *ptr = arr;
    tok_t **dat=NULL; size_t cap=0, top=0;

That will certainly shrink the object code and binary size by 30K and the stack allocation should be near instant.

I get near identical perf when I run it both ways. As a matter of fact, both builds run faster.

$ time ./mainlex.exe input.txt > /dev/null

real    0m6.385s
user    0m6.359s
sys     0m0.015s

$ time ./lexmain.exe input.txt > /dev/null

real    0m6.353s
user    0m6.343s
sys     0m0.015s

I'm not an expert on page sizes, code paging, or even how the linker and loader operate. But I do know that global variables, including that 30K array, are expanded into the object code directly (thus increasing the object code size itself) and are effectively part of the binaries final image. And smaller code is often faster code.

That 30K buffer in global space might be introducing a sufficiently large enough number of bytes between the functions in lex, main and the c-runtime itself to effect the way code gets paged in and out. Or just causing the loader to take longer to load the binary.

In other words, globals cause code bloat and increase object size. By moving the array declaration to the stack, the memory allocation is near instant. And now the linkage of lex and main probably fits within the same page in memory. Further, because the variables are on the stack, the compiler can likely take more liberty with optimizations.

So in other words, I think I found the root cause. But I'm not 100% sure as to why. There is not a whole lot of function invocations getting made. So it's not like the instruction pointer is jumping around a lot between code in lex.o and code in main.o such that the cache is having to reload the page.

A better test might be to find a much larger input file that triggers a longer run. That way, we can see if the runtime delta is fixed or linear between the two original builds.

Any more insight will require doing some some actual code profiling, instrumentation, or binary analysis.

user_1044580
Related