Javaで学ぶアルゴリズム -スタック（java.util.Stack と java.util.ArrayDeque のパフォーマンス比較）

# Javaでの効率的なスタック実装：ArrayDeque vs Stack

Javaの標準ライブラリには `java.util.Stack` と `java.util.ArrayDeque` という二つのスタック実装があるけど、

> スタックとして使われるときはStackよりも高速

と言われているので検証。

https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html


# 実行環境

- Java 8
- ヒープサイズ：`-Xms512m -Xmx1024m` で設定


# テスト（検証用）コード

- スタックの基本的な操作である `push` / `pop` / `peek` をそれぞれ 1000000 回やる
- `System.nanoTime()` を使用して、1000000 回実行したときのナノ秒単位の時間を取得する

```java:StackPerformanceTest.java
import java.util.ArrayDeque;
import java.util.Stack;

public class StackPerformanceTest {

	private static final int OPERATIONS_COUNT = 1000000;

	public static void main(String[] args) {

		long[] stackTimes = measureStackPerformance();
		long[] dequeTimes = measureArrayDequePerformance();

		System.out.println("Operation\tStack (ns)\tArrayDeque (ns)");
		System.out.println("Push\t\t" + stackTimes[0] + "\t\t" + dequeTimes[0]);
		System.out.println("Peek\t\t" + stackTimes[1] + "\t\t" + dequeTimes[1]);
		System.out.println("Pop\t\t" + stackTimes[2] + "\t\t" + dequeTimes[2]);
	}

	private static long[] measureStackPerformance() {
		Stack<Integer> stack = new Stack<>();
		long pushTime = 0;
		long peekTime = 0;
		long popTime = 0;

		long pushStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			stack.push(i);
		}
		pushTime += System.nanoTime() - pushStart;

		long peekStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			stack.peek();
		}
		peekTime += System.nanoTime() - peekStart;

		long popStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			stack.pop();
		}
		popTime += System.nanoTime() - popStart;

		return new long[] { pushTime, peekTime, popTime };
	}

	private static long[] measureArrayDequePerformance() {
		ArrayDeque<Integer> deque = new ArrayDeque<>();
		long pushTime = 0;
		long peekTime = 0;
		long popTime = 0;

		long pushStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			deque.push(i);
		}
		pushTime += System.nanoTime() - pushStart;

		long peekStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			deque.peek();
		}
		peekTime += System.nanoTime() - peekStart;

		long popStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			deque.pop();
		}
		popTime += System.nanoTime() - popStart;

		return new long[] { pushTime, peekTime, popTime };
	}
}
```

# 実行結果
### 平均値比較（※ 単位はナノ秒）

| 観点 \ ライブラリ | `java.util.Stack` | `java.util.ArrayDeque` |
| :--: | --: | --: |
| push | 20,356,860 | 6,374,430 |
| peek | 17,176,950 | 254,450 |
| pop | 19,884,760 | 795,100 |

### 各回比較（※ 単位はナノ秒）

| 回 | Stack | Stack | Stack | ArrayDeque | ArrayDeque | ArrayDeque |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| - | push | peek | pop | push | peek | pop |
| 1 | 28770200 | 34148300 | 44782999 | 14775600 | 2544100 | 3526000 |
| 2 | 27759301 | 15423599 | 15435001 | 13483700 | 0 | 536701 |
| 3 | 25714001 | 15431900 | 15267799 | 6342900 | 0 | 519700 |
| 4 | 16711800 | 15421600 | 15442400 | 3009800 | 0 | 475001 |
| 5 | 16810599 | 15161099 | 15479701 | 2940400 | 100 | 477399 |
| 6 | 22395800 | 15311601 | 15372400 | 3061600 | 100 | 544300 |
| 7 | 16666500 | 16591599 | 32503301 | 3013500 | 0 | 474600 |
| 8 | 16678900 | 15316400 | 15426399 | 11209401 | 100 | 488500 |
| 9 | 16178200 | 14491301 | 14553700 | 2948001 | 0 | 454999 |
| 10 | 15883300 | 14472101 | 14583899 | 2959400 | 100 | 453800 |

優位に `java.util.ArrayDeque` の方がパフォーマンスよいことが分かるけど、ArrayDequeのpeeks処理があまりにも最適化されてそう（キャッシュの影響かなぁ？）なので、プログラムを書き換えて再実行してみる。

# テスト（検証用）コードその２

計測の仕様を以下のように変更したうえで、全体のパフォーマンスを測定してみる。

- すべての要素を push する
- その後 peek と pop を繰り返す
- 1000000 この要素分の push / peek / pop の合計時間を測定

```java: StackPerformanceTest.java
import java.util.ArrayDeque;
import java.util.Stack;

public class StackPerformanceTest {

	private static final int OPERATIONS_COUNT = 1000000;

	public static void main(String[] args) {

		StringBuilder sb = new StringBuilder();
		sb.append("回数, java.util.Stack, java.util.ArrayDeque");
		sb.append(System.lineSeparator());

		for (int i = 1; i < 11; i++) {

			long stackTimes = measureStackPerformance();
			long dequeTimes = measureArrayDequePerformance();

			sb.append(i + ", " + stackTimes + ", " + dequeTimes);
			sb.append(System.lineSeparator());
		}
		System.out.println(sb.toString());
	}

	private static long measureStackPerformance() {
		Stack<Integer> stack = new Stack<>();
		long stackTime = 0;

		long start = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			stack.push(i);
		}

		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			stack.peek();
			stack.pop();
		}
		stackTime = System.nanoTime() - start;

		return stackTime;
	}

	private static long measureArrayDequePerformance() {
		ArrayDeque<Integer> deque = new ArrayDeque<>();
		long dequeTime = 0;

		long start = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			deque.push(i);
		}

		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			deque.peek();
			deque.pop();
		}

		dequeTime = System.nanoTime() - start;

		return dequeTime;
	}
}
```

# 実行結果

とはいえ、優位に `java.util.ArrayDeque` の方がパフォーマンスよいね。

### 平均値比較（※ 単位はナノ秒）

| 回数 \ ライブラリ | `java.util.Stack` | `java.util.ArrayDeque` |
| :--: | --: | --: |
| 平均 | 38,941,760 | 6,880,650 |

### 各回比較（※ 単位はナノ秒）

| 回数 | java.util.Stack | java.util.ArrayDeque |
| :--: | --: | --: |
| 1 | 88,468,199 | 17,380,101 |
| 2 | 41,395,700 | 13,799,700 |
| 3 | 39,710,899 | 7,140,700 |
| 4 | 30,828,800 | 3,426,101 |
| 5 | 31,008,800 | 3,410,800 |
| 6 | 36,107,300 | 3,417,100 |
| 7 | 30,359,300 | 3,375,900 |
| 8 | 30,327,900 | 10,002,101 |
| 9 | 30,658,101 | 3,418,000 |
| 10 | 30,552,600 | 3,435,999 |