c++ - 取消引用 char 指针会随着它指向的字符串变长而变慢。为什么？

Question

我遇到了一个奇怪的问题:我有以下代码:

int matches = 0;
for (int str_id = 0; str_id < STR_COUNT; str_id++) {
    if (test(strings1[str_id], strings2[str_id]) == 0)
        matches++;
}

它使用 test() 函数比较成对的以 null 结尾的字符串。 strings1 和 strings2 是包含 STR_COUNT 个相同长度的空终止字符串的 vector 。

根据 test() 是否取消引用其参数，此代码段会根据 strings1 和 中字符串的长度以恒定时间或线性时间执行字符串 2。也就是说，如果我使用:

int test(char* a, char* b) {
    return (a != b)
}

那么运行时间不依赖于 strings1 和 strings2 中存储的字符串的长度。另一方面，如果我使用

int test(char* a, char* b) {
    return (*a != *b)
}

然后运行时间随着存储在strings1和strings2中的字符串的长度线性增加。

为什么会这样？

编辑:此处问题的完整示例:http://pastebin.com/QTPAkP1g

Answer 1

您正在看到数据局部性的影响。

在您仅比较指针的情况下，该操作仅访问两个 vector 中的内存。 vector 连续存储它们的元素，因此每次内存访问的位置都非常接近上一次迭代期间访问的位置。这是一个非常好的地方，缓存对你微笑。

在取消引用指针的情况下，您正在向混合中添加额外的内存访问，因此缓存有更多工作要做，效果在很大程度上取决于实现。

从您的数据推断，字符串似乎在内存中打包在一起，因此从一个字符串的开头到下一个字符串的开头的距离取决于字符串的长度。短字符串比长字符串更紧密。

特别是，您可以将一些非常短的字符串打包到单个缓存行中。当发生这种情况时，单个缓存行可以为多次迭代的内存访问提供服务。随着字符串变长，适合单个缓存行的字符串会越来越少，因此缓存效率会降低。最终，字符串足够长以致于每个字符串都占据一个单独的缓存行，而缓存没有任何好处。