5 ms·
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 inte
by 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 agoIsn'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 agoIt 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 agoRight. 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 agoNot sure I understand your question, but all kinds of juggling with pointers is I think idiomatic in C.
- jongraehl 17y agoSince 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 17y ago[deleted]
- deleted 17y ago[deleted]
- aminuit 17y agoNot 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 by the standard. In this case GCC is just subtracting the two addresses, with no division. His results (and mine above) bear this out. If you compile with -pedantic you'll actually get a warning about it.
- jongraehl 17y agoI'd noticed that I misread the original code and replied to my top-level post. 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.
- paulgb 17y agoYeah, I thought the top comment was saying that the way the author did it wasn't idiomatic, in which case I was wondering what is.
- jongraehl 17y agoYou 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).