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

 

Venice floods: Climate change behind highest tide in 50 years, says mayor (13 Nov 2019)

 

Hong Kong protests: Students fight police with petrol bombs, bows and arrows (13 Nov 2019)

 

'Berlin rocks,' says Elon Musk as he chooses European factory (13 Nov 2019)

 

Australia bushfires: Fresh warnings in Queensland and New South Wales (13 Nov 2019)

 

Secrets of the largest ape that ever lived (13 Nov 2019)

 

Ebola vaccine approved as second jab trialled (13 Nov 2019)

 

Israel-Gaza fighting continues for second day after militant's death (13 Nov 2019)

 

Greta Thunberg to sail to Spain climate summit with YouTubers (13 Nov 2019)

 

New Zealand to hold referendum on euthanasia (13 Nov 2019)

 

Saudi Arabia apologises for video labelling feminism as extremism (13 Nov 2019)

more »

 

SF Gate

 

Is some of Calif.'s .3 billion in unclaimed assets yours? Here's how to find out (13 Nov 2019)

 

Ship traffic, November 13 (12 Nov 2019)

 

Disney’s ambitious streaming service is here. And cable feels the force (11 Nov 2019)

 

Stocks slip as uncertainty reigns in US-China trade talks (11 Nov 2019)

 

Apple co-founder says Goldman’s Apple Card algorithm discriminates (11 Nov 2019)

 

Ship traffic, November 12 (11 Nov 2019)

more »


Site feed Updated: 2019-Nov-13 12:00