言語別Stack処理速度比較


## 1. はじめに
Go言語にはStackが実装されていませんが、

Stackの処理自体は、どの言語でも、
配列や線形リストを使って自作で実装することができます。

Go言語向けに自作で作ったついでに、
Stackが実装されている他言語との処理速度（処理時間）を比較してみました。

実験で使用した言語は、

* C#(.NET Core3.0)
* go1.14.4
* java 13.0.2
* Python 3.8.3
* ~~C言語(MinGW.org GCC-8.2.0-3)(2020/07/12追記)~~
* C言語(gcc.exe \(x86_64-posix-seh-rev0, Built by MinGW-W64 project\) 8.1.0)(2020/07/17更新)

の５言語です。

各言語のソースは、githubでも公開しています。
https://github.com/NobuyukiInoue/StackSpeedTest

* C#
https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_CS

* Go(64K個のセグメント(配列)でStackを実装)(2020/07/17追加)
https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Go_Stack_by_Segment

* Go(配列でStackを実装)
https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Go_Stack_by_Array

* Go(線形リストでStackを実装)
https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Go_Stack_by_ListNode

* Java
https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Java_Stack
https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Java_ArrayDeque
https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Java_Deque

* Python
https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Python3

* C言語(64K個のセグメント(配列)でStackを実装)
https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_C_Stack_by_Segment

* C言語(線形リストでStackを実装)
https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_C_Stack_by_ListNode

## 2. 言語別のメソッド比較

Stackといっても、言語によって、各種操作がメソッドで提供されていたり、
プロパティでチェックしなければならないなど、細かな処理の実装内容が異なります。

今回の実験で使用した各言語でのクラス／インタフェース／機能を一覧にすると、以下のようになります。

|処理内容|C#(.NET Core3.x)<br>(Stackクラス)|Java 8<br>(クラスStack)|Java 8<br>(クラスArrayDeque)|Java 8<br>(クラスDeque)|Python3.8.3<br>(リスト)|
|---|----|----|----|----|----|
|Stackへの書き込み|Pushメソッド|pushメソッド|pushメソッド|addFirstメソッド|append関数|
|Stackからの取り出し|Popメソッド|popメソッド|popメソッド|removeFirstメソッド|pop関数|
|値の検索|Containsメソッド<br>(戻り値はbool型)|searchメソッド<br>(戻り値はindex番号)|Containsメソッド<br>(戻り値はbool型)|Containsメソッド<br>(戻り値はbool型)|index関数|
|Stackが空かどうか調べる|Countプロパティを利用|emptyメソッド|isEmptyメソッド|isEmptyメソッド|len関数を利用|

## 3. 検証環境と実験結果(2020/07/11追記)

|項目|値|
|---|---------|
|OS|MS-Windows 10|
|CPU|Intel Core-i7 8559u|
|メモリ|16GB(LPDDR3/2133MHz)|

メモリ容量を追記しました。(2020/07/11)


処理の内容は、

* 1～1億までの数値のpush()
* 最も深い位置にある値1の検索
* 1億～1までのPop()

です。

（なぜに1億個かというと、このあたりから各言語間の処理時間が開き始めたからです。超巨大なJSONのparse処理をスタックで実装するとかしない限り、そこまで消費しないでしょうけど。）

1億個の数値をint64(8byte)で割り当てると、762MByteの容量が必要になります。
int32(4byte)なら、半分の381MByteですね。

生成するスタックの容量が小さいうちは、それほど処理時間に差はありませんが、
1億個のスタック生成となると、選択した方法によってはメモリ消費が4GBを超えます。

搭載されているメモリが8GB以下だと、言語によっては（デフォルト設定では）、
ヒープメモリが足りないといったエラーがでます。

各言語での処理時間は以下の通りでした。

消費したメモリについても、Windows10のリソースモニター（コミット値）による表示の目視ではありますが、参考程度に掲載しています。(2020/07/11追記)

### C# NET Core 3.0.100

Stackクラスを使用
https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.stack-1?view=netcore-3.1

メモリ消費は0.39GBでした。

|times|Execution time|
|---|---------|
|1st|977 [ms]|
|2nd|1003 [ms]|
|3rd|1004 [ms]|

メモリ消費からみて、内部ではint32で処理が行われているようです。

他言語と比べてかなりメモリ消費が少なく、
処理データの少なさが処理時間の短さに影響しているようです。

### go1.14.4 windows/amd64(64K個単位のセグメント(配列)でStackを実装)(2020/07/17追加)

リソースモニタのサンプリング間隔よりもプログラム終了までの時間が短すぎて、メモリ消費は目視では確認できませんでした。（終了時は0.02GB)
恐らくC言語と同等程度だと思われます。

|times|Execution time|
|---|---------|
|1st|874 [ms]|
|2nd|881 [ms]|
|3rd|904 [ms]|

C言語と同様の64k個単位のセグメント(配列)で実装してみたところ、ほぼC言語に迫る処理時間となりました。

gcc 32bit版でコンパイルしていた2020/07/15時点のC言語のプログラムよりも速かったので、
その後、C言語版はMinGW-W64版でコンパイルして再計測しています。(2020/07/17)

### go1.14.4 windows/amd64(配列版)

メモリ消費は2.36GBでした。

|times|Execution time|
|---|---------|
|1st|2089 [ms]|
|2nd|1853 [ms]|
|3rd|1737 [ms]|

配列の再割り当てを繰り返しても、それほど遅くはないようです。
Javaより速い結果となりました。

### go1.14.4 windows/amd64(線形リスト版)

メモリ消費は1.49GBでした。

|times|Execution time|
|---|---------|
|1st|5617 [ms]|
|2nd|5400 [ms]|
|3rd|5569 [ms]|

処理時間は配列版よりも遅くなりました。

線形リストでは次ノードへのポインタが必要なので、
直線的なメモリ配置の配列より不要なデータが増えてしまいますが、
配列版より消費が少ない結果となりました。

Go言語では、配列の再割り当てを行っても、
プログラムの終了までメモリの解放が行われていないのかもしれません。
（あくまで推測で、だれか検証してほしい）

### java 13.0.2(クラスStack版)

クラスStackを使用
https://docs.oracle.com/javase/jp/8/docs/api/java/util/Stack.html

メモリ消費は4.21GBでした。

|times|Execution time|
|---|---------|
|1st|6743 [ms]|
|2nd|6690 [ms]|
|3rd|6733 [ms]|

### java 13.0.2(クラスArrayDeque版)

クラスArrayDequeを使用
https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html

メモリ消費は3.96GBでした。

|times|Execution time|
|---|---------|
|1st|4397 [ms]|
|2nd|4612 [ms]|
|3rd|4477 [ms]|

クラスStackよりも処理時間が短くなりました。


### java 13.0.2(インタフェースDeque版)

インタフェースDequeを使用
https://docs.oracle.com/javase/jp/8/docs/api/java/util/Deque.html

メモリ消費は4.31GBでした。

|times|Execution time|
|---|---------|
|1st|21416 [ms]|
|2nd|20187 [ms]|
|2nd|20341 [ms]|

クラスStackよりも処理時間が増えてしまいました。

### Python 3.8.3

リストを使用

メモリ消費は4.42GBでした。

|times|Execution time|
|---|---------|
|1st|16957 [ms]|
|2nd|16561 [ms]|
|3rd|17558 [ms]|

他言語では、一度確保したメモリは消費したままでしたが、
Python3では、１億個のPush直後がメモリ消費の最大値で、
Pop処理が進むにしたがって消費メモリが減っていく様子が目視できます。

### C言語(64K個単位のセグメント(配列)でStackを実装)(2020/07/17更新)

メモリ消費は0.38GBでした。

さすがにC言語は速いですね。
コンパイル時の最適化オプションとして-O3を指定してみました。

|times|Execution time|
|---|---------|
|1st|843 [ms]|
|2nd|828 [ms]|
|3rd|828 [ms]|

ちなみに、pop時にメモリを解放しない場合は以下の処理時間となりました。

|times|Execution time|
|---|---------|
|1st|734 [ms]|
|2nd|734 [ms]|
|3rd|734 [ms]|

### C言語(線形リストでStackを実装)(2020/07/17更新)

メモリ消費は1.55GBでした。

コンパイル時の最適化オプションとして-O3を指定してみました。
メモリの確保・解放の処理回数が多いので、それだけ処理時間が遅くなっています。

|times|Execution time|
|---|---------|
|1st|7816 [ms]|
|2nd|7828 [ms]|
|3rd|7953 [ms]|


## 関連(2020/07/11追記)

LeetCodeのProblemの中にも、Stackを自分で実装する問題があります。
いろんな言語での回答例が投稿されているので、処理時間を比較するのも面白いと思います。

* 225. Implement Stack using Queues<br>
https://leetcode.com/problems/implement-stack-using-queues/