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

Question

我决定找到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函数如何使自己如此之快？

Answer 1

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

你正在计算str1TWICE 的长度.这就是你的功能失去游戏的一个原因.

此外,xstrcmp与(大多数)标准库中定义的实现相比,您的实现非常幼稚.例如,您一次xstrcmp比较一个字节,实际上它可以一次比较多个字节,也可以利用正确的对齐,或者在实际比较之前可以进行少量预处理以对齐存储块.

Answer 2

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

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

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

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

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

其中许多问题需要详细的汇编指令,并且C中没有对所使用的确切指令的所需控制.所使用的确切技术从处理器模型到处理器模型各不相同,并且从架构到架构有很大差异.

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实现更快.