Ubuntu – Why is cython so much slower than numba for this simple loop?

It looks like

decorated py code  --Numba-->  LLVM IR  --LLVM-->  machine code 

is just producing better-optimized code than

cython code  --Cython-->  C  --gcc-or-clang-->  machine code

There are three things that conspire to give Cython worse performance in this benchmark.

1. Cython overhead (minor)

2. The loop Cython generates (major)

3. Which compiler is being used (major)

Overhead (reason 1)

Cython apparently has some extra overhead. You can observe this by passing in an array of shape (1,0).
The Numba function is still much faster.
This isn’t too surprising, given that Cython is the more general tool, and it tries to be extra careful with inputs, error handling, etc., even when it’s overkill.
Unless you’re calling this function a lot with very small inputs, this shouldn’t matter much.

Loop Unrolling (reasons 2 & 3 together)

Based on the disassembly in the updated question (copied here), Numba + LLVM are creating a nicely unrolled loop.
Notice how it’s using YMM0..YMM3, not just one vector register.

vaddpd  -96(%rsi,%rdx,8), %ymm0, %ymm0
vaddpd  -64(%rsi,%rdx,8), %ymm1, %ymm1
vaddpd  -32(%rsi,%rdx,8), %ymm2, %ymm2
vaddpd  (%rsi,%rdx,8), %ymm3, %ymm3
addq    $16, %rdx
cmpq    %rdx, %rcx
jne .LBB0_5
vaddpd  %ymm0, %ymm1, %ymm0
vaddpd  %ymm0, %ymm2, %ymm0
vaddpd  %ymm0, %ymm3, %ymm0
vextractf128    $1, %ymm0, %xmm1
vaddpd  %xmm1, %xmm0, %xmm0
vpermilpd   $1, %xmm0, %xmm1
vaddsd  %xmm1, %xmm0, %xmm0

In contrast, here’s core decompiled loop from Cython when using gcc. There’s no unrolling here.

    do {
      uVar9 = uVar8 + 1;
      auVar15 = vaddpd_avx(auVar15,*(undefined (*) [32])(local_118 + local_d0 + uVar8 * 0x20));
      uVar8 = uVar9;
    } while (uVar9 < (ulong)local_108 >> 2);

The decompilation of the clang output is similar, but happens to perform even worse (see the benchmark results below). For some reason, clang doesn’t want to unroll Cython’s loop.

    do {
        auVar1._8_8_ = 0;
        auVar1._0_8_ = *(ulong *)(local_e8.data + lVar4 * 8 + local_e8.strides[0]);
        auVar5 = vaddsd_avx(auVar5,auVar1);
        lVar4 = (long)((int)lVar4 + 1);
    } while (lVar4 < local_e8.shape[1]);

Making Cython Fast

It can sometimes be tricky to make Cython generate ultra-fast code, but fortunately there’s another option: use Cython only for glue between Python and C.

Try putting this in your .pyx file:

cdef extern from "impl.h":
    double fast_sum_c(double[] x, size_t n) nogil

def fast_sum_cyc(double[:, ::1] arr):
    # The pointer retrieval is only safe 
    # because of the "::1" constraint.
    return fast_sum_c(&arr[1, 0], arr.shape[1])

and then create an impl.h file with the following contents:

#pragma once

double fast_sum_c(double const *x, size_t n) {
    double s = 0.0;
    for (size_t i = 0; i < n; ++i) {
        s += x[i];
    }
    return s;
}

On my machine, with a (2,1000) input array, here are the timeit runtimes:

Compiler    Numba  OrigCy  CyAndC
----------  -----  ------  ------
LLVM/Clang  240ns   900ns   250ns
gcc         n/a     380ns   380ns

Observations:

• Numba has a little lower overhead than Cython.

• Cython + Clang performs exceptionally poorly on this benchmark.

• …but a thin Cython wrapper + hand written C code + Clang is almost as good as Numba.

• GCC doesn’t seem as sensitive to the code Cython generates. We get the same speed with Cython’s code and hand written code.

Here’s the most important assembly snippet from the clang-compiled version of fast_sum_c.
Unsurprisingly, it’s very similar to what Numba produced (since they both use LLVM as their backend):

58b0:       c5 fd 58 04 cf          vaddpd (%rdi,%rcx,8),%ymm0,%ymm0
58b5:       c5 f5 58 4c cf 20       vaddpd 0x20(%rdi,%rcx,8),%ymm1,%ymm1
58bb:       c5 ed 58 54 cf 40       vaddpd 0x40(%rdi,%rcx,8),%ymm2,%ymm2
58c1:       c5 e5 58 5c cf 60       vaddpd 0x60(%rdi,%rcx,8),%ymm3,%ymm3
58c7:       48 83 c1 10             add    $0x10,%rcx
58cb:       48 39 c8                cmp    %rcx,%rax
58ce:       75 e0                   jne    58b0 <fast_sum_c+0x40>
58d0:       c5 f5 58 c0             vaddpd %ymm0,%ymm1,%ymm0
58d4:       c5 ed 58 c0             vaddpd %ymm0,%ymm2,%ymm0
58d8:       c5 e5 58 c0             vaddpd %ymm0,%ymm3,%ymm0
58dc:       c4 e3 7d 19 c1 01       vextractf128 $0x1,%ymm0,%xmm1
58e2:       c5 f9 58 c1             vaddpd %xmm1,%xmm0,%xmm0
58e6:       c4 e3 79 05 c8 01       vpermilpd $0x1,%xmm0,%xmm1
58ec:       c5 fb 58 c1             vaddsd %xmm1,%xmm0,%xmm0

Notes

• Compiler options to encourage more loop unrolling didn’t help. In the "Making Cython Fast", I tried adding various pragmas and compiler flags to gcc to encourage it to do some unrolling; nothing helped. Additionally, clang never had trouble with my hand written C code, but never wanted to unroll the Cython-generated loop.

• objdump -d test_sum.*.so produces a disassembly. Looking for the vaddpd instructions helps with locating the loop of interest.

• Ghidra can be used to decompile the code. This helps a little with understanding it. Compiling the extension module with -g and -gdwarf-4 makes it so Ghidra’s DWARF decoding works, injecting a bit more metadata in the decompilation.

• For these tests, I used clang 14.0.0 and gcc 11.3.0.