난이도 : 초급
Erwin Vervaet, 소프트웨어 엔지니어, Ervacon
Maarten De Cock, 애플리케이션 엔지니어, ASQdotCOM
2002 년 6 월 11 일
2003 년 5 월 13 일 수정
자바 프로그램을 최적화 할 수 있는 유용한 기술들이 많이 있다. 이 글에서는 특정 기술 하나에 포커스를 맞추는 것 대신 최적화 프로세스를 전체적으로 다룬다. 간단한 기술 팁에서부터 고급 알고리즘 최적화까지 다양한 기술들을 세분화하여 문제 해결 프로그램의 퍼포먼스 튜닝을 한다.
우리가 개발하고 최적화 할 프로그램은 Meteor 퍼즐에 대한 모든 가능한 솔루션을 계산할 것이다. Meteor 퍼즐은 10개의 퍼즐 조각과 5개의 육각형으로 구성된 다른 색상들로 이루어져 있다 (각 변의 길이가 같은 육면의 다각형이다). 퍼즐 보드 자체는 가로 5 x 세로 10 패턴으로 레이아웃은 50개의 육각형을 모아 직사각형 형태가 된다. 10개의 조각을 사용하여 전체 보드를 채워서 퍼즐을 풀 수 있다. 이 퍼즐에 대한 솔루션은 그림 1이 된다.
 |
|
그림 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 클래스를 설계하기 전에, 이 클래스가 무엇을 나태낼것인지를 생각해야 한다. 그림 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 클래스를 구현하기 전에, 두 가지 재미있는 문제를 짚고 넘어가자. 우선, 데이터 구조에 대해 결정해야 한다. 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 6 은 initializeBoardCell()메소드로서 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;
}
}
}
|
처음 알고리즘의 두 번째 단점은 이것이 기본적으로 많은 섬들을 만들어낸다는 것이다. 이것은 우리가 한 조각에서 하나의 순열을 취해 그 조각의 다음 순열로 변환하기 전에 보드로 이동시키기 때문이다. 예를 들어, 그림 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 배의 속도 향상이다.
| Version | 시간 (초) |
| meteor.initial | ~ 60,422,400 (약 2년) |
| meteor.algorithm | 157 |
| meteor.caching | 25 |
하지만 이 최적화가 아무리 놀라워도 이 실험에서 우리가 배울 수 있는 것이 무엇인가 라는 중요한 질문이 남아있다. 우리가 사용했던 다양한 최적화 기술은 각각 장점과 단점을 갖고있다. 그들을 조합하여 하나의 최적화 프로세스로 만드는 것은 사용법을 명확히 하고 애플리케이션의 구식화를 방지한다.
퍼즐 풀이 프로그램에서 다양한 최적화 기술을 조합해서 얻은 놀라운 퍼포먼스 향상으로, 모든 자바 프로그래머들이 그들의 코드를 되돌아 보고 어떻게 이를 최적화하는지를 연구하도록 동기를 부여할 수 있기를 바란다.
- developerWorks worldwide 사이트에서 이 기사에 관한 영어원문.
- "Merlin brings nonblocking I/O to the Java platform" (developerWorks, 2002년 3월).
- JDC Tech Tips .
- developerWorks Java technology zone.
|
||
|
Erwin Vervaet은 소프트웨어 엔지니어이다. 1996년부터 자바 언어를 다뤘으며 벨기에의 Katholieke Universiteit Leuven에서 컴퓨터 공학 학위를 받았다. 현재 IT 연구, 이커머스 프로젝트, 오픈소스 이니셔티브, 산업 소프트웨어 시스템 분야에서 일하고 있다. 프리랜스 컨설턴트이며 자바로 객체 지향 비지니스 정보 시스템을 구현하고 있다. | |
|
||
|
Maarten De Cock는 자바 프로그래머이다. 특히 깨끗하고 빠른 자바 코드에 관심을 갖고 있다. 벨기에의Katholieke Hogeschool Leuven을 졸업한 후 99년 부터 자바 언어를 다루기 시작했다.현재ASQdotCOM의 컨설턴트로 일하고 있다. | |
'Java' 카테고리의 다른 글
| [펌]JSF(JavaServer Faces) 활용하기 [1/3] (0) | 2005.10.06 |
|---|---|
| [펌]자바성능을 향상시키는 코딩 (0) | 2005.06.15 |
| 자바 스레드 고급 동기화 1 (0) | 2005.01.26 |