← Back to context

Comment by CerryuDu

1 month ago

Not to mention the potential signed integer overflow in (*right - *left) and (*left - *right), which is undefined behavior. And even if you rely on common two's complement wraparound, the result may be wrong; for example, (INT_MAX-(-1)) should mathematically yield a positive value, but the function will produce INT_MIN, which is negative.

And then we have this "modern" way of spelling pointers, "const int* right" (note the space). In C, declaration syntax mirrors use, so it should be "const int *right", because "*right" is a "const int".

I feel too old for this shit. :(

11 comments

CerryuDu

Reply
Joker_vD  1 month ago 

    const int left = *(const int*)untyped_left, right = *(const int*)untyped_right;

    return in_reverse?
        (right > left) - (right < left)
      : (left > right) - (left < right);

I wonder if there is a way to actually do it with only arithmetic, without comparisons?

  • adrian_b  1 month ago

    Using only arithmetic operators would require explicit checks for overflow and this would be a very inefficient implementation, because the comparison operators handle overflow implicitly without any overhead (because the comparison operators do not use the sign of the subtraction result to decide their truth value, but they compute the true sign of the result, by the modulo 2 sum, a.k.a. XOR, of the result sign with the integer overflow flag; this is done in hardware, with no overhead).

    The feature that integer comparison must be correct regardless of overflow has been a requirement in CPU design since the earliest times. Very few CPUs, the most notable examples being Intel 8080 and RISC-V, lacked this feature. The competitors and successors of Intel 8080, i.e. Motorola MC6800 and Zilog Z80 have added it, making them much more similar to the previously existing CPUs than Intel 8080 was. The fact that even microprocessors implemented with a few thousand transistors around 1975 had this feature emphasizes how weird is that RISC-V lacks such a feature in 2025, after 50 years and being implemented with a number of transistors many orders of magnitude greater.

  • CerryuDu  1 month ago 

        return in_reverse?
        (right > left) - (right < left)
      : (left > right) - (left < right);

    I prefer (with "greater" being ±1, defaulting to +1):

        return left < right ? -greater :
           left > right ? greater :
           0;

adrian_b  1 month ago

You are right, the implementation of the "compare" function should have used only comparison operators, not subtraction, because unlike subtraction the comparison operations are not affected by overflow (the hardware implementation of integer comparison handles overflow automatically).

When there is no overflow, the sign of the subtraction result provides the same information as a comparison operator, but this is no longer true when overflow happens.