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]