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

 

Webkit based Opera

Earlier this year Opera has announced they will abandon their render engine and move to Webkit. As a long time Opera fans, I am very ambivalent about this.

The day has come as last. As I download and setup Opera on a new computer, I find that the old Opera is no more. The new Opera is essentially a custom shell of Chrome. The biggest surprise is perhaps I'm still using Opera at all. This is probably not out of loyalty, but rather more of a habit.

The good thing is I can reliably use many web applications without running into compatibility problem. The bane of old Opera is from time to time, web applications will run into problem and not working fully. You learn to become observant and switch to another major browser when necessary in order to proceed. Now web applications work in Opera with greater certainty.

The flip side is it has lost a number of features. One of them is the ability to applied user defined style sheet. I hate to read web page with grayish low contrast font. With old Opera I can switch to high contrast style sheet at my pleasure. Now I have to put up with bad web design. This is a feature I miss. I hope in time Opera will add back these good features into webkit based browser.

2013.12.26 comments

 

Tasty Restaurant - Outer Richmond, San Francisco

We were at Tasty Restaurant (5530 Geary Blvd) for dinner. This is a Chinese restaurant in Outer Richmond, San Francisco. The food is nothing remarkable. The decor is basic. But its price is cheap. A dinner can be have for less than $10. Yet somehow these neighborhood restaurants give me some warm and fuzzy feeling.

tasty restaurant

Next door is a Russian Bakery. And next there is an old school Italian restaurant Gaspare. It feels like the same scene from the 80s. In contrast to all the glitzy new places opened up in Mission, it is as if gentrification has yet to come to Richmond.

2013.12.24 comments

 

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

 

Getting Cython to work with Python 3.3 on Windows

I have spent a fair bit of time to get Cython to work with Python 3.3 on Windows. So I just add a note here in case anyone want a similar setup. These are the components I use:

  • Windows 7
  • Python 3.3 (Anaconda distribution)
  • Visual C++ 2010 Express

To install Python 3.3 version of Anaconda there is a twist. The Anaconda Windows installer (as of 2013-12) is of Python 2.7. You could add the Python 3.3 environment after Anaconda is installed. But then you will be adding the 3.3 packages on top of the 2GB base 2.7 installation. If you don't need 2.7, there is a way to save the disk space. Download and install the Miniconda3 installer. It should be a 32M base installer only. Note that I have only successfully used the x86 32 bit version. I would explain the problem of the 64 bit version later. Next run this to install the Python 3.3 Anaconda packages.

conda update conda
conda create -n py33 python=3.3 anaconda
activate py33

Previously I have tried to download miniconda and install individual packages as needed. But then I find that I did not save much disk space compare to the 2GB full Anaconda packages. So I rather save myself hassle and install everything.

Next you need a C compilers. The idea is your C compiler should be of the same version that compiles the Python interpreter. How do you find out what version of compiler is used? Notice when you start the Python interpreter, it output one line that says the system version. From this we can find out the what it is compiled from. The Anaconda Python version string looks like:

Python 3.3.3 |Anaconda 1.8.0 (32-bit)| (default, Dec 3 2013, 11:58:39) [MSC v.1600 32 bit (Intel)]

1600 is the MSVC version string. Divide it by 100 and then minus 6 gets you 10. This corresponds to Visual Studio 2010 Express. If you have Python 2.7, the version string reads 1500 and it corresponds to Visual Studio 2008 express. I found out this only after tracing the source code in msvc9compiler.py in the distutils packages.

Originally I have installed the 64 bit version of miniconda. In this case the version is like

Python 3.3.3 |Continuum Analytics, Inc.| (default, Dec 3 2013, 11:56:40) [MSC v.1600 64 bit (AMD64)] on win32

I don't know what is the significance of the label (AMD64) in there (my PC is Intel i7). But this prevent the msvc9compiler from associating with the correct compiler. It gives me a cryptic error when I tried compiling:

ValueError: ['path']

I have succeed only after I reinstall with the 32 bit miniconda. With this I am able to compile Cython's hello world example. I hope this helps.

2013.12.18 [] - comments

 

past articles »

 

BBC News

 

Hong Kong protests: Police officer wounded with arrow at campus stand-off (17 Nov 2019)

 

Prince Andrew criticised for 'car-crash' BBC Newsnight interview (17 Nov 2019)

 

Sri Lanka election: Wartime defence chief Rajapaksa wins presidency (17 Nov 2019)

 

US election 2020: Democrats respond to Obama's warning (17 Nov 2019)

 

Venice floods: Further warnings of high tides (17 Nov 2019)

 

Australian politicians banned from China 'will not repent' for criticism (17 Nov 2019)

 

Trump's health 'very good' after unscheduled physical exam (17 Nov 2019)

 

Iran petrol price hike: Supreme Leader condemns 'hooligan' protesters (17 Nov 2019)

 

UK government and military 'covered up war crimes' (17 Nov 2019)

 

Yellow vest protests: More than 100 arrested as violence returns to Paris (16 Nov 2019)

more »

 

SF Gate

 

Ship traffic, November 18 (17 Nov 2019)

 

Best holiday gifts under (17 Nov 2019)

 

I got access to my secret consumer score. Now you can, too (16 Nov 2019)

 

Oops! Judge cuts Johnson & Johnson fine (15 Nov 2019)

 

Apple bans vaping apps from App Store (15 Nov 2019)

 

Twitter details political ad ban, admits it’s imperfect (15 Nov 2019)

more »


Site feed Updated: 2019-Nov-17 09:00