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

 

Canadians Michael Spavor and Michael Kovrig freed by China arrive home (25 Sep 2021)

 

Meng Wanzhou: The PowerPoint that sparked an international row (24 Sep 2021)

 

Germany elections: Merkel backs 'bridge-builder' Laschet as successor (25 Sep 2021)

 

Foreign visas planned to ease UK lorry driver shortage (25 Sep 2021)

 

Afghanistan: Taliban hang bodies as warning in city of Herat, say reports (25 Sep 2021)

 

Afghanistan: Inside the prison staffed by former inmates released by the Taliban (24 Sep 2021)

 

Prince Andrew's lawyers accept he was served with US case papers (24 Sep 2021)

 

Music company buys NFT of 'Side-eyeing Chloe' meme (25 Sep 2021)

 

R. Kelly trial: A look at the key moments as jury deliberates (24 Sep 2021)

 

Quad countries vow to work for freedom in region (25 Sep 2021)

more »

 

SF Gate

 

13 Best Background Check Sites & Services: Search Criminal Records and Social Media Accounts Online (28 Jul 2021)

 

It pays to search for top-quality auto shop (6 Feb 2021)

 

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)

more »


Site feed Updated: 2021-Sep-21 07:00