取消引用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相同长度的以null结尾的字符串的向量.

根据是否test()取消引用它的参数,这个片段执行不变或与关于字符串的长度线性时间strings1和strings2.也就是说,如果我使用:

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

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

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

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

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

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