21–30 of 33 posts
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].
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].
((func_table+max) - (func_table+0))
(*(func_table+max) - *(func_table+0))
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 y…
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.
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.
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…
The "valuable" lession we can learn from this is this: Never access a million random memory locations in your innermost loop :-)
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.
Earlier quoted context omitted.
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 y…
Yeah, that's what I was getting at.
Earlier quoted context omitted.
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].
Not exactly. The standard only defines pointer subtraction between two pointers that point into the same array object. That's not what's going on here. If he had written ((func_table+max) - (func_table+0)) then yes you would just get max. The difference is that (func_table[max] - func_table[0]) is actually (*(func_table+max) - *(func_table+0)) which is subtraction of two arbitrary function pointers. It's not covered…
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.
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…