3 ms·

If LEA is slow, don't use it. A simple ADD followed by DEC outperforms LEA in throughput, latency, and size in recent Intel chips. If you're willing to reduce

by pbsd 12y ago

If LEA is slow, don't use it. A simple ADD followed by DEC outperforms LEA in throughput, latency, and size in recent Intel chips. If you're willing to reduce integers to 62 bits (and assuming no overflows are allowed), multiplication can also be simplified: (2x+1)(2y+1) = 4xy + 2x + 2y + 1. So: t = x + y - 2; // + 1 - 3 p = x * y; // 4*x*y + 2*x + 2*y + 1 return (p - t) >> 1; // (4*x*y + 3) / 2 In amd64, this can be done as ; input in rdi, rsi lea rax, [rdi + rsi - 2] ; slow, but runs concurrently with imul imul rdi, rsi sub rdi, rax shr rdi, 1 ; output

jzwinck 12y ago
GCC generates LEA even for a regular addition, even with -O3 and -march=native on a modern Intel x86-64 system. A simple addition of int64_t gives you: leaq (%rdi,%rsi), %rax Whereas subtracting the tag gives you: leaq -1(%rdi,%rsi), %rax So pretty much the same either way, though you do get five instruction bytes for the tag version vs. four bytes without. Here are the comparisons for multiply and divide, from "gcc -c -O3 -g -march=native" and "objdump -d": x * y: 10: 48 89 f8 mov %rdi,%rax 13: 48 0f af c6 imul %rsi,%rax (x >> 1) * (y - 1) + 1: 40: 48 d1 ff sar %rdi 43: 48 83 ee 01 sub $0x1,%rsi 47: 48 89 f8 mov %rdi,%rax 4a: 48 0f af c6 imul %rsi,%rax 4e: 48 83 c0 01 add $0x1,%rax x / y: 20: 48 89 f8 mov %rdi,%rax 23: 48 99 cqto 25: 48 f7 fe idiv %rsi (((x >> 1) / (y >> 1)) << 1) + 1: 60: 48 89 f8 mov %rdi,%rax 63: 48 d1 fe sar %rsi 66: 48 d1 f8 sar %rax 69: 48 99 cqto 6b: 48 f7 fe idiv %rsi 6e: 48 8d 44 00 01 lea 0x1(%rax,%rax,1),%rax
- pbsd 12y ago
  3-operand LEA has a different performance profile than 2-operand LEA on Sandy Bridge and later chips. The former has 3 cycle latency and only one execution port, whereas the latter has single-cycle latency and can be dispatched to two execution ports. So while gcc (and every other compiler) may rightly generate an LEA instruction to replace regular addition, it's not optimal when a third argument is added. Curiously, if you need to move the result to another register (say, to respect calling conventions) the optimal solution is a 2-operand LEA plus a DEC: lea rax, [rdi + rsi] dec rax I was wrong about ADD + DEC being smaller, though. I forgot that amd64 took away the 1-byte INC/DEC instructions to serve as REX prefix, so the DEC takes 3 bytes, not 1.

by pbsd 12y ago

jzwinck 12y ago

GCC generates LEA even for a regular addition, even with -O3 and -march=native on a modern Intel x86-64 system. A simple addition of int64_t gives you: leaq (%rdi,%rsi), %rax Whereas subtracting the tag gives you: leaq -1(%rdi,%rsi), %rax So pretty much the same either way, though you do get five instruction bytes for the tag version vs. four bytes without. Here are the comparisons for multiply and divide, from "gcc -c -O3 -g -march=native" and "objdump -d": x * y: 10: 48 89 f8 mov %rdi,%rax 13: 48 0f af c6 imul %rsi,%rax (x >> 1) * (y - 1) + 1: 40: 48 d1 ff sar %rdi 43: 48 83 ee 01 sub $0x1,%rsi 47: 48 89 f8 mov %rdi,%rax 4a: 48 0f af c6 imul %rsi,%rax 4e: 48 83 c0 01 add $0x1,%rax x / y: 20: 48 89 f8 mov %rdi,%rax 23: 48 99 cqto 25: 48 f7 fe idiv %rsi (((x >> 1) / (y >> 1)) << 1) + 1: 60: 48 89 f8 mov %rdi,%rax 63: 48 d1 fe sar %rsi 66: 48 d1 f8 sar %rax 69: 48 99 cqto 6b: 48 f7 fe idiv %rsi 6e: 48 8d 44 00 01 lea 0x1(%rax,%rax,1),%rax

pbsd 12y ago
3-operand LEA has a different performance profile than 2-operand LEA on Sandy Bridge and later chips. The former has 3 cycle latency and only one execution port, whereas the latter has single-cycle latency and can be dispatched to two execution ports. So while gcc (and every other compiler) may rightly generate an LEA instruction to replace regular addition, it's not optimal when a third argument is added. Curiously, if you need to move the result to another register (say, to respect calling conventions) the optimal solution is a 2-operand LEA plus a DEC: lea rax, [rdi + rsi] dec rax I was wrong about ADD + DEC being smaller, though. I forgot that amd64 took away the 1-byte INC/DEC instructions to serve as REX prefix, so the DEC takes 3 bytes, not 1.