比较两个字符串的最佳或最快方法是什么？

Question

我不确定下面的代码有多快。如果有人知道比这更快/更优化的代码，请告诉我。

int xstrcmp(char *s1, char *s2)
{
  while (*s1 == *s2++)
            if (*s1++ == 0)
                    return (0);
  return (*(const unsigned char *)s1 - *(const unsigned char *)(s2-1));
}

- Jatin

---

你要比较的字符串有多长？它们来自哪里？ - R. Martinho Fernandes

这是一道作业题吗？如果不是，请使用供应商提供的问题。他们可能有更多的技巧可以利用处理器/编译器的特殊性。 - Ed Heal

如何找出供应商提供的代码？ - Jatin

您的函数签名有误：参数应为 char const*。 - Dietmar Kühl

我想知道是否有人将蒙特卡罗算法（http://en.wikipedia.org/wiki/Monte_Carlo_algorithm）与解决此问题的常规方法进行过比较？ - Ed Heal

Answer 1

使用::strcmp代替手写版本。你的编译器供应商很可能有一个仅使用CPU特定功能进行比较的汇编版本（例如，SSE4.2有专门用于快速字符串比较的指令）。例如，MSVC版本是用汇编语言编写的，并尽可能使用更大的比较操作（整个单词而不是单个字符），特殊处理字符串的非对齐开头/结尾（如果你安装了VS2010，则在VC/crt/src/intel/strcmp.asm中）。

- Anteru

---

我只是在开发我的概念......所以我选择不使用任何内置函数。 - Jatin

你无法击败内置函数在性能上的表现，但这一点并不重要。如果你只是玩一下，你的strcmp实现已经足够好了，所有进一步的加速都相当复杂。 - Anteru

我能理解你想要自己编写这样的代码...重新发明轮子可能是一种非常令人满意的体验。但如果是这种情况，那么向他人请求提供代码不就是一种作弊吗？另一方面，如果你追求的是性能，那么没有什么比内置例程更好了。那么你想做什么呢？ - Mr Lister

在这个路径中给出的代码：VC/crt/src/intel/strcmp.asm和我编写的代码，哪一个更好？ - Jatin

手写汇编更好，但你的也差不多。你想要实现什么？一个相当快的strcmp？那么你已经完成了，你的代码和任何其他代码一样好。最快的strcmp？那么你就必须从汇编版本开始，并针对现代CPU进行调整等。但对于小字符串来说，你很难比内置的strcmp函数更快，因为它已经经过多年的优化。 - Anteru

Answer 2

你有没有测量过这个比strcmp快多少？C的strcmp应该已经被优化得很好了。

以下是一些其他的方法：

- 如果你已经知道字符串的长度，可以使用memcmp。 - 通过将字符串重新解释为int32或int64数组，并处理剩余的字符作为字符，每次比较4或8个字符。 - 如果指针指向非4字节或8字节对齐的内存，则可能会出现问题，请作为字符进行比较，直到达到对齐位置。

- Kevin Hsu

---

我不知道如何衡量我的代码有多快。我确信这段代码不可能是最快的。 - Jatin

你可以编写一个测试程序，在随机字符串上执行strcmp和xstrcmp数百万次。然后，对代码运行分析器（例如Google的gperf）。 - Kevin Hsu

Answer 3

如果我要测试相等性，有时会写成这样：

if (a[0]==b[0] && strcmp(a, b)==0){.....

因此，它只会在第一个字符匹配时调用 strcmp，而大多数情况下它们并不匹配。

- Mike Dunlavey

---

这是无用的，因为在strcmp的实现中已经包含了这个功能：https://dev59.com/PGct5IYBdhLWcg3wXsbH#12136398 - Stefan Rein

@StefanRein: 但在调用函数时有开销。这就是它试图节省的内容。在大多数情况下，这并不重要，但在这占用了大量时间的情况下，它确实很重要。 - Mike Dunlavey

难道 strcmp 也很可能被内联吗？ - Nik

@Nik：我总是使用这个来查看哪些操作需要时间。如果我在堆栈上看到strcmp出现超过一次，我就知道它需要很长时间并且没有被内联。如果它被内联了，我可能会在strcmp的初始指令中看到它，否则，就不值得担心了。 - Mike Dunlavey

@Nik：我刚看到了@Anteru的回答。你可以看到，strcmp在字符串相等且较长的情况下会尽力优化。这是为了处理通常不太可能出现的情况而产生的很多开销。根据我的经验，大部分时间字符串都很短，并且通常只有第一个字符不同。 - Mike Dunlavey