Optimization: structure and algorithm

I've spent the past few weeks re-working a library that is used to construct 3D models of machines. The library accepts as input a set of options for the machine - the components that are required for it, basic dimensions, etc. - and uses several sets of rules written by the manufacturer to calculate exact positions and dimensions for each aspect of the machine.

This is a heavily-used library: not only is it used to display several different preview images of the machine as its being specified, but the output is also used as a base for several other important calculations, as well as the generation of a final set of detailed construction drawings and measurements used as input in the manufacturing process. In short, those rules are processed frequently, and there are many of them.

Therein lies the problem. This system had been in place for nearly a decade, and while it had been tweaked over the years to better handle the ever-growing library of rules and options, the heart of the beast was still chained to a decision made early on: the rules were to be pulled from the database periodically and cached, stored on disk and in-memory in nearly the same way they were stored in the DB - flat tables. While this did go a long way towards eliminating the problems of latency when communicating with a remote, heavily-loaded database, it strongly encouraged the use of some very bad algorithms. When i first started profiling, the calculations involved anywhere from several hundred thousand to several million iterations over some of the tables, with each iteration involving at least one look-up into the hash table used to store the options specified for the machine.

And remember, these calculations happen often. Even on a fast machine with plenty of memory, making non-trivial changes to the machine quickly became very, very slow. To say nothing of operations that involved a series of changes, with each change dependent on an accurate model of the machine having been calculated following the previous change!

After spending a few days analyzing the system, it became obvious that it cried for a thorough re-design and re-implementation of the class structure. Not only was nearly everything stored in a list of some sort (slowing iteration beyond even what a flat array would have provided), and nearly devoid of any intelligent indexing, but guessing at the cost of a routine was made frustrating by the reliance on MFC's old, non-type-safe collection classes: all objects were stored by void* or CObject*, all IDs were LONGs (or worse yet, CStrings!). Even identifying the purpose of a routine became an exercise in searching through code for the source of every parameter, then searching the rest of the code to extract the (otherwise implicit) requirements and constraints.

Unfortunately, I've nowhere near enough time to do a thorough analysis of the system as a whole, much less a re-write. One month is barely enough time to properly document such a system, and I knew the more changes I made to it, the less likely they would be properly tested before release. And this was hardly the only urgent project on my plate.

And this is where templates and the STL really come into their own. One piece at a time, I took the slowest routines, identified a better (usually non-iterative!) algorithm, and re-wrote just those routines. Since the new routines depended on having either an index or a fast method of filtering the rules they were driven from, I then wrote specialized containers for that data, taking into account the requirements of the newly re-designed routines that used them. LONGs became RuleID, lists of arrays became std::multimap combined with std::vector, complex filtering routines became simple look-ups on containers with complex keys. Finally, I wrote adapters for the new types that would allow them to be used with the old, un-changed routines: ID types converted to / from LONGs / CStrings as necessary, routines were provided for iteration / serialization / etc. In this way, one set of routines could be re-written, profiled and regression tested, without worrying about the rest of the system.

By the time I was seeing acceptable speed, I'd modified probably 30% of the entire library, one small piece at a time. And a good number of those changes were things like making parameters or access methods const, just so I could have a better idea of where things were actually being modified.

It's hard to be proud of work like this. The library is still a mess. In some ways, it's a bigger mess than it was before, since now there's a mix of new, type-safe, near-orthogonal code, in with the old; it's harder to know what to expect. If given the chance, I'd spend a lot more time cleaning things up... but for now, I've accomplished my primary goal in time for release. Proud? No. But satisfied.