Lyapunov Fractals in Python: Performance and Pretty Pictures
Posted in Computer Tips, Personal on April 15th, 2011 by Ryan Marcus – Be the first to commentI spent some time earlier this week playing around with Lyapunov fractals in Python. While normally I wouldn’t consider Python to be a performance-packing language, the ease-of-use (programmer cycles vs. machine cycles) inherent in Python has always been attractive. However, I was able to speed up my Python code substantially using Psyco, the Python multiprocessing module, and a fast implementation of Python called PyPy.
Lyapunov fractals are generated from a specific binary sequence, generally denoted with A’s and B’s. For example, the sequence “ABA” produces a different fractal than the sequence “BBAA.” An algorithm for generating these fractals is described by the Wolfram folk here.
Lyapunov fractals are formed by associating an exponent (which, from what I can determine, is generally between -2.0 and 2.0) with a color. Each point on a 4.0×4.0 plane gets an exponent. A visual representation of the fractal is then formed by associating each exponent with a color.
Because of the computationally intense aspects of calculating an exponent, I decided to create one program to calculate all the exponent data, saving it to a file*, and another program to create an image from it. My source is available at the end of the post.
After I’d written my code, I felt the wraith of Python in the form of slowness. After some trivial optimizations, I found Pysco and the Python multiprocessing module.
Psyco is pretty straightforward: it does a bunch of JIT-style compilation (read: magic) on vanilla python to speed it up. It is pretty easy to use:
import psyco
psyco.full()
Or, if you are slightly more error-cautious:
try:
import psyco
psyco.full()
print "Psyco'd!"
except ImportError:
print "No psyco"
pass
The Python multiprocessing library is a real gem. It provides a parallel version of the “map” function. This is pretty awesome — since each exponent calculation depends only upon a point (embarrassingly parallel), it is easy to create a function that takes in a point and spits out an exponent.
Of course, all the concerns of parallel programming still apply. You can’t have any race conditions, and your code needs to be conceptually parallel. Python takes care of all the messy bits (semaphores, join/fork management, etc.) for you.
If you were using the map() function like this:
a = map (function, list)
… you can simply replace that line with:
try:
from multiprocessing import Pool
pool = Pool(8)
print "Parallel!"
a = pool.map(function, list)
except ImportError:
print "Not parallel"
a = map(function, list)
This will preform the map function in parallel (if the multiprocessing module is available) using 8 workers (which is pretty optimal for an i7 920).
I also discovered an alternative flavor of Python called PyPy, which is a performance-driven Python that uses technology similar to Psyco. Sadly, PyPy doesn’t have an implementation of the multiprocessing module, so I was forced to choose between PyPy and traditional Python with multiprocessing and Psyco. I was incredibly doubtful that PyPy’s speed would be able to make up for parallelism and Psyco. I’ll let the numbers talk for me.
The test system contains an un-overclocked i7 920 and 3GB of DDR3 RAM. These numbers are from generating a 1000×1000 fractal worth of data with the sequence “AB” to a depth of 500 (iterations). I run Ubuntu 10.10 32-bit.
Time in seconds. Smaller is better.
| Trial | Python with Psyco and MP | Python with Pysco | Python with MP | Python | PyPy |
|---|---|---|---|---|---|
| Trial 1 | 36.4 | 273 | 253 | 2041 | 71 |
| Trial 2 | 36.3 | 268 | 258 | 2042 | 66 |
| Trial 3 | 35.2 | 269 | 255 | 2058 | 71 |
| Average | 35.966667 | 270 | 255.333333 | 2047 | 69.33333333 |
Clearly, Python on its own is pretty darn slow. Psyco provides nearly a 10x speedup, and if you can write your code to take advantage of the multiprocessing library, you can go really fast.
The PyPy results, compared to the Pysco results, are quite impressive. If PyPy had an implementation of the multiprocessing library (which I’m fairly certain it doesn’t — feel free to correct me), it would probably dominate.
The multiprocessing results for this test aren’t completely fair — generating fractals is an embarrassingly parallel problem. But, of course, if you can break your problem up into parallel pieces, you can expect a relatively big speed bump.
Conclusion: Python doesn’t have to be as slow as Python normally is. Drop-in replacements like Psyco can greatly accelerate code. if your code is vanilla enough to not require many external libraries (like PIL) then PyPy can probably give you quite the boost as well.
You can download my source here.
Here’s some pretty pictures:
* A note about pickle: I realize that many Python developers would’ve decided to use pickle (or the faster cPickle) to save their exponent data to a file. I found cPickle to be far, far slower than just writing out comma separated values.
