終点枕崎

プログラミングとvimと音楽と地理

switch vs ハッシュマップ+関数オブジェクト

前々からちょっと気になってたやつです。

switch case 文で分岐するのと、switchの式をキーにしてハッシュマップに関数オブジェクトを突っ込んだものとどちらが速いかか調べました。

検証方法

16の分岐を持つ処理を100,000,000回繰り返して、それにかかった時間の平均を取る。岐条件の定数式は整数型とする。言語はC++

分岐数を16にしたのは、それ以上の分岐数になることが滅多にないからです。

定数式の値がバラバラでない時

定数式の値があまりバラバラでない時(例えば 1, 2, 4, 5, 8)、switch case 文に対してコンパイラはジャンプテーブルと呼ばれるアドレス表を生成します。なのでswitchを使ってもハッシュマップを使っても定数時間で分岐します。ただハッシュマップはハッシュテーブルを経由する為、switchと比べて無駄が多いです。

ソースコード

#include <iostream>
#include <functional>
#include <chrono>
#include <unordered_map>

int main(int argc, char* argv[])
{
	int i;
	std::cin >> i;

	auto start = std::chrono::system_clock::now();

	for(int j = 0; j < 100000000; j++)
	{
		switch(i)
		{
			case 0:
				i = 1;
				break;
			case 1:
				i = 2;
				break;
			case 2:
				i = 3;
				break;
			case 3:
				i = 4;
				break;
			case 4:
				i = 5;
				break;
			case 5:
				i = 6;
				break;
			case 6:
				i = 7;
				break;
			case 7:
				i = 8;
				break;
			case 8:
				i = 9;
				break;
			case 9:
				i = 10;
				break;
			case 10:
				i = 11;
				break;
			case 11:
				i = 12;
				break;
			case 12:
				i = 13;
				break;
			case 13:
				i = 14;
				break;
			case 14:
				i = 15;
				break;
			case 15:
				i = 0;
				break;
		}
	}

	auto end = std::chrono::system_clock::now();
	auto msec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

	std::cout << msec << std::endl;

	std::unordered_map<int, std::function<void()>> func_table;
	func_table.insert(std::make_pair(0, [&i](){ i = 1; }));
	func_table.insert(std::make_pair(1, [&i](){ i = 2; }));
	func_table.insert(std::make_pair(2, [&i](){ i = 3; }));
	func_table.insert(std::make_pair(3, [&i](){ i = 4; }));
	func_table.insert(std::make_pair(4, [&i](){ i = 5; }));
	func_table.insert(std::make_pair(5, [&i](){ i = 6; }));
	func_table.insert(std::make_pair(6, [&i](){ i = 7; }));
	func_table.insert(std::make_pair(7, [&i](){ i = 8; }));
	func_table.insert(std::make_pair(8, [&i](){ i = 9; }));
	func_table.insert(std::make_pair(9, [&i](){ i = 10; }));
	func_table.insert(std::make_pair(10, [&i](){ i = 11; }));
	func_table.insert(std::make_pair(11, [&i](){ i = 12; }));
	func_table.insert(std::make_pair(12, [&i](){ i = 13; }));
	func_table.insert(std::make_pair(13, [&i](){ i = 14; }));
	func_table.insert(std::make_pair(14, [&i](){ i = 15; }));
	func_table.insert(std::make_pair(15, [&i](){ i = 0; }));

	start = std::chrono::system_clock::now();

	for(int j = 0; j < 100000000; j++)
	{
		func_table[i]();
	}

	end = std::chrono::system_clock::now();

	msec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
	std::cout << msec << std::endl;

	return 0;
}

コンパイル

clang++ switch.cpp --std=c++11 -o switch.out -O2

結果

8回測った平均です。

switch case 178.5ms
ハッシュマップ 1146.375ms

圧倒的にswitchが速い!!!!

定数式の値がバラバラの時

このような時、switch case 文に対してコンパイラは一部で二分探索をするアセンブリコードを生成します。

ソースコード

#include <iostream>
#include <functional>
#include <chrono>
#include <unordered_map>

int main(int argc, char* argv[])
{
	int i;
	std::cin >> i;

	auto start = std::chrono::system_clock::now();

	for(int j = 0; j < 100000000; j++)
	{
		switch(i)
		{
			case 1:
				i = 2;
				break;
			case 2:
				i = 4;
				break;
			case 4:
				i = 8;
				break;
			case 8:
				i = 16;
				break;
			case 16:
				i = 32;
				break;
			case 32:
				i = 64;
			case 64:
				i = 128;
				break;
			case 128:
				i = 256;
				break;
			case 256:
				i = 512;
				break;
			case 512:
				i = 1024;
				break;
			case 1024:
				i = 2048;
				break;
			case 2048:
				i = 4096;
				break;
			case 4096:
				i = 8192;
				break;
			case 8192:
				i = 16384;
				break;
			case 16384:
				i = 32768;
				break;
			case 32768:
				i = 1;
				break;
		}
	}

	auto end = std::chrono::system_clock::now();
	auto msec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

	std::cout << msec << std::endl;

	std::unordered_map<int, std::function<void()>> func_table;
	func_table.insert(std::make_pair(1, [&i](){ i = 2; }));
	func_table.insert(std::make_pair(2, [&i](){ i = 4; }));
	func_table.insert(std::make_pair(4, [&i](){ i = 8; }));
	func_table.insert(std::make_pair(8, [&i](){ i = 16; }));
	func_table.insert(std::make_pair(16, [&i](){ i = 32; }));
	func_table.insert(std::make_pair(32, [&i](){ i = 64; }));
	func_table.insert(std::make_pair(64, [&i](){ i = 128; }));
	func_table.insert(std::make_pair(128, [&i](){ i = 256; }));
	func_table.insert(std::make_pair(256, [&i](){ i = 512; }));
	func_table.insert(std::make_pair(512, [&i](){ i = 1024; }));
	func_table.insert(std::make_pair(1024, [&i](){ i = 2048; }));
	func_table.insert(std::make_pair(2048, [&i](){ i = 4096; }));
	func_table.insert(std::make_pair(4096, [&i](){ i = 8192; }));
	func_table.insert(std::make_pair(8192, [&i](){ i = 16384; }));
	func_table.insert(std::make_pair(16384, [&i](){ i = 32768; }));
	func_table.insert(std::make_pair(32768, [&i](){ i = 1; }));

	start = std::chrono::system_clock::now();

	for(int j = 0; j < 100000000; j++)
	{
		func_table[i]();
	}

	end = std::chrono::system_clock::now();

	msec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
	std::cout << msec << std::endl;

	return 0;
}

コンパイル

clang++ switch.cpp --std=c++11 -o switch.out -O2

結果

8回計測して平均

switch case 249.5ms
ハッシュマップ 2065.25ms

当たり前ですが、さっきとあまり変わりませんね。二分探索のオーダーはO(log(n))なので、もっと分岐数が多ければ差は縮まるかもしれませんが、そんなに多くの分岐を使うことがまずないですね。

結論

switch case でいいやん。