8 ms·
Subtraction is not comparison
- seivadmas 12y agoWTF? The article states: x = 1987654321 and y = -1987654321? Then the difference between them is -319658654 (negative) which proves that x is less than y. That’s less than correct. Which is completely 100% wrong. Surely the difference would be x - y i.e (1987654321 - (-1987654321)) = (1987654321 + 1987654321) = 3975308642. Which is perfectly ok, because that's positive and so proves x is greater than y. So this comparison works just fine for negative integers...
- Scaevolus 12y ago(int32_t)3975308642 == -319658654 Overflow makes intuitive arithmetic do unusual things. Similarly, using a+b/2 for binary search midpoints is wrong. http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html?m=1 http://googleresearch.blogspot.com/2006/06/extra-extra-read-...
- imron 12y agoThe writer assumes that the reader understands and knows about how integer overflows work in C.
- bluedino 12y agoExactly, don't use subtraction for comparison in C. The previous commenter may have entered that into say, a Python console where it wouldn't exhibit that behavior.
- seivadmas 12y agoAh I see the problem. Actually I used a Ruby console. So what then is the CORRECT way of doing this comparison in C, avoiding potential overflow pitfalls?
- cygx 12y agoreturn (x > y) - (x < y);
- vardump 12y agoThat can be very expensive operation. Potentially two branches, not counting return from subroutine.
- cremno 12y agoIf performance really is of concern, qsort() or similar functions probably shouldn't be used. Instead a dedicated function, which allows to choose a specific algorithm (qsort() doesn't have to use quicksort) and also doesn't involve calling a comparison function pointed to by a function pointer, can be used.
- bluecalm 12y agoOne interesting thing I have learned recently is that GCC can do inlining through function pointers. That doesn't make your point about dedicated function being better idea for performance but it's one thing "std::sort is faster by design" people often miss. From GCC documentation: >>-findirect-inlining Inline also indirect calls that are discovered to be known at compile time thanks to previous inlining. This option has any effect only when inlining itself is turned on by the -finline-functions or -finline-small-functions options. Enabled at level -O2.
- cremno 12y agoBut GCC likely isn't able to do that for libc functions like qsort(). Maybe if LTO is enabled and libc is linked statically, it might.
- bluecalm 12y agoI have no idea when it can and when it can't do that to be honest. I tested qsort vs std::sort on my machine on my data and performance was the same (Windows, MinGW, GCC 4.8, -flto enabled) but other people reported different results.
- CamperBob2 12y agoExactly, don't use subtraction for comparison in C.... when the difference might exceed 2^31. For many data types, like time, that will normally never happen, making subtraction the safest no-brainpower-needed approach. If in doubt, use the next larger integer type.
- tptacek 12y agoIf you ever want to make a vulnerability researcher drool visibly, have a C programmer say, "that will normally never happen, making ${XXX} the safest no-brainpower-needed approach".
- CamperBob2 12y agoYou know what causes bugs in C (besides memory leaks)? Complex or clever expressions that don't reveal their semantics at first glance. As an example from elsewhere in the thread: return (x > y) - (x < y); Quick. What's that do? What will the next person who looks at the code think it does?
- marvy 12y agoIf it's in a function called "cmp", I think they will guess.
- CamperBob2 12y ago"I think they will guess." I think tptacek must be ready to have his bib changed, with all the drooling he must be doing.
- nitrogen 12y agoA C programmer should know that comparisons evaluate to 1 for true and 0 for false.
- pbsd 12y agoC programmers should also be familiar with carry propagation; I see no reason they shouldn't be expected to work out the correctness of int cmp(int x, int y) { const unsigned a = x; const unsigned b = y; const unsigned s = sizeof x * 8 - 1; return ((b^((b^(b-a))&(a^(b-a))))>>s)&~-((a^((a^(a-b))&(b^(a-b))))>>s)^-((a^((a^(a-b))&(b^(a-b))))>>s)&~-((b^((b^(b-a))&(a^(b-a))))>>s); }
- kragen 12y agoDon't use subtraction for comparison in any language that uses floating-point (like Lua or JS) or silent overflow (like, typically, C, C++, Java, and C#). There are a few languages, like Python, where integer subtractions that overflow will transparently produce bignums, but they are kind of the exception.
- _almosnow 12y agoYeah but that's what happens when people become so adapted to their tools that they forget how real math/world works... and they even have the nerve to stand up for their flawed tools. I actually like and use C everyday, but it would be aberrant for me to say essentially what the article implies: "A math algorithm is wrong because it doesn't work in C"
- ufo 12y agoSubtraction is comparison at the assembly level though. C sadly doesn't give any way to interact with the overflow flags though...
- vardump 12y agoYup. On pretty much any architecture I can think of, a CMP is exactly like a SUB that does not store result, but sets only flags.
- haberman 12y agoWhen something is easy at the hardware level but there is no easy way to express it in programs, it suggests a failure of the abstraction. Or more positively, room for improvement. I'd love to see some way that this can be expressed elegantly in C.
- psyklic 12y agoThe way that C expresses it elegantly is via the comparison operator. The author is concerned that people try to be clever and use subtraction instead. Here is how the author corrected this error by using comparison operators instead of subtracting (in the tree man page): int intcmp(struct node *e1, struct node *e2) { - return (e1->i - e2->i); + return (e1->i < e2->i ? -1 : e1->i > e2->i); } The ternary operator is necessary, because in C a relational operator is evaluated to 0 (false) or 1 (true). So, the author added a special case for returning a negative value (indicating the first argument should be sorted before the second).
- caf 12y agoAn alternative without the ternary is return (e1->i > e2->i) - (e1->i < e2->i);
- xmodem 12y agoMy C's a little rusty, but isn't the exact integer returned by the comparison undefined? Isn't is just defined as just zero or non-zero? Therefore i would argue this is just as risky as the original solution, and that it's better to use the ternary operator
- gonzo 12y agoSomeone needs to explain to Teddy how the compiler implements subtraction. Hint: his example is fine (and thus, Ted is wrong). But, since Ted is OpenBSD.. here come the downvotes. As the poster below states, the example in the last link of Ted's posting has overflow problems.
- cremno 12y agoYou should read the post again and then open the last link. Then tell us again that the example is fine.
- imron 12y agoDoesn't seem so fine to me.. /*compare.c*/ #include <stdio.h> int compare( int x, int y ) { return x - y; } void testCompare( int x, int y ) { if ( compare( x, y ) < 0 ) { printf( "%d is less than %d\n", x, y ); } else { printf( "%d is greater than or equal to %d\n", x, y ); } } int main() { testCompare( 5, 10 ); testCompare( 10, 5 ); testCompare( 1987654321, -1987654321 ); return 0; } $ clang -o compare compare.c $ ./compare 5 is less than 10 10 is greater than or equal to 5 1987654321 is less than -1987654321
- deleted 12y ago[deleted]
- industriousthou 12y agoI'm learning javascript, so this sort of issue doesn't really make sense to me, but I gather this is a specific issue with C and it has to do with how large integers are handled. Fair enough, but I'm actually quite curious how you should solve this kind of problem in a low level language and why.
- SamReidHughes 12y agoYou just write a function that returns -1, 0, or 1. It's not specific to C, it's in any language that has fixed-size types. Another reason (a lame one) to return -1, 0, or 1 is that often the caller expects one of those return values for some reason (because the caller is dumb and your comparison function is replacing another one that behaved that way).
- TwoBit 12y agoThis isn't a problem with comparison by subtraction, it's a problem with integer overflow. There's nothing wrong with comparison via subtraction if you account for overflow, which you always need to do in programming.
- marvy 12y agoBut the only way to account for overflow is to avoid comparison by subtraction.
- arielby 12y agoYou can also do the comparison over larger integers, for example int cmp(int x, int y) { return (int) (((long)x-(long)y)>>32); }
- Sharlin 12y agoIn mainstream compilers, even on x64, sizeof(long) == sizeof(int). You need long long instead. Of course, in the general case there's exactly zero guarantee that there even exists an integral type wider than int.
- TwoBit 12y agoThe C99 language standard requires support for long long.
- dezgeg 12y agoBut an implementation where sizeof(int) == sizeof(long) == sizeof(long long) is allowed by the specification.
- marvy 12y agoOn a (slightly) more practical level: there exists some largest integer type. You may someday need to sort it. If you want your sort to always work, you can't afford to overflow.
- ambrop7 12y agoJust do (x>y)-(x<y). It's actually pretty fast: http://stackoverflow.com/questions/10996418/efficient-integer-compare-function/10997428#10997428 http://stackoverflow.com/questions/10996418/efficient-intege... Disclaimer: not actually my original invention.
- pkhuong 12y agoThat's a good one for integers and if you don't intend the comparator to be inlined. For inlined comparison, I prefer if (x == y) return 0; return (x < y) ? -1 : 1;. The control flow is more transparent and C compilers are usually able to perform the if/if conversion necessary to get the single comparison you'd expect in hand-rolled sorts or searches.
- salmonellaeater 12y agoOne way to reduce the chance of this problem occurring is to change the specification of the comparison function to only allow -1, 0, and 1 to be returned (or even better, use enums like LESS, EQUAL, GREATER). This makes doing the wrong thing more cumbersome when implementing a comparison function, but it also makes it easier to implement the actual sort function because jump tables and switch statements become possibilities.
- Garlef 12y agoFrom a category theoretic point of view, subtraction is a natural candidate for comparison: It is the internal hom-functor in the ordered monoid of integers. One could argue that internal hom functors are the very essence of a "comparison". The sole problem seems to be that integers in C are not actually integers.
- emmelaich 12y agoI think you're right but it goes deeper. Integers as represented in computers are not integers.
- marcosdumay 12y agoNobody handles overflow in practice. There are all kinds of code patterns that are sensitive to overflow, and people do use those patterns because they are simple. A program that does not fail on overflow is something almost illegible, and for most applications the only difference it can make is displaying the correct error message before closing, because the problem domain has no procedure for that. C programmers are implicitly expected to estimate the value ranges they'll be dealing with, and correctly size their variables.