一个时钟周期内的C++字符串比较

Question

是否可以在单个处理器周期中比较整个存储器区域？更准确地说,是否可以使用某种MMX汇编程序指令在一个处理器周期中比较两个字符串？或者是strcmp- 已经基于该优化的实现？

编辑:或者是否可以指示C++编译器删除字符串重复项,以便可以简单地通过内存位置比较字符串？而不是memcmp(a,b)通过a==b(假设a和b都是本机const char*字符串)进行比较.

Answer 1

只需使用标准C strcmp()或C++ std::string::operator==()进行字符串比较.

它们的实现相当不错,可能编译成一个非常高度优化的程序集,即使是有才华的程序集程序员也会发现难以匹配.

所以不要为小东西出汗.我建议您考虑优化代码的其他部分.

Answer 2

您可以使用Boost Flyweight库来实现您的不可变字符串.字符串相等/不等式测试然后变得非常快,因为在那一点上它必须做的就是比较指针(双关语).

Answer 3

不是真的.典型的1字节比较指令需要1个周期.您最好的选择是使用MMX 64位比较指令(请参阅此页面的示例).但是,那些操作寄存器,必须从存储器加载.内存负载会显着损害您的时间,因为您最多会出现L1缓存,这会增加10倍的时间减速*.如果你正在做一些繁重的字符串处理,你可能会在那里获得一些漂亮的加速,但同样,它会受到伤害.

其他人建议预先计算字符串.也许这对你的特定应用程序有效,也许不会.你需要比较字符串吗？你能比较数字吗？

您的编辑建议比较指针.这是一个危险的情况,除非你能特别保证你不会进行子字符串比较(即你正在比较一些两个字节的字符串:[0x40,0x50]和[0x40,0x42].那些不是"相等",而是指针比较会说它们是).

你看过gcc strcmp()来源了吗？我建议这样做是理想的起点.

*松散地说,如果一个循环需要1个单位,一个L1命中需要10个单位,一个L2命中需要100个单位,而实际的RAM命中需要很长时间.

Answer 4

在一个周期内执行通用字符串操作是不可能的,但是可以使用额外信息进行许多优化.

• 如果您的问题域允许对适合机器寄存器的字符串使用对齐的固定大小缓冲区,则可以执行单周期比较(不计算加载指令).
• 如果你总是跟踪字符串的长度,你可以比较长度和使用memcmp,这比快strcmp.如果您的应用程序是多文化的,请记住,这仅适用于序数字符串比较.
• 看来你正在使用C++.如果您只需要与不可变字符串进行相等比较,则可以使用字符串实习解决方案(复制/粘贴链接,因为我是新用户)以保证相同的字符串存储在同一个内存位置,此时您可以简单地比较指针.请参阅en.wikipedia.org/wiki/String_interning
• 另外,请参阅英特尔优化参考手册第10章,了解有关SSE 4.2文本处理说明的详细信息.www.intel.com/products/processor/manuals/

编辑:如果您的问题域允许使用枚举,那就是您的单周期比较解决方案.不要打它.

Answer 5

这取决于你做了多少预处理.C#和Java都有一个名为interning strings的进程,如果它们具有相同的内容,它们会使每个字符串映射到相同的地址.假设有这样的过程,您可以使用一条比较指令进行字符串相等性比较.

订购有点困难.

编辑:显然,这个答案正在回避尝试在一个周期内进行字符串比较的实际问题.但这是唯一的方法,除非您碰巧有一系列指令可以在恒定时间内查看无限量的内存以确定strcmp的等效值.这是不可能的,因为如果你有这样一个架构,把它卖给你的人会说"嘿,这是一个很棒的指令,可以在一个循环中做一个字符串比较!那真是太棒了？" 而且您不需要在stackoverflow上发布问题.

但这只是我的理由.

Answer 6

如果您正在优化字符串比较,则可能需要使用字符串表(然后您只需要比较两个字符串的索引,这可以在单个机器指令中完成).

如果这不可行,您还可以创建包含字符串和哈希的散列字符串对象.那么大多数时候你只需要比较字符串不相等的哈希值.如果哈希确实匹配,你必须做一个完整的比较,但要确保它不是误报.