2
\$\begingroup\$

For my current job, I've been told that soon I'm going to be porting our Python code to Cython, with the intent of performance upgrades. In preparation of that, I've been learning as much about Cython as I can. I've decided that tackling the Fibonacci sequence would be a good start. I've implemented a Cython + Iterative version of the Fibonacci sequence. Are there any more performance upgrades I can squeeze out of this? Thanks!

fibonacci.pyx

cpdef fib(int n):
    return fib_c(n)

cdef int fib_c(int n):
    cdef int a = 0
    cdef int b = 1
    cdef int c = n
    while n > 1:
        c = a + b
        a = b
        b = c
        n -= 1
    return c

And how I test this code:

testing.py

import pyximport ; pyximport.install() # So I can run .pyx without needing a setup.py file #
import time

from fibonacci import fib

start = time.time()
for i in range(100_000):
    fib(i)
end = time.time()
print(f"Finonacci Sequence: {(end - start):0.10f}s (i=100,000)") # ~2.2s for 100k iterations
\$\endgroup\$
2
  • 5
    \$\begingroup\$ Yes you can; there is a \$O(\log n)\$ algorithm, but it has nothing to do with Cython. \$\endgroup\$
    – vnp
    Commented Apr 12, 2021 at 3:31
  • \$\begingroup\$ memoize goes a long way here. youtube.com/watch?v=Qk0zUZW-U_M&t=240s Sometimes you get better speedup by not using Cython. Numpy is strongly optimized. So is Numba. \$\endgroup\$ Commented Dec 20, 2022 at 20:38

2 Answers 2

2
\$\begingroup\$

Using one less variable seems faster:

cdef int fib_c(int n):
    if n == 0:
        return 0
    cdef int a = 0
    cdef int b = 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Running your test on my machine:

Original = 2.934 s
Improved = 1.522 s
\$\endgroup\$
1
  • \$\begingroup\$ I wonder whether it's because of the multi-assignment or because of the loop-kind... \$\endgroup\$
    – Manuel
    Commented Apr 12, 2021 at 11:12
2
\$\begingroup\$

How about unrolling the loop a bit, doing two steps per iteration so you don't need to "swap" a and b? (I'm not familiar with Cython, so didn't benchmark):

cdef int fib_c(int n):
    cdef int a = 0
    cdef int b = 1
    while n > 1:
        a += b
        b += a
        n -= 2
    return b if n > 0 else a
\$\endgroup\$

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.