22

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

  • 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 函数做了什么让自己变得如此之快？

4

6 回答 6

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

您正在计算str1TWICE 的长度。这就是你的函数输掉比赛的原因之一。

xstrcmp此外，与（大多数）标准库中定义的相比，您的实现非常幼稚。例如，您xstrcmp一次比较一个字节，而实际上它可以一次比较多个字节，也可以利用适当的对齐，或者在实际比较之前可以做很少的预处理以对齐内存块。

于 2012-07-17T12:34:19.760 回答
27

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

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

即使进行了这种简单的优化，也有许多问题需要处理。如果字符串地址不是四个字节的倍数，则处理器可能没有将加载四个字节的指令（许多处理器需要四字节加载才能使用与四个字节的倍数对齐的地址）。根据处理器的不同，实现可能必须使用较慢的未对齐加载或为每个对齐情况编写特殊代码，以执行对齐加载和移位寄存器中的字节以对齐要比较的字节。

当实现一次加载四个字节时，它必须确保它不会加载超出终止空字符的字节，如果这些字节可能导致段错误（错误，因为您试图加载一个不可读的地址）。

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

其中许多问题需要详细的汇编指令，而对所使用的确切指令的所需控制在 C 中不可用。所使用的确切技术因处理器模型而异，并且因架构而异。

于 2012-07-17T12:47:04.643 回答
5

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 实现要快。

于 2012-07-17T12:48:17.047 回答
4

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

已经就 SO的主题进行了一些讨论。

于 2012-07-17T12:34:26.927 回答
2

试试这个：

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;
}

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

于 2012-07-17T12:50:04.100 回答
1

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 字节的 int，然后比较它，如果整个匹配，则只比较单个字节。您需要成为专家才能知道什么适合这种情况，但是您可以找到人们讨论堆栈溢出最有效的实现（链接？）

如果编码人员可以知道存在比编译器可以找到的更有效的实现，则某些平台的某些标准库函数可能是用汇编手工编写的。现在这种情况越来越少见，但在某些嵌入式系统上可能很常见。

4. 链接器“欺骗”标准库

使用一些标准库函数，链接器可以让你的程序调用它们的开销比在代码中调用函数要少，因为它旨在更多地了解函数的特定内部结构（链接？）我不知道是否这适用于这种情况，它可能不适用，但这是你必须考虑的事情。

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

在我看来，这样做的唯一原因是：

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

6. 但是……

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

如果有充分的理由，请打开另一个问题，可能会有更具体的答案。因此，如果我遗漏了一些明显的东西，我很抱歉，但是依赖标准库通常会好得多，除非你想改进一些特定的东西。

于 2012-07-18T12:23:03.967 回答