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

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

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

所以不要为小事操心。我建议您考虑优化代码的其他部分。

你可以使用 Boost Flyweight 库来实习您的不可变字符串。字符串相等/不相等测试会变得非常快,因为在这一点上它所要做的就是比较指针(并非有意使用双关语)。

不 真正地 最好使用MMX 64位比较指令(请参阅 this page for an example) . 然而,这些操作是在寄存器上进行的,这些寄存器必须从内存中加载。内存负载会严重损害您的时间,因为您最多只能使用一级缓存,这会增加大约10倍的时间延迟*。如果你正在做一些繁重的字符串处理,你可能会得到一些漂亮的加速,但同样,它会伤害你。

其他人建议预先计算字符串。也许这对你的特定应用有用,也许不会。你…吗 有 比较字符串?你能比较一下数字吗?

您的编辑建议比较指针。这是一种危险的情况,除非您能够明确保证不会进行子字符串比较(即,您正在将一些双字节字符串:[0x40,0x50]与[0x40,0x42]进行比较)。这些字符串不是“相等”,但指针比较会说它们是相等的)。

您看过gcc strcmp()源代码了吗?我认为这样做是一个理想的起点。

真的很长 .

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

• 如果始终跟踪字符串的长度,则可以比较长度并使用 memcmp ,这比 strcmp . 如果您的应用程序是多文化的,请记住这只适用于 ordinal string comparison .
• 看来你正在使用C++。如果您只需要对不可变字符串进行相等比较,那么可以使用字符串内部解决方案(因为我是新用户,所以使用复制/粘贴链接)来确保相等的字符串存储在相同的内存位置,此时您可以简单地比较指针。看见 en.wikipedia.org/wiki/String_interning
• www.intel.com/products/processor/manuals/

编辑:如果您的问题域允许使用枚举,则 是 您的单周期比较解决方案。不要反抗。

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

如果不可行,还可以创建一个包含字符串和哈希的哈希字符串对象。大多数情况下,如果字符串不相等,则只需比较哈希。如果哈希值确实匹配,那么您必须进行完整的比较,以确保它不是误报。

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

订购有点困难。

编辑:显然,这个答案回避了试图在单个周期内进行字符串比较的实际问题。但这是唯一的方法,除非你碰巧有一系列指令,可以在恒定时间内查看无限量的内存,以确定strcmp的等效值。这是不可能的,因为如果你有这样一个架构,卖给你的人会说“嘿,这是一条很棒的指令,可以在一个周期内进行字符串比较!这有多棒?”你就不需要在stackoverflow上发帖了。

但这只是我合理的观点。

或者可以指导C++ 编译器删除重复的字符串, 根据他们的记忆位置?

不可以。编译器可能会在内部删除重复项,但据我所知,没有编译器能够保证或提供访问此类优化的工具(可能关闭它的情况除外)。当然,C++标准在这方面没有什么可说的。

假设你是说 x86 ... Here 是英特尔的文档。

但是我想,不,我认为你一次只能比较一个寄存器的大小。

出于好奇,你为什么这么问?我是最后一个过早调用Knuth的人,但是。。。 strcmp 通常做得很好。

编辑 :Link现在指向

您当然可以在一个周期中比较多个字节。以x86-64为例,一条指令最多可以比较64位(8字节)( cmps ),这不一定是一个周期,但通常为低个位数(确切的速度取决于特定的处理器版本)。

但是,这并不意味着您能够比以前更快地完成比较内存中两个阵列的所有工作 strcmp

1. 不仅仅是比较——你需要比较这两个值,检查它们是否相同,如果相同,就转到下一个块。
2. 字符串比较函数

除非你看到很多时间花在 字符串比较函数 ,我不担心-您是否有具体的问题/用例需要改进?

即使两个字符串都被缓存,也不可能在单个处理器周期内比较(任意长的)字符串。strcmp在现代编译器环境中的实现应该得到相当多的优化,因此您不应该费心进行太多优化。

编辑(回复您的编辑):

2. 通过将字符串添加到映射并在之后比较迭代器,您可能会获得更好的性能。。。然后,比较本身可能是一个周期(或不多)

3. 如果要使用的字符串集是固定的,则使用枚举-这就是它们的用途。

struct MultiEnum
{
    vector<MultiEnum*> enumList;
    MultiEnum()
    {
        enumList.push_back(this);
    }
    MultiEnum(MultiEnum& base)
    {
        enumList.assign(base.enumList.begin(),base.enumList.end());
        enumList.push_back(this);
    }
    MultiEnum(const MultiEnum* base1,const MultiEnum* base2)
    {
        enumList.assign(base1->enumList.begin(),base1->enumList.end());
        enumList.assign(base2->enumList.begin(),base2->enumList.end());
    }
    bool operator !=(const MultiEnum& other)
    {
        return find(enumList.begin(),enumList.end(),&other)==enumList.end();
    }
    bool operator ==(const MultiEnum& other)
    {
        return find(enumList.begin(),enumList.end(),&other)!=enumList.end();
    }
    bool operator &(const MultiEnum& other)
    {
        return find(enumList.begin(),enumList.end(),&other)!=enumList.end();
    }
    MultiEnum operator|(const MultiEnum& other)
    {
        return MultiEnum(this,&other);
    }
    MultiEnum operator+(const MultiEnum& other)
    {
        return MultiEnum(this,&other);
    }
};

MultiEnum 
    ¤someString,
    ¤someString1(¤someString),  // link to "someString" because it is a substring of "someString1"
    ¤someString2(¤someString);


void Test()
{
    MultiEnum a = ¤someString1|¤someString2;
    MultiEnum b = ¤someString1;

    if(a!=¤someString2){}
    if(b==¤someString2){}
    if(b&¤someString2){}
    if(b&¤someString){}  // will result in true, because someString is substring of someString1
}

另外,今天早上我确实有太多的空闲时间,但有时重新发明轮子太有趣了……)