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