Pattern Patter
| Quick-and-Dirty Check |
April, 1998 |
| Make expensive operations cheaper using a
quick-and-dirty check. [Low-level Design Pattern] |
Context
Performance is important.
Forces
- You have a time-consuming operation.
- If only ..., the operations wouldn't be so expensive.
Resolution
Develop two versions of the operation: one that handles all
complications, and another that deals with a common simple case.
Devise a quick-and-dirty check that can tell which version to use.
Discussion
We want our operation to be less expensive. If a quick check lets
us use a cheaper version of the operation often enough, we'll speed
things up.
We want to take advantage of Pareto's Law, the 80-20 rule. (80%
of the cost comes from 20% of the cases.) Instead of 100 expensive
operations, we might be able to use 100 checks + 80 cheap
operations + 20 expensive operations.
Note that the checks must be included in the cost. There is a
check for each operation, cheap or expensive. (This is why the
checks must be quick: if the check plus the cheap operation costs
more than the expensive operation did, we'll always be worse off.)
The relative cost of the check must be balanced against the
relative frequency of the expensive operation.
Examples
- Bounding box for graphic objects. Suppose we have sprites on a
playfield. We'd like to know if any sprites collide. Sprites can
have arbitrary shapes, though, so it's a fair amount of work to
check. Instead, a quick test can be made of their bounding boxes
(the smallest rectangle that contains them). If the bounding boxes
don't intersect, there's no need for the expensive test.
- Class type match test in Smalltalk. In some OO language
implementations, the cost of a virtual function call includes a
search of some sort to locate the proper method. (If the type were
static, the lookup would be unnecessary.) Some implementations use
the fact that most call sites tend to see the same types again and
again. They will "plug in" the fixed call that would be used if the
type were constant, but first they'll do a check to see if the type
is in fact the same. If so, the previously plugged in values will
be used. If not, the type must be fully looked up and different
calls used.
- Spin-lock for multi-CPU threads. In a threaded system, you may
want to acquire a lock. If you sit in a spin loop, you will
eventually get it, but you've wasted CU time waiting for it. But,
being put on a waiting queue may force you to do an expensive
context switch. A quick and dirty check might spin for a few cycles
in hopes of finding the lock available cheaply, but if not
available then go on the queue.
Related Patterns
- Polya's Rule attempts to go in the opposite direction: to find
a better solution to a more general problem.
- A rule of optimization says that you can either call cheaper
operations or call them less frequently. This pattern tries to call
a cheaper operation, but it might pay more to call things less
frequently in the first place.
[Written 4-10-98]
|