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.
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
- 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
- Using let to scope
- 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
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.
“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.
- Find objects that have their collision detection flag turned on
- Check to see if they pass the bounding sphere test
- Perform triangle-triangle test for objects that pass bounding sphere test
- Go through the triangles of object A
- For each triangle of object A that is within the bounding sphere of object B, go through the triangles of object B
- Find triangles of object B that is within the bounding sphere of object A
- With those triangles, perform test for intersection
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.
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.
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.