我在看一个演讲,"Efficiency with Algorithms, Performance with Data Structures" , 并且是 对以下评论感到惊讶:
#include <string>
#include <unordered_map>
#include <memory>
struct Foo {
int x;
};
Foo* getFoo(std::string key,
std::unordered_map<std::string,
std::unique_ptr<Foo>> &cache) {
if (cache[key])
return cache[key].get();
cache[key] = std::unique_ptr<Foo>(new Foo());
return cache[key].get();
}
Foo* getFooBetter(std::string key,
std::unordered_map<std::string,
std::unique_ptr<Foo>> &cache) {
std::unique_ptr<Foo> &entry = cache[key];
if (entry)
return entry.get();
entry = std::unique_ptr<Foo>(new Foo());
return entry.get();
}
getFooBetter()
更好。我一直相信我可以依靠
在编译器上执行这种转换
我期望多次出现的 x+y
只被评估的方式
一次。毫不奇怪,生成的 LLVM IR 确实与
主持人。即使使用 -O9,我们仍然有 3 次调用 cache[key]
getFoo()
版本。
我已经移动了长LLVM IR of both with c++ symbols unmangled越界以免造成视觉上的冒犯。
Another StackOverflow question揭示了这里的部分答案是 operator[]
假定能够修改它希望的任何全局状态,并且
因此我们不能省略电话。 A linked proposal关于介绍一个
[[pure]]
注解在 CSE 中的应用。
如果我们保持在 4 个电话,我就能在这里结束时感到满意。
然而,如果我对 IR 的解读是正确的,那么看起来我们优化了
getFoo()
就像我们写的一样:
Foo* getFoo(std::string key,
std::unordered_map<std::string,
std::unique_ptr<Foo>> &cache) {
if (cache[key])
return cache[key].get();
std::unique_ptr<Foo> &entry = cache[key];
entry = std::unique_ptr<Foo>(new Foo());
return entry.get();
}
谁能解释一下 clang 对代码的看法是这样的
它能够合并最后两个 cache[key]
,但不是所有的
他们? (我本地的 clang 是 3.4。)
最佳答案
llvm 中的 CSE 实现对算术表达式进行操作。 你可以在 llvm/lib/Transforms/Scalar/EarlyCSE.cpp 中查看 llvm Common Subexpression Elimination 源代码
我们在这里面临的案例是过程间优化。
这次调用cache[key]
原来是[](cache,key)
函数。因此,根据 [] 函数的内联成本,内联等优化可能会起作用。 Chandler 提到了同样的问题,考虑到散列函数的计算成本很高,内联被阻止,一个人最终会不止一次地计算散列函数!
如果发生内联,IR at -O3, cache[key]
首先被计算并且给定 cache
key
根本没有改变这样的调用将被优化为相同的 SSA 值。
在 cache[key].get()
的情况下,我们通常会将 IR 编写为 cache[key] 返回对象并使用 get()中的 getelementpointer 获取字段值
。启用优化后,此 IR 变成了我们之前计算的“缓存[key]”的 SSA 值,其中元素从唯一指针的结构访问。
回到 getFooBetter()
在最坏的情况下,如果编译器无法跨过程进行优化,更多的 cache[key]
将导致更多的计算和此调用即使在 O3 也会按原样出现!
关于c++ - C++ 中公共(public)子表达式消除的局限性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30521162/