100k robots musical chairs microsimulation diagram

Stackless Python is Python with support for lightweight microthreads called tasklets. Tasklets communicate by sending messages through channels — similar to Erlang, but with Python syntax (guess which I prefer :-). Stackless also has a sibling called Greenlet (greenlet), which brings similar microthread support to standard CPython.

Scale

Tasklets have very low overhead compared to OS threads, so you can run hundreds of thousands of them simultaneously. When a single machine gets too crowded, you can pickle tasklets and send them to another machine — better known as mobile agents in computer science. Because tasklets still live under Python's GIL, combining multiple processes (multiprocessing) to utilize multicore machines with many tasklets per process is a natural scaling strategy.

API Alignment Challenge

In Python 2.6, the multiprocessing and threading APIs were aligned. A natural next step would be aligning those APIs with Stackless tasklets (process > thread > tasklet), and perhaps extending that pattern out to the cloud as well.

Example — Simulation with 100k Robots

The robots are playing a variant of musical chairs on a rectangular arena. Unlike regular musical chairs, once a chair has been sat on, it cannot be sat on again. Finding out who won is left as an exercise.

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 its 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 re-insert the tasklet into the scheduler
            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)