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

# これは何

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

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](https://github.com/reki2000/langs-bench-dijkstra) に置いてあります

## まずはざっくり実装で

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

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

最新の所感は

  - C++, Rust がほぼ拮抗（このベンチの精度だと優劣つけがたいがわずかにC++リード）

これを 1 として

  - 1.3倍に Go (手が入っていないのでまだ改善余地があるかも)
  - 2.5倍に Julia (初心者コードだったので改善幅が一番大きかった）
  - 5倍 Kotlin、6倍弱 Cython
  - 8倍弱 JavaScript、10倍 Python

Kotlin と JavaScript は User 時間が実行時間よりも少し長めなので GC など裏でもCPUを使っていると推測します。並列化したときに影響がある。

PyPy もやるべき.

言語別の速度に関するの知見も得られましたが、各言語の書き心地（書いたりデバグするのにかかる時間）も自分なりの感覚がわかりましたし、ベテランの方の良い書き方をまとめてキャッチアップできたことが大変有用でした。

速度を求めるものではないですがここまで来たら Haskell と Elixir、Scheme も試してみたい

```
Testing cpp...
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      1.931 s ±  0.032 s    [User: 1.903 s, System: 0.028 s]
  Range (min … max):    1.912 s …  2.017 s    10 runs

Testing rust...
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      1.969 s ±  0.012 s    [User: 1.933 s, System: 0.035 s]
  Range (min … max):    1.947 s …  1.982 s    10 runs

Testing go...
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      2.608 s ±  0.017 s    [User: 2.740 s, System: 0.097 s]
  Range (min … max):    2.589 s …  2.642 s    10 runs

Testing javascript...
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):     15.780 s ±  0.583 s    [User: 19.901 s, System: 1.581 s]
  Range (min … max):   15.175 s … 16.953 s    10 runs

Testing julia...
make: *** No rule to make target 'clean'.  Stop.
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):      5.222 s ±  0.185 s    [User: 5.575 s, System: 0.730 s]
  Range (min … max):    5.044 s …  5.538 s    10 runs

Testing kotlin...
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):     10.084 s ±  0.636 s    [User: 18.102 s, System: 0.605 s]
  Range (min … max):    9.153 s … 10.995 s    10 runs

Testing python...
make: *** No rule to make target 'clean'.  Stop.
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):     19.991 s ±  0.494 s    [User: 19.759 s, System: 0.267 s]
  Range (min … max):   19.198 s … 20.841 s    10 runs

Testing cython...
Benchmark #1: ./bench.sh 20 < ../data/Tokyo_Edgelist.csv
  Time (mean ± σ):     11.723 s ±  0.509 s    [User: 11.572 s, System: 0.188 s]
  Range (min … max):   11.103 s … 12.981 s    10 runs
```

## 追記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ロード時間の影響が想定より大きいので、そこだけのベンチマークを追加しました。[^1]
[^1]: 先ほど投稿したものはCythonのデータが変だったため、再測定しました

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/52184/dcb1f01f-6003-28b3-73b5-4bfb56bcf5da.png)

```
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回探索) 

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/52184/ed87e84f-33b1-61a5-d447-507f1887ddec.png)

```
  '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'
```

![result-20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/52184/d2a0a679-9e67-d323-e4a7-471984a9e8d6.png)

## 追記6

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

[Haskellに再入門して100万エッジのグラフネットワークでDijkstra探索するまで](https://qiita.com/reki2000/items/2c0fbc9be298044f9a03)

![result-20.png](https://github.com/reki2000/langs-bench-dijkstra/raw/master/result-20.png)