Hacker News Reader

Comment by masklinn | Hacker News Reader

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.

View on HN

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

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.

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.

Reply on news.ycombinator.com