I thought I’d summarize some of the results of trying to fix garbage collection pauses in c3dl animation and speed up performance in general.

The problem

Every now and then there is a small pause. It’s only 250 milliseconds for the most part. For any other JavaScript application that wouldn’t be a problem because most people can afford to wait 250 ms. It’s a problem for animation, though. Ideally, we want a frame rendered every 25 ms. Any slower and the animation is not fluid. Frames that take 250 ms stick out like sore thumbs. The problem is garbage collection. Every time JavaScript collects garbage it has to pause execution. Because we are rendering so many frames and doing so many calculations, there are a slew of tiny memory allocations that need to be collected. It takes a while to wade through them. So we need solutions.

What doesn’t work

  • Removing validation code
    Profiling shows that the most frequently called functions of the library are short functions that check if matrices, quats and such are valid. One way to get rid of any overhead associated with these is to remove the checks entirely. However, doing that doesn’t stop gc pauses. It doesn’t seem to have any other performance enhancements either. Although those functions are called frequently, they don’t create temporary variables or do a lot of expensive operations.

  • Creating a global pool of variables
    In C language, if want to conserve memory, you just re-use it. Instead of constantly allocating a temporary array every time you need one, you declare it once and re-use it. Unfortunately, JavaScript doesn’t work that way. JavaScript doesn’t really have arrays or types in way C does. Something like var pi = 3.14 is not like double pi = 3.14. In JavaScript, pi would be a reference to a double. The interpreter might decide to drop it and re-allocate it if the value is changed. Worse, arrays are not really arrays, but hash tables. So an array of doubles is really a hash table of references. The interpreter handles all the low level stuff and you don’t. (Integers behave a bit more the way you would hope for, and I should note that doubles don’t always behave so badly. It’s just that you don’t have any control over this behaviour.) I tried putting a lot of variables that could be reused into a global scope where they could be re-used. But for the reason, I have outlined, this didn’t work.

  • Changing setInterval to setTimeout
    Currently each frame is rendered according the schedule of a setInterval. Another way of doing it is to put a recursive setTimeout at the end of the render cycle. Subjectively speaking I thought this looked smoother. But the data said it didn’t make any difference. The length of time each frame took on average was the same. And the gc pauses were still there.

  • delete keyword
    The garbage collector might work more efficiently if it knew earlier when an object becomes garbage. With the delete keyword you can tell the interpreter you are done with an object. Unfortunately delete doesn’t work on arrays or primitives. You can only delete objects created with a constructor. So there wasn’t too many places were a delete could usefully be placed. Certainly not enough to produce positive results.

What does work, sort of

  • passing by reference rather than value
    If it’s possible to avoid creating a temporary variable by passing by reference then you should. JavaScript always passes by reference, so instead of returning a value from a function, get your return value as a function parameter. Sometimes this is not an effective way of avoiding temporary variables, but usually it is. Making a few such changes in the code did positively affect our frame count. Unfortunately, it didn’t change the gc problem.

  • Using let to scope
    When including a script into an html document it’s possible to specify that you want to use the features of JavaScriptipt 1.8. This gives you access to the let keyword. This allows you to do with arrays and primitives what you can’t do with delete. What let can do is scope variables explicitly. For instance, in C a for loop written as for(int i=0,i=5,i++) has a variable i that goes out of scope when the loop is done. But in JavaScript, for(var i=0, i=5, i++) creates a variable that doesn’t go out of scope. Using let instead of var tells the interpreter you are done with i. After putting lots of lets in I observed that the heap delta had a more regular sine wave pattern that would indicate to me that garbage was being collected in a more timely fashion. However, this didn’t really change the length of the gc pauses since it ultimately doesn’t cut down of the amount of garbage. I think there are still places in the code where let could replace var, but it’s hard to do without breaking things.

  • eval is evil
    I know eval is super useful, but it gets in the way of compiler optimizations. The interpreter can’t look ahead at code inside the quotes and optimize. It’s an expensive operation (as is anything with strings). There are other functions that have eval like qualities too. For instance, setInterval can take a string argument, but it doesn’t need to if it’s just a single function reference. I took out the evals and the strings in setTimeout and setInterval. It does moderately boost performance as far a frame rates go, but it doesn’t prevent gc pauses.

What may work

  • implement our own floating point class
    I don’t even know how you would do this. Because integers tend to just be integers and not references, it might be possible to do calculations with two integers instead of one double by implementing some sort of floating point scheme in high level code. But it would be tricky (impossible?) without static types. Also, you would at some point need to convert the two integers to a double to pass to the canvas context.

What would help

  • debugging tools with correct granularity
    I’ve used two tools to profile JavaScript. Firebug which was made for the task, and Shark which was not. Firebug tells me what functions get called the most and how much time is expended in executing them. Shark tells me how much memory the browser is allocating, how many allocations it makes and what size they are. What I don’t have is a tool that tells me how much memory a particular piece of JavaScript code is allocating. You can read the code and make back of the envelope calculations. But a real profiler could reveal something surprising and unexpected that needs to be fixed. Wouldn’t it be great to get a stack trace of js code whenever the interpreter allocates. That’s why I cried bittersweet tears when I read this: A new memory tool for the web So what I want will exist someday. But not today.

Bug report

In the end, I decided that’s it’s JavaScript’s fault and not the library’s and filed a bug: Bug 482853
Hopefully it gets some love.

Updated benchmark tool

I’ve revised the new benchmark tool significantly. When I first wrote it I didn’t have Shark in mind, so I had to make a few changes.

The benchmark no longer runs all of the tests one after the other. Now the user can select which test to run. This makes it easier to connect to a Shark session at the beginning and end of a test.

I also had to move the canvas element outside of the table I’m using for layout. (I know, tables aren’t for layout.) There’s some sort of bug caused by using a canvas element inside a table. It causes the hooks for Shark to be unloaded. I’m not sure why. I know there is another possible bug that messes up picking inside a table, so there is definitely something going on with canvas inside tables. I don’t know if using CSS for layout is a work around or not. (I know, CSS is not a workaround. It’s the correct way.)

I’ve also changed the structure of the tests.js file to make it easier to read. An example template is included in the file.

Two new tests have been added to tests.js for free cameras. They test moving the camera location and rolling the camera.

Testing javascript’s limits

Here’s an interesting snippet from an irc discussion on managing garbage collection pauses in javascript:

“is it possible to do your matrix math with ints? In jsapi, 31-bit ints are stored directly in tagged jsvals, whereas doubles are stored as pointers. Collecting a bare jsval is bound to be faster than collecting a jsval + free’ing a pointer to a gcthing”

Perhaps using two integers to represent a floating point would improve the performance of the library. This would presumably use more memory, but as I’ve blogged before, it’s not the amount of memory, it’s the gazillion references to small allocations that is most likely causing the pauses. I’m not sure how this would work, though, if the canvas3d api still expects a single number. It means converting from two ints to one double in order to pass it across the xpconnect divide. There must be overhead for that.

I’ve been trying to think of a way to test if this would work. So far I haven’t had any luck devising simple tests. I’m not very good at making stand alone tests that mirror the operation of the library. I think I’m going to have to embed the tests right into the library.

On a related issue, bug 482853 is getting some notice. However, the devs want a better test. A stand-alone test. But I don’t think I can improve on this one for bug 482204. Perhaps the author will allow me to steal some of it.

Thinking back at the discussing I had with Andor, I remember discussing about adding the functionality in so that the users can turn off the triangle-triangle test, using only the bounding sphere test. Taking up on that suggestion, I had just finished adding that functionality in.

The collision detection now by default, has the triangle-triangle test turned off. To turn it on, the user just need to pass in a boolean true value. cd = new CollisionDetection(scn); cd.setTriangleTest(true);Thinking more about it, it does make a lot of sense to have this feature. I mean, most of the time, I think the bounding sphere collision detection test suffice. Most collision do happen between very simple objects like a wall or a ball, and I think the bounding sphere is enough to serve that purpose.

Plus, if users want a higher performance, the bounding sphere can definitely provide that. Comparing the testing speed for collision between two spheres, the bounding sphere test takes about 20-30 ms where as the triangle triangle test takes about 200-300ms. That’s 10 times longer, and I can’t guarantee that the results will stay the same for even more complex objects. Of course, I’m not saying all collision detection are this slow with triangle-triangle tests, and I am still trying to find out if there are more ways to increase the speed of my collision detection.

Lets hope I can get another big jump in performance soon. =) Finally, I’m starting to see faster movements in my sphere during collision! I still remember in my previous blog, I mentioned how the collision detection between spheres would take around 16000ms just to finish the test. Although, I still consider my collision test to be running slow for sphere-sphere, I am proud to say that, I have increased the efficiency to a somewhat acceptable speed. How long does the test take for a sphere-sphere collision detection now? About 200-300ms. That’s a significant reduction from the 16000ms I originally had. Not bad eh? How did I achieve that? Remember in that same previous blog, I suggested to cut down the number of triangles to test by checking to see if the triangles are at the front of the object? I’ve further improved that and narrowed down to even less triangles. I don’t know why it took me to think of doing this, but now that I’ve thought about it, it only seemed obvious. So instead of checking to see if the triangle is in the front of the object, which actually took more work than what I’m doing now, I check to see if the triangle in object A is within the bounding sphere of object B (Ex1 in diagram below). And then, I apply this same rule to the triangles of object B as well (Ex2 in diagram below). In this case, only the triangles in the region of the objects marked as yellow will be checked for collision.

So now, the logic of the whole collision detection goes like this:
  1. Find objects that have their collision detection flag turned on
  2. Check to see if they pass the bounding sphere test
  3. Perform triangle-triangle test for objects that pass bounding sphere test
And then what happens in the triangle-triangle test is this:
  1. Go through the triangles of object A
  2. For each triangle of object A that is within the bounding sphere of object B, go through the triangles of object B
  3. Find triangles of object B that is within the bounding sphere of object A
  4. With those triangles, perform test for intersection
With this, we can narrow down the number of triangles not only to about half (in the front of the object), but we’ve narrowed down to only triangles that have a possibility of colliding with the other object. See the new and improved collision detection in action at http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev4/testDemo.html.

Last year during GDC I went to Mountain View to visit with my professor Dr. Dekang Lin.  It takes about 1 hour to go from downtown San Francisco to Mountain View via CALTrain.  As I sat in the train last year I wrote two blog posts.  One to announce that our website has gone live, and another announcing our 0.1 Release.  It has been more than a year now and I figured that since I was making the same journey, I should do a review blog of all the things that have happened in the past year. It’s a bit long but I think it’s a good summary of where we came from, where we are and where we’re headed.

Library then and now

One year ago, our library was able to create a scene made of cubes and manipulate those cubes.  This screenshot is of a demo built with our first release.

last years demo
It was fairly primitive at the time but considering it had just started it was not too bad.

Since then, much work has been done (we are now in our 0.7 release with 0.8 coming very very soon).  We added texture support and used it to create our first mashup.  We defined how meshes were to be stored and wrote some converters and scripts to create these.   Our demos finally looked like it was more than just cubes and rectangular logs.  Later in the year we added support for loading collada models. We added lighting and particle effects to our library as well as elementary picking routines.  Our code has been refactored and reorganized for consistency and style.  Many changes have been added to make it as efficient as possible.  We had some user testing done by people at Big Hadron Games, who are studying at the Great Northern Way Campus.  They did some excellent demos for us (c3dl Asteroids, Duck and Cup,  DuckDreamz) and gave us some much needed feedback.

Last year our demo had 4 spinning cubes.  This year we have… well a lot more.  I made a youtube video showcasing some of these.

People Then and Now

Initally when C3DL started, the main contributors were Mark Paruzel and Andrew Smith.  Both had graduated from Seneca’s BSD program and had experience working with 3D and open source.  Both worked on C3DL part time.  Just before GDC last year Mark put together enough for our library to create cubes and make them move.  Since both Mark and Andrew had other full time commitments, the time they could afford for their part time work was limited.  As a result, I decided to try and hire some more help near the end of March.  I made a general announcement of this to the classes I was teaching and found 2 candidates.  Chris Bishop and Andor Salga.  Chris worked part time on the project to test and make demos with the library.  Andor on the other hand would work on the library itself.   Much of the improvements to the library since May has been result of Andor’s hard work.  At some point (and I don’t remember exactly when this was), Jeremy Giberson contacted us with ideas he had about our library.  This was a first for us as we had not expected help from people that we didn’t even know.  Summer passed on and the Fall semester hit.  Seneca runs courses that teaches students how to work on open source projects.  As part of their course work, Leonard Lee and Patrick Lam joined our team.  Leonard worked on creating a browser with the canvas 3d extension already packaged (for those that did not have firefox or extension installed) while Patrick worked on adding picking to the project.  Jay Edry joined us near the end of the semester and added an artistic eye to our demos.  James Boston joined our team in January to work on fixing some performance issues.  Joe Drew also joined us in January and is working to refactor our code.  David Hill has been working on adding a physics module to our library.  Peter Callaghan is the newest person to join our project.  His work is to stream motion capture data through the browser.

Aside from people who have contributed code, we have had incredible support from a number of other people in different capacities.  In particular a number of people from Mozilla has been incredible in their support of our project.  Vladimir Vukićević has been working on the Canvas 3D extension itself and has given us much guidance to our project.  Today the announcement by Kronos is an exciting step for all of us working with the the canvas 3D extension.  Vlad best summed up what is happening on that front in his post.  A number of other folks from Mozilla (Stuart Parmenter, Mark Finkle, Mike Shaver, Ted Mielczarek) have helped us along the way with little bits and of advice and perspectives. Their kind guidance is greatly appreciated.

From within our school, David Humphrey has been extremely helpful in offering us advice on how to work in an open source community. Dawn Mercer has been our rock.  She helped us with everything from budgets to hiring.  Our department head Evan Weaver has been very supportive of our efforts and offered advice when needed.  In communicating with our other network partners (C3DL is part of the CATGames research network) Laura Jo Gunther and Marcella Kouroupis has been invaluable.

So many people have contributed in numerous capacities for our project.  I hope I have not missed mentioning anyone.  If I did I appologize in advance.  My swiss cheese like memory is to blame.

What next….

And yet there is so much that still needs to be done.  Things on the todo list include:

  • Adding better documentation
  • Adding more tutorials
  • Making sure all the functionality in the gles11 context works with the gles20 context.
  • Adding per triangle picking
  • Continued performance improvements
  • Adding materials
  • Adding multi texture support

The list goes on. We have come a long way since our 0.1 release and its 4 spinning cubes and yet so much more can be done. It is hard to believe that it has already been a year.