Announcing: Chipmunk for Javascript!

[josephg]

I've spent the last few weeks line-by-line rewriting Chipmunk into Javascript!

Merry christmas everybody - now you can use chipmunk to port your games to the browser!
http://dl.dropbox.com/u/2494815/code.html

Joints and the spatial hash haven't been implemented yet, and even in chrome its running about 3.5 times slower than the C implementation of chipmunk. But I think there's a lot of room for improvement with some clever tweaking[1].

The API is slightly more OO now, but 99% of API calls still have a direct translation. Eg, instead of calling cpSpaceAddBody(space, body), you call space.addBody(body). Stuff like that.

Have fun with it! Repay me by sending me a link when you make cool things

If anyone is keen to help port Chipmunk's demos over, or get all the joints working, I'd greatly appreciate it. Fork the project on github and send me some pull requests.

https://github.com/josephg/Chipmunk-js/


[1]: Currently vectors and bounding boxes are stored on the heap. In 5 seconds of benchmark run, chipmunk is allocating 6 million objects. Unsurprisingly, I'm spending 25% of the time garbage collecting, to say nothing of object allocation costs. I might have also broken the persistant collision code. Between those two, and re-enabling object pools for bbtree nodes, I think there's a *lot* of room for performance improvements.

Oh yeah, and incase you're curious - ChipmunkJS minifies to 44k of JS, or 13k gzipped. Sexy.

[Edit: Adjusted timing numbers to reflect the 45% improved performance from an afternoon of tweaking. Booyah.]

[Murphy]

Now this will get confusing for people (:
http://chipmunk-physics.net/forum/viewt ... f=6&t=1926

[josephg]

Hahahaha well how about that. Apparently a month or so of coding has saved me 5 minutes with google!

Having done all that work, its interesting seeing the differences between implementations.

Briefly:

• I'm not using requirejs. My code is really flat, and my build step just cats everything together then runs uglifyjs.
• We made identical changes to the API. Aside from requirejs, code written against either implementation should run against the other implementation with no modification.
• I've spent time benchmarking & optimizing my implementation. I suspect my implementation will be faster than murphy's. (Actually, running my ported benchmarking code against murphy's implementation should be easy.)
• I don't have joints implemented, and Murphy doesn't have BBTree implemented. (Wanna trade? )
• Murphy has documented some of the code. If he keeps that up, it might be possible to run the google closure compiler on the codebase. Closure *might* be able to do some further optimizations, although the Requirejs style will probably get in the way.

Anyway, we should probably merge our projects or something.

Murphy: How should we do this?

Have you been tracking the changes in chipmunk -> 6.0.3? What version of chipmunk are you current with? (I'm a few revisions back in github)

Chipmunk spends a lot of its time in Arbiter.applyImpulse, and a lot of time in the garbage collector because of all the vects & bounding boxes on the heap. Just inlining the vector code in applyImpulse (and util.apply_impulse and util.apply_bias_impulse) decreased the number of vectors that were being allocated during the benchmark by a factor of 11, and I got a ~30% speed boost overall from that optimization alone.

I'm tracking my optimizations in this spreadsheet:
https://docs.google.com/spreadsheet/ccc ... 2szdVotOXc
My benchmarking code is here, if you want to play the optimization game too.
https://github.com/josephg/Chipmunk-js/ ... /benchmark

[slembcke]

That's really awesome guys! It's great to see such enthusiasm in porting Chipmunk to different languages and platforms.

I wouldn't really bother porting the spatial hash. There are very few instances where the spatial hash will actually run faster than the BBTree. You need a very large number (thousands generally) of objects that are all the same size. I suspect that these aren't going to be the sorts of things that people will commonly do in web browser games.

Also, I do have a set of benchmarking demos built into Chipmunk's Demo app: https://github.com/slembcke/Chipmunk-Ph ... mo/Bench.c You might find them useful for performance tuning as I have a bunch of different stress tests to try.

[josephg]

@slembcke: You might find my benchmarking code eerily familiar:
https://github.com/josephg/Chipmunk-js/ ... k/bench.js

As good as they are, I'm probably going to add some of the other demos to that benchmark set. According to the bench.c tests, I'm now only 3.2x slower than your implementation. - But the PyramidTopple demo is heaps slower than that. - Its got completely different performance profile than the other tests you have in there (45% of time in Arbiter.ApplyImpulse!) - http://dl.dropbox.com/u/2494815/demo/PyramidTopple.html

Actually - maybe its so slow because I removed the 4-contacts-per-arbiter limit. What effect does that limit have on the simulation quality? Do you think I should put it back in?

I'll leave the spatial hash alone - optimizing BBTree in JS is work enough. I needed to inline all the bounding boxes in tree nodes to avoid extra allocations. (Ugly, it yielded a 7.5% performance gain).

Oh yeah - and thanks for chipmunk! Its really impressive code - you've done a great job with it. Reading the little tweaks you put in there made the translation process really enjoyable.

[slembcke]

Hah, I guess I should have looked at that before I said anything. :p I just had a couple of minutes to be at my computer today. Strange that pyramid topple would be that much slower. To quite sure why that would be really...

The 4 contact per arbiter limit really shouldn't be that much of a big deal I would think. It should be very rare to have a collision that produces more than 3 contacts. Although the 4-contact per arbiter limit was really just a hack that I had put in so that I knew I wouldn't overflow the statically allocated contact buffers at the expense of wasting up to 3 contact points at the end. Ideally, a contact should never ever need more than 3 contact points in 2D to be stable, but I don't have a good (or any) contact set reduction algorithm, so 4 seemed like a better number. You should check I guess, but it should be pretty rare to ever get more than 4 contact points, and it should be impossible with boxes I think.

Anyway, yeah cpArbiterApplyImpulse() is very often the hot spot in C Chipmunk programs as well. I've done a number of passes at optimizing it over the years. Most recently I rewrote it from scratch to use ARM NEON intrinsics for Chipmunk Pro. That was sort of fun actually and I got a pretty huge performance boost out of it. I assume hand inlining all the vector operations would help the code generator and GC out a lot as it wouldn't need to allocate a bajillion intermediate vectors.

Glad that you were able to figure out how the BBTree worked. I really need to write up something on how it works or at least comment the code better. I'm pretty proud of how the performance of it turned out after I added the collision pair caching. It's not terribly different than the tree based index in Box2D (both are inspired by the one in Bullet), but with the caching, mine is pretty consistently 3-4x faster. In most contact heavy simulations the collision detection cost barely even shows up on the profile trace anymore.

[Murphy]

Well if we can work out how to do it, we should probably merge the projects.

Your implementation will probably outperform mine easily, because I wanted to get it completely ported first.
The version I have on Github is based on Chipmunk 6.0.2, my local repo is on 6.0.3 (also includes a BBTree port and annotated comments for API-docs).
I'll be off to a conference the next few days, so I'll look into your port a little closer in 2012. Happy holidays, guys! (o:

[josephg]

Well if we can work out how to do it, we should probably merge the projects.

Great. Can you push your local version to a branch on github? I want your javascript joint code.

Strange that pyramid topple would be that much slower. To quite sure why that would be really...

Yeah I don't know. I think the pyramid topple stresses applyImpulse more heavily than the other tests. I've been chatting to some of the v8 developers. Apparently calling foo.bar = 5 in javascript causes a (small) heap allocation, to box the number. About 18% of the total runtime during pyramid topple is spent in those allocations. The allocation doesn't happen if the result is stored in a typed array (part of WebGL, and only supported in modern browsers + IE10.) However, allocating typed arrays is quite slow. I'm going to look into replacing Contacts with pooled Float64 arrays; and indexing into them when I access their properties.

I'm starting to feel like I'm manually compiling the code :/

The persistant contact code really is amazing. I have to scroll down to page 2 in the profile to even find a reference to BBTree. The first function that appears is BBTree.each, which is using 0.1% of CPU time. I spend 10 times as much time in max() as I do in any of the BBTree functions.

That said, I worry that there are bugs lurking around the place. Bugs in BBTree could be masked in a lot of ways - and could still result in a correct (or correct-looking) simulation. I've been considering writing some unit tests - though a lot of this stuff is sort of hard to test. I might try adding some crazy debugging logs to both chipmunk and chipmunkjs to check that they perform the same set of calculations.

You were right about limiting detection to 4 contact points - adding that limit back in made no difference to the simulation's performance.

[slembcke]

Yeah. Languages like that suck when you are trying to reason about performance or make portable optimizations, but great for writing game logic code. The farther you get from the machine the harder it is to know some of the important little details. On the other hand, most of the time you don't want to care about the little implementation details. :p /me shrugs

Also, I noticed that the pyramid topple demo uses 30 iterations while the benchmarks all use 10. That would explain why it stresses the impulse solver so much.

[josephg]

Yeah. Its funny - I've spent most of this year writing crockford-style coffeescript. High level javascript (where you don't care about performance) may as well be a completely different language. I wonder which of the two languages was intended when Javascript was originally written... I'm now really appreciating why googlers think the closure compiler, GWT and Dart are good ideas. (Well, I still don't like GWT.)

It turns out a bug in poly2poly was forcing v8 to deoptimize applyImpulse. I'm down to only 2.8 times slower than C. Using your C code, the pyramid topple demo takes 5 seconds of CPU time for the boxes to come to rest. In javascript, it takes 9 seconds. I'm not sure why the demo still looks so laggy - maybe I'm pushing the limits of what Canvas can render efficiently.

In most environments, most objects are stationary most of the time. Either there are no forces, or the forces cancel out. Would it be possible to cache the impulses a stationary object experiences and reuse them in subsequent frames? Considering how much CPU time is spent in applyImpulse, there would be decent performance gains in reducing the number of times applyImpulse needs to actually be called.