Feel the cache size: a definitive experiment
melikyan.blogspot.com
melikyan.blogspot.com
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
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
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 secsSecond, 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.
I mean, he's just executing trivial code from random locations in memory - not a typical access pattern at all. Because of this, the experiment exaggerates the effect of code size on performance. For example, if you had a 1 million line program that didn't loop, it's performance would not degrade nearly as much as his results imply.
The "valuable" lession we can learn from this is this: Never access a million random memory locations in your innermost loop :-)
"What Every Programmer Should Know About Memory" - http://people.redhat.com/drepper/cpumemory.pdf
http://www.amazon.com/UNIX-Systems-Modern-Architectures-Mult...
The impact is that random access has suffered and cache has become vital in coping with the majority of those seemingly random jumps. Algorithms like quicksort benefit from locality of reference and hence better utilise the cache than algorithms that theorectically do less work.
Its interesting to see it jump like this, but its not indicative of large programs so much as it is indicative of what happens when you randomly access memory and effectively nullify your cache and your memorys DDR properties. Thankfully most programs don't in practice do this, if they did the programs would run about as well as they did in the mid 90's on an original Pentium.
iirc, the GNOME folks once did some benchmarking and found they could get huge speedups by trimming a few bytes here and there from the gnome libraries.
I hope more people take the time to consider the implications of code bloat. I'm not asking for hand written assembler, but just a little bit of thought here and there can produce huge improvements.
EDIT: This is also why ssd's are so exciting. Yes the're not perfect yet, but they promise to (all but) eliminate disk latency within the next few years.
"We should forget about small efficiencies, say about 97% of the time" Donald Knuth
We often forget about the rest 3% too.
Which doesn't help me :-(
I have a bit of code that steps through a binary file made up of blocks that are of a known size, in an arbitrary order, and come in N different flavors and save them into N output files, one for each flavor. It actually does much more too, but lets pretend this is the only operation. The simple way to do this is to step sequentially through the file and load everything into memory in N different structures and then save your files. But the problem is that sometimes you don't have enough memory to do that, so you have to loop through the file N times, loading a type, saving it, clearing memory and repeating. Since that seems very inefficient, so I thought I'd be clever and on the first pass through the file, load one of the flavors and also save file pointers to all the other blocks so that each subsequent pass could be done more quickly by seeking to the exact black that I needed to load.
Long story short, on regular hard drives, thanks to optimized sequential reads it can actually be faster to just do the dumb thing and loop through the file N times than seek though it randomly.
It's an excuse to show off the author's exciting new algorithm for computing the value of the integer "max": (func_table[max] - func_table[0]).
I'm not much of a C coder, is there a more idiomatic way to do this?
When I asked if there was more idiomatic way to do this, I meant more idiomatic than the original code, not actually using (max*11) in the code.
In other words, pointer subtraction gives an index (of integral type ptrdiff_t, which should be 64bit if pointers are). For all p2 and p1 pointing to the same type, p2==p1[p2-p1].
((func_table+max) - (func_table+0))
(*(func_table+max) - *(func_table+0))
But that's an interesting point about the standard - perhaps it's intended to allow a smaller sizeof(ptrdiff_t) than sizeof(void *), where no contiguous allocation would be allowed such that you the larger type.
However, you make a good point: the difference between two pointers is in multiples of the pointed-to size. It's not 11 bytes per function, but rather 11 * sizeof(pointer to function type) - probably 11 * 4 = 44 bytes. (the author is lucky that the functions are indeed laid out consecutively in memory)
When you want the difference between two pointers a and b to type T in bytes, either cast the pointers to char * before taking the pointer difference, or multiply by sizeof(T).