Thursday, September 18, 2008

Performance gain of memoization in Ruby

I and a some friends at work are developing a code generator that simplifies how we use a third-party library. Basically, the problems with the library are:

  • Hard to write code: we wish to express "get X.Y.Z", but the library force us to write "get Y from X by doing actions A and B, check that the result is a Y, cast it to a Y and then get Z by doing C actions and D". You get the point...
  • Hard to read code: given the code to "get X.Y.Z" is extremely hard to understand that it X.Y.Z that it returns. Self-documenting code is basically impossible to achieve here. We have tried, and fia
  • The library has no interfaces what-so-ever, making it very hard to our own code.

We've developed the code generator without any effort to make it fast (making it correct is hard enought). However, there have been a few instances where we simply "had to" optimize, because our test-cases started to take minutes to complete. Not good at all.

The first optimization we did was to write the parse tree of a file (which rarely changes) to disk by marshalling the Ruby objects. This made the parse phase go from 2-4 minutes to instantaneous. It was quite simple to implement, too. Very good! Actuallt, we didn't even use a profiler for this because it was to utterly obvious that it was the parse phase that was the bottleneck.

For the second optimization, though, we used a profiler. We found that a single method was responsible for around 90% of the used CPU time and that is was called alot. What to do?

Well, lucky us, we had been very careful to not have any state in our classes. That is, the code generator is purely functional (well, almost) . This made it possible for us to cache the result of the method the first time it was called, and use the cached value for all consecutive calls. (This only took one additional line of code, by the way.) We ran our test-suit and it passed. Great!

We ran the profiler again. The performance gain was 25 fold. Good stuff.

For me, this illustraits the age old truth that you should only optimize when you know you need to optimze and what/where to optimize. But it also shows how easy it is to optimize functional code, especially if there is a good test-suit making sure you don't mess anything up.

No comments: