4 ms·

Unrolling loops reduces the cost of loop termination checking. A tight loop like `for (i=0; i < n; i++) { acc += 1; }` is mostly overhead, you are constantly ch

Unrolling loops reduces the cost of loop termination checking. A tight loop like `for (i=0; i < n; i++) { acc += 1; }` is mostly overhead, you are constantly checking to see if you’re done or not. If you were given a loop like this in real life, like “come back to me and check if you’ve made enough doughnuts after every single individual doughnut you make, I’ll tell you when you’re done”, you would just quit your job in frustration, because it is a huge waste of your time. The compiler can unroll loops like that to `for (i=0; i < n; i+=8) { acc += 8; }` (ignoring the remainder of n/8), which does 8x fewer compare+conditional jump instructions. It has nothing to do with how many times you’ll be running the code; this kind of optimisation reduces the runtime of any single execution.

version_five 3y ago
Thanks for the explanation! So how would that play out in optimizing the code you posted? It will run all 2^32 iterations without checking for completion? How does it know when it's finished, and is that the only "unrolling" optimization? I had thought that in cases like this (where the output can already be determined at compile time) the compiler could just run the loop to get the answer, therefore avoiding running it every time the code runs, which was what I was picturing when I wrote my earlier comment.
- cormacrelf 3y ago
  Here is an annotated version of rustc's `--release --target aarch64-apple-darwin` assembly output, for the fast version of my code that runs in 500ms. Annotated https://gist.github.com/cormacrelf/4b2b37d1d870377d548b3a32a3c7b26a https://gist.github.com/cormacrelf/4b2b37d1d870377d548b3a32a... and full Godbolt https://rust.godbolt.org/z/aKK4TEs3x https://rust.godbolt.org/z/aKK4TEs3x. You may be interested to see the LLVM Opt Pipeline, any of the green passes (non-zero diffs) that are called LoopUnrollPass or LoopVectorizePass. You can see that it does a couple of LoopUnrollPasses and LoopVectorizePasses. In the end it results in a transformation from something like this: for (uint32_t i = 0; i <= 0xffff; i++) { if (in range) acc += 1; } to u32x4 v1 = [1,2,3,4]; u32x4 v0 = [0,0,0,0], v5 = [0,0,0,0]; u32x4 v6, v7; uint32_t w8 = 0xfff8; do { v6 = v1 + [4,4,4,4]; v7 = v1 >= 0 && v1 <= 1; v6 = v6 >= 0 && v6 <= 1; v0 -= v7; // add 1 to each lane if lane was true in v7 v5 -= v6; // add 1 to each lane if lane was true in v6 v1 += [8,8,8,8]; w8 -= 8; } while (w8); return element_sum(v0 + v5); That is basically unrolled x8, and then the loop body is grouped into two groups of four vector ops. You also save a lot of time by vectorising the sum operation over 8 lanes. The only non-vector operations in the loop body are on the w8 counter. The ratio of real work to "increment checking" is 8x better, and because we unrolled multiple ops into the loop body, we were able to vectorise it and run it in parallel. Re "how does it know when it's finished?": it counts like normal, as you can see there, it uses a register to count iteration. Unrolling does not mean "completely eliminate the termination check" unless your heuristic/supplied unroll threshold is larger than the (known) number of iterations. It generally just does the termination check fewer times by taking bigger strides. It's like walking up stairs two at a time. The answer re compile-time-full-evaluation: compilers use heuristics and pattern matching, they don't automatically try compile time evaluation for things they don't recognise. Nobody would have bothered to write a heuristic to detect "count floating point values in range" and eval it. There is no compiler pass to arbitrarily try to execute eveything in your program at compile time that's remotely possible.
  - cormacrelf 3y ago
    Edit: [0,1,2,3], not [1,2,3,4]. You get the gist.
  - version_five 3y ago
    Makes a lot of sense, thanks for taking the time to explain!

version_five 3y ago

Thanks for the explanation! So how would that play out in optimizing the code you posted? It will run all 2^32 iterations without checking for completion? How does it know when it's finished, and is that the only "unrolling" optimization? I had thought that in cases like this (where the output can already be determined at compile time) the compiler could just run the loop to get the answer, therefore avoiding running it every time the code runs, which was what I was picturing when I wrote my earlier comment.

cormacrelf 3y ago
Here is an annotated version of rustc's `--release --target aarch64-apple-darwin` assembly output, for the fast version of my code that runs in 500ms. Annotated https://gist.github.com/cormacrelf/4b2b37d1d870377d548b3a32a3c7b26a https://gist.github.com/cormacrelf/4b2b37d1d870377d548b3a32a... and full Godbolt https://rust.godbolt.org/z/aKK4TEs3x https://rust.godbolt.org/z/aKK4TEs3x. You may be interested to see the LLVM Opt Pipeline, any of the green passes (non-zero diffs) that are called LoopUnrollPass or LoopVectorizePass. You can see that it does a couple of LoopUnrollPasses and LoopVectorizePasses. In the end it results in a transformation from something like this: for (uint32_t i = 0; i <= 0xffff; i++) { if (in range) acc += 1; } to u32x4 v1 = [1,2,3,4]; u32x4 v0 = [0,0,0,0], v5 = [0,0,0,0]; u32x4 v6, v7; uint32_t w8 = 0xfff8; do { v6 = v1 + [4,4,4,4]; v7 = v1 >= 0 && v1 <= 1; v6 = v6 >= 0 && v6 <= 1; v0 -= v7; // add 1 to each lane if lane was true in v7 v5 -= v6; // add 1 to each lane if lane was true in v6 v1 += [8,8,8,8]; w8 -= 8; } while (w8); return element_sum(v0 + v5); That is basically unrolled x8, and then the loop body is grouped into two groups of four vector ops. You also save a lot of time by vectorising the sum operation over 8 lanes. The only non-vector operations in the loop body are on the w8 counter. The ratio of real work to "increment checking" is 8x better, and because we unrolled multiple ops into the loop body, we were able to vectorise it and run it in parallel. Re "how does it know when it's finished?": it counts like normal, as you can see there, it uses a register to count iteration. Unrolling does not mean "completely eliminate the termination check" unless your heuristic/supplied unroll threshold is larger than the (known) number of iterations. It generally just does the termination check fewer times by taking bigger strides. It's like walking up stairs two at a time. The answer re compile-time-full-evaluation: compilers use heuristics and pattern matching, they don't automatically try compile time evaluation for things they don't recognise. Nobody would have bothered to write a heuristic to detect "count floating point values in range" and eval it. There is no compiler pass to arbitrarily try to execute eveything in your program at compile time that's remotely possible.
- cormacrelf 3y ago
  Edit: [0,1,2,3], not [1,2,3,4]. You get the gist.
- version_five 3y ago
  Makes a lot of sense, thanks for taking the time to explain!