c++ - 什么是更有效的 switch case 或 std::map

Question

我正在考虑这里的分词器。
每个标记在解析器中调用不同的函数。
什么更高效:

• std::functions/boost::functions 的映射
• 一个开关盒

Answer 1

我建议阅读 switch() vs. lookup table?来自 Joel 的软件。特别是，这个回应很有趣:

" Prime example of people wasting time trying to optimize the least significant thing."

Yes and no. In a VM, you typically call tiny functions that each do very little. It's the not the call/return that hurts you as much as the preamble and clean-up routine for each function often being a significant percentage of the execution time. This has been researched to death, especially by people who've implemented threaded interpreters.

在虚拟机中，存储计算地址以供调用的查找表通常比交换机更受欢迎。 (直接线程，或“标签作为值”。直接调用存储在查找表中的标签地址)这是因为它允许在某些条件下减少 branch misprediction ，这在长流水线 CPU 中非常昂贵(它会强制刷新流水线)。但是，它会降低代码的可移植性。

这个问题已经在 VM 社区中进行了广泛的讨论，如果您想了解更多相关信息，我建议您查找该领域的学术论文。 Ertl & Gregg 在 2001 年就这个主题写了一篇很棒的文章，The Behavior of Efficient Virtual Machine Interpreters on Modern Architectures

但如前所述，我很确定这些细节与您的代码无关。这些都是小细节，你不应该过分关注它。 Python 解释器使用开关，因为他们认为它使代码更具可读性。你为什么不选择你最舒服的用法呢？性能影响会比较小，你现在最好关注代码的可读性；)

编辑:如果重要，使用哈希表总是比查找表慢。对于查找表，您使用枚举类型作为“键”，并使用单个间接跳转检索值。这是一个单一的装配操作。 O(1)。哈希表查找首先需要计算一个哈希值，然后检索值，这要昂贵得多。

使用存储函数地址的数组，并使用枚举的值进行访问是好的。但是使用哈希表来做同样的事情会增加一个重要的开销

总而言之，我们有:

• 成本(Hash_table) >> 成本(direct_lookup_table)
• cost(direct_lookup_table) ~= cost(switch) 如果您的编译器将开关转换为查找表。
• cost(switch) >> cost(direct_lookup_table) (O(N) vs O(1)) 如果你的编译器不翻译开关和使用条件，但我想不出有任何编译器这样做。
• 但内联直接线程会降低代码的可读性。