On: Feel the cache size: a definitive experiment

[aminuit]

Experiments ought to be repeatable. Here is a quick bash/perl script to generate the parts he left out. It expects that you have copied his main module to a file called main.c in the CWD.

    echo "Generating funcs.h"
    perl -e 'for ($i=0;$i<=1000000;$i++) {print "int f${i}(void);\n";}' > funcs.h
    echo "Generating funcs.c"
    perl -e 'print "#include \"funcs.h\"\n\n";for ($i=0;$i<=1000000;$i++) {print "int f${i}() {return ".($i+1)."; }\n";}' > funcs.c
    echo "Generating tab.h"
    perl -e 'print "#include \"funcs.h\"\n\n";print "int (*func_table[])(void) = {\n";for ($i = 0; $i <= 1000000; $i++) {print "f${i},\n";}print "};\n";' > tab.h
    echo "Compiling funcs.c"
    time gcc -O0 -c -o funcs.o funcs.c
    echo "Compiling main.c"
    time gcc -O0 -c main.c -o main.o
    echo "Linking..."
    time gcc -O0 main.o funcs.o -o func-time
    echo "Running..."
    time ./func-time

I'm using gcc 4.x which seems to generate a slightly smaller function (10 bytes vs. 11):

    00000000 <f0>:
           0:       55                      push   %ebp
           1:       89 e5                   mov    %esp,%ebp
           3:       b8 01 00 00 00          mov    $0x1,%eax
           8:       5d                      pop    %ebp
           9:       c3                      ret    

I ran it on a 3GHz Xeon with 4MB cache (so 2MB per core I think) and I get roughly the same, but with much reduced compile times.

    Running...
    code size: 10  time: 30 secs
    code size: 100  time: 48 secs
    code size: 1000  time: 49 secs
    code size: 10000  time: 47 secs
    code size: 100000  time: 51 secs
    code size: 1000000  time: 59 secs
    code size: 10000000  time: 202 secs

[mojuba → aminuit]

First, on your assembly output: mine was a 64-bit system, and there's one opcode that's different. Ok, doesn't matter.

Second, the fact that your timing is not a lot different for sizes that fit the cache means your system probably lacks some kind of smarter instruction pipelining which is, I presume, present on mine. To be honest, I have no idea why in my case there was such a notable difference, i.e. from 12 to 45 seconds, while in your case it's 30 to 59.