News for hackers. Stuff that matters.
Re:Almost Always Unsigned by virtualritz on Sunday January 02, 2022 @04:51AM (#29767312)
While wrapping parts of OpenSubdiv for Rust [1] I noticed the C++ API was littered with uses of int for indexing/lengths (both are always positive) of geometry buffers.

So I opened a ticket with Pixar [2].

Some of the same strange arguments were brought forward (incl. the Google style guide BS). I wrote a longish reply [3] that mentions two comments [4,5] from an ill-guided article promoting use of signed in C++.

I closed the ticket in the end because I felt that if people really believe there are good reasons for signed in the cases at hand they haven't grokked the problem sufficiently – trying to convince them otherwise would not be a good use of my time.

[1] https://crates.io/crates/opensubdiv-petite

[2] https://github.com/PixarAnimationStudios/OpenSubdiv/issues/1...

[3] https://github.com/PixarAnimationStudios/OpenSubdiv/issues/1...

[4] https://www.learncpp.com/cpp-tutorial/unsigned-integers-and-...

[5] https://www.learncpp.com/cpp-tutorial/unsigned-integers-and-...

Re:Almost Always Unsigned by jcelerier on Sunday January 02, 2022 @05:28AM (#29767507)
Quoting one of these comments:

> The argument with substracting 5 from 3 is not an argument against using unsigned. When you use signed you can run into a similar problem when the result underflows. This happens much less frequent and causes UB, at INT_MIN, which is the worst kind of bug. The bug is often not triggered durring testing and you will only notice it when it is too late.

The "When you use signed you can run into a similar problem" part is just not true in our world. 3 - 5 happens much more often than anything that may cause signed .*flow.

    "signed underflow" "bug report"
yields 8 results on google FFS
Re:Almost Always Unsigned by leni536 on Sunday January 02, 2022 @05:44AM (#29767615)
No such thing as "underflow" for integers. Signed integers overflow in both directions. Underflow is a floating point concept.

Edit: https://en.m.wikipedia.org/wiki/Arithmetic_underflow

Re:Almost Always Unsigned by cies on Sunday January 02, 2022 @09:54AM (#29769152)
So what about an unsigned int going below zero? I think most in the comments here mean that by "underflow", but i could be mistaken (and it should correctly be called "overflow" as well).

I agree with the WP article saying integers more correctly "wrap around" (than overflow).

Re:Almost Always Unsigned by leni536 on Sunday January 02, 2022 @10:56AM (#29769728)
The C standard only calls certain integer arithmetic to "overflow" if it results in undefined behavior. In that sense undefined integer arithmetic never overflows, but they "wrap around", as the behavior is defined there.

I can't actually find a normative definition for "overflow" in the C or C++ standards, but there are sections and notes that describe this interpretation:

C++: https://eel.is/c++draft/full#basic.fundamental-note-2

C: http://web.archive.org/web/20211231011139/https://cigix.me/c...

There can be subtle differences between various definitions of "overflow", and I imagine there could be other subtly different definitions outside C and C++. But "underflow" is exclusively a floating point concept, as far as I know.

Re:Almost Always Unsigned by von_lohengramm on Sunday January 02, 2022 @05:55AM (#29767675)
API contracts aside, signed indices do have a major benefit: https://godbolt.org/z/q4eTdPdcd
Re:Almost Always Unsigned by strictfp on Sunday January 02, 2022 @07:59AM (#29768371)
Thanks! If you don't mind explaining, what are we seeing here?
Re:Almost Always Unsigned by masklinn on Sunday January 02, 2022 @09:05AM (#29768770)
After the initial setup block,

    c1 = block[i1]; c2 = block[i2];
    if (c1 != c2) return (c1 > c2);
    i1++; i2++;
becomes

        mov     cl, byte ptr [rdx + rcx]
        cmp     byte ptr [rdx + rax], cl
        jne     .LBB0_6
        lea     eax, [rdi + 2]
        lea     ecx, [rsi + 2]
if the indices are unsigned, but

        mov     al, byte ptr [rcx + rdx + 1]
        cmp     byte ptr [rdi + rdx + 1], al
        jne     .LBB1_6
if the indices are signed, that is the compiler just removes the indices and traverses the block directly (starting at the input offsets).

That's because in C (and C++) overflow is UB, so the compiler can assume it doesn't happen. Clang is apparently unable to make such a determination or work around it for unsigned, so for every increment of the indices it actually goes and computes the indices to fetch the items from the array.

Incidentally, GCC does not care and generates the exact same (rather different) code for both signednesses.

Re:Almost Always Unsigned by graphitemaster on Sunday January 02, 2022 @11:27AM (#29770068)
In this case the problem is more specifically the use of uint32_t. I never quite mentioned in the article that if you're going to use unsigned integers for this sort of thing to always use the native-word-size unsigned type, e.g size_t, if you actually change that to uint64_t (or size_t) the code generation is better as you can see here: https://godbolt.org/z/11nEz6EPT
Re:Almost Always Unsigned by sparkie on Sunday January 02, 2022 @09:42AM (#29769048)
I see no reason why the same addressing mode could not be used in both versions. This just seems like an optimization that has been made under the assumption that in the addressing mode

    [reg1 + reg2 + disp]
reg2 refers to a signed integer (Which may result in the effective address being < reg1 if reg2 is negative).

Obviously you would not want to make the same assumption if reg2 refers to an unsigned integer, because if the most significant bit is set, it would result in an effective address below reg1, which is definitely not what we would expect from adding an unsigned integer.

But in this case, 64-bit addressing is being used, and the value of reg2 is a 32-bit integer which has been specifically zero-extended. We can make the assumption that [reg1 + reg2 + disp] can never result in an effective address below reg1 (assuming positive disp).

If you take the signed version, and replace the lines

    movsxd  rdi, edi
    movsxd  rcx, esi
with

    movzx  rdi, edi
    movzx  rcx, esi
I believe you will have something functionally equivalent to the unsigned version.

Of course, this same optimization could not apply if we were using uint64, but it could in the case of int64.

Either way, buggy code with no bounds checking is not a reliable method of determining what optimizations can be done in production.

Re:Almost Always Unsigned by tom_ on Sunday January 02, 2022 @01:28PM (#29771851)
The code is compiled as it is in order to handle the case where the indexes need to wrap around. Suppose i1=0xffffffff on entry - you then want to access block[0x00000000ffffffff], block[0x0000000000000000], block[0x00000000000000001]. I've written out all 64 bits of the offset, in the hope this makes the problem clearer: there's no addressing mode for getting the 32 bit truncation. That's why there's an LEAs after each access. (Note that they write to the 32 bit part of each register.)

In the int32_t case, suppose i1=-1. Then you want to access block[0xffffffffffffffff], block[0x0000000000000000], block[0x0000000000000001], and so on. You can do an initial sign extension of the indexes, and then the base64+index64+disp32 addressing mode gives you the right result.

Make the unsigned version take uint64_t indices, and you get the same code for both. Or #include <stddef.h>, and make it take size_t - same thing. This is exactly the sort of thing that size_t is there for.