Tools for Accelerating Python

If you need to speed up your Python program there are several possible approaches, with varying degree of effort needed, here is (probably not complete) overview:

1. Rewrite your Python code by parallelizing or optimizing/replacing/tuning algorithm(s), e.g. using: 
• Hadoop or Disco
• Open source implementations of MapReduce 
• Parallel Python 
• Message Passing Interface (MPI)
• Frequently used for numerical programming
• Bulk Synchronous Parallel (BSP) 
• RPyC
• RPC for Distributed/Parallel Programming
  
• Twisted
• Network libraries for Distributed/Parallel Programming
  
• Profiling Tools
• Threading or Microthreads (Stackless) 
2. Use a tool that can speed up your code more or less unchanged
   
• Psyco
• Just in time compiler, note: this is probably the easiest approach to try
• Pyrex
• Write and compile Python with a flavor of C data structures
• Cython 
• PyJs 
• Compile (large subset of) Python to Javascript, note: probably more interesting for client development (ajax) than server side.
• Rpython
• Compile (large subset of) Python to native code, note: part of PyPy project
• PyStream
• GPULib
• Shedskin 
• Compile (large subset of) Python to C++, some benchmarks
  
3. Replace (parts of) your Python code with another language
• Simplified Wrapper and Interface Generator (SWIG) 
• Use C/C++ from Python
  
• Fortran to Python Interface Generator (F2PY) 
• Use Fortran from Python
• llvm-py 
• Code and Compile to Assembler for running on Low-Level Virtual Machine
• CorePy 
• Write Assembly Code in Python
• Weave 
• PyInline 
• Boost.Python
• Cinpy 
• C code blended with Python (using ctypes) and runtime compilation with tcc

Example of Microsimulation with Stackless Python

Stackless Python is roughly Python with support for microthreads (called tasklets). Tasklets communicate with each other by sending messages through channels , i.e. similar to Erlang, but of course with Python syntax (guess which I prefer :-).  Stackless has a sibling called Greenlet Python , which is a library that can be used with traditional Python to get decent mictrothread support.

Scale
Tasklets have low overhead (compared to traditional threads) so you can have hundreds of thousands of them simultaneously, and when it gets overly crowded and busy on one machine, you can easily scale up by pickling some tasklets and send them to another machine (better known as mobile agents in computer science). Since tasklets also live Python's GIL regime, it might be idea to use the processing API to spawn several processes to better utilize multicore machines (and have many tasklets within each process), or use some of these libraries .

API Alignment Challenge
In Python 2.6 the process and thread APIs are aligned, but a missing piece would be to align those apis with stackless/tasklet apis. From my perspective a natural order would be process > thread > tasklet, and perhaps adding your favorite piece of the cloud would make sense for the API as well?

Example - simulation with 100k robots
The robots are playing a variant of musical chairs on a rectangular arena, it differs from regular musical chairs since if a chair has been sat on once, it can't be sat on again. Finding out who won is left as an exercise (hint: it can be found more than 1 place)

from random import randint
import stackless
import sys
import time

class Arena:
    def __init__(self, xdim, ydim):
        self.arena = [[None]*ydim for x in range(xdim)]
        (self.xdim, self.ydim) = (xdim, ydim)

    def find_unused_place_for_robot(self, robotname):
        (x, y) = randint(0,self.xdim-1), randint(0,self.ydim-1)
        if not self.arena[x][y]:
            self.arena[x][y] = robotname
        return self.arena[x][y] == robotname

class Robot:
    def __init__(self, name=0, arena=None, maxrounds=0):
        self.name = name
        self.arena = arena
        self.points = 0
        self.maxrounds = maxrounds

        # bind Robot's live method to it's tasklet
        self.tasklet = stackless.tasklet(self.live)()

    def live(self):
        rounds = 0
        while rounds < self.maxrounds:
            self.play()
            rounds += 1
        self.tasklet.kill()

    def play(self):
        # entire play method is atomically executed
        atomic = self.tasklet.set_atomic(True)
        if self.arena.find_unused_place_for_robot(self.name):
            self.points += 1
        self.tasklet.set_atomic(atomic)

class RobotArenaSimulator:
    def __init__(self, num_robots, xdim, ydim, maxrounds):
        self.maxrounds = maxrounds
        self.arena = Arena(xdim, ydim)
        self.robots = [Robot(id, self.arena, maxrounds)
                       for id in range(1,num_robots+1)]

    def run_preemptive(self, nopreempt_steps=1):
        tstart = time.clock()
        while stackless.getruncount() != 1:
            # run() takes out the tasklet after nopreempt_steps
            t = stackless.run(nopreempt_steps)
            # so need to add the tasklet to scheduler again
            if t: t.insert()
        return (time.clock()-tstart)

if __name__ == "__main__":
    tstart = time.clock()
    simulator = RobotArenaSimulator(num_robots = 100000,
                                    xdim = 10000, ydim = 10000,
                                    maxrounds = 10)
    simulationtime = simulator.run_preemptive()
    print "simulation time was %.2f seconds" % (simulationtime)
    print "total running time was %.2f seconds" % (time.clock()-tstart)

The Rebirth of Confounding and Theory in Science?

Wired recently published an interesting article titled: The End of Theory: The Data Deluge Makes the Scientific Method Obsolete, where they roughly conclude that with enough data and processing correlation is all you need. While interesting I think it misses a few important points.

Confounding variables
At the end of the article they claimed: "Correlation supersedes causation, and science can advance even without coherent models, unified theories, or really any mechanistic explanation at all".

Correlation between two variables can give some information, and with a lot of data and computational horsepower you can find correlation relatively easily, but the danger is if correlation is interpreted as causation (and that can happen).

Example: Correlation between GDP and Children´s Weight
An example is the positive correlation between a country´s Gross Domestic Product (GDP) and the weight of its children, if that was interpreted as a causation the cheapest way to increase GDP for a country would be put kids on e.g. a Chankonabe diet (note: I am not saying that is a likely action). The GDP and weight correlation is an example of where a third confounding variable time was not accounted for.

Example: Correlation between substance X and your health
In the press you frequently see eating/drinking substance X is good for your health and makes you live longer, in several of those cases I believe correlation is reported and not the confounding variables, i.e. many of these substances are luxury goods and may not be affordable to most of the worlds population, so the confounding variable might be personal economy which is probably correlated with access to vaccines and medical care.

The value of theory
My personal hypothesis is that the likelihood of not finding confounding variables increases exponentially with the complexity or level of abstractness of the domain investigated for correlation (e.g. in medicine, farmacology, biology or physics) The useful information is more likely to be found when discovering confounding variables, and the correlation is primarily a signal that says that something exciting is underneath (there can be cases where correlation is sufficiently interesting in itself though). In order to find or propose confounding variables I believe the need for models and theories is still very much needed, probably even more than earlier (but the simplicity or complexity of models is another discussion, I tend to lean towards KISS).

Disclaimer: This posting (and all my others) represent only my personal views.

Annual Echo Chamber

Having blogged for a bit more than a year (April 2007), here are some rough stats and opinions of blog entries so far. Most read entries:

1. Pragmatic Classification with Python
2. Greenlet Python is concurrently alive and kicking
3. RPython GCLB Benchmark - Recursive
4. How to complete your PhD
5. Future number of programming languages - singularity or infinity?

In terms of self-eval (read: navel gazing..) of entries, the list would look like this:

• Increase Automation of Test-Driven Development
• PhD Subject in Computer Science?
• Pragmatic Classification: The very basics
• Pragmatic Classification of Classifiers
• Dining Philosophers and Quarreling Kids

As always this blog only expresses my personal opinions.

Pragmatic Classification of Classifiers

recap: In my previous machine learning related postings I have written about the basics of classification and given an overview of Python tools for classification (and also a machine learning dream team and how to increase automation of test-driven development).

In this posting I will "go meta" and say something about classes and characteristics of classifiers.



Informative vs Discriminative Classifiers
Informative classifiers model the densities of classes and select the class that most likely produce the features, in the naive bayes case this modeling involves counting (see here for an example with these data).

Discriminative classifiers have a different approach - they try to model class boundary and membership directly, e.g. in a simple 2-feature dimension case this could mean trying to finding the line that best separates the classes (in >3 feature dimensions case it would be looking for the hyperplane that best separate classes). Examples of discriminative classifiers are support vector machines (SVM) and ridge regression.

Classifier training methods
Many classifiers are batch-based, that means that they need to have access to all training data at the same time (including historic data in a re-training case). Online classifiers don't need all data for every training round, they supporting updating the classifier data incrementally. A related training method is decremental training, which is about dealing with classifier problems where there is concept drift (i.e. forgetting out-of-date examples). Other training methods include stochastic training which is about training using random samples of data.

Linear vs Non-Linear Classifiers
If you have a situation where one class is inside a circle and the other class is outside the circle (and surrounding the circle), it will be impossible to linearly separate the two classes (with a discriminative classifier), fortunately there are non-linear classifiers that can solve this (typically by transforming the problem into a more computationally heavier problem using a kernel trick, but at least the new problem is possible to solve).

Sequential vs Parallel Classifiers
Sequential classifier algorithms can typically utilize one core, cpu or machine, and parallel classifier algorithms are able to utilize more cores, cpus or machines (e.g. in order to handle more data or get faster results).

Non-orthogonal Data
Non-orthogonality is handled by some classifiers, this can happen when there are repeated occurrences of training data.

Dependencies between features
Dealing with dependencies between features (e.g. correlations) is handled by some classifiers (this is sometimes a symptom of potential for improvement in feature representation).

Blogging is good for you..

Source: Blogging -- It's Good for You (Scientific American)

Scrum makes you smarter

Disclaimer: cartoon presents a free interpretation of this