与字符串函数相关的代码优化

字符串函数供您使用。如果需要比较两个字符串,请调用 strcmp . 不要担心性能上的细微差别,因为这些差别大多是想象出来的。先让代码工作。

首先,要回答有关性能的任何问题,如果您问“多少优化将…”,答案是“配置文件!”没人能预测出什么东西跑得有多快。c stdlib的实现已经在 年 ,任何你试图想出的优化技巧都可能会伤害它。

例如,我认为gcc在比较字符串时会使用矢量化,所以实际上您一次要比较4-8个元素。你在等吗?做你的单字比较实际上可能会减慢速度。

也就是说,一个典型的实现只是检查字符,所以您只需将一个比较移出循环,就不会获得净收益。(但如前所述,可能是净损失!)

因此,指导方针是:

现在编程,稍后优化。

优化合理的方法:用证据和测试,而不是猜测。

担心 strcmp() 大部分时间都是微观优化——不值得付出努力。还有其他事情需要警惕,例如:

for (i = 0; i < strlen(s); i++)
{
     ...do stuff with s[i]...
}

优化器可能没有意识到它可以并且应该避免每次循环迭代时的函数调用-如果您增加 s 在循环中,它可能无法避免。那太贵了。

很久以前,我使用的函数 strstr() 在20kb左右的缓冲区上,程序在我开发它的HP设备上运行良好。我把它移植回一台太阳机器(记住,这是20年前的事了——问题已经解决了很久),程序甚至都没有爬行——它实际上是静止的。结果发现问题是一个循环 字符串() 其中使用 strlen() 或多或少如上图所示。当用于短缓冲区时,没有一个主要的问题;当用于20KB缓冲区时,搜索每隔几KB出现的模式,可怜的机器就会停止工作。通过分析应用程序显示了问题。我接通了代理 strstr()。 这样就避免了错误,事情又恢复了正常。

另一个常见的缓慢的来源是使用 strcat() . 例如:

strcpy(dst, name);
strcat(dst, "/subdir/");
strcat(dst, file);
strcat(dst, ".sfx");

通常,这些实际上并不是性能问题的根源——但在没有相反证据的情况下,它可能是缓冲区溢出的根源。你需要知道长度足够小 dst .但是,如果你知道每一位的长度(你应该确保它们适合),你可以写:

strcpy(dst, name);
dst += len_name;
strcpy(dst, "/subdir/");
dst += sizeof("/subdir/") - 1;
strcpy(dst, file);
dst += len_file;
strcpy(dst, ".sfx");

这就节省了在添加新材料之前重复扫描已知长度的字符串以查找结尾的时间。对于短字符串,这并不重要;对于长字符串和许多连接操作,这可能很重要。和以前一样,关键是衡量成本。

Kernighan和Pike有一个有趣的故事,讲的是如何提高书中垃圾邮件过滤器的性能。 he Practice of Programming '.它开始使用 字符串() 在一个循环中;它以一个非常不同的设计结束,因为 字符串() 设计的垃圾邮件过滤系统不符合要求。但是,同样地,他们只做了这些工作,因为已经证明存在性能问题,并且他们做了足够的工作来防止程序成为系统上的瓶颈,而不是更多。

它不会提供任何优化,因为这正是strcmp()所做的。

一般来说,由于str…()函数的使用量很大,所以您可以依赖库编写器尽可能高效地实现它们。只有在您编写了自己使用这些函数的代码,发现有问题,并使用探查器跟踪它之后,才应该考虑编写替换代码。

学习 glibc implementation of strlen 以下内容:

• 不检查空参数(甚至不检查断言)
• 字符串按字节进行比较,直到到达长字对齐的地址。之后,所有的比较都以4字节或8字节的块进行。
• 没有矢量化或特定于体系结构的东西(即没有ifdefs)。
• 当一次比较4或8个字节时,最棘手的部分是在比较失败时找出哪个字节是零。

你可能对 this article (乔尔·斯波斯基)这是关于低级(尤其是C字符串)函数以及它们是如何优化的。

<sarcasm>

与其他答案相反,关于你的陈述:

例如,在调用strcmp之前,比较两个字符串的第一个字符(并检查它们是否相等)会提供多少优化?

我想这是一个 杰出的 想法。所以,我们应该这样做:

int compstr(const char *a, const char *b)
{
   if (*a == *b) return strcmp(a+1, b+1);
   else return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

但是,为什么停在那里?我们应该再检查一个字符,以便更好地优化:

int compstr(const char *a, const char *b)
{
    size_t i;
    for (i=0; *a == *b && i < 2; ++a, ++b, ++i)
        if (*a == 0)
            return 0;
    if (i == 2) return strcmp(a, b);
    return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

当然,我们可以做得更好。让我们将要比较的字符数设为一个参数:

/* Really fast implementation to compare strings,
   takes the optimization parameter n_comp */
int compstr(const char *a, const char *b, size_t n_comp)
{
    int i;
    for (i=0; *a == *b && i < n_comp; ++a, ++b, ++i)
        if (*a == 0)
            return 0;
    if (i == n_comp) return strcmp(a, b);
    return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

但是,如果我们要把前几个字符进行比较,那么为什么不自己来做呢?所以,这里是最后一个完全优化的版本:

/* Final, highly optimized function to compare strings */
int strcmp (const char *a, const char *b)
{
    for (; *a == *b; ++a, ++b)
        if (*a == 0)
            return 0;
    return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

在写了我们的版本之后,我们很高兴地发现它是 identical 到P.J.Plauger的版本 标准C库 (当然,它也避免了好的库会使用的任何特定于体系结构的优化)!

</sarcasm>

换句话说,正如其他人所说,提前优化是没有意义的。

注释 :我还没有真正检查上面的代码片段是否正确。避免重新发明轮子的另一个原因是:你必须自己努力工作!

乔纳森是绝对正确的,尤其是 strlen(s) 例如,我通过一个stackshot找到(在其他人的代码中为-)。

你说的是微观优化,这是在你不这样做之后应该担心的事情。 tuned the blazes out of the code .在调用前比较第一个字符 strcmp 由于函数入口/出口的开销,确实节省了一些时间,但我的经验法则是,只有那些调用 字符串比较函数 成本超过10%。

标准的C运行时字符串是非常优化的。除了利用C-Runtime所不具备的关于问题域的知识之外,您不太可能改进它。

你关于预测试第一个字符的想法有一些优点——如果你的大多数比较都是在不同的字符串之间进行的。(即大多数都会失败)。在这种情况下,可以避免函数调用的开销。

但是,比较匹配的字符串会更昂贵!

当给定匹配的字符串时,strcmp是最昂贵的。因此,如果您的算法将传递相同的指针作为strcmp的两个参数,您可以通过首先比较指针进行优化。只有您才能知道您的代码是否真的会经常这样做,值得这样做。

我唯一的建议是:不要使用 strcat . 当然,它既快又容易,但是你用得越多,它就越贵。最好跟踪字符串的结尾和strcpy的结尾。

C标准库很好,因为它非常优化。一些编译器内嵌CRT函数,这样可以节省调用指令的开销。 但是,如果您仍然想要更高的速度,有几个选项可用。如果您访问我给您的这个链接,您将能够下载一个程序,它包含一些由专业汇编语言程序员编写的strcmp例程。

http://www.masm32.com/board/index.php?topic=2508.0

我特别想看看论坛成员Lingo写的功能。这家伙写了我见过的最快的汇编代码。

如果您不知道如何在C程序中使用汇编语言函数,只需再问一个stackoverflow问题,许多人(包括我)都可以帮助您。

下面是比较字符串abcdefg和abcz时得到的结果

lstrcmp - original (from Microsoft) : 19314 clocks; Return value: 1
lstrcmp - kunt0r  : 957 clocks; Return value: 24832
lstrcmp - Lingo   : 501 clocks; Return value: 1

从时钟的数量来看(越少越好),其他函数的速度就快得多。

在调用C中的标准字符串函数之前,是否有可用的指导原则?

是的:不要担心哪个库函数比其他函数快或慢,也不要担心如何在微观上将它们调整得更快(或更慢!).相反,找到能让你最清楚地表达你的意图的功能。

最后,如果您有证据表明您的应用程序速度太慢,那么您可以分析并查看字符串函数是否与您的问题有关。如果改进更可能来自像Boyer Moore这样的次线性算法,而不是通过调整 strcmp .

迈克尔A.杰克逊的两条优化规则:

1. 不要这样做。

2. (仅供专家使用)暂时不要这样做。

我认为重要的一点是,每个与字符串相关的存储库/数据库可能都有其自身的特性,这些特性可以被操作或用于创建最佳的字符串操作函数。 然而,在本文中,有些场合有一些简单的技巧-您可以选择适合您需要的并使用它: http://www.codemaestro.com/articles/21