All our effort to improve the implementation of our puzzle-solving program certainly paid off. Table 1 summarizes the different versions we created and their execution times. The overall result is an amazing estimated 2,000,000-fold speedup.
|meteor.initial||~ 60,422,400 (about 2 years)|
However impressive this optimization might be, the important question is what can we learn from this experiment? The different optimization techniques we used each have their benefits and drawbacks. Combining them into a single optimization process clarifies their use and prevents out-of-order application:
- High-level optimization techniques, like the algorithm improvements
we used, have great potential. If you need to optimize a
performance-critical piece of code, first try to analyse the process
this code implements. Visualizing the process is an excellent way to
gain a better understanding of it. Also try to tackle the problem from
different angles. You might come up with a vastly better solution than
the one you originally invented. An obvious difficulty with this kind
of optimization is that it's hard to generalize. Every algorithm is
specific to a particular application domain and as such there are few
general guidelines that can be provided. It's up to the programmer to
- Once you're sure you have a good working solution in place, it's time to apply technical performance improvement techniques. The basic idea is to exchange time complexity for data complexity.
Object caches are one of the most typical of such techniques. In Java
programs, object caches are particularly useful because they help you
avoid expensive object creation and garbage collection overhead.
Remember, this kind of system adds extra infrastructure code to your
programs, so don't introduce it too early. The more complex your code
is, the harder it is to optimize.
- Finally, we can apply a range of low-level programming optimizations. Most Java programmers are familiar with these kinds of techniques. However, their benefit is limited in most real-world programs. Apply them where possible, but don't focus all your optimization effort on these kinds of idioms. Rather, they should be part of your programming toolset to help you avoid well-known performance traps.
The spectacular performance increases we achieved by combining different optimization techniques in our puzzle-solving program should motivate all Java programmers to take a look at their own code and see how it could be optimized.
The authors would like to acknowledge the assistance of Bieke Meeussen
in reviewing this document for publication. We would also like to
acknowledge the contributions of Pieter Bekaert and Kris Cardinaels.
Pieter came up with the fill-up puzzle-solving algorithm and Kris
developed parts of the puzzle visualisation code.