There are multiple ways to optimize software that is too slow or too big (uses too much memory): make individual pieces of code more efficient, speed up computation of common cases, or store results for reuse. Here I describe ways to optimize algorithms by domain-specific pattern matching for common cases. See Software Optimization by Code Rewriting for ways to speed up small sections of code and Software Optimization by Data Caching for ways to store results for reuse.
A first implementation of an algorithm is often simplified in some ways to reduce development time. For most programs, where the performance "hotspots" are not known ahead of time, this is the best strategy. "Make it right before you make it fast (or small)." Highly optimized code tends to be more complex, and increased complexity leads to a higher bug rate for two reasons: there are more lines of code, and the number of errors per line of code tends to be higher for code that is not straightforward.
Once you have working software, profiling will tell you where the program spends most of its time (or uses the most memory). This original implementation provides a reference against which you can compare the improved software for correctness and efficiency. If there are differences, you can single-step through the implementations in parallel to identify the point at which the differences begin. If a trial solution is slower or bigger, you can use this information to refine your understanding of the software.
Common Cases in Plane Geometry
In many problem domains, some parameter sets require fewer computations. I do a lot of work in computational plane geometry for integrated circuits, and a lot of time in these applications is spent working with straight lines and their intersections. Recall that the equation for a line in a plane is
Ax + By = C
Given an x (y) coordinate on the line, the corresponding y (x) coordinate can be computed as:
y = (C - Ax) / B
x = (C - By) / A
The intersection between two lines A1x1 + B1y1 = C1 and A2x2 + B2y2 = C2 can be computed by substituting using the above calculations and equating the results:
y1 = (C1 - A1x1) / B1
y2 = (C2 - A2x2) / B2
(C1 - A1x1) / B1 = (C2 - A2x2) / B2
If x1 == x2, we get
(C1 - A1x) / B1 = (C2 - A2x) / B2
x = (C1B2 - C2B1) / (A1B2 - A2B1)
Even if A1, B1, C1, A2, B2, and C2 are all integers, this involves a floating point division, which is expensive. Not only that, but the slope of a vertical line is infinite, so some special case handling is necessary anyway.
In computer graphics and integrated circuit design, lines often have a slope of +1 or -1 (45 degrees up or down). Here the y coordinate changes by one unit up or down for every unit that the x coordinate changes. We can take advantage of this to convert the floating point division to an integer addition or subtraction.
Similar logic applies when one of the two lines is vertical or horizontal: the x or y coordinate of the intersection is fixed, so only the second coordinate must be computed using the slope of the non-orthogonal line (which is often stored anyway, since it is used so often).
Finally, no calculations are needed if both lines are orthogonal; the appropriate x or y coordinate can simply be used directly.
Thus considerable computational cost can be avoided by considering all of the special cases for lines in the problem domain. More lines of code are required, and the instructions necessary to select the additional special cases have some cost, but on low-power hardware these optimizations are always worthwhile, and they usually provide some savings even on workstation-class machines.
Finding Common Patterns in Your Code
The optimizations for computational geometry are well-known, and someone writing plane geometry code now would probably implement the speedups from the start. If your problem domain is new or less well-defined, you will have to develop your own patterns.
For me, pattern matching has been of most benefit when I am trying to reduce runtime, so most of this discussion will focus there. Similar logic will apply when you have