@Eric Shinn said:
@bstorer said:
It's not a bad algorithm for this but it's really no better than the obvious method. Something like this:
<clip>
has a worst case of roughly 2n comparisons and a best case of n - 1 comparisons. The OP's has a worst (and best) case of roughly 1.5n comparisons. Hardly worth the effort.
Aha, so that's why it was done like that. It seems all the more useless in the context that it is only called a few times when the program is run, and the values are remembered.
Ah, but you missed where the author failed miserably. He spent his this time optimizing the algorithm, but he is referencing *min and *max directly instead of locals. I know what you're thinking. "Oh, the compiler caches these so it doesn't matter". Ah, but it doesn't, because if someone called the function with min and max pointing to the same memory, then caching would not work because the output produced would be different due to overlapping writes. Obviously no one in their right mind would do this and the results would be wrong, but the compiler doesn't know this. The compiler instead knows that it needs to maintain correct memory access behavior, so it forces a write to these memory addresses every time, and a subsequent read on every comparison.
Here is a simplification:
int set_and_add(int *a, int *b)
{
*a = 5;
*b = 6;
return *a + *b;
}
This would normally return 11. Unless a == b, in which case it returns 12. And this is the correct behavior. Since the compiler supports this behavior, *a and *b are written and then *a is read back before adding. Similarly with the WTF's min and max.
The C keyword "restrict" solves this problem, for you trying this at home.