Doug's Weblog

In the official CPython implementation, the Python interpreter mixes the state of Python’s stack with the state of the underlying C code’s stack. Under normal operation, this design choice has little impact, but if one looks more closely there are some major drawbacks.

One such drawback is that Python’s stack depth is now limited by the maximum stack depth supported by the underlying CPython process. This might not seem so bad until you consider that one function call in Python may cause many C functions to be pushed onto the stack.

A solution to this problem is to separate Python’s stack from C’s stack. This is exactly what Stackless Python does. Now, Python’s stack size is only limited by the amount of memory in the machine.

I’ve implemented the Sieve of Eratosthenes example from last time using the tasklets and channels that Stackless provides. I haven’t really written any Stackless code until now, but I feel this is a decent translation.

import stackless

def ints(n, ch):
    while 1:
        ch.send(n)
        n = n + 1

def filter_mul(n, i, o):
    while 1:
        num = i.receive()
        if (num % n):
            o.send(num)

def sieve(i, o):
    while 1:
        head = i.receive()
        o.send(head)
        n = stackless.channel()
        stackless.tasklet(filter_mul)(head, i, n)
        i = n

def printer(i):
    while 1:
        print i.receive()

def gather(i, o, n):
    l = []
    for x in range(int(n)):
        l.append(i.receive())
    o.send(l)

def main():
    intch = stackless.channel()
    intt = stackless.tasklet(ints)(2, intch)
    sieveo = stackless.channel()
    sievet = stackless.tasklet(sieve)(intch, sieveo)
    #printert = stackless.tasklet(printer)(sieveo)
    gathero = stackless.channel()
    gathert = stackless.tasklet(gather)(sieveo, gathero, 1e4)
    print len(gathero.receive())

    stackless.run()

if __name__ == "__main__":
    main()

Running this results in decent performance:

--( 9:22 : $)-- ~/local/stackless/bin/python --version
Python 2.6.2
--( 9:24 : $)-- time ~/local/stackless/bin/python sless.py
10000

real    0m47.369s
user    0m46.123s
sys     0m0.076s

I tried running the same example to find the millionth prime, but after hours of execution time I killed the process. While the memory consumption was reasonable, the execution time suffered from, what I believe to be, much overhead from object creation and switching between tasklets. Still, it’s encouraging that this version didn’t fail due to stack depth problems.

Stackless Python is an interesting experiment, and I wish the features implemented here were part of the official Python release. If you haven’t heard of Stackless before, I encourage you to read about what it offers to Python and why this can be useful beyond the toy example I have here.

In the programming language Scheme the concept of infinite lists can be implemented using streams. A stream is really nothing more than a cons cell that contains a value in the cdr field and a pointer to some code to generate the cdr field. While simple in design, the concept is powerful, allowing the programmer to create infinite sequences by simply defining a function to generate the next value in the sequence.

Python supports a similar concept in the form of generator functions. The implementation here is a little more complex, but it can be thought of as a function that returns a result, but maintains its current state for later execution.

Both can be used to write rather elegant code. Take for instance the Sieve of Eratosthenes. This can be implemented in Scheme like so (borrowed from SICP):

(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))

(define (divisible? x y) (= (remainder x y) 0))

(define (sieve stream)
(cons-stream
(stream-car stream)
(sieve (stream-filter
(lambda (x)
(not (divisible? x (stream-car stream))))
(stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

In this code, a new stream is created to filter out the unwanted multiples from the previous stream.

Similarly, it can be expressed in Python using generators:

def integers(n):
while 1:
yield n
n = n + 1

def filter_mul(n, s):
for i in s:
if (i % n):
yield i

def sieve(stream):
while 1:
head = stream.next()
yield head
stream = filter_mul(head, stream)

The expression is elegant and theoretically allows us to represent an infinite list that is evaluated lazily. However, the reality strays from the theory. While this code works just fine to find small primes, it breaks for larger values:

;Loading "sieve.scm"... done

1 ]=> (stream-ref primes 1000)

;Aborting!: out of memory

>>> from sieve import *
>>> primes = sieve(integers(2))
>>> [primes.next() for x in range(1000)]
RuntimeError: maximum recursion depth exceeded

In both cases, we’ve exhausted the language implementation’s ability to hold the data structures necessary to represent the lazy lists. The result is elegant code that fail rather quickly. Now, we could always buy ourselves a little more execution time by increasing the heap for Scheme and the recursion depth for Python, but that will only take us so far.

So, that leaves me wondering: is there a similarly elegant way to write code of this sort that won’t expire so quickly? To clarify, I’d like to keep using streams and generators, but find some way to limit the overhead incurred from the creation of so many filters (1 for each prime!) without resorting to a different algorithm.

Update:
I want to address the alternative primes calculation listed in SICP:

(define primes
(cons-stream
2
(stream-filter prime? (integers-starting-from 3))))

(define (prime? n)
(define (iter ps)
(cond ((> (square (stream-car ps)) n) true)
((divisible? n (stream-car ps)) false)
(else (iter (stream-cdr ps)))))
(iter primes))

This procedure is still recursive (primes uses prime? which uses primes), but has much less memory overhead — I managed to generate primes much larger than the 1000th without hitting memory limits. However, this solution strikes me as not quite the same in spirit as the first. Here, a given integer is tested by comparing it to the current list of generated primes while the first definition is building up a function to generate the next prime without having to explicitly scan the list of the already generated primes.