3 ms·

Your custom 24-byte version is just two bytes smaller than the "size_t n" gcc -Os version, probably within a rounding error of what compiler developers care to

by dzaima 3y ago

Your custom 24-byte version is just two bytes smaller than the "size_t n" gcc -Os version, probably within a rounding error of what compiler developers care to achieve.

kragen 3y ago
yes, agreed! it wasn't that the code size was so important to me in the grand scheme of things, it's that i was surprised by the particular way it happened to fail
- dzaima 3y ago
  I will agree it's slightly weird. But it seems to me it's less that it "fails", more that there's heuristics at play other than "speed up loop". Perhaps on other loops it's more reasonable and makes a bigger difference.
  - kragen 3y ago
    well, i haven't looked at gcc's guts, but how would not strength-reducing pointer arithmetic ever make your loops smaller? or, what other kinds of heuristics are you thinking might be in play, that happen to have that effect here? my guess is that it's not intentional behavior at that level
    - dzaima 3y ago
      hmm, maybe you're right. Looking back at the "-Os -march=rv64gc_zba" output, it does the strength reduction, even though the applicability of sh2add is the same regardless of strength reduction or not. A thing that might fit that is wanting to keep the length-0 case short, but I'd be surprised if that's the actual reason. Then there's clang which does yet another thing of changing the loop to a decrementing one, which is smaller than all options here so far: https://godbolt.org/z/M14rdfzq3 https://godbolt.org/z/M14rdfzq3; 5-instr loop though, and it stays that way even to -O3.
      - kragen 3y ago
        interesting! only 18 bytes! all compressed instructions! i'd thought of doing that (in general it can be a very tricky transformation for a compiler to make safely, since it requires the loop reduction to be commutative, which of course it is in this case) but had come to the conclusion that it wouldn't help. incorrectly, it seems in this case it's doing a tricky thing: because it's done the strength-reduction on the pointer arithmetic, it's free to do whatever it wants with the loop counter—not just eliminate it, but also, say, reverse it. that means it doesn't have to care about the loop reduction being commutative or not https://godbolt.org/z/M14rdfzq3 https://godbolt.org/z/M14rdfzq3 has the trailing semicolon removed, for the convenience of hypothetical other readers of this thread here's my untested, hopefully uncorrupted reformatting of it: .globl sumarray sumarray: li a2, 0 # total := 0 beqz a1, 1f # skip loop if array empty 2: lw a3, (a0) # load *a addw a2, a2, a3 # add it to total addi a1, a1, -1 # decrement n-i (previously initialized to n) addi a0, a0, 4 # a++ bnez a1, 2b # repeat loop unless n-i == 0 1: mv a0, a2 # move total into return value slot ret that's 9 instructions, 5 inside the loop, but the only output from one instruction used as an input to another is the output of the lw; plausibly a sufficiently superscalar implementation of risc-v could run an iteration of the loop per cycle? kind of funny instruction scheduling, though, with those two dependent instructions being right next to each other, which would stall a naïve pipeline. macro-op fusion won't help in this case, you really need superscalar this is an instruction shorter than my version because it doesn't need the slli or the extra instruction to compute the loop end, though it does need the extra addi in the loop. because it's only using beqz and bnez, its branches can all be compressed. i think the main thing i wasn't appreciating was how much space i was wasting on the array end computation, because that's the kind of thing that never matters the 'pulp' core (now core-v) got a significant speedup on dsp loops by adding special zero-overhead looping registers, so you don't have to waste cycles on decrementing and testing loop counters (on your two inner levels of looping, anyway); part of their claim was that in-order scalar execution took more time per instruction but less picojoules, so if you're limited by energy consumption rather than transistor budgets or nonparallelizable algorithms, you're better off with more, slower in-order cores. from https://docs.openhwgroup.org/projects/cv32e40p-user-manual/en/latest/instruction_set_extensions.html#hardware-loops-operations https://docs.openhwgroup.org/projects/cv32e40p-user-manual/e... i think that would make the loop look like this: .balign 4 # must be 4-byte aligned .option norvc # no compressed insns! cv.setup 0, 1f, a1 # loop starts on next insn lw a3, (a0) # load *a addw a2, a2, a3 # add it to total addi a0, a0, 4 # a++ but for larger loops the loop setup can take three instructions this is also the kind of thing that the vector extensions ought to help with, of course!

by dzaima 3y ago

Your custom 24-byte version is just two bytes smaller than the "size_t n" gcc -Os version, probably within a rounding error of what compiler developers care to achieve.

kragen 3y ago

yes, agreed! it wasn't that the code size was so important to me in the grand scheme of things, it's that i was surprised by the particular way it happened to fail

dzaima 3y ago
I will agree it's slightly weird. But it seems to me it's less that it "fails", more that there's heuristics at play other than "speed up loop". Perhaps on other loops it's more reasonable and makes a bigger difference.
- kragen 3y ago
  well, i haven't looked at gcc's guts, but how would not strength-reducing pointer arithmetic ever make your loops smaller? or, what other kinds of heuristics are you thinking might be in play, that happen to have that effect here? my guess is that it's not intentional behavior at that level
  - dzaima 3y ago
    hmm, maybe you're right. Looking back at the "-Os -march=rv64gc_zba" output, it does the strength reduction, even though the applicability of sh2add is the same regardless of strength reduction or not. A thing that might fit that is wanting to keep the length-0 case short, but I'd be surprised if that's the actual reason. Then there's clang which does yet another thing of changing the loop to a decrementing one, which is smaller than all options here so far: https://godbolt.org/z/M14rdfzq3 https://godbolt.org/z/M14rdfzq3; 5-instr loop though, and it stays that way even to -O3.
    - kragen 3y ago
      interesting! only 18 bytes! all compressed instructions! i'd thought of doing that (in general it can be a very tricky transformation for a compiler to make safely, since it requires the loop reduction to be commutative, which of course it is in this case) but had come to the conclusion that it wouldn't help. incorrectly, it seems in this case it's doing a tricky thing: because it's done the strength-reduction on the pointer arithmetic, it's free to do whatever it wants with the loop counter—not just eliminate it, but also, say, reverse it. that means it doesn't have to care about the loop reduction being commutative or not https://godbolt.org/z/M14rdfzq3 https://godbolt.org/z/M14rdfzq3 has the trailing semicolon removed, for the convenience of hypothetical other readers of this thread here's my untested, hopefully uncorrupted reformatting of it: .globl sumarray sumarray: li a2, 0 # total := 0 beqz a1, 1f # skip loop if array empty 2: lw a3, (a0) # load *a addw a2, a2, a3 # add it to total addi a1, a1, -1 # decrement n-i (previously initialized to n) addi a0, a0, 4 # a++ bnez a1, 2b # repeat loop unless n-i == 0 1: mv a0, a2 # move total into return value slot ret that's 9 instructions, 5 inside the loop, but the only output from one instruction used as an input to another is the output of the lw; plausibly a sufficiently superscalar implementation of risc-v could run an iteration of the loop per cycle? kind of funny instruction scheduling, though, with those two dependent instructions being right next to each other, which would stall a naïve pipeline. macro-op fusion won't help in this case, you really need superscalar this is an instruction shorter than my version because it doesn't need the slli or the extra instruction to compute the loop end, though it does need the extra addi in the loop. because it's only using beqz and bnez, its branches can all be compressed. i think the main thing i wasn't appreciating was how much space i was wasting on the array end computation, because that's the kind of thing that never matters the 'pulp' core (now core-v) got a significant speedup on dsp loops by adding special zero-overhead looping registers, so you don't have to waste cycles on decrementing and testing loop counters (on your two inner levels of looping, anyway); part of their claim was that in-order scalar execution took more time per instruction but less picojoules, so if you're limited by energy consumption rather than transistor budgets or nonparallelizable algorithms, you're better off with more, slower in-order cores. from https://docs.openhwgroup.org/projects/cv32e40p-user-manual/en/latest/instruction_set_extensions.html#hardware-loops-operations https://docs.openhwgroup.org/projects/cv32e40p-user-manual/e... i think that would make the loop look like this: .balign 4 # must be 4-byte aligned .option norvc # no compressed insns! cv.setup 0, 1f, a1 # loop starts on next insn lw a3, (a0) # load *a addw a2, a2, a3 # add it to total addi a0, a0, 4 # a++ but for larger loops the loop setup can take three instructions this is also the kind of thing that the vector extensions ought to help with, of course!