IBM Korea Skip to main content
       IBM 홈    |  제품 & 서비스  |  고객지원 & 다운로드  |  회원가입  

자바 최적화 기술
목 차:
실행 솔루션
알고리즘 개선
중간 결과 캐싱하기
프로그래밍 최적화
결론
참고자료
필자소개
기사에 대한 평가
관련 dW 링크:
Merlin brings nonblocking I/O to the Java platform
Improve the performance of your Java code
Subscribe to the developerWorks newsletter
US 원문 읽기
Also in the Java zone:
Tutorials
Tools and products
Code and components
Articles
자바 애플리케이션의 퍼포먼스 향상을 위한 실질 가이드

Erwin Vervaet, 소프트웨어 엔지니어, Ervacon
Maarten De Cock, 애플리케이션 엔지니어, ASQdotCOM

2002년 6월

자바 프로그램을 최적화 할 수 있는 유용한 기술들이 많이 있다. 이 글에서는 특정 기술 하나에 포커스를 맞추는 것 대신 최적화 프로세스를 전체적으로 다룬다. 간단한 기술 팁에서부터 고급 알고리즘 최적화까지 다양한 기술들을 세분화하여 문제 해결 프로그램의 퍼포먼스 튜닝을 한다.

대부분의 자바 퍼포먼스 관련 글들은 프로그래머들이 프로그램 속도를 향상시키는데 적용할 수 있는 기술에 초점을 맞추고 있다. 이 글에서는 StringBuffer 클래스 같은 간단한 프로그래밍 이디엄을 비롯하여, 객체 캐시(object caches)의 사용 같은 고급 기술을 설명하겠다.

우리가 개발하고 최적화 할 프로그램은 Meteor 퍼즐에 대한 모든 가능한 솔루션을 계산할 것이다. Meteor 퍼즐은 10개의 퍼즐 조각과 5개의 육각형으로 구성된 다른 색상들로 이루어져 있다 (각 변의 길이가 같은 육면의 다각형이다). 퍼즐 보드 자체는 가로 5 x 세로 10 패턴으로 레이아웃은 50개의 육각형을 모아 직사각형 형태가 된다. 10개의 조각을 사용하여 전체 보드를 채워서 퍼즐을 풀 수 있다. 이 퍼즐에 대한 솔루션은 그림 1이 된다.

Eternity 퍼즐
이 글에 소개된 자바 프로그램이 10 조각의 Meteor 퍼즐을 푸는 것이라면 진짜 목표는 훨씬 큰 209 조각의 퍼즐을 푸는 것이였다. 이것은 Christopher Monckton이 고안한 것으로 1999년 6월에 영국에서 소개되었다. 퍼즐 이름은 Eternity 퍼즐이다. Eternity 퍼즐이 발표됨과 동시에 Monckton은 다양한 작은 퍼즐들을 발표하기 시작했다. Meteor, Delta, Heart 등이 그것이다. 1백오십만 달러 상당의 상금이 이 퍼즐을 푸는 사람에게 제공되었다. 2000년 5월 15일에 Alex Selby와 Oliver Riordan에게 돌아갔다. 두 번째 솔루션은 나중에 Guenter Stertenbrink가 발견했다. 재밌게도 이 솔루션 중 어떤것도 Christopher가 미리 만들어둔 6개의 단서와 맞지 않았다. 이는 아직도 알려지지 않고 있다.

그림 1. Meteor 퍼즐 풀이


풀이가 아주 간단해보이는 만큼 컴퓨터 프로그램의 구현에 있어 중요한 문제이다. 이 프로그램을 작성하는 것은 많은 다른 자바 퍼포먼스 관련 아티클에서 찾을 수 있는 예제와는 다른 것을 제공한다. 이것은 많은 최적화 기술을 나타낼 수 있고 그들을 조합하는 방법을 나타낼 수 있다. 최적화 작업을 시작하기 전에 실행 솔루션을 개발해야 한다.

실행 솔루션
이 섹션에서는 퍼즐 풀이 프로그램의 초기 구현에 대해 이야기할 것이다. 여기에는 상당히 많은 코드 조각들이 포함되어 있다. 따라서 인내심을 가져야한다. 일단 기본 알고리즘을 설명하고 나서 최적화를 시작한다. 이 초기 구현에 쓰인 소스코드 뿐만아니라 최적화 소스코드는 참고자료에서 이용할 수 있다.

퍼즐 풀이 알고리즘
이 퍼즐 풀이 프로그램은 Meteor 퍼즐에 대해 모든 가능한 솔루션을 계산한다. 이는 조각들을 사용하여 보드를 채울 수 있는 모든 가능한 방법을 샅샅이 찾아야 함을 의미한다. 이러한 작업의 첫 번째 단계는 조각에 대해 모든 순열을 결정하는 것이다. 순열은 보드에 조각들을 위치시키는 방법이다. 모든 조각이 앞뒤로 뒤집어질 수 있고 여섯 개의 변 중 하나가 다른 여섯개의 변 주위로 회전될 수 있다는 것을 안다면 보드의 한 위치에 조각을 넣을 수 있는 총 12가지의 가능한 방법이 있다는 것에 도달한다. 보드의 50개의 위치가 있으므로 하나의 조각을 보드에 넣을 모든 가능한 방법은 600 (2 x 6 x 50)가지 이다.

물론 이 모든 가능성들이 실제로 작동하는 것은 아니다. 모든 조각들에 대해 이러한 프로세스를 반복하면 조각을 사용하여 가능한 모든 채우기를 시도함으로서 모든 가능한 솔루션을 찾을 첫 번째 알고리즘에 이른다. Listing 1은 이 알고리즘 코드이다. pieceList라고 불리는 간단한 ArrayList를 사용하여 모든 조각들을 보유할 수 있다. board 객체는 퍼즐 보드를 나타낸다.

Listing 1. 초기의 퍼즐 풀이 알고리즘

public void solve() {
  if (!pieceList.isEmpty()) {
    // Take the first available piece
    Piece currentPiece = (Piece)pieceList.remove(0);

    for (int i = 0; i < Piece.NUMBEROFPERMUTATIONS; i++) {
      Piece permutation = currentPiece.nextPermutation();

      for (int j = 0; j < Board.NUMBEROFCELLS; j++) {
        if (board.placePiece(permutation, j)) {
          
          /* We have now put a piece on the board, so we have to
             continue this process with the next piece by 
             recursively calling the solve() method */
          
          solve();
          
          /* We're back from the recursion and we have to continue
             searching at this level, so we remove the piece we
             just added from the board */
          
          board.removePiece(permutation);
        }
        // Else the permutation doesn't fit on the board
      }
    }

    // We're done with this piece
    pieceList.add(0, currentPiece);
  }
  else {
    
    /* All pieces have been placed on the board so we
       have found a solution! */
    
    puzzleSolved();
  }
}

기본 알고리즘을 설정했으니 두 가지 다른 중요한 문제들을 연구해야 한다:

  • 한 조각의 퍼즐을 어떻게 나타낼 것인가?
  • 퍼즐 보드를 어떻게 구현할 것인가?

Listing 1에 나와있는 알고리즘에서 Piece 클래스와 Board 클래스를 사용했다. 두 가지 클래스의 구현에 대해 알아보자.

Piece 클래스
Piece 클래스를 설계하기 전에, 이 클래스가 무엇을 나태낼것인지를 생각해야 한다. 그림 2를 보면, Meteor 퍼즐 조각이 다섯개의 셀로 연결되어 있다는 것을 알 수 있다. 각 셀은 6 변(side)을 가진 정육각형이다: EAST, SOUTHEAST, SOUTHWEST, WEST, NORTHWEST, NORTHEAST. 한 조 각의 두 셀이 특정한 변에서 만날 때 우리는 이러한 셀들을 이웃(neighbour)이라고 부른다. 결국, Piece 객체는 단지 다섯 개의 연결된 Cell 객체에 지나지 않는다. 각 Cell 객체는 여섯 개의 변과 여섯 개의 가능한 이웃 셀들을 가지고 있다. Cell 클래스 구현은 단순하다 (Listing 2). Cell 객체에서 processed 플래그를 관리한다는 것을 주목하라. 나중에 무한 루프를 피하기 위해 이 플래그를 사용할 것이다.

그림 2. 퍼즐 조각과 셀

Listing 2. Cell 클래스

public class Cell {
  public static final int NUMBEROFSIDES = 6;

  // The sides of a cell
  public static final int EAST      = 0;
  public static final int SOUTHEAST = 1;
  public static final int SOUTHWEST = 2;
  public static final int WEST      = 3;
  public static final int NORTHWEST = 4;
  public static final int NORTHEAST = 5;

  private Cell[] neighbours = new Cell[NUMBEROFSIDES];

  private boolean processed = false;

  public Cell getNeighbour(int side) {
    return neighbours[side];
  }

  public void setNeighbour(int side, Cell cell) {
    neighbours[side] = cell;
  }

  public boolean isProcessed() {
    return processed;
  }

  public void setProcessed(boolean b) {
    processed = b;
  }
}

Piece 클래스는 조금 더 재미있다. Piece의 순열을 계산하기 위해서는 메소드가 필요하기 때문이다. 셀의 여섯 변 주위에서 조각을 회전시키고, 이를 앞뒤로 뒤집으며 마지막으로 셀의 여섯 변 중 한 변 주위에 이를 다시 회전시키면서 모든 순열들을 찾을 수 있다. 앞서 언급했듯이, 조각은 다 섯 개의 인접 셀들로 구성되어 있다. 조각을 뒤집거나 회전시키는 것은 이것의 모든 셀들을 뒤집거나 회전시키는 것이다. 따라서 Cell 객체를 위해 flip()rotate() 메소드가 필요하다. 뒤집기와 회전 모두 이웃하는 변을 변화시킴으로서 쉽게 수행할 수 있다. 이러한 메소드들은 Cell 클래스의 PieceCell 하위 클래스에서 제공된다. (Listing 3). PieceCell 객체는 Piece 객체에서 사용되는 셀이다.

Listing 3. PieceCell 하위클래스

public class PieceCell extends Cell {
  public void flip() {
    Cell buffer = getNeighbour(NORTHEAST);
    setNeighbour(NORTHEAST, getNeighbour(NORTHWEST));
    setNeighbour(NORTHWEST, buffer);
    buffer = getNeighbour(EAST);
    setNeighbour(EAST, getNeighbour(WEST));
    setNeighbour(WEST, buffer);
    buffer = getNeighbour(SOUTHEAST);
    setNeighbour(SOUTHEAST, getNeighbour(SOUTHWEST));
    setNeighbour(SOUTHWEST, buffer);
  }

  public void rotate() {
    // Clockwise rotation
    Cell eastNeighbour = getNeighbour(EAST);
    setNeighbour(EAST, getNeighbour(NORTHEAST));
    setNeighbour(NORTHEAST, getNeighbour(NORTHWEST));
    setNeighbour(NORTHWEST, getNeighbour(WEST));
    setNeighbour(WEST, getNeighbour(SOUTHWEST));
    setNeighbour(SOUTHWEST, getNeighbour(SOUTHEAST));
    setNeighbour(SOUTHEAST, eastNeighbour);
  }
}

PieceCell 클래스를 사용하여, Piece 클래스 구현을 완성할 수 있다. Listing 4는 소스 코드이다:

Listing 4. Piece 클래스

public class Piece {
  public static final int NUMBEROFCELLS = 5;
  public static final int NUMBEROFPERMUTATIONS = 12;

  private PieceCell[] pieceCells = new PieceCell[NUMBEROFCELLS];
  private int currentPermutation = 0;

  private void rotatePiece() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      pieceCells[i].rotate();
    }
  }

  private void flipPiece() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      pieceCells[i].flip();
    }
  }

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

    switch (currentPermutation%6) {
      case 0:
        // Flip after every 6 rotations
        flipPiece();
        break;

      default:
        rotatePiece();
        break;
    }

    currentPermutation++;

    return this;
  }

  public void resetProcessed() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      pieceCells[i].setProcessed(false);
    }
  }

  //Getters and setters have been omitted
}

Board 클래스
Board 클래스를 구현하기 전에, 두 가지 재미있는 문제를 짚고 넘어가자. 우선, 데이터 구조에 대해 결정해야 한다. Meteor 퍼즐 보드는 기본적으로 정육각의 5x10 그리드이다. 50 Cell 객체 어레이로서 표현할 수 있다. Cell 클래스를 직접 사용하는 대신 BoardCell 하위클래스를 사용할 것이다.(Listing 5). 셀을 차지하고 있는 조각을 트래킹할 수 있다:

Listing 5. BoardCell 하위클래스

public class BoardCell extends Cell {
  private Piece piece = null;

  public Piece getPiece() {
    return piece;
  }

  public void setPiece(Piece piece) {
    this.piece = piece;
  }
}

한 어레이에 50개의 모든 보드 셀을 저장하려면 약간 장황한 초기화 코드를 작성해야 한다. 초기화는 보드의 각 셀에 대한 인접 보드 셀을 구분하는 것이다. (그림 3). cell 0은 두개의 이웃을 갖고 있다: 동쪽의 cell 1과 남동쪽의 cell 5. Listing 6initializeBoardCell()메소드로서 Board 클래스의 생성자에서 호출되어 초기화를 수행한다.

그림 3. 셀 어레이로 표현된 보드

보드용 데이터 구조를 구현했다면 다음 문제로 옮겨가보자: 보드에 조각을 놓는 메소드인 placePiece()를 작성하는 것이다. 이 메소드를 작성하는 데 있어 가장 어려운 부분은 조각이 기존 위치에서 보드와 맞는지의 여부를 결정하는 것이다. 조각이 맞는지 여부를 결정하는 한 가지 방법은 그것이 보드에 놓여져 있다면 조각의 셀에 의해 점유된 모든 보드 셀을 찾는 것이다. 이러한 보드 셀들을 갖는다면 쉽게 새로운 조각이 맞는지를 쉽게 결정할 수 있다. 모든 상응하는 보드 셀들은 비워있어야 하며 조각은 보드에 완벽하게 맞아야 한다. 이 프로세스는 findOccupiedBoardCells() 메소드와 placePiece() 메소드로 구현된다. (Listing 6). PieceCell 객체의 processed 필드를 사용하여 findOccupiedBoardCells() 메소드의 무한 재귀(recursion)를 피한다는 것에 주목하자.

Listing 6. Board 클래스

public class Board {
  public static final int NUMBEROFCELLS = 50;
  public static final int NUMBEROFCELLSINROW = 5;

  private BoardCell[] boardCells = new BoardCell[NUMBEROFCELLS];

  public Board() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      boardCells[i] = new BoardCell();
    }

    for (int i = 0; i < NUMBEROFCELLS; i++) {
      initializeBoardCell(boardCells[i], i);
    }
  }

  /**
   * Initialize the neighbours of the given boardCell at the given
   * index on the board
   */
  private void initializeBoardCell(BoardCell boardCell, int index) {
    int row = index/NUMBEROFCELLSINROW;

    // Check if cell is in last or first column
    boolean isFirst = (index%NUMBEROFCELLSINROW == 0);
    boolean isLast = ((index+1)%NUMBEROFCELLSINROW == 0);

    if (row%2 == 0) { // Even rows
      if (row != 0) {
        // Northern neighbours
        if (!isFirst) {
          boardCell.setNeighbour(Cell.NORTHWEST, boardCells[index-6]);
        }
        boardCell.setNeighbour(Cell.NORTHEAST, boardCells[index-5]);
      }
      if (row != ((NUMBEROFCELLS/NUMBEROFCELLSINROW)-1)) {
        // Southern neighbours
        if (!isFirst) {
          boardCell.setNeighbour(Cell.SOUTHWEST, boardCells[index+4]);
        }
        boardCell.setNeighbour(Cell.SOUTHEAST, boardCells[index+5]);
      }
    }
    else { // Uneven rows
      // Northern neighbours
      if (!isLast) {
        boardCell.setNeighbour(Cell.NORTHEAST, boardCells[index-4]);
      }
      boardCell.setNeighbour(Cell.NORTHWEST, boardCells[index-5]);
      // Southern neighbours
      if (row != ((NUMBEROFCELLS/NUMBEROFCELLSINROW)-1)) {
        if (!isLast) {
          boardCell.setNeighbour(Cell.SOUTHEAST, boardCells[index+6]);
        }
        boardCell.setNeighbour(Cell.SOUTHWEST, boardCells[index+5]);
      }
    }

    // Set the east and west neighbours
    if (!isFirst) {
      boardCell.setNeighbour(Cell.WEST, boardCells[index-1]);
    }
    if (!isLast) {
      boardCell.setNeighbour(Cell.EAST, boardCells[index+1]);
    }
  }

  public void findOccupiedBoardCells(
    ArrayList occupiedCells, PieceCell pieceCell, BoardCell boardCell) {
    if (pieceCell != null && boardCell != null && !pieceCell.isProcessed()) {
      occupiedCells.add(boardCell);
      
      /* Neighbouring cells can form loops, which would lead to an
         infinite recursion. Avoid this by marking the processed 
         cells. */
      
      pieceCell.setProcessed(true);

      // Repeat for each neighbour of the piece cell
      for (int i = 0; i < Cell.NUMBEROFSIDES; i++) {
        findOccupiedBoardCells(occupiedCells,
                               (PieceCell)pieceCell.getNeighbour(i),
                               (BoardCell)boardCell.getNeighbour(i));
      }
    }
  }

  public boolean placePiece(Piece piece, int boardCellIdx) {
    // We will manipulate the piece using its first cell
    return placePiece(piece, 0, boardCellIdx);
  }

  public boolean 
    placePiece(Piece piece, int pieceCellIdx, int boardCellIdx) {
    // We're going to process the piece
    piece.resetProcessed();

    // Get all the boardCells that this piece would occupy
    ArrayList occupiedBoardCells = new ArrayList();
    findOccupiedBoardCells(occupiedBoardCells,
                           piece.getPieceCell(pieceCellIdx),
                           boardCells[boardCellIdx]);

    if (occupiedBoardCells.size() != Piece.NUMBEROFCELLS) {
      // Some cells of the piece don't fall on the board
      return false;
    }

    for (int i = 0; i < occupiedBoardCells.size(); i++) {
      if (((BoardCell)occupiedBoardCells.get(i)).getPiece() != null)
        // The board cell is already occupied by another piece
        return false;
    }

    // Occupy the board cells with the piece
    for (int i = 0; i < occupiedBoardCells.size(); i++) {
      ((BoardCell)occupiedBoardCells.get(i)).setPiece(piece);
    }

    return true; // The piece fits on the board
  }

  public void removePiece(Piece piece) {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      // Piece objects are unique, so use reference equality
      if (boardCells[i].getPiece() == piece) {
        boardCells[i].setPiece(null);
      }
    }
  }
}

이것으로 첫 번째 솔루션 구현이 완성되었다. 이제 테스트 해보자.

프로그램 실행하기
첫 번째 퍼즐 해결 프로그램을 끝마쳤으니 Meteor 퍼즐에 대한 모든 가능한 솔루션을 찾을 수 있다. 이전 섹션에서 설명한 소스 코드는 소스 다운로드의 meteor.initial 패키지에 있다. 이 패키지는 프로그램을 시작하는 solve() 메소드와 main() 메소드가 있는 Solver 클래스를 포함하고 있다. Solver 클래스의 생성자는 모든 퍼즐 조각들을 초기화하고 그들을 pieceList에 추가한다. java meteor.initial.Solver를 사용하여 프로그램을 시작할 수 있다.

이 프로그램은 솔루션을 찾기 시작한다. 하지만 여러분도 보듯이 아무것도 못 찾는다. 실제로 이것은 모든 가능한 솔루션을 찾기는 하지만 대신 인내심을 가져야한다. 단 하나의 솔루션을 찾는데 많은 시간이 걸린다. 우리의 테스트 컴퓨터인 RedHat Linux 7.2와 Java 1.4.0을 구동하는 Athlon XP 1500+(512MB RAM)는 8 시간 후에 첫 번째 솔루션을 찾았다. 모든 솔루션을 찾으려면 수 개월이 걸릴지도 모른다.

분명히 퍼포먼스 문제가 있다. 최적화를 위한 첫 번째 후보는 퍼즐 풀이 알고리즘이다. 우리는 현재 모든 가능한 솔루션을 찾는데 순진하고 무식한 접근방식을 사용하고 있다. 이 알고리즘을 튜닝해야 한다. 우리가 할 수 있는 두 번째 일은 임시 데이터를 캐싱하는 것이다. 예를 들어 매번 조각의 순열을 재계산 하는 대신에 그러한 순열을 캐싱하는 것이다. 마지막으로 몇 가지 저수준 최적화 기술, 예를들어 불필요한 메소드 호출을 피하는 식의 저수준 기술을 적용하는 것이다. 다음 섹션에서 저 수준 최적화 기술을 연구하겠다.

알고리즘 향상시키기
Listing 1을 다시 보면서 처음의 퍼즐 풀이 알고리즘을 어떻게 최적화할 수 있는지를 생각해보자. 알고리즘을 최적화하는 좋은 방법은 이를 시각화하는 것이다. 시각화는 구현되고있는 프로세스의 이해를 돕는다. 다음 섹션에서는 두 가지 비효율성에 대해 이야기하겠다.

섬 탐지(Island detection) pruning
Listing 1의 알고리즘은 조각을 보드의 모든 위치에 맞춘다. 그림 4는 프로세스의 처음에 있는 가능한 보드 상황을 보여준다. 푸른 조각의 현재 순열은 첫 번째 가능한 보드에 있고 노란색 조각의 현재 순열은 두 번째 가능한 보드 위치로 이동했다. 그런다음 세 번째 조각으로 이어진다. 하지만 그림 4를 자세히 보면 이러한 위치에서는 푸른색과 노란색을 가진 퍼즐에는 가능한 솔루션이 없다는 것이 명백해진다. 이유는 그러한 두 조각은 이웃하는 빈 셀의 섬(island)을 형성했기 때문이다. 모든 퍼즐 조각은 다섯개의 셀로 구성되어있기 때문에 이러한 섬을 채울 방법이 없다. 보드에 남아있는 여덟개의 조각들을 맞추려는 모든 노력은 무의미하다. 필요한 것은 채워질 수 없는 보드에서 섬을 발견했다면 알고리즘을 끝내는 것이다.

그림4. 보드의 섬(island)

여기에서 재귀 검색 알고리즘을 막는 이러한 프로세스를 pruning이라고 하겠다. pruning 함수를 Solver 클래스에 추가하는 것은 쉽다. solve() 메소드에 모든 재귀 호출을 하기 전에 보드 상의 섬을 점검한다. 5의 배수가 아닌 많은 빈 셀들로 구성되어있는 섬이 있다면 재귀 호출을 하지 않는다. 대신 알고리즘은 현재 레벨의 재귀로 계속된다. Listing 7과 8은 필수적인 코드 조정을 보여주고 있다:

Listing 7. pruning을 이용한 퍼즐 풀이 알고리즘

public class Solver {
  public void solve() {
    ...
            if (!prune()) solve();
    ...
  }

  private boolean prune() {
    /* We'll use the processed field of board cells to avoid 
    infinite loops */
    board.resetProcessed();

    for (int i = 0; i < Board.NUMBEROFCELLS; i++) {
      if (board.getBoardCell(i).getIslandSize()%Piece.NUMBEROFCELLS != 0) {
        // We have found an unsolvable island
        return true;
      }
    }

    return false;
  }
}

Listing 8. getIslandSize() 메소드

public class BoardCell {
  public int getIslandSize() {
    if (!isProcessed() && isEmpty()) {
      setProcessed(true); // Avoid infinite recursion
      int numberOfCellsInIsland = 1; // this cell 

      for (int i = 0; i < Cell.NUMBEROFSIDES; i++) {
        BoardCell neighbour=(BoardCell)getNeighbour(i);
        if (neighbour != null) {
          numberOfCellsInIsland += neighbour.getIslandSize();
        }
      }
      return numberOfCellsInIsland;
    }
    else {
      return 0;
    }
  }
}

채우기(fill-up) 알고리즘
처음 알고리즘의 두 번째 단점은 이것이 기본적으로 많은 섬들을 만들어낸다는 것이다. 이것은 우리가 한 조각에서 하나의 순열을 취해 그 조각의 다음 순열로 변환하기 전에 보드로 이동시키기 때문이다. 예를 들어, 그림 5에서 푸른 조각의 현재 순열을 세 번째 가능한 보드 위치로 이동시켰다. 보다시피 이것은 보드의 상단에 섬을 만들어낸다. 이전 섹션에서 추가한 아일랜드 탐지 pruning이 우리가 만들어낸 많은 섬들 때문에 놀라운 퍼포먼스 향상을 가져오지만 첫 번째 장소에서 만든 섬의 수를 최소화하는 알고리즘을 업데이트 할 수 있다면 좋을 것이다.

그림 5. 섬 만들기

우리가 만든 섬의 수를 줄이기위해서 알고리즘이 비어있는 보드 위치에 집중되어있다면 최상이다. 따라서 보드를 채우기 위해 모든 가능한 방법을 시도하는 대신 보드를 왼쪽에서 오른쪽으로 위에서 아래로 채워간다. 이 새로운 퍼즐 풀이 알고리즘은 Listing 9에 나타나있다:

Listing 9. 채우기 방식의 퍼즐 풀이 알고리즘

public void solve() {
  if (!pieceList.isEmpty()) {
    // We'll try to find a piece that fits on this board cell
    int emptyBoardCellIdx = board.getFirstEmptyBoardCellIndex();

    // Try all available pieces
    for (int h = 0; h < pieceList.size(); h++) {
      Piece currentPiece = (Piece)pieceList.remove(h);

      for (int i = 0; i < Piece.NUMBEROFPERMUTATIONS; i++) {
        Piece permutation = currentPiece.nextPermutation();
        
        /* Instead of always using the first cell to manipulate
           the piece, we now try to fit any cell of the piece on 
           the first empty board cell */
        
        for (int j = 0; j < Piece.NUMBEROFCELLS; j++) {
          if (board.placePiece(permutation, j, emptyBoardCellIdx)) {
            if (!prune()) solve();
            board.removePiece(permutation);
          }
        }
      }

      
      /* Put the piece back into the list at the position where
         we took it to maintain the order of the list */
      
      pieceList.add(h, currentPiece);
    }
  }
  else {
    puzzleSolved();
  }
}

우리의 새로운 접근 방식은 모든 가능한 조각을 첫 번째 빈 보드 셀에 맞추기 위함이다. 이용할 수 있는 모든 조각의 모든 가능한 순열을 시도하는 것만으로는 충분하지 않다. 우리는 또한 조각의 어떤 조각 셀을 가지고 비어있는 보드 셀을 채워야한다. 첫 알고리즘에서 우리는 이 첫 번째 셀을 사용하여 조각을 조작한다고 가정했다. 이제는 그림 6 처럼 그 조각에 모든 셀을 시도해야 한다. 핑크색 조각의 현재 순열은 보드 위치 5에 인덱스 0으로 조각 셀을 놓을 때 보드에 맞지 않는다. 하지만 두 번째 조각 셀을 사용할 때 맞는다.

그림 6. 조각 셀

업데이트 프로그램 실행하기
첫 프로그램을 실행하면서 오랜 시간동안 솔루션을 찾지 못했다. 이제 향상된 알고리즘과 섬 탐지(island-detection) pruning으로 다시 시도해보자. 이 프로그램 버전 코드는 meteor.algorithm 패키지에 있다. java meteor.algorithm.Solver를 사용하면 갑자기 솔루션이 떠오르는 것을 경험하게 된다. 테스트 컴퓨터는 157초 만에 2,098개의 가능한 솔루션을 계산한다. 굉장한 퍼포먼스 향상을 이룩했다. 솔루션 당 수 시간에서 최소 0.1초로 낮아진것이다. 대략 400,000 배 빨라졌다. 섬 탐지 pruning으로 조합된 처음 알고리즘은 6,363 초 안에 완성했다. pruning 최적화는 10,000 배의 속도향상을 가져오고 채우기 알고리즘은 추가로 40배의 속도향상을 가져온다.

중간 결과 캐싱하기
퍼즐 풀이 알고리즘을 재설계 함으로서 프로그램의 실행 속도를 크게 향상시켰다. 최적화를 더욱 진행시키기 위해서 기술적 퍼포먼스 기술을 살펴보자. 자바 프로그램에서 고려해야 하는 중요한 문제는 가비지 컬렉션(garbage collection)이다. -verbose:gc 명령행 스위치를 사용하여 프로그램이 실행되는 동안 가비지 컬렉터의 작동을 보여줄 수 있다.

java -verbose:gc meteor.algorithm.Solver

이 스위치로 프로그램을 실행하면 가비지 컬렉터에서 많은 아웃풋(ourput)을 얻는다. 소스 코드를 분석해보면 문제는 Board 클래스의 placePiece() 메소드에 있는 ArrayList 리스트 임시 객체의 초기화이다. (Listing 6) 한 조각의 특정 순열이 채워질 보드 셀을 갖기위해서는 ArrayList 객체를 사용한다. 이 리스트를 매번 계산하는 대신, 다음 레퍼런스를 위해 이 결과를 캐싱하는 것이 낫다.

findOccupiedBoardCells() 메소드는 그 조각의 특정 셀이 특정 보드 위치에 놓이게되면 퍼즐 조각으로 채워진 퍼즐 보드의 셀을 결정한다. 메소드의 결과는 세 개의 매개변수에 의해 결정된다. 첫째 퍼즐 조각 또는 그것의 순열을 갖고 있다. 둘째, 조각을 조작하는데 사용하는 조각의 셀이 있다. 마지막으로 조각들을 놓을 보드의 셀을 갖고 있다. 이 결과를 캐싱하기위해서 테이블을 모든 가능한 조각 순열로 연결한다. 이 테이블은 지정된 조각 셀 인덱스와 보드 셀 위치를 사용하여 그 순열에 대한 findOccupiedBoardCells() 메소드의 결과를 갖고있다. Listing 10은 그와같은 테이블을 보유하고 있는 Piece 클래스의 업데이트 버전이다:

Listing 10. findOccupiedBoardCells() 메소드의 결과 캐싱하기

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
      permutations[i]=
        ((Piece)prevPermutation.clone()).nextPermutation_orig();
      prevPermutation=permutations[i];
    }

    // Calculate occupied board cells for every permutation
    for (int i = 0; i < NUMBEROFPERMUTATIONS; i++) {
      permutations[i].generateOccupiedBoardCells(board);
    }
  }

  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
        board.findOccupiedBoardCells(occupiedBoardCells[i][j],
                                     pieceCells[i],
                                     board.getBoardCell(j));
      }
    }
  }

  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];
  }
}

generatePermutations() 메소드는 Piece 객체가 만들어질때 작동한다. 이것은 조각의 모든 순열을 계산하고 그러한 순열에 대한 findOccupiedBoardCells() 메소드의 모든 가능한 결과를 캐싱한다. 채워진 보드 셀을 계산하기 원하면 퍼즐보드로 액세스 해야한다는 것이 명확해 졌다. 또한 한 조각의 순열은 원래 Piece 객체의 클론이라는 점을 주목하라. Piece를 복제는 이것의 셀 모두를 복사하는 과정이 포함된다.

이제 마지막으로 해야할 일은 Board 클래스의 placePiece() 메소드에서 캐시를 액세스하는 것이다. (Listing 11):

Listing 11. 채워진 보드 셀 캐시에 액세스하기

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);
    ...
  }
}

프로그램 한번 더 실행하기
퍼즐 풀이 프로그램의 업데이트 버전의 소스코드는 meteor.caching 캐싱 패키지에 있다. java meteor.caching.Solver를 실행하면 놀라운 퍼포먼스 향상을 보게된다. 테스트 머신에서도 모든 솔루션이 25초 안에 가능했다. 캐싱도 6배나 빠른 속도로 결과가 나왔다. -verbose:gc 스위치를 사용한다면 가비지 컬렉션이 더이상 문제가 아니라는 것을 알게된다.

캐시를 구현하기 위해 도입한 추가 코드는 프로그램을 복잡하게 한다. 이것은 중간 결과를 저장하여 계산 시간을 줄이려 할 때 발생하는 전형적인 단점이다. 하지만 이 경우 퍼포먼스에서 얻은 이득은 복잡성을 능가한다.

프로그래밍 최적화
퍼즐 풀이 프로그램을 위한 최적화 프로세스에서 또 하나의 가능한 방법은 저수준 자바 코드 최적화 이디엄을 사용하는 것이다. 우리는 애플리케이션에서 어떤 스트링도 조작하지 않았다. 따라서 잘 알려진 StringBuffer 이디엄을 적용하는 것은 쓸모가 없다. 직접적인 멤버 액세스로 게터(getter)와 세터(setter)를 바꿈으로서 게터와 세터에 대한 메소드 호출 오버헤드를 피할 수 있다. 하지만 이것은 코드 질을 강등시키고 테스트 결과 이는 속도향상을 전혀 가져오지 않음을 알 수 있다. final 메소드의 사용도 마찬가지이다. 메소드를 final로 선언함으로서 동적 바인딩을 피하고 자바 가상 머신이 좀더 효율적인 정적 바인딩을 사용할 수 있도록 할 수 있다. 또한 자바 컴파일러의 -0 최적화 스위치의 사용은 실제적인 퍼포먼스 증가를 가져오지 않는다.

미미한 실행 속도향상은 prune() 메소드 구현을 발전시켜서 얻어낼 수 있다. Listing 7 의 코드는 항상 재귀적인 getIslandSize() 메소드로 호출한다. 보드 셀이 이미 프로세스 되어있거나 비어있지 않을 때에도 그렇다. getIslandSize()를 호출하기 전에 적극적으로 이것을 점검한다면 10%의 향상을 기대할 수 있다.

저수준 최적화의 결과는 아주 작은 퍼포먼스 증가를 가져온다. 이러한 최적화 기술은 코드의 질을 강등시킨다는 단점도 가지고 있고 따라서 저수준의 최적화 사용은 매력적이지 않다.

결론
퍼즐 풀이 프로그램의 구현을 향상시키기 위한 모든 노력은 확실히 효과가 있었다. Table 1에는 우리가 만든 각각의 버전과 실행시간을 요약해 놓았다. 전체 결과는 2,000,000 배의 속도 향상이다.

Table 1. 실행 시간 비교
Version 시간 (초)
meteor.initial ~ 60,422,400 (약 2년)
meteor.algorithm 157
meteor.caching 25

하지만 이 최적화가 아무리 놀라워도 이 실험에서 우리가 배울 수 있는 것이 무엇인가 라는 중요한 질문이 남아있다. 우리가 사용했던 다양한 최적화 기술은 각각 장점과 단점을 갖고있다. 그들을 조합하여 하나의 최적화 프로세스로 만드는 것은 사용법을 명확히 하고 애플리케이션의 구식화를 방지한다.

  • 알고리즘 향상과 같은 고수준 최적화 기술은 상당한 잠재력이 있다. 퍼포먼스가 중요한(performance-critical) 코드 조각을 최적화 시켜야 한다면 우선 이 코드가 구현하는 프로세스를 분석한다. 프로세스를 시각화하는 것은 프로세스 이해를 위한 최선의 방법이다. 또한 다른 각도로 문제를 짚어가라. 원래 고안한것 보다 훨씬 나은 솔루션을 도출해 낼 것이다. 이런 종류의 최적화는 일반화가 어렵다. 모든 알고리즘은 특정 애플리케이션 도메인에 따라 다르고 일반적인 가이드라인도 부족하다. 프로그래머가 얼마나 창조적이 되는가에 달려있다.

  • 일단 좋은 실행 솔루션이 있다고 확신한다면 이것을 기술적 퍼포먼스 향상 기술에 적용할 때이다. 기본적인 개념은 시간 복잡도(time complexity)와 데이터 복잡도(data complexity)를 교환하는 것이다. 객체 캐시는 그와같은 기술의 전형적인 예이다. 자바 프로그램에서 객체 캐시는 값비싼 객체 생성이나 가비지 컬렉션 오버헤드를 피하고자 할 때 특히 유용하다. 이러한 종류의 시스템은 프로그램에 추가적인 기반 코드를 추가해야하기 때문에 도입을 너무 서두르지 말아야 한다. 코드가 복잡해 질 수록 최적화는 더욱 어려워진다.

  • 마지막으로 저수준 프로그래밍 최적화를 적용할 수 있다. 대부분의 자바 프로그래머들은 이러한 종류의 기술에 익숙하다. 하지만 실제 프로그램에서 얻는 이익은 제한되어 있다. 가능한 곳에 적용시키되 이러한 종류의 이디엄에 최적화의 포커스를 맞추지 말라. 잘 알려진 퍼포먼스 트램을 방지하기위한 프로그래밍 툴셋의 일부로 사용하라.

퍼즐 풀이 프로그램에서 다양한 최적화 기술을 조합해서 얻은 놀라운 퍼포먼스 향상으로, 모든 자바 프로그래머들이 그들의 코드를 되돌아 보고 어떻게 이를 최적화하는지를 연구하도록 동기를 부여할 수 있기를 바란다.

참고자료

필자소개
Erwin Vervaet은 소프트웨어 엔지니어이다. 1996년부터 자바 언어를 다뤘으며 벨기에의 Katholieke Universiteit Leuven에서 컴퓨터 공학 학위를 받았다. 현재 IT 연구, 이커머스 프로젝트, 오픈소스 이니셔티브, 산업 소프트웨어 시스템 분야에서 일하고 있다. 프리랜스 컨설턴트이며 자바로 객체 지향 비지니스 정보 시스템을 구현하고 있다.


Maarten De Cock는 자바 프로그래머이다. 특히 깨끗하고 빠른 자바 코드에 관심을 갖고 있다. 벨기에의Katholieke Hogeschool Leuven을 졸업한 후 99년 부터 자바 언어를 다루기 시작했다.현재 ASQdotCOM의 컨설턴트로 일하고 있다.



이 기사에 대하여 어떻게 생각하십니까?

정말 좋다 (5) 좋다 (4) 그저그렇다 (3) 수정보완이 필요하다(2) 형편없다 (1)

  회사소개  |  개인정보 보호정책  |  법률  |  문의