Just as my freshest gamedev.net article about Memoization and caching is in a pre-publishing review state, today I used the technique of result caching to significantly improve the performance of some code.

Here's the deal: the Qt application (a simulation log viewer, aka Scope) I've been writing lately should display values of buses (groups of bits) in various bases.

As a design decision, everything in the internal data structures is kept in binary, and only if the user asked to convert some display to hex/decimal I do the conversion. This simplifies implementation, because all the other operations the user does are best made on binary buses.

Well what is the problem then ?

The problem is that these calculations are done during a paint event, and being costly the display flickers when the user wants to see many buses as decimal/hex.

The solution: caching the conversion results.

I have a class named base_conv - a singleton that provides various base conversion functions - bin2dec, bin2hex, hex2bin, etc. All the data given to and returned from the functions is QStrings (Qt's string class).

And here another praise to Qt is due: their QCache class that provided just what I needed - an easy to use LRU cache. Using it, it was a matter of 5 minutes to add caching to the conversion functions, and viola - it now works very quickly.

The QCache class also provides statistics when asked to, and I indeed see a very high cache hit rate, as expected (> 99%). This is easy to understand - the only cache misses are when new values are converted to some base. All further repaints ask for the same conversions and get the result immediately - QCache is implemented with a hash table, and knowing how many items the cache will keep (it's LRU - deleting all the old items automagically) it's easy to make the hash array big enough to get *real* O(1) insertion/extraction.

Thus, caching allows for both a faster implementation and a more robust design.

I tell ya, good libraries just rule. It's a lesson I learned at least 3 times in the last month.


Comments

comments powered by Disqus