More than 3 years have passed since last update.

言語別Stack処理速度比較

Last updated at 2020-07-17Posted at 2020-07-10

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) (Stackクラス)	Java 8 (クラスStack)	Java 8 (クラスArrayDeque)	Java 8 (クラスDeque)	Python3.8.3 (リスト)
Stackへの書き込み	Pushメソッド	pushメソッド	pushメソッド	addFirstメソッド	append関数
Stackからの取り出し	Popメソッド	popメソッド	popメソッド	removeFirstメソッド	pop関数
値の検索	Containsメソッド (戻り値はbool型)	searchメソッド (戻り値はindex番号)	Containsメソッド (戻り値はbool型)	Containsメソッド (戻り値は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]