34

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

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

6 回答 6

39

我建议阅读switch() 与查找表？来自 Joel 的软件。特别是，这个回应很有趣：

“人们浪费时间试图优化最不重要的事情的典型例子。”

是和不是。在 VM 中，您通常会调用微小的函数，而每个函数都做的很少。伤害你的不是调用/返回，因为每个函数的序言和清理例程通常占执行时间的很大一部分。这已经被研究死了，特别是那些已经实现线程解释器的人。

在虚拟机中，存储要调用的计算地址的查找表通常比交换机更受欢迎。（直接线程，或“标签作为值”。直接调用存储在查找表中的标签地址）这是因为它允许在某些条件下减少分支预测错误，这在长流水线 CPU 中非常昂贵（它强制刷新管道）。但是，它使代码的可移植性降低。

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

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

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

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

总结一下，我们有：

  • 成本（哈希表）>>成本（direct_lookup_table）
  • cost(direct_lookup_table) ~= cost(switch) 如果您的编译器将开关转换为查找表。
  • cost(switch) >> cost(direct_lookup_table) (O(N) vs O(1)) 如果您的编译器不转换开关并使用条件，但我想不出任何编译器会这样做。
  • 但是内联直接线程使代码的可读性降低。
于 2009-05-31T12:20:15.387 回答
26

Visual Studio 2008 附带的 STL Map 将为您提供每个函数调用的 O(log(n))，因为它在下面隐藏了一个树结构。使用现代编译器（取决于实现），switch 语句将为您提供 O(1) ，编译器将其转换为某种查找表。所以一般来说，切换速度更快。

但是，请考虑以下事实：

map 和 switch 的区别在于： map 可以动态构建，而 switch 不能。Map 可以包含任意类型作为键，而 switch 仅限于 c++ 原始类型（char、int、enum 等）。

顺便说一句，您可以使用散列映射来实现接近 O(1) 的调度（虽然，取决于散列表的实现，在最坏的情况下有时可能是 O(n)）。即使 ， switch 仍然会更快。

编辑

我写以下内容只是为了好玩和讨论的问题

我可以为您建议一个很好的优化，但这取决于您的语言的性质以及您是否可以预期您的语言将被如何使用。

编写代码时：您将令牌分为两组，一组将是非常常用的，另一组将是低常用的。您还可以对频繁使用的令牌进行排序。对于频繁使用的标记，您编写一个 if-else 系列，使用频率最高的首先出现。对于低常用的，你写一个switch语句。

这个想法是使用 CPU 分支预测来避免另一个级别的间接性（假设 if 语句中的条件检查几乎没有成本）。在大多数情况下，CPU 会选择正确的分支而无需任何间接级别。但是很少有分支会去错误的地方。根据您语言的性质，统计上它可能会提供更好的性能。

编辑：由于下面的一些评论，改变了这句话告诉编译器总是将开关转换为 LUT。

于 2009-05-31T11:56:13.717 回答
3

你对“高效”的定义是什么？如果您的意思是更快，那么您可能应该分析一些测试代码以获得明确的答案。但是，如果您追求灵活且易于扩展的代码，那么请帮自己一个忙并使用 map 方法。其他一切都只是过早的优化......

于 2009-05-31T11:59:48.687 回答
2

就像 yossi1981 说的那样，可以优化开关以使用快速查找表，但不能保证，每个编译器都有其他算法来确定是否将开关实现为连续的 if 或快速查找表，或者两者的组合。

要获得快速切换，您的值应符合以下规则：它们应该是连续的，例如 0、1、2、3、4。您可以省略一些值，但像 0、1、2、34、43 这样的值极不可能被优化。

真正的问题是：您的应用程序中的性能是否如此重要？从文件中动态加载其值的映射不会比跨越多页代码的巨大语句更具可读性和可维护性吗？

于 2009-05-31T12:08:05.753 回答
1

你没有说你的令牌是什么类型。如果它们不是整数，则您别无选择 - 开关仅适用于整数类型。

于 2009-05-31T12:02:42.380 回答
0

C++ 标准没有说明其要求的性能，只是说功能应该在那里。

除非您说明您正在谈论哪种实现，否则这些关于哪个更好、更快或更有效的问题是没有意义的。例如，某个 JavaScript 实现的某个版本中的字符串处理非常糟糕，但您不能将其推断为相关标准的一个特性。

我什至会说，无论实现如何都无关紧要，因为switchand提供的功能std::map是不同的（尽管有重叠）。

在我看来，这些微优化几乎是不必要的。

于 2009-05-31T12:12:26.807 回答