switch-case 的替换 - c++ | 梧—

switch-case 是我们常用的一种语法，几乎所有的语言都有这种语法，可以根据变量的不同情况进行对应处理。但 switch-case 仅支持整型（int），字符（char）和枚举 (enum)，而且 switch-case 实现应该是类似 multi-if，在情况较多时效率较低，并且代码可读性会降低，所以这次想思考下如何优化。

# 1. 优化方式

一次 switch-case 的过程其实就是一次寻找元素的过程。而在元素固定的情况下，寻找元素，最快的结构就是 HashTable，也就是 c++ 的 unordered_map。只要通过将处理函数抽象成通用函数便可以利用。
like this:

	enum CASE
	{
	CASE_1,
	};

	struct Param
	{
	int param = 0;
	};

	unordered_map<int, function<void(Param)>> mapFunc;

	void handle(CASE eCase, Param param)
	{
	auto it = mapFunc.find((int)eCase);
	if (it != mapFunc.end())
	{
	it->second(param);
	}
	else
	{
	cout << "error" << endl;
	}
	}

	// 注册处理函数
	mapFunc[(int)CASE_1] = [](Param param) {
	cout << "handle case 1" << endl;
	};

这样，就实现了使用 unordered_map 来完成 switch-case 的工作。当 case 较多，处理函数较复杂时，这样可以有效地减少代码的复杂度。并且因为 unordered_map 使用的是 hashtable 的树结构，所以相比比 switch-case 有更好的时间效率（理论上）。

# 2. 性能对比

刚才对于性能的对比是基于理论的猜想，实际性能需要数据支持，于是我写了下面的测试代码：

	unordered_map<int, function<void(Param)>> mapFunc =
	{
	{CASE_1, [](Param param) {}},
	{CASE_2, [](Param param) {}},
	{CASE_3, [](Param param) {}},
	{CASE_4, [](Param param) {}},
	{CASE_5, [](Param param) {}},
	};

	vector<pair<int, function<void(Param)>>> vectorFunc =
	{
	make_pair(CASE_1, [](Param param) {}),
	make_pair(CASE_2, [](Param param) {}),
	make_pair(CASE_3, [](Param param) {}),
	make_pair(CASE_4, [](Param param) {}),
	make_pair(CASE_5, [](Param param) {}),
	};

	void handleWithMap(CASE eCase, Param param)
	{
	auto it = mapFunc.find((int)eCase);
	if (it != mapFunc.end())
	{
	it->second(param);
	}
	else
	{
	cout << "error" << endl;
	}
	}

	void handleWithVector(CASE eCase, Param param)
	{
	auto it = find_if(vectorFunc.begin(), vectorFunc.end(), [&](const pair<int, function<void(Param)>> &func) -> bool {
	return eCase == func.first;
	});
	if (it != vectorFunc.end())
	{
	it->second(param);
	}
	else
	{
	cout << "error" << endl;
	}
	}

	void handleWithSwitch(CASE eCase, Param param)
	{
	switch (eCase)
	{
	case CASE_1:
	{
	}
	break;
	case CASE_2:
	{
	}
	break;
	case CASE_3:
	{
	}
	break;
	case CASE_4:
	{
	}
	break;
	case CASE_5:
	{
	}
	break;
	default:
	{
	}
	break;
	}
	}

	int main()
	{
	int times = 10000000;
	struct timeval start;
	struct timeval end;
	gettimeofday(&start, NULL);
	srand(123);
	for (int i = 0; i < times; i++)
	{
	CASE randCase = static_cast<CASE>(rand() % 5);
	handleWithMap(randCase, Param());
	}
	gettimeofday(&end, NULL);
	double time_use = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
	cout.setf(ios::fixed);
	cout << "time:" << time_use / 1000 << "ms" << endl;

	gettimeofday(&start, NULL);
	srand(123);
	for (int i = 0; i < times; i++)
	{
	CASE randCase = static_cast<CASE>(rand() % 5);
	handleWithSwitch(randCase, Param());
	}
	gettimeofday(&end, NULL);
	time_use = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
	cout << "time:" << time_use / 1000 << "ms" << endl;

	gettimeofday(&start, NULL);
	srand(123);
	for (int i = 0; i < times; i++)
	{
	CASE randCase = static_cast<CASE>(rand() % 5);
	handleWithVector(randCase, Param());
	}
	gettimeofday(&end, NULL);
	time_use = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
	cout << "time:" << time_use / 1000 << "ms" << endl;

	return 0;
	}

结果有些出乎意料：

"map:1711.493000ms"
"switch:285.326000ms"
"vector:1442.688000ms"

switch-case 的效率和 stl 相比快了很多，难道 switch-case 的实现原理不是挨个对比？

于是我又通过测试代码，获取对应汇编：

	int main()
	{
	int a, sc = 1;
	switch (sc)
	{
	case 1:
	a = 1;
	break;
	case 2:
	a = 2;
	break;
	}
	}

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 1
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, 1
        je      .L3
        cmp     eax, 2
        je      .L4
        jmp     .L2
.L3:
        mov     DWORD PTR [rbp-8], 1
        jmp     .L2
.L4:
        mov     DWORD PTR [rbp-8], 2
        nop
.L2:
        mov     eax, 0
        pop     rbp
        ret

大概可以看到 switch-case 就是简单的比较和跳转，时间复杂度理论上是 O (n)，但实际上为什么 switch-case 会比 O (1) 的 unordered_map 和 O (n) 的 vector 效率相差这么多呢？我用的是 O0 的优化，使用了 5 个 case，猜想可能和优化等级和 case 数目有关？于是我使用不同数目的 case 在 O0 和 O2 下做了性能统计。(如何使用变量控制 n 个 case，头疼了蛮久，不太会使用宏去生成，用脚本去生成 c++ 代码又觉得有些浪费，最后网上找到这篇博客：用 C 语言宏批量生成代码的思考与实现，使用博主提供的头文件，使用宏生成了测试代码 ——switchcaseOptTest)

	unordered_map	switch-case	vector	array
O0，case-5	1610ms	287ms	1393ms	584ms
O0，case-100	1718ms	318ms	8346ms	622ms
O0，case-255	1929ms	326ms	17491ms	1278ms
O2，case-5	229ms	60ms	181ms	200ms
O2，case-100	278ms	60ms	472ms	239ms
O2，case-255	312ms	60ms	805ms	314ms

发现不论在 O0 还是 O2 的情况下，switch-case 的效率都是最高的，而且在 O2 的情况下几乎不会随着 case 数增长而增长；map 消耗时间随 case 数缓慢增长而 vector 随 case 数接近线性增长。

这与我们理论上得到的结论大相径庭。(网上找到一篇 go 中类似的性能对比 map vs switch performance in go，其中使用 slice 代替 switch-case，效率得到了一定的提升，于是我在测试中加入了 array，但实际性能和 unordered_map 类似）

# 3.switch-case 原理

根据 Advantage of switch over if-else statement 了解到，通常情况下编译器会为 switch-case 建立二叉决策树或者建立跳转表，因此和 multi-if 的遍历的做法其实是不一样的，效率回避 multi-if 高很多。

但是决策树和跳转表的结构照理和 stl 的 map 和 unordered_map 的结构类似，但是为什么效率还是差了很多呢？我猜测是由于 stl 的结构占得内存较大，默认的 switch-case 结构占得内存较小，在 cache 机制中容易整段进入 cache，所以效率较高，但是我也没细究了。

# 4. 结论

switch-case 作为原生的机制，效率还是非常高的，在百个 case 这个量级下比 stl 的容器效率高很多（目前大多项目一个 case 百量级应该够用了），但 switch-case 在 case 较多的情况下，即使每个 case 只用一个函数可读性感觉还是没那么好，所以在效率没那么敏感，case 较多的情况下还是用一些结构如 map 等去整理 case 比较好。

switch-case

# 1. 优化方式

# 2. 性能对比

# 3.switch-case 原理

# 4. 结论

机器学习与AI

proto2和proto3兼容的一次尝试