I write the physics code in ROBLOX and have just finished a major re-write to add articulated characters. The new engine is fast, simple and easier to maintain (we hope!).  When I look at what I threw out, I see lots of code that was prematurely optimized.

Some background on the ROBLOX physics engine. It’s designed to handle colliding bodies and joints in roughly order-N time.  This means that 1000 colliding bodies should only be twice as slow as 500 colliding bodies. The engine is constantly evolving and has not been highly optimized.  For example, there are many areas of the ROBLOX engine that would lend themselves to SIMD code (doing four numeric operations in parallel). This has not been done yet.  The engine has been designed to work on n-core processing architectures, but once again we have not made this optimization. We’re looking forward to getting our hands on a quad-core box to see if our physics really runs 4x faster!

In earlier versions of the engine I developed several high-speed container classes to hold lots (20,000+) of objects with very fast insert, find, and erase operations.  For those of you that are familiar with the standard template library, you know that each of the container classes has some problems in this area.  A std::vector will be slow in the find operation, because you have to traverse the complete array, as will a list.  A std::set carries the overhead of a binary tree, and the find operation is n log(n).  To make a long story short, the new engine is able to exceed performance of my prior versions while just using std::set instead of my finely crafted high-speed containers.  In time I will put my high speed containers back in, but it’s good to know that they are icing on the cake – core algorithms are much more important for performance.

Moral of the story (for me at least):  The more you optimize, the more calcified your code becomes, and the less your C++ looks like the pretty examples from a college algorithm textbook. And the harder it is to make sweeping changes that affect performance in a big-picture way.  Design for speed, but do the hard core optimization when the big picture is nailed.

– Builderman