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.

Related posts:

1. AoHoHoAoA
2. dfa minimization + log
3. some thoughts on XML (XmlWriter and DOM)

This entry was posted on Tuesday, January 18th, 2005 at 17:19 and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.