Sunday, December 4, 2011

DDTe4 Hours 16 to 18 Optimization


After creating the game, it became clear to me that there are more efficient ways of implementing the game other than using a grid like I did but as I have a short time-limit on the creation of the game, these faster implementations are out of the question. Still, there is some time left for doing an optimization pass. One problem that a lot of programmers have is the desire to prematurely optimize code. While the desire to write efficient code is a good desire, spending a large amount of time on a piece of code that has minimal impact on the performance of the final product is not a good way of spending your time. This is why tools like the profiler that is included in FireBug is such a great feature. The profiler tracks how many times and how much time is spent in every function that is executed while the profiler is running. This lets you know what parts of your program is taking the most time.

In the case of the life game, the code that spent the most time executing due to the huge number of times it was called was the getCell function. The problem with this function is that it needs to support calls outside of the proper bounds in order to properly support the borders. That said, the bounds should only be out by 1 in any given direction which means that if the grid size was slightly bigger and the border was computed along the edges every iteration then we could greatly simplify the getCell function.

To handle this change, the grid size was increased by 2 in both directions, with 1,1 being the top corner internally, though externally 0,0 will be the coordinate passed to get the data. This may not be intuitive, but the downside to optimization is that it can make the code a bit more complicated. The getCell function, on the other hand, becomes a very simple single line of code: return this.grid[y+1][x+1];

This means that if -1 is passed, it goes to the extra bottom or left row and passing the size of the grid as a coordinate will get the extra bottom or right row. To properly fill these rows, the setBorder function has been enhanced. It will fill the border rows and columns with the appropriate data. To make sure the data is correct, it is called at the start of every iteration. To finish up my first optimization pass, the countNeighbors and countCancer functions were quickly optimized by unrolling the loops and replacing the call to getCell with directly obtained cell data as a single line of code is easy to inline.

In JavaScript, there are no explicit types for variables. Variables get converted into whatever type is needed for the current operation. The problem is that this does not always work as planned leading to some real interesting bugs that would not appear in typed languages. In my case, I was using a value from a combo box. The value was a number, but because it is from an html control it's value is stored as a string. When it was passed to my function, 2 gets added to it. The problem is that JavaScript did not convert the string into a number then add two to it, but instead it converted the number into a string and appended it to the string. This resulted in "32" + 2 = "322" which is way off. I solved this bug by flooring the input value forcing it into a number, but finding the bug was a huge problem due to the fact that the code seemed correct (and in a typed language would have been correct). Thank you FireBug.

After fixing the bug and running the profiler again, the getCell, countNeighbors and countCancer drastically dropped in execution time. This optimization pass improved the speed of the simulation quite a bit. The game is quite fun to play with though I am sure there are many features people may want. I can't really think of any features that can be implemented in the few hours left within the allotted development time. For that reason, I am considering the game done. Still, if there is enough interest and suggestions, an enhanced version is something that I would certainly consider working on.

No comments: