7 ms·

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

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.)
      - BeeOnRope 6y ago
        memcpy doesn't have this same problem because it is known-length without any early exit.
- ridiculous_fish 6y ago
  The page size is a runtime property - for example recent iOS devices have 16KB pages while older ones are 4k. There may be ways to make it safe, but it seems to be firmly in the "compiler heroics" camp.
  - mehrdadn 6y ago
    Page sizes are easy to lower bound when you're compiling. You know the target system you're compiling for. This most definitely is not in the "compiler heroics" camp.
    - ridiculous_fish 6y ago
      IMO this is one of those fragile optimizations. If the optimization is important, it should be explicit (hand-rolled asm) or else you risk breaking it. If it's not important, then nobody cares. Emitting OoB reads dependent on optimization level? Think about ASAN, debugger watchpoints...can't be worth it! clang has a cool feature that highlights missed vectorization opportunities: > clang++ -O3 -c test.cpp -Rpass-analysis=loop-vectorize test.cpp:5:4: remark: loop not vectorized: loop control flow is not understood by vectorizer [-Rpass-analysis=loop-vectorize] love it!
      - BeeOnRope 6y ago
        In practice this type of over-read is not uncommon in library code (even for standard routines), but I haven't seen compilers generate it. False positives with memory-sanitizers is definitely a problem: the hand-rolled library uses can be whitelisted, but that's not feasible once the compiler starts generating it in arbitrary code.
    - cesarb 6y ago
      > Page sizes are easy to lower bound when you're compiling. You know the target system you're compiling for. Do you really know the target system? Most of the time, you want the compiled code to work not only on the current system, but also in future systems of the same lineage. What prevents a future version of the architecture from for instance lowering the translation granule from 4096 bytes to 512 bytes, or even lower?
userbinator 6y ago
More interestingly: if I use "good old-school C89" char instead of bool and make the loop body branchless, I get actual vector instructions that appear to be consuming 256 bytes at a time: https://godbolt.org/z/57766b https://godbolt.org/z/57766b Wow! If I use bool and keep the body branchless (z |= (string[i] < 0);), the vector instructions disappear and it goes back to doing only 4 bytes at a time. That is very odd.
- im3w1l 6y ago
  256 bits (=32 bytes)? EDIT: Oh I see now, it's an unrolled loop each iteration of which uses 8 256bit vector instructions for a total of 256 bytes.
deathanatos 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. If `size` was enormous and the first character "was negative"¹, then one extra byte of lookahead would never SIGSEGV; `size` is enormous, and by definition, that is presumably more than our lookahead. If you mean, "the first character of the lookahead's block" then it still doesn't make sense. Even in the case where we exit later, we still can't access later bytes of the lookahead if we don't know them to be out of bounds. In the example Godbolt you linked to, the compiler is doing 8 byte jumps with the index. (It's not doing a great job, as we're still reading a byte at a time. But the bounds checks and the index increment will get reduced.) But, what the compiler is doing in your example could also be done in the early exit example. It'd be basically the same code, but replace .LBB0_10 with something like, cmpb $0, (%rdi,%rdx) js do_exit cmpb $0, 1(%rdi,%rdx) js do_exit # etc. for the remaining 6 reads .do_exit xorl %eax, %eax retq This is very similar to your Godbolt, which also does 8 individual memory accesses. We know they won't segfault here for the same reason we know they won't in your Godbolt: we check ahead that we can access the next 8 bytes and abort to the non-unrolled version if not. The cmp/js's are very likely not as efficient as the mov/or's, but that's not the point; the point is the unroll is possible. It is not the early exit that prevents a loop unroll. Something else is stopping it, either it does not think it worth it, is not sufficiently intelligent, or some arcana of C prevents it. (Your example alternates between mov and or, in a very interesting pattern, which makes me suspect it also knows something there, and perhaps more opportunity.) ¹This is an ugly example, since the implementation is free to have a char with range 0-255.
- ridiculous_fish 6y ago
  > one extra byte of lookahead would never SIGSEGV; `size` is enormous, and by definition, that is presumably more than our lookahead But `size` is just arbitrary number, while the code as written will not proceed past the first negative char. For example some jerk may write: c_is_ascii_branchy("\xFF", a_gazillion); but the function has to stop at the first char. > It is not the early exit that prevents a loop unroll It really is!

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.)
    - BeeOnRope 6y ago
      memcpy doesn't have this same problem because it is known-length without any early exit.
ridiculous_fish 6y ago
The page size is a runtime property - for example recent iOS devices have 16KB pages while older ones are 4k. There may be ways to make it safe, but it seems to be firmly in the "compiler heroics" camp.
- mehrdadn 6y ago
  Page sizes are easy to lower bound when you're compiling. You know the target system you're compiling for. This most definitely is not in the "compiler heroics" camp.
  - ridiculous_fish 6y ago
    IMO this is one of those fragile optimizations. If the optimization is important, it should be explicit (hand-rolled asm) or else you risk breaking it. If it's not important, then nobody cares. Emitting OoB reads dependent on optimization level? Think about ASAN, debugger watchpoints...can't be worth it! clang has a cool feature that highlights missed vectorization opportunities: > clang++ -O3 -c test.cpp -Rpass-analysis=loop-vectorize test.cpp:5:4: remark: loop not vectorized: loop control flow is not understood by vectorizer [-Rpass-analysis=loop-vectorize] love it!
    - BeeOnRope 6y ago
      In practice this type of over-read is not uncommon in library code (even for standard routines), but I haven't seen compilers generate it. False positives with memory-sanitizers is definitely a problem: the hand-rolled library uses can be whitelisted, but that's not feasible once the compiler starts generating it in arbitrary code.
  - cesarb 6y ago
    > Page sizes are easy to lower bound when you're compiling. You know the target system you're compiling for. Do you really know the target system? Most of the time, you want the compiled code to work not only on the current system, but also in future systems of the same lineage. What prevents a future version of the architecture from for instance lowering the translation granule from 4096 bytes to 512 bytes, or even lower?

userbinator 6y ago

More interestingly: if I use "good old-school C89" char instead of bool and make the loop body branchless, I get actual vector instructions that appear to be consuming 256 bytes at a time: https://godbolt.org/z/57766b https://godbolt.org/z/57766b Wow! If I use bool and keep the body branchless (z |= (string[i] < 0);), the vector instructions disappear and it goes back to doing only 4 bytes at a time. That is very odd.

im3w1l 6y ago
256 bits (=32 bytes)? EDIT: Oh I see now, it's an unrolled loop each iteration of which uses 8 256bit vector instructions for a total of 256 bytes.

deathanatos 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. If `size` was enormous and the first character "was negative"¹, then one extra byte of lookahead would never SIGSEGV; `size` is enormous, and by definition, that is presumably more than our lookahead. If you mean, "the first character of the lookahead's block" then it still doesn't make sense. Even in the case where we exit later, we still can't access later bytes of the lookahead if we don't know them to be out of bounds. In the example Godbolt you linked to, the compiler is doing 8 byte jumps with the index. (It's not doing a great job, as we're still reading a byte at a time. But the bounds checks and the index increment will get reduced.) But, what the compiler is doing in your example could also be done in the early exit example. It'd be basically the same code, but replace .LBB0_10 with something like, cmpb $0, (%rdi,%rdx) js do_exit cmpb $0, 1(%rdi,%rdx) js do_exit # etc. for the remaining 6 reads .do_exit xorl %eax, %eax retq This is very similar to your Godbolt, which also does 8 individual memory accesses. We know they won't segfault here for the same reason we know they won't in your Godbolt: we check ahead that we can access the next 8 bytes and abort to the non-unrolled version if not. The cmp/js's are very likely not as efficient as the mov/or's, but that's not the point; the point is the unroll is possible. It is not the early exit that prevents a loop unroll. Something else is stopping it, either it does not think it worth it, is not sufficiently intelligent, or some arcana of C prevents it. (Your example alternates between mov and or, in a very interesting pattern, which makes me suspect it also knows something there, and perhaps more opportunity.) ¹This is an ugly example, since the implementation is free to have a char with range 0-255.

ridiculous_fish 6y ago
> one extra byte of lookahead would never SIGSEGV; `size` is enormous, and by definition, that is presumably more than our lookahead But `size` is just arbitrary number, while the code as written will not proceed past the first negative char. For example some jerk may write: c_is_ascii_branchy("\xFF", a_gazillion); but the function has to stop at the first char. > It is not the early exit that prevents a loop unroll It really is!