c - 在 C 中比较两个字符串的最快方法是什么？

Question

为了清楚起见，我只讨论以 null 结尾的字符串。

我熟悉在 C 中使用 strcmp 进行字符串比较的标准方法。但我觉得它很慢且效率低下。

我不一定要寻找最简单但最有效的方法。

能否在底层代码保持跨平台的情况下进一步优化当前的比较方法(strcmp)？

如果 strcmp 无法进一步优化，那么在没有 strcmp 的情况下，执行字符串比较的最快方法是什么？

当前用例:

• 判断两个任意字符串是否匹配
• 字符串不会超过 4096 字节，也不会小于 1 字节
• 字符串在同一代码/库中分配/释放和比较
• 一旦比较完成，我就会将字符串传递给另一个 C 库，该库需要格式为标准的空终止格式
• 系统内存限制不是一个大问题，但我会有数以万计的此类字符串排队等待比较
• 字符串可能包含高位 ascii 字符集或 UTF-8 字符，但出于我的目的，我只需要知道它们是否匹配，内容不是问题
• 应用程序在 x86 上运行，但也应该在 x64 上运行

对当前 strcmp() 实现的引用:

• How does strcmp work?
• What does strcmp actually do?
• GLIBC strcmp() source code

编辑:澄清解决方案不需要修改 strcmp。

编辑 2:为此用例添加了具体示例。

Answer 1

恐怕您对 strcmp() 的引用实现既不准确又不相关:

• 它是不准确的，因为它使用 char 类型而不是 C11 标准中指定的 unsigned char 类型来比较字符:

  7.24.4 Comparison functions

  The sign of a nonzero value returned by the comparison functions memcmp, strcmp, and strncmp is determined by the sign of the difference between the values of the first pair of characters (both interpreted as unsigned char) that differ in the objects being compared.

• 这无关紧要，因为现代编译器使用的实际实现要复杂得多，使用手工编码的汇编语言扩展内联。

任何通用实现都可能不是最优的，尤其是在编码以保持跨平台可移植性的情况下。

如果您的程序的瓶颈是比较字符串，这里有几个方向可以探索。

• 分析您的算法，尝试找到减少比较次数的方法:例如，如果您在数组中搜索字符串，对该数组进行排序并使用二分搜索来大幅减少比较次数。
• 如果您的字符串是在许多不同地方使用的标记，请分配这些标记的唯一副本并将它们用作标量值。当且仅当指针相等时，字符串才相等。我一直在编译器和解释器中通过哈希表使用这个技巧。
• 如果您的字符串具有相同的已知长度，您可以使用 memcmp() 而不是 strcmp()。 memcmp() 比 strcmp() 更简单，并且可以在已知字符串正确对齐的地方更有效地实现。

编辑:有了提供的额外信息，您可以为您的字符串使用这样的结构:

typedef struct string_t {
    size_t len;
    size_t hash;  // optional
    char str[];   // flexible array, use [1] for pre-c99 compilers
} string_t;

你可以这样分配这个结构:

string_t *create_str(const char *s) {
    size_t len = strlen(s);
    string_t *str = malloc(sizeof(*str) + len + 1;
    str->len = len;
    str->hash = hash_str(s, len);
    memcpy(str->str, s, len + 1);
    return str;
}

如果您可以对所有字符串使用这些str 东西，您可以通过首先比较长度或哈希值来大大提高匹配效率。您仍然可以将 str 成员传递给您的库函数，它以 null 正确终止。