3
\$\begingroup\$

I found this question in Stackoverflow asking why his/her assembly program isn't faster than the C++ program. In his/her assembly program I saw the lines mov rbx, 2; xor rdx, rdx; div rbx, and I didn't even read further. Anyway the question was interesting enough for me to write an assembly program to see how much I can beat the compiler.

The program is a simple bruteforce solution to problem 14 of Project Euler.

The algorithm used in both the C and assembly version is the same; no algorithmic optimization was done.

This is the result in rdtscp cycles, which has a constant tick on my CPU. The first output number is the result of the function with input 10,000,000.

/* gcc */
8400511   c 1,710,915,921
8400511 asm 1,656,971,166
8400511   c 1,707,514,184
8400511 asm 1,653,252,527
8400511   c 1,702,896,033
8400511 asm 1,652,814,196

/* clang */
8400511   c 2,011,935,915
8400511 asm 1,655,126,396
8400511   c 2,009,606,165
8400511 asm 1,649,501,254
8400511   c 2,016,743,666
8400511 asm 1,653,020,407

My assembly version has a marginal win against gcc and quite a visible gap with clang. The assembly output by each compiler can be seen here.

lcs_c.c

#include <inttypes.h>

static unsigned bsfq(uint64_t a) {
#if LONG_MAX == UINT64_MAX
    return __builtin_ctzl(a);
#else
    return __builtin_ctzll(a);
#endif
}

uint64_t lcs_c(uint64_t n) {
    uint64_t Mn;
    unsigned Mc = 1;
    do {
        unsigned c = 1;
        uint64_t n_ = n;
        for (;;) {
            unsigned c_ = bsfq(n_);
            n_ >>= c_;
            c += c_;
            if (n_ == 1) {
                break;
            }
            n_ = n_ * 3 + 1;
            ++c;
        }
        if (c > Mc) {
            Mc = c;
            Mn = n;
        }
    } while (--n > 0);
    return Mn;
}

lcs_asm.s

%define n rdi
%define n_ rsi
%define Mc r8d
%define c edx

    align 16
global lcs_asm
lcs_asm:
    mov Mc, 1
    jmp L0
    align 16
L0:
    mov c, 1
    mov n_, n
    jmp L1
    align 16
L1:
    bsf rcx, n_
    shr n_, cl
    cmp n_, 1
    je next
    lea n_, [n_ + n_ * 2 + 1]
    lea c, [c + ecx + 1]
    jmp L1
    align 16
next:
    add c, ecx
    cmp c, Mc
    ja L2
    dec n
    jz end
    jmp L0
    align 16
L2:
    mov Mc, c
    mov rax, n
    dec n
    jz end
    jmp L0
    align 16
end:
    ret

main.c

#include <stdio.h>
#include <locale.h>
#include <inttypes.h>

extern uint64_t lcs_c(uint64_t);
extern __attribute__((sysv_abi)) uint64_t lcs_asm(uint64_t);

static uint64_t rdtscp() {
    unsigned _;
    return __builtin_ia32_rdtscp(&_);
}

static void test(const char *id, uint64_t (*lcs)(uint64_t), uint64_t lim) {
    uint64_t c = rdtscp();
    uint64_t Mn = lcs(lim);
    c = rdtscp() - c;
    printf("%"PRIu64"%4s %'"PRIu64"\n", Mn, id, c);
}

int main() {
    setlocale(LC_NUMERIC, "");
    uint64_t lim = 1e7;
    for (int i = 0; i < 3; ++i) {
        test("c", lcs_c, lim);
        test("asm", lcs_asm, lim);
    }
}

build.sh

#!/bin/sh -x

C="gcc"
O="-O3 -march=tigerlake"
$C -c $O lcs_c.c
nasm -felf64 lcs_asm.s
$C $O -or main.c lcs_c.o lcs_asm.o
rm *.o
\$\endgroup\$
2
  • 2
    \$\begingroup\$ In the future it might be better to ask a follow up question rather than editing the current question. \$\endgroup\$
    – pacmaninbw
    Commented Feb 6, 2022 at 3:59
  • 2
    \$\begingroup\$ Please refrain from adding updated code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see What should I do when someone answers my question? as well as what you may and may not do after receiving answers. \$\endgroup\$ Commented Feb 8, 2022 at 18:39

2 Answers 2

1
\$\begingroup\$

I rewrote your assembly code a bit. I leave it to you if this results in any better performance.

  • I reduced the number of branches. You had 2 in your inner loop, my code uses 1.
  • I also inverted the conditional branch near the bottom and removed some code that was repeating itself. Again reducing branches.
  • The few remaining branch targets are still paragraph aligned but I replaced the 'jump-over the nops' by the recommended sequence of multi-byte nop.
    align 16
lcs_asm:
    mov r8d, 1                         ; 6
    mov edx, 1                         ; 5
    mov rsi, rdi                       ; 3
    jmp L2                             ; 2
L1: lea rsi, [rsi + rsi * 2 + 1]       ; 5
    lea edx, [edx + ecx + 1]           ; 5
    db  66h, 0Fh, 1Fh, 44h, 00h, 00h   ; jmp L2 : align 16 -> 66 nop word ptr [rax + rax * 1 + 0]
L2: bsf rcx, rsi
    shr rsi, cl
    cmp rsi, 1
    jne L1
    add edx, ecx
    cmp edx, r8d
    jna L3
    mov r8d, edx
    mov rax, rdi
    db  66h, 0Fh, 1Fh, 44h, 00h, 00h   ; jmp L3 : align 16 -> 66 nop word ptr [rax + rax * 1 + 0]
L3: dec rdi
    mov edx, 1
    mov rsi, rdi
    jnz L2
    ret

The entire code fits in 78 bytes.

\$\endgroup\$
1
  • \$\begingroup\$ Your code is the fastest and the smallest. I just changed bsr to tzcnt to get a small boost. \$\endgroup\$
    – xiver77
    Commented Feb 8, 2022 at 18:17
2
\$\begingroup\$

2-jump loop

The loop pattern of this loop could be changed to a 1-jump loop:

L1:
    bsf rcx, n_
    shr n_, cl
    cmp n_, 1
    je next
    lea n_, [n_ + n_ * 2 + 1]
    lea c, [c + ecx + 1]
    jmp L1

Move the part that exits from the loop to the bottom, the other part to the top, and then you have a loop with only one branch in it and no jmp, at the cost of having to enter the loop in the middle, but that's easy in assembly and there was already a jmp to enter the loop anyway to skip the alignment padding.

Like this:

    jmp Lentry
    align 16
L1:
    lea n_, [n_ + n_ * 2 + 1]
    lea c, [c + ecx + 1]
Lentry:
    bsf rcx, n_
    shr n_, cl
    cmp n_, 1
    jne L1
    .. etc

Avoid 32-bit address in lea

In 64-bit code, lea with a 32-bit address costs an extra address-size-override prefix. lea with a 64-bit address and a 32-bit destination doesn't need any prefixes and has almost the same semantics, except that some specific encodings have different meanings. The differences are not important here, so you may as well use lea with a 32-bit destination but a 64-bit address, that's the cheapest option for x64. The cost in this case should be insignificant and quite possibly unmeasurable, it's not as if lea with an address-size-override is slower in and of itself, but it costs an extra byte and that may have decoding and µop cache implications.

Depending on the target processor and context, maybe avoid 3-component lea

On some processors, notably Intel processors older than Ice Lake, 3-component lea has a latency of 3 cycles while the other forms have a latency of 1 cycle. That makes it have a higher latency than a 2-component lea plus a separate add, though that costs 2 µops and the 3-component lea still only costs one.

Depending on the context, the latency or the µop count may be more important. In this case I think the latency is important, because it's part of a loop-carried dependency, so replacing lea n_, [n_ + n_ * 2 + 1] with lea n_, [n_ + n_ * 2] \ inc n_ may help. LLVM-MCA doesn't think so, but uiCA agreed and it's more accurate than LLVM-MCA, so it looks promising.

Intel Ice Lake and AMD processors would either prefer the original 3-component lea or at least don't penalize it.

Consider using tzcnt instead of bsf

For Intel processors that shouldn't make any difference, but bsf is typically somewhat slow on AMD processors, while tzcnt is fast on all processors that support it (it is very widely supported at this point) and especially on AMD processors which tend to implement it even more efficiently than Intel. So using tzcnt is neither a win nor a loss on Intel processors, but a significant win on AMD processors.

\$\endgroup\$
9
  • \$\begingroup\$ tzcnt was actually very slightly faster on my machine (Tigerlake). I'm suspecting maybe bsf having an output dependency is making a tiny difference even though there is a bit of gap between executing bsf. AFAIK tzcnt should be free from output dependency on Tigerlake, but still gcc zeros the output before tzcnt as if there is. clang doesn't do this. Both were given march=tigerlake. \$\endgroup\$
    – xiver77
    Commented Feb 6, 2022 at 0:23
  • \$\begingroup\$ Whether or not gcc is mis-optimizing in this case, I've seen somewhere that some CPU's have hardware bugs that tzcnt/lzcnt/popcnt has a false dependency on the output register, so I didn't feel comfortable using tzcnt. Well, while writing this comment I realized bsf has an output dependency by default, so I don't seem to lose anything using tzcnt anyway, apart from a bit of portability. \$\endgroup\$
    – xiver77
    Commented Feb 6, 2022 at 0:23
  • \$\begingroup\$ @xiver77 yea actually I discovered that bug (well, maybe, it's hard to tell and hopefully Intel engineers knew even if they didn't come out and warn us) or at least noticed it pretty early \$\endgroup\$
    – user555045
    Commented Feb 6, 2022 at 0:33
  • \$\begingroup\$ I appended a revised version on the OP applying some of your suggested optimizations. It is about 0.15% faster than the original. About 0.1% is from switching to tzcnt, and about 0.05% is from rearranging the loop. These are very rough numbers, but I ran enough tests to be sure that a certain version is at least slightly faster than another. \$\endgroup\$
    – xiver77
    Commented Feb 6, 2022 at 2:39
  • \$\begingroup\$ I couldn't change the 3-component lea to lea + inc because that resulted to be more than 20% slower on my machine. I don't have a spare machine right now to test if the result is different, but I'm now wondering what would be a better generic choice, 3-component lea vs lea + inc. \$\endgroup\$
    – xiver77
    Commented Feb 6, 2022 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.