5 ms·

gcc does give the 4-instr loop on all of -O1, -O2, and -O3 for the basic loop. And, to its credit, the worse loop on -Os does result in the function being 2 byt

by dzaima 3y ago

gcc does give the 4-instr loop on all of -O1, -O2, and -O3 for the basic loop. And, to its credit, the worse loop on -Os does result in the function being 2 bytes smaller (if I'm reading it right), which is what you ask for with -Os. And on -march=rv64gc_zba, the -Os version is 4 bytes smaller than the -O3 one.

kragen 3y ago
iiinteresting! i can't see how to get machine code listings on godbolt, but on my own machine (with 12.2.0) the -Os sumarray is 30 bytes, sumarray_opt is 22. with -O3 sumarray shrinks to 28 bytes but its loop is indeed only 4 instructions long, and sumarray_opt is 26 bytes (with the same inner loop with slightly different register assignments). so at least that one is smaller. and it's probably true that the 22-byte sumarray_opt with its 5-instruction loop is slower on most machines than the 26-byte version—but the 26-byte version would have been both smaller and faster than what -Os emitted for sumarray originally with -Os (please forgive objdump's unreadable disassembly and incorrect mnemonics): 00000000000007e8 <sumarray>: 7e8: 872a mv a4,a0 7ea: 4781 li a5,0 7ec: 4501 li a0,0 7ee: 0007869b sext.w a3,a5 7f2: 00d59363 bne a1,a3,7f8 <sumarray+0x10> 7f6: 8082 ret 7f8: 00279693 sll a3,a5,0x2 7fc: 96ba add a3,a3,a4 7fe: 4294 lw a3,0(a3) 800: 0785 add a5,a5,1 802: 9d35 addw a0,a0,a3 804: b7ed j 7ee <sumarray+0x6> 0000000000000806 <sumarray_opt>: 806: 058a sll a1,a1,0x2 808: 87aa mv a5,a0 80a: 95aa add a1,a1,a0 80c: 4501 li a0,0 80e: 00b79363 bne a5,a1,814 <sumarray_opt+0xe> 812: 8082 ret 814: 4398 lw a4,0(a5) 816: 0791 add a5,a5,4 818: 9d39 addw a0,a0,a4 81a: bfd5 j 80e <sumarray_opt+0x8> with -O3: 00000000000007f0 <sumarray>: 7f0: cd81 beqz a1,808 <sumarray+0x18> 7f2: 058a sll a1,a1,0x2 7f4: 87aa mv a5,a0 7f6: 00b506b3 add a3,a0,a1 7fa: 4501 li a0,0 7fc: 4398 lw a4,0(a5) 7fe: 0791 add a5,a5,4 800: 9d39 addw a0,a0,a4 802: fef69de3 bne a3,a5,7fc <sumarray+0xc> 806: 8082 ret 808: 4501 li a0,0 80a: 8082 ret 000000000000080c <sumarray_opt>: 80c: 058a sll a1,a1,0x2 80e: 87aa mv a5,a0 810: 95aa add a1,a1,a0 812: 4501 li a0,0 814: 00b78863 beq a5,a1,824 <sumarray_opt+0x18> 818: 4398 lw a4,0(a5) 81a: 0791 add a5,a5,4 81c: 9d39 addw a0,a0,a4 81e: fef59de3 bne a1,a5,818 <sumarray_opt+0xc> 822: 8082 ret 824: 8082 ret still, aside from risc-v's unnecessarily pedagogical syntax, what's wrong with this? .globl sumarray sumarray: mv a2, a0 # compensate for abi design blunder: first argument (array base address) in return value register slli a1, a1, 2 # convert array size to byte count li a0, 0 # initialize return value to 0 add a1, a1, a2 # compute array end beq a1, a2, 1f # skip loop if empty 2: lw a3, (a2) # load array item from memory add a0, a0, a3 # add to total addi a2, a2, 4 # increment array pointer bne a1, a2, 2b # continue loop unless done 1: ret except for the snarky comments, isn't this the code you'd expect from the compiler (without zba)? i wouldn't describe it as thoroughly tested, but it does seem to work. as i count it, it's 24 bytes and so smaller than anything except the original sumarray_opt, and it contains the same 4-instruction loop as the -O3 versions. i guess it's the -O3 sumarray_opt without the useless extra ret instruction, which is presumably some kind of minor bug
- dzaima 3y ago
  Output → Compile to binary object. Appears I was testing on a version with the int counter replaced with size_t (namely, https://godbolt.org/z/sTW64EEYv https://godbolt.org/z/sTW64EEYv vs https://godbolt.org/z/zKqjTa5fz https://godbolt.org/z/zKqjTa5fz). Regardless, indeed, your sumarray_opt one is shorter still, and with less instructions in the loop. Though beating compilers by an instruction or two is nothing particularly new, being possible often even on x86.
  - kragen 3y ago
    i did see that option but when i selected it i got no output; maybe i have to look for the output somewhere else? the thing i was surprised by was not really that i could beat it by an instruction or two by rewriting the c code, but that i could reduce the number of instructions in the inner loop by 37% with no apparent tradeoffs by hand-applying an optimization that the compiler already does apply, itself, on arm
    - dzaima 3y ago
      Seems it doesn't like -S being present (and it makes sense as you don't want assembly, you want a disassembled object file). In general there's no need for -S in compiler explorer.
      - kragen 3y ago
        aha, thanks! this has been very edifying! i wonder how i ended up with -S in there
- 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
kimixa 3y ago
I've also seen that -Os with GCC produces significantly slower code in pretty much all use cases I've looked at it on (Game rendering code, optimizing shader compiler, GPU drivers). And that's on mobile devices where you might expect to be more cache/memory bandwidth limited. I believe the general idea that -Os was often the best choice was popularized as it became the default on MacOS, which uses Clang, which may bias it's optimization options differently. And Clang has had the -Oz option for if you really want to focus on total size, trading possibly lower performance, for quite a while. GCC only introduced the same relatively recently in gcc 12. So maybe it'll change the bias of Os going forward? EDIT: Though I'm not sure about the disassembler on godbolt - I tried seeing if the c++ std::accumulate function would affect code generation, and the disassembled code looks incomplete, and doesn't match the compiler assembler output (by disabling "Compile to Binary Object") at all [0] https://godbolt.org/z/5443fo75n https://godbolt.org/z/5443fo75n
- kragen 3y ago
  hey, my reply seems to have been lost! i'll try again yes, using -Os does seem to have been my main problem! possibly in the past gcc's optimization wasn't as flexible and so couldn't trade off performance for code size as effectively but what surprised me in this case was not that -Os was reducing size at the expense of speed; it's that it was failing to apply a well-known, widely-applicable optimization that both reduces size and improves speed getting down to the 4-instruction form of the loop does require an optimization that increases size while (usually) improving speed: transforming while (x) y; into if (x) do y; while (x);, which costs four bytes in this case (because the beq/bne doesn't fit into a compressed instruction; risc-v 2-byte compressed branches can only test a single register, so you only have c.beqz and c.bnez)
  - kimixa 3y ago
    You can control most of the optimization flags separately, I think most are listed under the various levels here [0], might be interesting to see what causes the difference, or if it's one of the unspecified "tuning values". [0] https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

by dzaima 3y ago

kragen 3y ago

iiinteresting! i can't see how to get machine code listings on godbolt, but on my own machine (with 12.2.0) the -Os sumarray is 30 bytes, sumarray_opt is 22. with -O3 sumarray shrinks to 28 bytes but its loop is indeed only 4 instructions long, and sumarray_opt is 26 bytes (with the same inner loop with slightly different register assignments). so at least that one is smaller. and it's probably true that the 22-byte sumarray_opt with its 5-instruction loop is slower on most machines than the 26-byte version—but the 26-byte version would have been both smaller and faster than what -Os emitted for sumarray originally with -Os (please forgive objdump's unreadable disassembly and incorrect mnemonics): 00000000000007e8 <sumarray>: 7e8: 872a mv a4,a0 7ea: 4781 li a5,0 7ec: 4501 li a0,0 7ee: 0007869b sext.w a3,a5 7f2: 00d59363 bne a1,a3,7f8 <sumarray+0x10> 7f6: 8082 ret 7f8: 00279693 sll a3,a5,0x2 7fc: 96ba add a3,a3,a4 7fe: 4294 lw a3,0(a3) 800: 0785 add a5,a5,1 802: 9d35 addw a0,a0,a3 804: b7ed j 7ee <sumarray+0x6> 0000000000000806 <sumarray_opt>: 806: 058a sll a1,a1,0x2 808: 87aa mv a5,a0 80a: 95aa add a1,a1,a0 80c: 4501 li a0,0 80e: 00b79363 bne a5,a1,814 <sumarray_opt+0xe> 812: 8082 ret 814: 4398 lw a4,0(a5) 816: 0791 add a5,a5,4 818: 9d39 addw a0,a0,a4 81a: bfd5 j 80e <sumarray_opt+0x8> with -O3: 00000000000007f0 <sumarray>: 7f0: cd81 beqz a1,808 <sumarray+0x18> 7f2: 058a sll a1,a1,0x2 7f4: 87aa mv a5,a0 7f6: 00b506b3 add a3,a0,a1 7fa: 4501 li a0,0 7fc: 4398 lw a4,0(a5) 7fe: 0791 add a5,a5,4 800: 9d39 addw a0,a0,a4 802: fef69de3 bne a3,a5,7fc <sumarray+0xc> 806: 8082 ret 808: 4501 li a0,0 80a: 8082 ret 000000000000080c <sumarray_opt>: 80c: 058a sll a1,a1,0x2 80e: 87aa mv a5,a0 810: 95aa add a1,a1,a0 812: 4501 li a0,0 814: 00b78863 beq a5,a1,824 <sumarray_opt+0x18> 818: 4398 lw a4,0(a5) 81a: 0791 add a5,a5,4 81c: 9d39 addw a0,a0,a4 81e: fef59de3 bne a1,a5,818 <sumarray_opt+0xc> 822: 8082 ret 824: 8082 ret still, aside from risc-v's unnecessarily pedagogical syntax, what's wrong with this? .globl sumarray sumarray: mv a2, a0 # compensate for abi design blunder: first argument (array base address) in return value register slli a1, a1, 2 # convert array size to byte count li a0, 0 # initialize return value to 0 add a1, a1, a2 # compute array end beq a1, a2, 1f # skip loop if empty 2: lw a3, (a2) # load array item from memory add a0, a0, a3 # add to total addi a2, a2, 4 # increment array pointer bne a1, a2, 2b # continue loop unless done 1: ret except for the snarky comments, isn't this the code you'd expect from the compiler (without zba)? i wouldn't describe it as thoroughly tested, but it does seem to work. as i count it, it's 24 bytes and so smaller than anything except the original sumarray_opt, and it contains the same 4-instruction loop as the -O3 versions. i guess it's the -O3 sumarray_opt without the useless extra ret instruction, which is presumably some kind of minor bug

dzaima 3y ago
Output → Compile to binary object. Appears I was testing on a version with the int counter replaced with size_t (namely, https://godbolt.org/z/sTW64EEYv https://godbolt.org/z/sTW64EEYv vs https://godbolt.org/z/zKqjTa5fz https://godbolt.org/z/zKqjTa5fz). Regardless, indeed, your sumarray_opt one is shorter still, and with less instructions in the loop. Though beating compilers by an instruction or two is nothing particularly new, being possible often even on x86.
- kragen 3y ago
  i did see that option but when i selected it i got no output; maybe i have to look for the output somewhere else? the thing i was surprised by was not really that i could beat it by an instruction or two by rewriting the c code, but that i could reduce the number of instructions in the inner loop by 37% with no apparent tradeoffs by hand-applying an optimization that the compiler already does apply, itself, on arm
  - dzaima 3y ago
    Seems it doesn't like -S being present (and it makes sense as you don't want assembly, you want a disassembled object file). In general there's no need for -S in compiler explorer.
    - kragen 3y ago
      aha, thanks! this has been very edifying! i wonder how i ended up with -S in there
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

kimixa 3y ago

I've also seen that -Os with GCC produces significantly slower code in pretty much all use cases I've looked at it on (Game rendering code, optimizing shader compiler, GPU drivers). And that's on mobile devices where you might expect to be more cache/memory bandwidth limited. I believe the general idea that -Os was often the best choice was popularized as it became the default on MacOS, which uses Clang, which may bias it's optimization options differently. And Clang has had the -Oz option for if you really want to focus on total size, trading possibly lower performance, for quite a while. GCC only introduced the same relatively recently in gcc 12. So maybe it'll change the bias of Os going forward? EDIT: Though I'm not sure about the disassembler on godbolt - I tried seeing if the c++ std::accumulate function would affect code generation, and the disassembled code looks incomplete, and doesn't match the compiler assembler output (by disabling "Compile to Binary Object") at all [0] https://godbolt.org/z/5443fo75n https://godbolt.org/z/5443fo75n

kragen 3y ago
hey, my reply seems to have been lost! i'll try again yes, using -Os does seem to have been my main problem! possibly in the past gcc's optimization wasn't as flexible and so couldn't trade off performance for code size as effectively but what surprised me in this case was not that -Os was reducing size at the expense of speed; it's that it was failing to apply a well-known, widely-applicable optimization that both reduces size and improves speed getting down to the 4-instruction form of the loop does require an optimization that increases size while (usually) improving speed: transforming while (x) y; into if (x) do y; while (x);, which costs four bytes in this case (because the beq/bne doesn't fit into a compressed instruction; risc-v 2-byte compressed branches can only test a single register, so you only have c.beqz and c.bnez)
- kimixa 3y ago
  You can control most of the optimization flags separately, I think most are listed under the various levels here [0], might be interesting to see what causes the difference, or if it's one of the unspecified "tuning values". [0] https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html