5

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

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()它使用该函数比较成对的以空字符结尾的字符串。strings1并且是包含相同长度的以空字符结尾的字符串的strings2向量。STR_COUNT

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

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

4

2 回答 2

3

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

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

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

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

特别是，您可以将一些非常短的字符串打包到单个缓存行中。发生这种情况时，单个高速缓存行可以服务于多次迭代的内存访问。随着字符串变得更长，它们中的更少的将适合单个高速缓存行，因此高速缓存效率降低。最终，字符串足够长，以至于每个字符串占用一个单独的缓存行，缓存没有任何好处。

于 2012-10-01T17:02:35.743 回答
2

因为在第一种情况下，可以证明只要strings1 != strings2，条件永远不会为真。优化编译器可以推断出整个循环永远不会有任何可观察到的副作用，因此它可以优化它以消除它。

考虑strings[str_id]等于strings + str_id * sizeof(*strings); 为简单起见，我们假设sizeof等于 1（我们可以在不失一般性的情况下这样做）。然后你的情况变成：

if (test(strings1 + str_id, strings2 + str_id) == 0)

如果编译器能够内联test，第一个版本test的代码就会变成

if ((strings1 + str_id != strings2 + str_id) == 0)

或（连续简化但等价的形式）

if (strings1 + str_id == strings2 + str_id)

if (strings1 == strings2)

因此，由于strings1 != strings2（几乎可以肯定是这种情况）并且由于编译器可以假设strings1并且strings2不会被外部原因修改，它可以简单地跳过整个循环而什么也不做。无所事事是不变的时间。

对于第二个版本，test除了实际执行循环并在每次迭代中取消引用指针之外，没有办法知道条件是否为真，因此运行时间变成线性的。

于 2012-09-29T18:17:14.170 回答