4 ms·

Feel the cache size: a definitive experiment

37 points by mojuba 17y ago

c00p3r 17y ago
http://people.redhat.com/drepper/cpumemory.pdf http://people.redhat.com/drepper/cpumemory.pdf
spitfire 17y ago
This is something that's been bothering me for the last decade (okay, more.). Every time I've articulated it in the past I've been dismissed, but it really is key to good performance. 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.
- rarestblog 17y ago
  Too true. "We should forget about small efficiencies, say about 97% of the time" Donald Knuth We often forget about the rest 3% too.
  - lallysingh 17y ago
    It's a shame that profiling/performance/cache utilization analysis tools aren't nearly as common/standardized as the rest of a developer's toolbox.
    - mojuba 17y ago
      Valgrind/cachegrind are fairly common in the UNIX/C world. Our company uses it as part of the automated build/test run.
      - lallysingh 17y ago
        Sadly they only support: X86/Linux, AMD64/Linux, PPC32/Linux, PPC64/Linux Which doesn't help me :-(
- joeyo 17y ago
  Side anecdote to your SSD note: 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.
jongraehl 17y ago
This article is not really about the memory cache hierarchy. 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]).
- deleted 17y ago
  [deleted]
- paulgb 17y ago
  Isn't it really calculating max * 11, since the functions pointed at by func_table[max] are 11 bytes long? I'm not much of a C coder, is there a more idiomatic way to do this?
  - mojuba 17y ago
    It could be max * 11, yes, but with optimizations turned on the compiler could produce something that wouldn't be that easy to calculate in a more general case. It's just that a file with one million functions is practically impossible to compile with optimizations.
    - paulgb 17y ago
      Right. What I meant was that (func_table[max] - func_table[0]) is equivalent to (in the example assembly given) max * 11. 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.
      - mojuba 17y ago
        Not sure I understand your question, but all kinds of juggling with pointers is I think idiomatic in C.
        jongraehl 17y ago
        Since not every one got it: in C, the difference between two pointers of type (T *) is the difference in (byte) addresses divided by sizeof(T). 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].
surki 17y ago
if you want to know more on this topic "What Every Programmer Should Know About Memory" - http://people.redhat.com/drepper/cpumemory.pdf http://people.redhat.com/drepper/cpumemory.pdf
- lallysingh 17y ago
  Over the top, but fun: Unix Systems for Modern Architectures http://www.amazon.com/UNIX-Systems-Modern-Architectures-Multiprocessing/dp/0201633388 http://www.amazon.com/UNIX-Systems-Modern-Architectures-Mult...
- Jebdm 17y ago
  Should this be encrypted? My computer says it is.
- terminus 17y ago
  A detailed (maybe too detailed) look at the interaction between Hierarchies of Memory and CPUS. Memory Systems: Cache, Memory, Disk [ http://www.amazon.com/Memory-Systems-Cache-DRAM-Disk/dp/0123797519 http://www.amazon.com/Memory-Systems-Cache-DRAM-Disk/dp/0123... ]
aminuit 17y ago
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 17y ago
  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.
comatose_kid 17y ago
Isn't this 'definitive experiment' just showing that code which doesn't take advantage of locality of reference is bound to be really slow if it is larger than the cache size? 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.
- fauigerzigerk 17y ago
  Exactly. This experiment shows pretty much the opposite of what it aims to prove. It shows that code bloat is completely irrelevant as long as locality is taken into account in performance critical parts of the code. The "valuable" lession we can learn from this is this: Never access a million random memory locations in your innermost loop :-)
- mojuba 17y ago
  The experiment does exaggarate the impact indeed, but I think there are real-world examples that are pretty close to it. For one thing, some bloated virtual machines. Let the effect of optimization of your VM be 20%, not 15 times, then 20% would be a huge gain you might struggle for if this is the runtime environment for your language.
PKeeble 17y ago
The massive difference in random access speeds in comparison to sequential speeds is the thing that changed in the last 15 years. The gap between memory clock speed and CPU clock speed has been increasing for all this time, whereas prior to that they were often similar. 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.

37 points by mojuba 17y ago

http://people.redhat.com/drepper/cpumemory.pdf http://people.redhat.com/drepper/cpumemory.pdf

This is something that's been bothering me for the last decade (okay, more.). Every time I've articulated it in the past I've been dismissed, but it really is key to good performance. 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.

rarestblog 17y ago
Too true. "We should forget about small efficiencies, say about 97% of the time" Donald Knuth We often forget about the rest 3% too.
- lallysingh 17y ago
  It's a shame that profiling/performance/cache utilization analysis tools aren't nearly as common/standardized as the rest of a developer's toolbox.
  - mojuba 17y ago
    Valgrind/cachegrind are fairly common in the UNIX/C world. Our company uses it as part of the automated build/test run.
    - lallysingh 17y ago
      Sadly they only support: X86/Linux, AMD64/Linux, PPC32/Linux, PPC64/Linux Which doesn't help me :-(
joeyo 17y ago
Side anecdote to your SSD note: 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.

jongraehl 17y ago

This article is not really about the memory cache hierarchy. 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]).

deleted 17y ago
[deleted]
paulgb 17y ago
Isn't it really calculating max * 11, since the functions pointed at by func_table[max] are 11 bytes long? I'm not much of a C coder, is there a more idiomatic way to do this?
- mojuba 17y ago
  It could be max * 11, yes, but with optimizations turned on the compiler could produce something that wouldn't be that easy to calculate in a more general case. It's just that a file with one million functions is practically impossible to compile with optimizations.
  - paulgb 17y ago
    Right. What I meant was that (func_table[max] - func_table[0]) is equivalent to (in the example assembly given) max * 11. 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.
    - mojuba 17y ago
      Not sure I understand your question, but all kinds of juggling with pointers is I think idiomatic in C.
      - jongraehl 17y ago
        Since not every one got it: in C, the difference between two pointers of type (T *) is the difference in (byte) addresses divided by sizeof(T). 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].

surki 17y ago

if you want to know more on this topic "What Every Programmer Should Know About Memory" - http://people.redhat.com/drepper/cpumemory.pdf http://people.redhat.com/drepper/cpumemory.pdf

lallysingh 17y ago
Over the top, but fun: Unix Systems for Modern Architectures http://www.amazon.com/UNIX-Systems-Modern-Architectures-Multiprocessing/dp/0201633388 http://www.amazon.com/UNIX-Systems-Modern-Architectures-Mult...
Jebdm 17y ago
Should this be encrypted? My computer says it is.
terminus 17y ago
A detailed (maybe too detailed) look at the interaction between Hierarchies of Memory and CPUS. Memory Systems: Cache, Memory, Disk [ http://www.amazon.com/Memory-Systems-Cache-DRAM-Disk/dp/0123797519 http://www.amazon.com/Memory-Systems-Cache-DRAM-Disk/dp/0123... ]

aminuit 17y ago

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 17y ago
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.

comatose_kid 17y ago

Isn't this 'definitive experiment' just showing that code which doesn't take advantage of locality of reference is bound to be really slow if it is larger than the cache size? 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.

fauigerzigerk 17y ago
Exactly. This experiment shows pretty much the opposite of what it aims to prove. It shows that code bloat is completely irrelevant as long as locality is taken into account in performance critical parts of the code. The "valuable" lession we can learn from this is this: Never access a million random memory locations in your innermost loop :-)
mojuba 17y ago
The experiment does exaggarate the impact indeed, but I think there are real-world examples that are pretty close to it. For one thing, some bloated virtual machines. Let the effect of optimization of your VM be 20%, not 15 times, then 20% would be a huge gain you might struggle for if this is the runtime environment for your language.

PKeeble 17y ago

The massive difference in random access speeds in comparison to sequential speeds is the thing that changed in the last 15 years. The gap between memory clock speed and CPU clock speed has been increasing for all this time, whereas prior to that they were often similar. 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.