Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Feel the cache size: a definitive experiment

melikyan.blogspot.com

Post reply on HN
Print view View original

11–20 of 33 posts

Re: Feel the cache size: a definitive experiment

#11

Post by mojuba »

paulgb wrote: post #9
jongraehl wrote: post #3

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]).

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?

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.

Re: Feel the cache size: a definitive experiment

#12

Post by mojuba »

lallysingh wrote: post #7
rarestblog wrote: post #4

Earlier quoted context omitted.

Too true. "We should forget about small efficiencies, say about 97% of the time" Donald Knuth We often forget about the rest 3% too.

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.

Valgrind/cachegrind are fairly common in the UNIX/C world. Our company uses it as part of the automated build/test run.

Re: Feel the cache size: a definitive experiment

#13

Post by paulgb »

mojuba wrote: post #11
paulgb wrote: post #9

Earlier quoted context omitted.

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?

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.

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.

Re: Feel the cache size: a definitive experiment

#14

Post by joeyo »

spitfire wrote: post #2

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 no…

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.

Re: Feel the cache size: a definitive experiment

#15

Post by mojuba »

paulgb wrote: post #13
mojuba wrote: post #11

Earlier quoted context omitted.

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.

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.

Not sure I understand your question, but all kinds of juggling with pointers is I think idiomatic in C.

Re: Feel the cache size: a definitive experiment

#16

Post by 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 funcs.h
    echo "Generating funcs.c"
    perl -e 'print "#include \"funcs.h\"\n\n";for ($i=0;$i funcs.c
    echo "Generating tab.h"
    perl -e 'print "#include \"funcs.h\"\n\n";print "int (*func_table[])(void) = {\n";for ($i = 0; $i  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 :
           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

Re: Feel the cache size: a definitive experiment

#17

Post by mojuba »

aminuit wrote: post #16

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 funcs.h echo "Generating funcs.c" perl -e 'print "#include \"funcs.h\"\n\n";for ($i=0;$i funcs.c echo "Generating tab.h" perl -e 'print "#include \"funcs.h\"\n\n";print "int (*func_tab…

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.

Re: Feel the cache size: a definitive experiment

#18

Post by jongraehl »

mojuba wrote: post #15
paulgb wrote: post #13

Earlier quoted context omitted.

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.

Not sure I understand your question, but all kinds of juggling with pointers is I think idiomatic in C.

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].

Re: Feel the cache size: a definitive experiment

#19

Post by [deleted] »

jongraehl wrote: post #18
mojuba wrote: post #15

Earlier quoted context omitted.

Not sure I understand your question, but all kinds of juggling with pointers is I think idiomatic in C.

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].

[deleted]

Re: Feel the cache size: a definitive experiment

#20

Post by jongraehl »

jongraehl wrote: post #3

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]).

You idiot! What you wrote would have been true only if the expression were &func_table[max] - &func_table[0].

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).

Post reply on HN