Optimizing Swample
There was one big lesson I learned about software development that I picked up in a Algorithms and Data Structures class at Rice. When implementing a large application, get something working first, then add features one at a time. In that vein, I got swample working and online quickly. But soon thereafter, I focused on optimization.
As I touched on last time, from the beginning I wanted to support all possible words up to the maximum of sixteen letters. To do that, I knew that I would have to be clever in solving to keep the wait time to a minimum. So from the beginning I implemented the narrowing I mentioned. However, once the application was live, I knew I’d have to go back and revisit optimizing the solver. Which Google App Engine quickly reminded me of by spouting CPU quota warnings.
This request used a high amount of CPU, and was roughly 1.4 times over the average request CPU limit. High CPU requests have a small quota, and if you exceed this quota, your app will be temporarily disabled.
So I cleaned up my prototype code and turned to a profiler. Python has an included profiler, so getting some statistics about my algorithm was easy enough.
>>> cProfile.run('b.solve()')
1926701 function calls (1916099 primitive calls) in 3.640 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.014 0.014 3.640 3.640 :1()
1 1.489 1.489 3.626 3.626 board.py:20(solve)
2338/16 0.710 0.000 1.171 0.073 board.py:35(__bfs)
...
Which gave me some direction on where to focus my attention. From there, I refactored code to make use of pretty simple efficiency improvements and cut down the number of unnecessary string operations that I had thrown in just to get something working. Since I already had a working prototype, I could ensure that every optimization I made both (a) didn’t break the application and (b) actually lowered processing time.
Immediately wait time to the end user was dramatically lowered, and I haven’t gotten one of those CPU warnings since I posted the change.
