(Mostly) Pure Python Physics

Continuing my work on the Pure Python port, I did a small amount of profiling with the outstanding runsnakerun to determine what was bogging it down. As expected, the slow speed of Python's math operations -- and especially the matrix and vector operations -- were the major bottleneck.

Having said that, it would appear that there's very little I can do for the Pure Python port to speed it up. If you followed the previous post, you'll know that I tried PyPy (it works after a large number of iterations) and Cython (faster, but still not so great). I considered using some library like NumPy to get its matrix and vector functionality, but including such a massive library just for this tiny physics library just felt wrong.

I stumbled upon quite a few matrix and vector C extensions for Python, notably Casey Duncan's excellent Planar project. However, there were always issues with all of the ones I found: not supporting tuples in place of vector and matrix types, immutable vectors (though this can be a good thing for other projects which don't expect it), and just the general headache of requiring restructuring all of the pypybox2d code that already relies on vector and matrix classes with certain properties and functions. [side-note: were it not for this project, I would definitely be using the Planar library.]

In short, and for better or worse, I re-invented the wheel, creating pure C extensions for the Vec2, Mat22, Transform, and AABB types (should be compatible with Python 2.5~3.2, but let me know your results). Performance significantly improved (sorry, I don't have any benchmarks right now -- but run any of the testbed tests and you'll feel it). Most of the testbed tests run "fast enough". Exceptions include the pyramid and vertical stack ones, which have altogether too many contacts, and the solver gets very slow.

After adding pickling support for the above classes, I then really wanted to give multiprocessing a go. I made a simple test with a set of processes dedicated to doing shape distance calculations (i.e., consumers). I passed in thousands and thousands of shapes and transforms, and it properly generated the results. Unfortunately, comparing it to the single process version, regardless of the number of input sets, the multi-process version was on the order of 10-50x (!) slower -- not even including the time it took to start the processes. All of the overhead, presumably from synchronization and pickling the objects to pass between processes is just too expensive. It looks as if this will not be a viable option for a real-time physics engine.

Now, where to go from here? I'm stumped -- err, I mean -- I'm open to suggestions!

Pure Python physics?

Recently I tried to get pybox2d compiled and running with PyPy, but it failed for whatever reason. I had it in my head to just give up and port the whole bloody thing to pure Python and see how that would go. Not wanting to waste inspiration, I gave that a shot. Fast forwarding to today, and it's pretty much done.

So, what's in the port? (almost) All features of Box2D up to r175:

• All shape types (polygons, circles, edges, and loops)
• All joint types (distance, revolute, friction, prismatic, weld, rope, wheel, mouse, pulley, gear)
• A dynamic tree class for AABBs
• Collisions, contacts, shape distance calculations, etc.
• A mostly Pythonic interface to all of the useful classes
• The testbed, in simplified form

Before you jump for joy, there are many reasons to not use this:

• It's slow.
• It's really slow.
• It has a bad name (pypybox2d -- changing it is on the TODO list)
• It's still early, though almost everything has worked well enough in my tests. I'm positive there are plenty of typos and minor bugs.
• Some source files are much too big, because I haven't gotten around to splitting them up
• It uses __slots__ for my own debugging purposes. I have no qualms about (almost wholly) removing their usage eventually.

"Why do this, then, if it's so slow and unusable?" Do you really have to ask? Why not?

So, what of PyPy after all that hard work? Unfortunately, in my few tests, it's been slower than CPython **. Perhaps one day it will be sped up by another means. Or maybe I'll figure out a way to get Cython working with it such that it won't totally screw everything up. If you have any ideas, please do get in touch with me.

Find the source here. The testbed requires pygame, but there's a (very) simple graphic-less hello.py in examples/ if you simply must run something.

** edit May 20th: But those tests were superficial, only testing for a few iterations. Increase the number of iterations, and PyPy wins, hands-down. See Antonio Cuni's helpful comment below for more information.