5

我正在阅读有关哈希函数的内容（我是一名中级 CS 学生）并遇到了这个问题：

int hash (const string & key, int tableSize) {
    int hasVal = 0;

    for (int i = 0; i < key.length(); i++)
        hashVal = 37 * hashVal + key[i];

    .....
    return hashVal;
}

我正在查看这段代码，并注意到如果在 for 循环中而不是每次我们这样做时调用 key.length() 会更快：

int n = key.length();
for (int i = 0; i < n; i++)

我的问题是，既然这是一种稍微提高性能的明显方法，编译器会自动为我们做这件事吗？我对编译器还不太了解，但我很好奇这个问题的答案。在编写代码以使用较少的操作时，人们经常指出，我所做的事情通常已经由编译器为我完成，所以我在浪费时间，而是在做诸如内联函数之类的事情。我关心这一点，因为我正在编写一个游戏，其中物理处理需要高效，这样事情就不会显得笨重。

4

4 回答 4

3

简短的回答：它有时可以...

长答案：

如果编译器可以根据循环本身确定 key.length() 是一个“常量”值，那么它将能够优化调用。这又取决于所使用的类的定义（在这种情况下string，我们可以预期它是“写得很好”）。它还依赖于编译器理解循环不会key以改变key.length().

使其工作的关键要素是该函数是inline（或者是模板函数，inline需要允许它在不同的编译单元中多次包含 - 或在同一源文件中可用）并且源代码在标头中编译单元包含的文件。

当然，C++ 标准中并没有要求编译器执行此操作。每次调用该函数都完全符合标准。

于 2013-11-13T08:32:43.117 回答
2

只有当它是一个纯函数时，才能安全地key.length()退出循环——也就是说，一个没有副作用的函数。如果编译器可以检测到是这样，那么我会说它很可能会执行优化。

不幸的是，与 Fortran 不同，C++ 没有标准的方法来将某些东西标记为纯。如果该函数是inline（或可内联的），那么编译器就有了定义，并且可以自己解决它，或者至少消除函数调用。

将成员函数标记为const保证它不会影响当前实例，但原则上没有理由key.length()不能更改某些全局变量，所以我怀疑这本身就足够了。

（有各种编译器特定的方法来声明一个纯函数——比如__attribute__((pure))在 GCC 和兼容的编译器（Clang、Intel）中。也许可以尝试这些方法，看看它们是否有什么不同？）

于 2013-11-13T08:40:55.557 回答
0

有两个地方可以进行优化。

  1. 更聪明的编译器会反省短函数，看看它们是否对if子句有影响。可能大多数编译器都会inline调用，使其等同于您编写的内容。

  2. 与更“随机”相比，在 cpu 级别的分支预测也会使其（基本上）更快if。最重要的问题之一SO展示了这个很好的核心示例。

编辑：我之前假设声明方法length() const就足够了。但它太弱了。方法仍然可以在不改变对象状态的情况下抛出随机的东西。但是我 100% 肯定，体面的编译器会像我描述的那样内省函数和方法。

于 2013-11-13T08:28:31.520 回答
0

这是一个非常依赖编译器的答案。唯一可以确定的方法是生成汇编程序并检查它创建的内容（我建议学习如何使用您的编译器执行此操作并尝试它，这非常有启发性*）。

优化并不是那么明显——编译器可以执行该优化，但前提是它确定.length()不会改变——即没有其他线程可以访问数据并且它能够确定循环内的任何内容都不会.length()改变后者很容易检查，因为它是一个 const 字符串，但前者不太容易。话虽如此，我希望编译器假设它在中等优化水平的任何地方都是 const 。

*双关语是故意的；对不起。

于 2013-11-13T08:30:47.703 回答