5 ms·

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.

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.