54 CHAPTER 3 Fifteen Implementation Principles Are we done? No, we can do better by further exploiting degrees of freedom. First, in Figure 3.5 we assumed that the free space was at the top of the CAM. But the free space could be placed anywhere. In particular, it can be placed after the length-16 prefixes. This reduces the worst-case number of memory accesses by a factor of 2 [SG01]. A more sophisticated degree of freedom is as follows. So far the specification of the CAM insertion algorithm required that "a prefix of length i must occur before a prefix of length j if i > j." Such a specification is sufficient for correctness but is not necessary. For example, 010* can occur before 111001* because there is no address that can match both prefixes! Thus a less exacting specification is "if two prefixes P and Q can match the same address, then P must come before Q in the CAM if P is longer than Q." This is used in Shah and Gupta [SG01] to further reduce the worst-case number of memory accesses for insertion for some practical databases. While the last improvement is not worth its complexity, it points to another important principle. We often divide a large problem into subproblems and hand over the subproblem for a solution based on a specification. For example, the CAM hardware designer may have handed over the update problem to a microcoder, specifying that longer prefixes be placed before shorter ones. But, as before, such a specification may not be the only way to solve the original problem. Thus changes to the specification (principle P3) can yield a more efficient solution. Of course, this requires curious and confident individuals who understand the big picture or who are brave enough to ask dangerous questions. 3.2 ALGORITHMS VERSUS ALGORITHMICS It may be possible to argue that the previous example is still essentially algorithmic and does not require system thinking. One more quick example will help clarify the difference between algorithms and algorithmics.