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.
Sunday, February 25. 2007
Optimization: structure and algorithm
Trackbacks
Trackback specific URI for this entry
No Trackbacks

