标准字符串函数为什么比我的自定义字符串函数更快？

Question

我决定找到两个函数的速度：

• strcmp - 在string.h中定义的标准比较函数
• xstrcmp- 一个与参数相同、功能相同，只是由我创建的函数。

以下是我的xstrcmp函数：

int xstrlen(char *str)
{
    int i;
    for(i=0;;i++)
    {
        if(str[i]=='\0')
            break;
    }
    return i;
}

int xstrcmp(char *str1, char *str2)
{
    int i, k;
    if(xstrlen(str1)!=xstrlen(str2))
        return -1;
    k=xstrlen(str1)-1;
    for(i=0;i<=k;i++)
    {
        if(str1[i]!=str2[i])
            return -1;
    }
    return 0;
}

我不想依赖于strlen，因为我希望所有东西都是用户定义的。

所以，我找到了结果。strcmp每毫秒进行364次比较，而我的xstrcmp每毫秒只进行20次比较（至少在我的电脑上！）

有人能告诉我这是为什么吗？xstrcmp函数如何使自己如此快速？

- user1151738

---

“does the same”不准确……如果字符串长度不同，它会返回-1吗？此外，你的代码中有3个strlen()调用，它们的时间复杂度是O(n)。strcmp()不应该需要任何strlen()调用。 - FatalError

"由于我希望所有东西都是用户定义的。" 对于学习来说很好，但不要仅仅为了这个而重新实现已经存在的方法。 - Johan Lundberg

许多编译器会对 strcmp 和 strcpy 进行手动优化，产生非常紧凑的内联代码。 - Hot Licks

有人将GNU版本复制到了这个论坛帖子中：http://compsci.ca/v3/viewtopic.php?t=24383（第三篇帖子） - BoBTFish

@c.adhityaa - 这是高度优化的 GNU strlen 函数。从注释中可以看出：我们不使用传统循环来测试每个字符，而是一次测试一个长字。其中的棘手部分是测试所涉及的长字中的 任意四个 字节是否为零。 - rubber boots

Answer 1

if(xstrlen(str1)!=xstrlen(str2))    //computing length of str1
    return -1;                      
k=xstrlen(str1)-1;                  //computing length of str1 AGAIN!

你计算了str1的长度两次。这就是你的函数失败的原因之一。

此外，与（大多数）标准库定义的那些相比，你对xstrcmp的实现非常幼稚。例如，你的xstrcmp逐字节比较，而实际上它可以一次比较多个字节，利用正确的对齐方式，或者在实际比较之前进行一些预处理以对齐内存块。

- Nawaz

---

除此之外还有其他的优化方式吗？ - user1151738

@c.adhityaa 在数据处理任务中最重要的优化是找到尽可能快地访问内存中的数据的方法。通常，其他任何技巧都不会有太大帮助。 - rubber boots

比调用三次 strlen 更糟糕的是，这些调用都不是必需的。 - OrangeDog

@Nawaz，我正在检查glibc（2.21）的strcmp（）函数。那里没有使用内存块对齐技术，只使用了循环展开。如果使用内存对齐，它不会提供更好的性能吗？如果是这样，为什么没有使用呢？ - Soumen

Answer 2

strcmp和其他库函数是由经验丰富的工程师用汇编或专门的C代码编写，并使用多种技术。

例如，汇编实现可能一次将四个字节加载到寄存器中，并将该寄存器（作为32位整数）与另一个字符串的四个字节进行比较。在某些机器上，汇编实现可能会加载八个甚至更多字节。如果比较显示这些字节相等，则实现继续处理下一个四个字节。如果比较显示这些字节不相等，则实现停止。

即使有了这个简单的优化，还有许多问题需要处理。如果字符串地址不是四个字节的倍数，则处理器可能没有一条指令可以加载四个字节（许多处理器要求四个字节的加载使用四个字节的倍数地址）。根据处理器，实现可能必须使用较慢的非对齐负载，或者编写特殊代码以处理每个对齐情况，其中执行对齐加载并将字节移位到要比较的字节进行对齐。

当实现一次加载四个字节时，必须确保在可能导致分段错误的情况下不会加载超过终止空字符的字节（因为您尝试加载不可读取的地址而出错）。

如果这四个字节确实包含终止空字符，则实现必须检测并且不继续比较更多字节，即使当前四个字节在两个字符串中相等。

许多这些问题需要详细的汇编指令，并且在C中无法控制使用的确切指令。所使用的具体技术因处理器型号而异，并且从架构到架构都有很大差异。

- Eric Postpischil

---

+1，处理分段错误情况可以通过先执行非对齐的慢速测试，然后逐个字处理来轻松完成，这样可以确保所有4个字节来自同一缓存行（和内存页）。另一方面，在对齐的单词中检测终止字符并确定当空字符不是最后一个字符时的相等性要复杂得多。 - David Rodríguez - dribeas

@DavidRodríguez-dribeas：处理对齐的问题在于当你有多个字符串参数并且它们不必是类似地对齐时；如果一个字符串中的一个单词被对齐，那么来自另一个字符串的相应单词可能不是。有很多方法来处理这个问题，但它们可能会变得繁琐（比处理终止条件更加痛苦）。 - Stephen Canon

Answer 3

更快的strlen实现方法：

//Return difference in addresses - 1 as we don't count null terminator in strlen.
int xstrlen(char *str)
{
    char* ptr = str;
    while (*str++);
    return str - ptr - 1;
}

//Pretty nifty strcmp from here:
//http://vijayinterviewquestions.blogspot.com/2007/07/implement-strcmpstr1-str2-function.html
int mystrcmp(const char *s1, const char *s2)
{
    while (*s1==*s2)
    {
        if(*s1=='\0')
            return(0);
        ++s1;
        ++s2;
    }
    return(*s1-*s2);
}

如果我有时间，我会稍后做另一个。您还应该注意，大多数操作是用汇编语言或其他优化手段完成的，这比您自己编写的最佳纯C实现要快。

- John Humphreys

Answer 4

除了你代码中已经指出的问题外，至少在gcc-C-libs中，str和mem函数在大多数情况下都比较快，因为它们的内存访问模式被高度优化。

关于这个话题在SO上已经有一些讨论。

- rubber boots

Answer 5

试试这个：

int xstrlen(const char* s){
  const char* s0 = s;
  while(*s) s++;
  return(s - s0);
}

int xstrcmp(const char* a, const char* b){
  while(*a && *a==*b){a++; b++;}
  return *a - *b;
}

这可能可以通过一些循环展开来加速。

- Mike Dunlavey

---

@Mike，如果优化后的循环代码足够大以至于填满指令缓存，那么展开循环将无法加速程序。 - dadinck

strcmp需要进行365次比较，而你的xstrcmp只需要62次 - 效率提高了3倍。这是因为你的版本被优化得不够好。何不再加上十个strlen调用来增加乐趣呢？ - Jim Balter

Answer 6

1. 算法

您的strcmp实现可能有更好的算法。根本不需要调用strlen，因为每次调用strlen都会再次迭代整个字符串的长度。您可以在网上找到简单但有效的实现，可能最好的起点是：

// Adapted from http://vijayinterviewquestions.blogspot.co.uk
int xstrcmp(const char *s1, const char *s2)
{
  for (;*s1==*s2;++s1,++s2)
  {
    if(*s1=='\0') return(0);
  }
  return(*s1-*s2);
}

那并不能做到所有事情，但应该是简单的并且在大多数情况下都能工作。

2. 编译器优化

这是一个愚蠢的问题，但请确保在编译时打开了所有优化开关。

3. 更复杂的优化

编写库的人通常会使用更高级的技术，例如一次加载4字节或8字节的整数进行比较，并且只有在整个匹配时才比较单个字节。你需要成为专家才能知道什么对于这种情况是适当的，但你可以在stackoverflow（链接？）上找到人们讨论最有效的实现。

某些平台的标准库函数可能会手写汇编代码，如果程序员知道有比编译器更有效的实现方式。现在这种情况越来越少见，但在某些嵌入式系统上可能很常见。

4. 链接器与标准库“作弊”

通过一些标准库函数，链接器可能能够使您的程序以比调用代码中的函数更少的开销来调用它们，因为它被设计为了解有关特定函数内部的更多信息（链接？）我不知道这是否适用于此情况，可能不是，但这是您必须考虑的事情。

5. 好的，好的，我明白了，但是什么时候应该实现自己的strcmp？

我想到的唯一原因是：

• 你想学习如何实现。这是一个很好的理由。
• 您正在为没有足够好的标准库的平台编写代码。这是非常不可能的。
• 字符串比较已被证明是代码中的重要瓶颈，并且您知道有关您的字符串的某些特定信息，这意味着您可以比朴素算法更有效地比较它们。 （例如，所有字符串都分配了8字节对齐，或者所有字符串都具有N字节前缀。）这是非常非常不可能的。

6. 但是...

好的，您为什么要避免依赖strlen？您担心代码大小吗？担心代码或可执行文件的可移植性吗？

如果有充分的理由，可以提出另一个问题，也许会得到更具体的答案。所以如果我漏掉了一些显而易见的东西，我很抱歉，但通常依赖标准库会更好，除非你有特定的改进要求。

- Jack V.