Goも当然にMapよりSwitchが速い ― 制約によるコンパイル時最適化の威力
MapはO(1) O(N)
Goのmapは、なにか深遠なるアルゴリズムによって取得時
が成立していると聞いています。 O(1)
switchは単純に一つ一つの節にマッチするか検証しているからですよね？ O(N)
だから、switchよりもmapを使ったほうがいいと思います
switchで十分実現できる処理がmapで書かれていたのでレビューで変えるように指摘すると、このようなことを言われました。
確かにmapは取得時
ここで、
しかし実際に計測してみるとswitchのほうが速いケースのほうが多いです。
なんてこった！時間計算量が裏切った！信じていたのに！
納得できないレビュイーのために、せっかくなのでコンパイラの実装も交えて見ていきましょう。
switchはO(N)
switch文をコンパイラがどう解釈するかは
の部分がわかりやすいでしょうか。
jump tableをまず最初に適用可能か調べて適用可能であれば適用し、そうでなければ二分探索を行うという記述です。
jump tableは機械語で言えば大体1命令であるようなもので、ざっくり表現するなら配列アクセスと同じような処理で条件分岐を実現します。
mapアクセスの
そして、適用外だった場合の二分探索ですが、
適用外になるには、jump table命令が使用できない[1]かjump table命令では非効率[2]かといったときですが、そうなったとしても
一応ですが、if文の列挙と同レベルまで落ちるケースもあります。 逆に言えばこれまでの話はif文の列挙よりもswitch文の方が速くなりやすいという話でもあったわけです。
総じて、switchは基本的にcase数に対して
MapはO(1)
翻ってGoのmapはどうでしょうか。
まず触れておかなければならないのは、mapが
ハッシュ値が衝突するなどの理由で、最悪計算量は
最良で
まず、mapを動かすためにはhash計算が必要で、これは比較的重い処理であるというのが一つ。
またmapは、SwissTableなどアルゴリズムの進展でだいぶそのようなことはなくなりましたが、メモリ局所性などの理由から二分探索
対してswitchが
言い換えれば
- 線形の計算量であってもNが小さいうちは定数項が支配的になりやすい (mapは定数項が重い、switchは定数項が軽い)
- switchが線形の計算量であるというのが誤解
ということで、冒頭のレビュイーは推測の出発点を間違えていたということになります。
このようなことから、実際にベンチマークを取ってみたときに、mapで書くよりもif文の連鎖のほうが速く、それよりさらにswitch文で書いたほうが速いというケースがほとんどになるのです。
結論としてはswitchが基本的に速度面で有利なので、分岐数が100を超えてきて初めてmapを検討するために計測を始めるくらいの向き合い方でいいと思いますが、そもそもswitchで分岐数が100を超えそうなときは設計を疑ったほうがいいかもしれません。
SwitchよりMapのほうが対応関係を示しているとわかりやすい？
MapはKeyとValueの対応を表すための構造を値として示せるじゃないですか
対してSwitchは制御構造だから、対応関係を表しているとわからないじゃないですか
だから、switchよりもmapを使ったほうが分かりやすくていいと思います
これもレビューで指摘したときに言われました。
switch v {
case 1:
return "good morning"
case 2:
return "good afternoon"
case 3:
return "good evening"
default:
return "hello"
}
という節内で即座に値をreturnしているswitchと、
map[int]string{
1: "good morning",
2: "good afternoon",
3: "good evening",
}
というMapを見比べたとき、Mapが単純に対応関係を書いているだけなのに対し、switchは余計な構文がついてしまっているように見えます。
それもそのはずで、switchは即座に値を返して対応関係を作る以外のこともできるわけで、節内で即座に値のreturnしかしていないということは全節を見るまでわからないわけです。
また、一行目だけ見てみますと、
switch v {
はswitch文なんだなーと思うだけ
map[int]string {
はKeyがintでValueがstringのMapなんだなとわかるわけです。
なるほど、確かに冒頭の話は間違いではなさそうです。
ですが、速度よりも可読性を重視するとしてもmapは良い選択ではありません。
先程のmapを関数を通じて提供してみましょう。
var greetingMap = map[int]string{
1: "good morning",
2: "good afternoon",
3: "good evening",
}
func Greeting(t int) string {
if v, ok := greetingMap[t]; ok {
return v
}
return "hello"
}
どうでしょうか？
まず、Greeting関数のインターフェースを知りたい人は、
func Greeting(t int) string
を見るので、
var greetingMap = map[int]string
という記述の重要さは小さくなりました。
そして、このGreeting関数がどういう対応関係を持つのかというのを把握するためには、greetingMapとGreeting関数のfallbackの分断された二箇所を見る必要が出てきたということもわかります。
さらに、mapは実行時に要素を変更することが可能なので、スコープ内でmapが変更される可能性を調べ上げなければその二箇所に書かれていることだけが真実だということも確定できないということも言えます。
これがswitchになれば
func Greeting(t int) string {
switch t {
case 1:
return "good morning"
case 2:
return "good afternoon"
case 3:
return "good evening"
default:
return "hello"
}
}
素晴らしい。mapの持っていた問題点はすべて解決し、インターフェースが一見してわかるという特徴はそのままです。
switchで新たに発生している問題といえば、構文が宣言的なものから手続き的なものに変化したことによって、やろうと思えばcaseの中で長い処理をベタ書きできるようになってしまったというのが思い浮かびますが……それはレビューで弾きましょう。
そんなことが起こり得る環境でswitchではなくmapであれば宣言的に書いてくれるはずという仮定も虚しいです。
逆に、基本的に純粋関数で書かれているプロジェクトなら、あまり気にしなくてもいいでしょう。
mapよりもswitchが当然に速いという感覚
記事冒頭のレビュイーの感覚に、いやいやとんでもない誤解だぞと、推測せずとも計測せずともswitchのほうが速いことを当然に期待するものじゃないかと思われた方々も多くいらっしゃると思います。
自分もそうで、最初からこの記事のように(特にGo言語において)完全な根拠を揃えて言語化してからmapではなくswitchを使えとレビューしたわけではありません。
switchのほうがmapより速くてわかりやすいでしょうというのを当然の感覚として持っていたわけです。
実際に計測すること、実際のコンパイラの実装を読むこと、実際に生成されるマシン語を読むこと、これらは確実ですがコストがかかります。
なにより、そもそもの感覚がなければ疑問にも思わず、計測も調査も行おうとすら思わないかもしれません。
コンパイラ最適化を信じているとか、ハッシュテーブル実装が重いことを経験的に知っているとか、そもそも条件式をベタ書きでいくら列挙しようが
静的に決定できるものは静的な形で書け
ということです。
mapはメモリ上に積まれる構造体であるわけで、要素の増減はもちろんのこと、宣言時や取得時にも動的な要素が絡みます。
これは、コンパイル時の最適化が効きにくいことを意味していて、速度的に不利な傾向があります。
また動的であるということはそれだけ不確実性が増すということで、コード上の処理の追いやすさにも影響します。
この原則はmap以外のことにも言えて、最も単純なものでは変数よりも定数を選べとか、動的型よりも静的型を選べ、ということにも通底しています。
静的に決定できるものを静的に書くことが、静的型付け言語を好む人に共通する基本的なマインドセットとも言いかえられます。
動的型付け言語の人々はまた違ったマインドセットを持っていたりもします[3]が、静的型付け言語ではこの教訓を持っていれば一つ指針になるのではないでしょうか。
Discussion