6 ms·

I'm somewhat surprised that compilers doesn't optimize this automatically. I thought at first that it might be something C++ related, but I tried a straight C

by nkurz 6y ago

I'm somewhat surprised that compilers doesn't optimize this automatically. I thought at first that it might be something C++ related, but I tried a straight C equivalent[1] with Godbolt and it wasn't optimized by any the main compilers either. Is there a standard related reason why this can't be optimized to work on chunks of 8B ints? Or even longer vectors? Or is this just proof of the fact that there are so many possible optimizations that a compiler can't possibly do all of them? [1] https://godbolt.org/z/WfPWEz https://godbolt.org/z/WfPWEz

lilyball 6y ago
Is the optimizer allowed to add extra memory accesses to locations that otherwise wouldn’t have been accessed? Because that’s required here.
- kevingadd 6y ago
  In another language, perhaps. It'd definitely be introducing undefined behavior if you did it to C or C++, and it would likely cause intermittent crashes.
  - deathanatos 6y ago
    No, what they mean is that, say we have a block read of 8 in the unrolled version, and all upcoming 8 indexes are valid memory locations, that is, a read would never segfault and never cause UB. Say they are: 20 20 20 20 ff 20 20 20 ^^ The ff is where the naïve algorithm would abort. But, some versions of an unrolled loop, if they do an 8-byte move to a register would read/access all 8 bytes. But the naïve version won't; it'll stop at the ff, never accessing the last 3 bytes. Even if we can guarantee the bytes are valid, does C somehow guarantee that the accesses would not occur? But, even with that, you can still unroll the loop to: bounds check the next 8 bytes (is idx + 8 < size) read 1 byte, abort if not ascii read 1 byte, abort if not ascii etc. It isn't as efficient as reading 8 bytes in one fell swoop and using math magic to process them all in one pass. But it still means that, so long as we remain in this unrolled version, we're eliding 7 out of 8 bounds checks and increments to the index.
    - BeeOnRope 6y ago
      The benefit of unrolling like this is quite small: just some reduction of loop overhead. The primary trick demonstrated here is combining 8 checks into a single operation.
      - deathanatos 6y ago
        Oh, absolutely, the trick demonstrated in the article is significantly better. (That I had to elide 75% of the instructions in the psuedo-code that I wrote is practically proof of that.) My point was only that it is possible to unrolled the loop without introducing UB.
ridiculous_fish 6y ago
This particular code cannot be effectively optimized because of the early exit inside the loop. What if `size` was enormous and the first character was negative? One extra byte of lookahead might SIGSEGV! So it must gingerly step one byte at a time. Rewrite it to always consume the full string, and it goes 8 bytes at a time: https://godbolt.org/z/xG7avr https://godbolt.org/z/xG7avr In practice the best implementations will manually align and then unroll.
- mehrdadn 6y ago
  > What if `size` was enormous and the first character was negative? One extra byte of lookahead might SIGSEGV! So it must gingerly step one byte at a time. Pages aren't 1 byte each, they're 4KiB. You can't just segfault at by crossing 1 byte at any arbitrary address. Some alignment checks to handle edge cases should let the compiler at least read things 8-byte aligned in the steady state and only fall back on edge cases.
  - kevingadd 6y ago
    If you're at byte 4095 and you advance by 1 byte and the next page is a guard page, you're dead. You can minimize the risk of this by requiring that input addresses be aligned (and many ABIs/APIs do require this) but it's realistic to say that an extra byte of lookahead can and will SIGSEGV in unfortunate cases.
    - mehrdadn 6y ago
      What I'm saying is that the compiler can generate code that examines the memory address and looks ahead only when it's safe to do so.
      - saurik 6y ago
        (And for those who think this is strange, memcpy implementations usually do this, so there is precedent that this is very sane.)
deleted 6y ago
[deleted]
Someone 6y ago
I don’t think the compiler can assume the entire memory range from string to string+size (exclusive) can be read (the ‘C machine’ only reads it up to the first byte ≥ 128), but even if so, the compiler doesn’t know whether bytes ≥ 128 are rare or common, nor does it know the distribution of buffer lengths. ⇒ I think you should only start complaining if the compiler had pragmas to indicate that returning ‘false’ is extremely rare and that size can run in the kilobytes, and the program used them.

by nkurz 6y ago

lilyball 6y ago

Is the optimizer allowed to add extra memory accesses to locations that otherwise wouldn’t have been accessed? Because that’s required here.

kevingadd 6y ago
In another language, perhaps. It'd definitely be introducing undefined behavior if you did it to C or C++, and it would likely cause intermittent crashes.
- deathanatos 6y ago
  No, what they mean is that, say we have a block read of 8 in the unrolled version, and all upcoming 8 indexes are valid memory locations, that is, a read would never segfault and never cause UB. Say they are: 20 20 20 20 ff 20 20 20 ^^ The ff is where the naïve algorithm would abort. But, some versions of an unrolled loop, if they do an 8-byte move to a register would read/access all 8 bytes. But the naïve version won't; it'll stop at the ff, never accessing the last 3 bytes. Even if we can guarantee the bytes are valid, does C somehow guarantee that the accesses would not occur? But, even with that, you can still unroll the loop to: bounds check the next 8 bytes (is idx + 8 < size) read 1 byte, abort if not ascii read 1 byte, abort if not ascii etc. It isn't as efficient as reading 8 bytes in one fell swoop and using math magic to process them all in one pass. But it still means that, so long as we remain in this unrolled version, we're eliding 7 out of 8 bounds checks and increments to the index.
  - BeeOnRope 6y ago
    The benefit of unrolling like this is quite small: just some reduction of loop overhead. The primary trick demonstrated here is combining 8 checks into a single operation.
    - deathanatos 6y ago
      Oh, absolutely, the trick demonstrated in the article is significantly better. (That I had to elide 75% of the instructions in the psuedo-code that I wrote is practically proof of that.) My point was only that it is possible to unrolled the loop without introducing UB.

ridiculous_fish 6y ago

This particular code cannot be effectively optimized because of the early exit inside the loop. What if `size` was enormous and the first character was negative? One extra byte of lookahead might SIGSEGV! So it must gingerly step one byte at a time. Rewrite it to always consume the full string, and it goes 8 bytes at a time: https://godbolt.org/z/xG7avr https://godbolt.org/z/xG7avr In practice the best implementations will manually align and then unroll.

mehrdadn 6y ago
> What if `size` was enormous and the first character was negative? One extra byte of lookahead might SIGSEGV! So it must gingerly step one byte at a time. Pages aren't 1 byte each, they're 4KiB. You can't just segfault at by crossing 1 byte at any arbitrary address. Some alignment checks to handle edge cases should let the compiler at least read things 8-byte aligned in the steady state and only fall back on edge cases.
- kevingadd 6y ago
  If you're at byte 4095 and you advance by 1 byte and the next page is a guard page, you're dead. You can minimize the risk of this by requiring that input addresses be aligned (and many ABIs/APIs do require this) but it's realistic to say that an extra byte of lookahead can and will SIGSEGV in unfortunate cases.
  - mehrdadn 6y ago
    What I'm saying is that the compiler can generate code that examines the memory address and looks ahead only when it's safe to do so.
    - saurik 6y ago
      (And for those who think this is strange, memcpy implementations usually do this, so there is precedent that this is very sane.)

deleted 6y ago

[deleted]

Someone 6y ago

I don’t think the compiler can assume the entire memory range from string to string+size (exclusive) can be read (the ‘C machine’ only reads it up to the first byte ≥ 128), but even if so, the compiler doesn’t know whether bytes ≥ 128 are rare or common, nor does it know the distribution of buffer lengths. ⇒ I think you should only start complaining if the compiler had pragmas to indicate that returning ‘false’ is extremely rare and that size can run in the kilobytes, and the program used them.