tungwaiyip.info

home

about me

links

Blog

< December 2013 >
SuMoTuWeThFrSa
1 2 3 4 5 6 7
8 91011121314
15161718192021
22232425262728
293031    

past articles »

Click for San Francisco, California Forecast

San Francisco, USA

 

Cython for the win, 177x speed increase!

Putting Cython into use, I have great success in speeding up a computation algorithm. Previously I have great success of getting 10x speed increase just by swapping in pypy. This time, with a little bit of work, I get 177x speed improvement using Cython. This vastly exceed my expectation.

The code is to solve a string alignment problem in bioinformatics. With a string s and t, the algorithm has complexity of O(|s||t|). The first step of writing Cython is to identify the performance critical region of code. In this case it is quite obvious the bottleneck is in the inner loop with complexity of O(n^2). No profiling is needed. The origin Python code inner loop is like below. Note that M and B are numpy arrays.

def overlap_alignment_inner(s, t, sigma, M, B):
  for i in range(1,M.shape[0]):
    for j in range(1,M.shape[1]):
      match_score = M[i-1, j-1] + (1 if (s[i-1] == t[j-1]) else -2)
      M[i,j], B[i,j] = max([
                             (M[i-1, j] - sigma, (i-1, j  )),
                             (M[i, j-1] - sigma, (i  , j-1)),
                             (match_score,       (i-1, j-1)),
                           ])

After a few iterations, I have arrived with the optimized code below. It looks somewhat different from the first glance. But I would walk through the chances I have made. I have taken a lot of clues from the tutorial Working with NumPy.

import numpy as np
cimport numpy as np
DTYPE = np.int
ctypedef np.int_t DTYPE_t

def overlap_alignment_inner(s, t, int sigma, np.ndarray[DTYPE_t, ndim=2] M, np.ndarray[DTYPE_t, ndim=3] B):
    cdef int i, j
    cdef int s10, s01, s11
    for i in range(1,M.shape[0]):
        for j in range(1,M.shape[1]):
            s01 = M[i, j-1] - sigma
            s10 = M[i-1, j] - sigma
            s11 = M[i-1, j-1] + (1 if (s[i-1] == t[j-1]) else -2)
            if s11 >= s01 and s11 >= s10:
                M[i,j] = s11
                B[i,j,0] = i-1
                B[i,j,1] = j-1
            elif s01 >= s10 and s01 >= s11:
                M[i,j] = s01
                B[i,j,0] = i
                B[i,j,1] = j-1
            else:
                M[i,j] = s10
                B[i,j,0] = i-1
                B[i,j,1] = j

The first thing to do is to add type to certain variable for early binding. The simple int declaration below increase speed by about 10%.

cdef int i, j

The next thing to do is to type numpy ndarray objects like below. This allow faster indexing compares to normal Python operations. This speed things up a few times.

... np.ndarray[DTYPE_t, ndim=2] M, np.ndarray[DTYPE_t, ndim=3] B ...

The most significant problem turn out to be the use of the max function. In the original code it is a concise and stylish way to pick the best score and simultaneously assign two values to M and B. But this keep the statement as a costly Python function call. By unwinding the function into if statements, it allow the code to be fully optimized and attained the 177x speed improvement! This brings the performance to the league of C.

The unwind code, while longer, is actually quite straight forward. So I backported it to the pure Python code. This also result in a 3x improvement! Turns out use of max here is rather costly.

My first use of Cython is very successful. By identifying and optimizing only a few lines of critical code, it dramatically speed up the performance to the level of C. The rest of the code are not performance critical. They remain easy to write and debug using Python.

2013.12.19 [] - comments

 

 

blog comments powered by Disqus

past articles »

 

BBC News

 

Coronavirus: EU demands UK-made AstraZeneca vaccine doses (27 Jan 2021)

 

Biden to sign executive orders on environment (27 Jan 2021)

 

Boeing 737 Max cleared to fly in Europe after crashes (27 Jan 2021)

 

Nia Dennis: US gymnast's 'black excellence' routine goes viral (27 Jan 2021)

 

Hotel quarantine for England arrivals from hotspots (27 Jan 2021)

 

The sadness of marking Holocaust Memorial Day alone (27 Jan 2021)

 

China mine rescue: Miners saved after knocking on pipe (27 Jan 2021)

 

Independent Spirit Awards: Michaela Coel, Carey Mulligan among nominees (27 Jan 2021)

 

Biden raises election meddling with Putin in first phone call (27 Jan 2021)

 

Elliot Page: Juno actor to divorce Emma Portner (27 Jan 2021)

more »

 

SF Gate

 

Fired Boeing CEO is now working with Bay Area tractor startup (14 Dec 2020)

 

PG&E bills to rise over per year on average to fund wildfire risk reduction (5 Dec 2020)

 

Nasdaq seeks more diversity on boards of companies listed on exchange (2 Dec 2020)

 

Elizabeth Holmes Prosecutors Say Texts Show Theranos Beset With Problems (24 Nov 2020)

 

Ship traffic, November 1 (30 Oct 2020)

 

Ship traffic, November 2 (30 Oct 2020)

more »


Site feed Updated: 2021-Jan-26 18:00