Conclusion

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.

Table 1. Comparing execution times

Version	Time (seconds)
meteor.initial	~ 60,422,400 (about 2 years)
meteor.algorithm	157
meteor.caching	25

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 be creative.
  
  
• 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.

Acknowledgments

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.