Developer Forums | About Us | Site Map


Useful Lists

Web Host
site hosted by netplex

Online Manuals

Optimize your Java applications performance
By Erwin Vervaet & Maarten De Cock - 2003-12-15 Page:  1 2 3 4 5 6 7 8 9 10 11

Caching Intermediate Results

The redesign of our puzzle-solving algorithm dramatically improved the execution speed of our program. For further optimizations, we'll have to look at technical performance techniques. An important issue to consider in Java programs is garbage collection. You can show the activity of the garbage collector during program execution by using the -verbose:gc command line switch.

java -verbose:gc meteor.algorithm.Solver

If we run our program with this switch, we see a lot of output from the garbage collector. Studying the source code tells us that the problem is the instantiation of a temporary ArrayList object in the placePiece() method of the Board class (see Listing 6). We use this ArrayList object to hold the board cells that a particular permutation of a piece would occupy. Instead of recalculating this list every time, it would be better to cache the results for later reference.

The findOccupiedBoardCells() method determines the cells of the puzzle board that would be occupied by a puzzle piece if a certain cell of that piece is placed on a certain board position. The results of the method are determined by three parameters: first we have the puzzle piece, or a permutation thereof; second we have the cell of the piece that we're using to manipulate the piece; and finally we have the cell of the board we'll put the piece on. To cache these results, we can associate a table with every possible piece permutation. This table holds the results of the findOccupiedBoardCells() method for that permutation using a specified piece cell index and board cell position. Listing 10 shows an updated version of the Piece class that maintains such a table:

Listing 10. Caching the results of the findOccupiedBoardCells() method

public class Piece {
  private Piece[] permutations = new Piece[NUMBEROFPERMUTATIONS];
  private ArrayList[][] occupiedBoardCells =
    new ArrayList[Piece.NUMBEROFCELLS][Board.NUMBEROFCELLS];

  private void generatePermutations(Board board) {
    Piece prevPermutation=this;
    for (int i = 0; i < NUMBEROFPERMUTATIONS; i++) {
      // The original nextPermutation() has been renamed


    // Calculate occupied board cells for every permutation
    for (int i = 0; i < NUMBEROFPERMUTATIONS; i++) {

  private void generateOccupiedBoardCells(Board board) {
    for (int i = 0; i < Piece.NUMBEROFCELLS; i++) {
      for (int j = 0; j < Board.NUMBEROFCELLS; j++) {
        occupiedBoardCells[i][j]=new ArrayList();
        resetProcessed(); // We're going to process the piece

  public Piece nextPermutation() {
    if (currentPermutation == NUMBEROFPERMUTATIONS)
      currentPermutation = 0;

    // The new implementation of nextPermutation() 
    // accesses the cache

    return permutations[currentPermutation++];

  public ArrayList 
    getOccupiedBoardCells(int pieceCellIdx, int boardCellIdx) {
    // Access requested data in cache
    return occupiedBoardCells[pieceCellIdx][boardCellIdx];

The generatePermutations() method is triggered when a Piece object is created. It calculates every permutation of the piece and caches all possible results of the findOccupiedBoardCells() method for those permutations. It is clear that we'll need access to the puzzle board if we want to calculate the occupied board cells. Also note that the permutations of a piece are clones of the original Piece object. Cloning a Piece involves a deep copy of all of its cells.

The only thing left to do is to access the cache from the placePiece() method of the Board class, which is shown in Listing 11:

Listing 11. Accessing the occupied-board-cells cache

public class Board {
  public boolean 
    placePiece(Piece piece, int pieceCellIdx, int boardCellIdx) {
    // Get all the boardCells that this piece would occupy
    ArrayList occupiedBoardCells =
      piece.getOccupiedBoardCells(pieceCellIdx, boardCellIdx);

Running the program once more

The source code of this updated version of our puzzle-solving program can be found in the meteor.caching package. Running java meteor.caching.Solver shows us that we again improved the performance considerably. On our test machine all solutions are found in 25 seconds. Caching resulted in a six-fold speedup. If we use the -verbose:gc switch, we also see that garbage collection is no longer an issue.

The extra code we introduced to implement the cache obviously complicates the program. This is a typical downside of performance techniques that try to reduce computation time by storing intermediate results. However, in this case the performance gain seems to outweigh the added code complexity.

View Optimize your Java applications performance Discussion

Page:  1 2 3 4 5 6 7 8 9 10 11 Next Page: Programming Optimizations

First published by IBM developerWorks

Copyright 2004-2021 All rights reserved.
Article copyright and all rights retained by the author.