the*_*row 27 c++ parsing tokenize
我在这里考虑令牌化器.
每个标记在解析器内调用不同的函数.
什么更有效:
Nic*_*zet 34
我建议阅读switch()与查找表？来自Joel on Software.特别是,这种反应很有趣:
"人们浪费时间试图优化最不重要的事情的典型例子."
是的,不是.在VM中,您通常会调用每个函数都很少的微小函数.这不是因为每个函数的前导码和清理例程经常占执行时间的重要百分比而对你造成伤害的呼叫/返回.这已经被研究过死亡,特别是那些已经实施了线程解释器的人.
在虚拟机中,存储计算地址以进行调用的查找表通常优先于交换机.(直接线程,或"标签为值".直接调用存储在查找表中的标签地址)这是因为它允许在某些条件下减少分支错误预测,这在长流水线CPU中非常昂贵(它强制冲洗管道).但是,它使代码不那么便携.
此问题已在VM社区中进行了广泛讨论,如果您想了解更多相关信息,我建议您在此字段中查找学者论文.Ertl&Gregg在2001年写了一篇关于这个主题的精彩文章,关于现代建筑的高效虚拟机解释器的行为
但如上所述,我很确定这些细节与您的代码无关.这些都是小细节,你不应该过分关注它.Python解释器使用开关,因为他们认为它使代码更具可读性.你为什么不选择最舒服的用法？性能影响相当小,您现在最好关注代码可读性;)
编辑:如果重要,使用哈希表将始终比查找表慢.对于查找表,可以使用枚举类型作为"键",并使用单个间接跳转检索值.这是一个单独的装配操作.O(1).哈希表查找首先需要计算哈希值,然后检索值,这样更昂贵.
使用存储函数地址的数组,并使用枚举值访问是很好的.但是使用哈希表来做同样的事情会增加一个重要的开销
总之,我们有:
use*_*637 22
随着Visual Studio 2008附带的STL Map将为每个函数调用提供O(log(n)),因为它隐藏了下面的树结构.使用现代编译器(取决于实现),一个switch语句将为您提供O(1),编译器将其转换为某种查找表.所以一般来说,切换速度更快.
但是,请考虑以下事实:
map和switch之间的区别在于:Map可以动态构建,而switch也不能.Map可以包含任意类型作为键,而switch仅限于c ++ Primitive类型(char,int,enum等...).
顺便说一句,你可以使用哈希映射来实现几乎O(1)调度(但是,根据哈希表的实现,在最坏的情况下它有时可能是O(n)).尽管如此,开关仍然会更快.
编辑
我写这篇文章的目的只是为了好玩和讨论
我可以为您推荐一个很好的优化,但这取决于您的语言的性质以及您是否可以期望如何使用您的语言.
编写代码时:将令牌分为两组,一组经常使用非常高,另一组经常使用低.您还可以对经常使用的高级令牌进行排序.对于高频率令牌,您可以编写一个if-else系列,其中常用的频率最高.对于经常使用的低,你写一个switch语句.
我们的想法是使用CPU分支预测,以便甚至避免另一个间接级别(假设if语句中的条件检查几乎是无成本的).在大多数情况下,CPU将选择正确的分支而没有任何间接级别.然而,他们将是少数情况下分支将去错误的地方.根据你的语言的性质,统计它可以提供更好的表现.
编辑:由于下面的一些评论,更改了句子告诉编译器将总是转换为LUT.