これは何

最短経路探索のアルゴリズムを使っていくつかの言語の性能がどれくらい違うかを調べてみました。

Python は手軽に実装できるけど遅い、Go は早いけど C++ よりは遅い? 本当? のような疑問を一定解消したかったというのが動機です。

前提条件など

対象とする言語

本命 Go, Rust, C++
興味本位 Julia Python より段違いに早ければもう少し掘ってみたい
興味本位 Kotlin 意外とトップ集団に肉薄するのではないか
参考 Python JavaScript

性能差のイメージとしては Rust == C++ > Go >> Kotlin >>> JavaScript > Python == Julia

ちなみに fibonacci数の計算（計算結果のメモ化なし）で比較させてみたところ、C++ == Rust > Go > Kotlin == Julia > JavaScript > Python でした。Kotlin、Julia が意外に健闘。ただ、fibonacci 計算程度だと処理が単純なので、関数呼び出しのオーバーヘッドの差が強く出てしまうなど、あまりまともな性能比較にならなさそうです

測定項目

30万エッジ程度の道路ネットワークを csv から読み込む
20回特定のノードから全ノードへの最短経路を求める
上記の合計処理時間を 10 回測定して所要時間の平均と分散を求める

実装方針

csv の読み込み方は問わない（処理全体の実行時間に対して10%未満の処理時間に収まるようにする)
読み込んだ道路ネットワークデータを格納するグラフのデータ構造は後からデータを追加できることとする（最適化のために固定長配列を使った配置にはしない）
- とはいえ hash/dict を使うと処理系のオーバーヘッドが無視できないので、ノード番号はグラフ構築時に採番して連続した数値に変換し、エッジ情報はその数値をインデックスとして引けるようにする
- for i in graph.edges[node_index] 的な記述で特定ノードからのエッジ情報が O(1) でとれるようにする、ということ
- vector/map へのデータ追加の際、リサイズは power of 2 で行われていることを期待
標準ライブラリ以外は極力使わない (CSV読み込みは妥協あり)
最短経路探索はシンプルな Dijkstra 法で行う
- Dijkstra の処理時間を支配する Priority Queue は標準ライブラリにあればそれを使う
- 用意されていないか、あったとしても比較関数の受け渡しが性能に影響ありそうであれば、配列orベクタの完全二分木を使った独自実装のヒープを使う
そのほか
- 最適化オプションや inline 指定はカジュアルに指定できるものはやってよい
- VM 起動にかかる時間やインタプリタ言語の JIT 時間も含んだ比較とする
- GCを除いて並列処理は行わない (シングルスレッドでの性能が高ければ並列化は別のレイヤでできるので）

測定結果

ソースは Github に置いてあります

まずはざっくり実装で

WSL 2.0 (Ubuntu 18.04) on Windows 10 Home 64bit @ i5-8250 で測定

Testing cpp...
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      3.998 s ±  0.076 s    [User: 3.955 s, System: 0.042 s]
  Range (min … max):    3.907 s …  4.198 s    10 runs
 
Testing go...
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      2.737 s ±  0.072 s    [User: 2.914 s, System: 0.088 s]
  Range (min … max):    2.660 s …  2.923 s    10 runs
 
Testing rust...
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      2.447 s ±  0.021 s    [User: 2.431 s, System: 0.016 s]
  Range (min … max):    2.415 s …  2.474 s    10 runs
 
Testing javascript...
make: *** No rule to make target 'clean'.  Stop.
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):     13.711 s ±  0.255 s    [User: 17.650 s, System: 1.603 s]
  Range (min … max):   13.321 s … 14.193 s    10 runs
 
Testing julia...
make: *** No rule to make target 'clean'.  Stop.
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):     39.276 s ± 14.772 s    [User: 39.386 s, System: 0.943 s]
  Range (min … max):   26.985 s … 72.450 s    10 runs
 
Testing kotlin...
OpenJDK 64-Bit Server VM warning: Options -Xverify:none and -noverify were deprecated in JDK 13 and will likely be removed in a future release.
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):     15.542 s ±  2.046 s    [User: 27.487 s, System: 1.081 s]
  Range (min … max):   12.994 s … 18.660 s    10 runs```

Testing python...
make: *** No rule to make target 'clean'.  Stop.
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):     21.976 s ±  0.997 s    [User: 21.677 s, System: 0.341 s]
  Range (min … max):   20.092 s … 23.337 s    10 runs

性能の所感

Go == Rust > C++ >>>> Kotlin == JavaScript > Python >> Julia となった

Go が Rust と並んでトップ。普通に組んでこういう結果が出るのは Go の強みっぽい
C++ が Go に負けている。pq を自前に差し替えたほうが良いかもしれない
Julia が期待に反して最も遅い (簡単な Fibonacci での検証では Go と同等だったのに)
python がもっと遅いかと思ったがそこまででもない

改善その1

C++ を修正したところ Rust, Go と同等の速度が出るようになった

cin が遅い問題 に対処、csv 読み込みの split を改善、が大きかった（csv読み込み部分の高速化は今回の本筋ではないつもりだったがトップ争いには重要だった）
priority queue を独自実装に変更してもほとんど変わらなかった

Testing cpp...
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      2.586 s ±  0.012 s    [User: 2.555 s, System: 0.030 s]
  Range (min … max):    2.567 s …  2.607 s    10 runs

改善その2

Kotlin で priority queue のための比較関数を外部から渡すのをやめたところ性能が倍に！やはりホットスポット部分はオーバーヘッドを気にしたほうがよさそう

Testing kotlin...
OpenJDK 64-Bit Server VM warning: Options -Xverify:none and -noverify were deprecated in JDK 13 and will likely be removed in a future release.
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      9.596 s ±  0.557 s    [User: 17.708 s, System: 0.601 s]
  Range (min … max):    8.778 s … 10.305 s    10 runs

実装してみての所感

Rust

最初は borrow の考え方に慣れておらず大変だったがなれると安心感が半端ない
所有権の問題でグローバル変数が扱いづらいため、グラフデータはローカルで領域確保したものを持ちまわるようにした
コードは少しごちゃっと感がある印象。型推論をうまく使えるようになればもっとコンパクトにかけるかもしれない
Option な値を扱う際、if let Some(x) = hoge ... で x をキャプチャできるのはうれしい

Python

異様に早く実装完了。型がないこと、qheap が提供されていることなどが勝因か
改めて、インデントがブロックになるというのはコード全体がシンプルに見えてよい
Python より JavaScript のほうが早いイメージでした。実際もそうだった

Go

priority queue を実現する際、標準ライブラリ heap の実装だと比較関数を外部から渡す形になるので遅くなってしまうかもと思い独自実装することにした
:= での変数宣言はシンプルでいい

Kotlin

比較関数を外部から渡す実装にしてみた。が、速度が出ず結局修正することに
VSCode 上ではコンパイルエラーがうまく検出されずデバッグに苦労。(kotlin.* などがインポートされておらず参照できないというエラーになってしまう)
ネイティブコンパイル系言語の3-4倍くらい、というのは納得感

JavaScript

Python と同様に、型がない分シンプルなコードに。
ほかの言語と違って配列と object でアクセス性能に差がないかもしれない
V8 が頑張っているとはいえ Kotlinコンパイル + JVM にはかなわないか

C++

priority_queue に Pair を入れて比較させているがトップ争いをする上では性能に影響があるかもしれない

Julia

配列が 1 始まりなので移植がかなり面倒
Generics を使うと性能にインパクトがあるとのことなので priority queue は特定型に依存した実装にしてみた
思ったより性能が出ない…… もう少し勉強すれば大きなブレークスルーが作れるかも
いまのところは Python から乗り換えるほどの魅力を感じなかった

結論

C++ == Rust == Go
Kotlin(JVM)がその3-4倍
JavaScript は 5倍弱
Python は 10倍弱
Julia は 20倍弱

色々な言語で同じものを実装すると、各言語の文法の特徴がよりはっきり見えてきて面白いですね。

Julia をもう少し性能改善したい

追記1

コメントで非常に有用なご指摘と改善されたコードを頂いたので、こちらの環境でも測定してみました

Testing julia...
make: *** No rule to make target 'clean'.  Stop.
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      5.146 s ±  0.132 s    [User: 5.499 s, System: 0.727 s]
  Range (min … max):    4.925 s …  5.333 s    10 runs

Julia が Kotlin を超え2位集団のトップに……！グローバル変数は最適化対象外、Array{*, 1} の次元指定がないと遅くなる、など、最適化が効く条件をきちんと押さえていくことがポイントのよう。

Testing rust...
(略)
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      1.896 s ±  0.008 s    [User: 1.873 s, System: 0.022 s]
  Range (min … max):    1.884 s …  1.906 s    10 runs

Rust もトップ集団から頭一つ抜けました。ゼロコスト抽象化も頼もしい…… ここまでくると本来は測定対象として重要視していなかった CSV 読み込みのところのチューニングの効果が大きいので、Go や C++ ももう少し改善できるかもしれません。

最新状況： Rust > C++, Go >> Julia > Kotlin >> JavaScript > Python

追記2

色々と緩い条件のベンチマークなのにもかかわらず、想像以上に多くの改善提案を頂きありがとうございました。それらに対応した上で改めて全部測定しなおしました。

追記3

PyPy足しました。完全に Python(CPython) 用のコードがそのまま動いて、Cython より速いです。ステキ。C++, Rust の 4倍弱

Testing pypy...
make: *** No rule to make target 'clean'.  Stop.
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      7.957 s ±  0.731 s    [User: 7.787 s, System: 0.204 s]
  Range (min … max):    7.511 s …  9.428 s    10 runs

追記4

CSVロード時間の影響が想定より大きいので、そこだけのベンチマークを追加しました。¹

C++ では全体 2秒中 0.27秒前後がCSV読み込みでした。

CSVロード時間のみ (0回探索)

Benchmark #1: cd cpp; ./bench.sh 0 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):     271.5 ms ±  22.7 ms    [User: 251.2 ms, System: 19.5 ms]
  Range (min … max):   250.2 ms … 314.3 ms    10 runs

(省略)

Summary
  'cd cpp; ./bench.sh 0 < ../data/Tokyo_Edgelist.csv' ran
    1.26 ± 0.08 times faster than 'cd rust; ./bench.sh 0 < ../data/Tokyo_Edgelist.csv'
    2.08 ± 0.12 times faster than 'cd go; ./bench.sh 0 < ../data/Tokyo_Edgelist.csv'
    4.34 ± 0.32 times faster than 'cd pypy; ./bench.sh 0 < ../data/Tokyo_Edgelist.csv'
    8.53 ± 0.47 times faster than 'cd julia; ./bench.sh 0 < ../data/Tokyo_Edgelist.csv'
    9.38 ± 0.64 times faster than 'cd cython; ./bench.sh 0 < ../data/Tokyo_Edgelist.csv'
   13.10 ± 0.71 times faster than 'cd kotlin; ./bench.sh 0 < ../data/Tokyo_Edgelist.csv'
   16.26 ± 0.90 times faster than 'cd python; ./bench.sh 0 < ../data/Tokyo_Edgelist.csv'
   25.55 ± 1.55 times faster than 'cd javascript; ./bench.sh 0 < ../data/Tokyo_Edgelist.csv'

元の条件 (CSV読み込み + 20回探索)

  'cd cpp; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv' ran
    1.09 ± 0.01 times faster than 'cd rust; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    1.36 ± 0.02 times faster than 'cd go; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    2.88 ± 0.07 times faster than 'cd julia; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    3.80 ± 0.04 times faster than 'cd pypy; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    5.28 ± 0.27 times faster than 'cd kotlin; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    6.28 ± 0.30 times faster than 'cd cython; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    8.91 ± 1.16 times faster than 'cd javascript; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
   10.36 ± 0.26 times faster than 'cd python; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'

追記5

Dart を足しました。Kotlinより遅く、C++の5倍程度。今回は Linux で測定していますが、Dart は最終的にCPUからみて機械語としてどういうコードになっているのが想像しづらい（理解していない）ので、書き方を学べば早くなるかもしれませんが、普通に書いたら望めない印象です。

そのほか JavaScript(node)のCSV読み込みがあまりに遅いので改善したり、最新のバージョンに追従してみたりしましたが大勢は変わらず。

jsはbunが面白そうなので安定してきたら測定に追加する予定。（少しやってみたがローカルファイルの読み込みがうまくできなかった）

  'cd cpp; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv' ran
    1.14 ± 0.03 times faster than 'cd rust; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    1.44 ± 0.06 times faster than 'cd go; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    2.91 ± 0.25 times faster than 'cd julia; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    3.92 ± 0.09 times faster than 'cd pypy; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    3.96 ± 0.31 times faster than 'cd kotlin; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    4.97 ± 0.04 times faster than 'cd dart; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    6.23 ± 0.31 times faster than 'cd cython; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
    6.91 ± 0.68 times faster than 'cd javascript; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'
   11.22 ± 1.35 times faster than 'cd python; ./bench.sh 20 < ../data/Tokyo_Edgelist.csv'

追記6

ついにHaskellを足しました。慣れないうちはコーディングに相当時間がかかりますが、Priority Queue がImmutable(値が変わるたびに作り直し)でもC++の2倍程度と、ほかの言語に比べても意外と速いです。苦労含めたポエム記事を別に書きました。

Haskellに再入門して100万エッジのグラフネットワークでDijkstra探索するまで

先ほど投稿したものはCythonのデータが変だったため、再測定しました ↩

Python を Go に書き換えるとどれくらい速くなる？ 7つの言語で Dijkstra の実行速度を比較