Jak*_* M. 7 c++ optimization performance g++
我有一个消耗CPU资源的代码,其中执行了一些循环功能很多倍.此循环中的每个优化都会带来显着的性能提升.问题:你如何优化这个循环(虽然优化没有更多......)？
void theloop(int64_t in[], int64_t out[], size_t N)
{
for(uint32_t i = 0; i < N; i++) {
int64_t v = in[i];
max += v;
if (v > max) max = v;
out[i] = max;
}
}
我尝试了一些方法,例如我用每个循环中增加的指针替换数组,但是(令人惊讶的是)我失去了一些性能而不是获得...
编辑:
itsMaximums,错误)int64_t,所以是消极和积极的N 在编译时是未知的_m128i执行和存储的开销高于SSE速度增益.但我不是SSE的专家,所以也许我有一个穷人码)结果:
我添加了一些循环展开,以及来自Alex'es帖子的一个很好的黑客.下面我粘贴一些结果:
strage,那4)并不比3)和4)快.以下代码为4):
for(size_t i = 1; i < N; i+=CHUNK) {
int64_t t_in0 = in[i+0];
int64_t t_in1 = in[i+1];
int64_t t_in2 = in[i+2];
int64_t t_in3 = in[i+3];
max &= -max >> 63;
max += t_in0;
out[i+0] = max;
max &= -max >> 63;
max += t_in1;
out[i+1] = max;
max &= -max >> 63;
max += t_in2;
out[i+2] = max;
max &= -max >> 63;
max += t_in3;
out[i+3] = max;
}
jal*_*alf 15
首先,您需要查看生成的程序集.否则,您无法知道执行此循环时实际发生了什么.
现在:这个代码是在64位机器上运行的吗？如果没有,那些64位的添加可能会有点伤害.
这个循环似乎是使用SIMD指令的明显候选者.SSE2支持大量算术的SIMD指令,包括一些可处理两个64位值的指令.
除此之外,看看编译器是否正确地展开循环,如果没有,请自行完成.展开循环的几次迭代,然后重新排序它的地狱.将所有内存负载放在循环的顶部,这样它们就可以尽早启动.
对于该if行,检查编译器是否正在生成条件移动,而不是分支.
最后,看看你的编译器是否支持restrict/ __restrictkeyword 这样的东西.它在C++中不是标准的,但它对于向编译器指示并且不指向相同的地址非常有用.inout
N编译时是否知道size()？如果是这样,请将其设为模板参数(然后尝试传递in并out作为对正确大小的数组的引用,因为这也可以帮助编译器进行别名分析)
只是一些想法在我的头顶.但是,再次研究拆卸.你需要知道编译器为你做了什么,特别是它不能为你做什么.
编辑
与您的编辑:
max &= -max >> 63;
max += t_in0;
out[i+0] = max;
令我印象深刻的是你添加了一个巨大的依赖链.结果可以被计算之前,最大必须被否定,结果必须被移动,结果那个必须和 "与其原始值Ed在一起,结果其必须被添加到另一个变量.
换句话说,所有这些操作都必须序列化.在上一次完成之前,您无法启动其中一个.这不一定是加速.现代流水线无序CPU喜欢并行执行大量事务.用一长串依赖指令来绑定它是你可以做的最严重的事情之一.(当然,如果它可以与其他迭代交错,它可能会更好.但我的直觉是一个简单的条件移动指令会更好)
#公告见聊天嗨Jakub,如果我找到一个使用启发式优化的版本,你会说什么,对于均匀分布的随机数据将导致~
int64_t3.5倍的速度增加(10.56x有效使用floats)？
我还没有时间来更新帖子,但可以通过聊天找到解释和代码.Edit
我使用相同的测试床代码(下面)来验证结果是否正确并且与OP中的原始实现完全匹配:具有讽刺意味的是......测试平台有一个致命的缺陷,导致结果无效:启发式版本是实际上跳过部分输入,但由于现有输出没有被清除,它似乎有正确的输出......(仍在编辑...)
好的,我已根据您的代码版本发布了一个基准测试,以及我建议的使用partial_sum.
在这里找到所有代码 https://gist.github.com/1368992#file_test.cpp
对于默认配置
#define MAGNITUDE 20
#define ITERATIONS 1024
#define VERIFICATION 1
#define VERBOSE 0
#define LIMITED_RANGE 0 // hide difference in output due to absense of overflows
#define USE_FLOATS 0
它会(见这里的输出片段):
int64_t)有许多(令人惊讶或不足为奇)的结果:
有没有显著任何的任何算法(之间的性能差异整数数据),提供您与启用优化编译.(参见Makefile ;我的拱门是64位,带有gcc-4.6.1的Intel Core Q9550)
这些算法不是等价的(你会看到哈希值不同):值得注意的是Alex提出的位小提琴不会以完全相同的方式处理整数溢出(这可能是隐藏的定义
#define LIMITED_RANGE 1
它限制了输入数据,因此不会发生溢出; 请注意,该partial_sum_incorrect版本显示了相同的C++非按位_算术运算,它们产生相同的不同结果:
return max<0 ? v : max + v;
也许,你的目的没问题？)
令人惊讶的是,一次计算max算法的两个定义并不昂贵.你可以看到这是在里面完成的partial_sum_correct:它在同一个循环中计算max的'公式'; 这真的不过是一个triva,因为这两种方法都没有明显更快......
更令人惊讶的是,当您能够使用float而不是使用时,可以获得巨大的性能提升int64_t.快速而肮脏的黑客可以应用于基准测试
#define USE_FLOATS 0
显示基于STL的算法(partial_sum_incorrect)在使用而不是(!!!)时运行速度大约2.5倍.注意:floatint64_t
partial_sum_incorrect仅涉及整数溢出,不适用于浮点数; 从哈希匹配的事实可以看出这一点,所以事实上它是_partial_sum_float_correct_ :)partial_sum_correct正在进行双重工作,导致它在浮点模式下表现不佳.见子弹3.(而且我之前提到的OP中的循环展开版本中存在一个错误的错误)
为了您的兴趣,部分求和应用程序在C++ 11中看起来像这样:
std::partial_sum(data.begin(), data.end(), output.begin(),
[](int64_t max, int64_t v) -> int64_t
{
max += v;
if (v > max) max = v;
return max;
});
有时,您需要退后一步并再次查看它.第一个问题显然是,你需要这个吗？是否会有更好的替代算法？
话虽如此,并且为了这个问题而假设您已经确定了这个算法,我们可以尝试推理我们实际拥有的东西.
免责声明:我所描述的方法受到Tim Peters用于改进传统内部实施的成功方法的启发,导致TimSort.所以请耐心等待;)
1.提取属性
我可以看到的主要问题是迭代之间的依赖关系,这将阻止许多可能的优化并阻碍许多并行化尝试.
int64_t v = in[i];
max += v;
if (v > max) max = v;
out[i] = max;
让我们以功能的方式重新编写代码:
max = calc(in[i], max);
out[i] = max;
哪里:
int64_t calc(int64_t const in, int64_t const max) {
int64_t const bumped = max + in;
return in > bumped ? in : bumped;
}
或者更确切地说,是一个简化版本(baring溢出,因为它未定义):
int64_t calc(int64_t const in, int64_t const max) {
return 0 > max ? in : max + in;
}
你注意到尖端点吗？行为的变化取决于名字不好(*)max是正面还是负面.
这个引爆点使得in更密切地观察这些值变得有趣,特别是根据它们可能产生的影响max:
max < 0并in[i] < 0随后out[i] = in[i] < 0max < 0并in[i] > 0随后out[i] = in[i] > 0max > 0并in[i] < 0随后out[i] = (max + in[i]) ?? 0max > 0并in[i] > 0随后out[i] = (max + in[i]) > 0(*)名字不好,因为它也是一个名字隐藏的累加器.我没有更好的建议.
2.优化运营
这导致我们发现有趣的案例:
[i, j)只包含负值的数组(我们称之为负片),那么我们可以做一个std::copy(in + i, in + j, out + i)和max = out[j-1][i, j)只包含正值的数组,那么它是一个纯积累代码(可以很容易地展开)max一旦积极,就会in[i]变得积极因此,在实际使用输入之前建立输入的配置文件可能很有趣(但可能不是,我没有做出承诺).请注意,对于大型输入,可以通过块来创建配置文件块,例如,根据高速缓存行大小调整块大小.
对于参考,3个例程:
void copy(int64_t const in[], int64_t out[],
size_t const begin, size_t const end)
{
std::copy(in + begin, in + end, out + begin);
} // copy
void accumulate(int64_t const in[], int64_t out[],
size_t const begin, size_t const end)
{
assert(begin != 0);
int64_t max = out[begin-1];
for (size_t i = begin; i != end; ++i) {
max += in[i];
out[i] = max;
}
} // accumulate
void regular(int64_t const in[], int64_t out[],
size_t const begin, size_t const end)
{
assert(begin != 0);
int64_t max = out[begin - 1];
for (size_t i = begin; i != end; ++i)
{
max = 0 > max ? in[i] : max + in[i];
out[i] = max;
}
}
现在,假设我们可以使用简单的结构以某种方式表征输入:
struct Slice {
enum class Type { Negative, Neutral, Positive };
Type type;
size_t begin;
size_t end;
};
typedef void (*Func)(int64_t const[], int64_t[], size_t, size_t);
Func select(Type t) {
switch(t) {
case Type::Negative: return ©
case Type::Neutral: return ®ular;
case Type::Positive: return &accumulate;
}
}
void theLoop(std::vector<Slice> const& slices, int64_t const in[], int64_t out[]) {
for (Slice const& slice: slices) {
Func const f = select(slice.type);
(*f)(in, out, slice.begin, slice.end);
}
}
现在,除非内部循环中的工作是最小的,因此计算特性可能过于昂贵......但是它很好地导致并行化.
3.简单的并行化
请注意,表征是输入的纯函数.因此,假设您以每块方式工作,可以并行:
Slice::Type值即使输入本质上是随机的,提供块也足够小(例如,CPU L1缓存线),可能存在它可以工作的块.两个线程之间的同步可以通过Slice(生产者/消费者)的简单线程安全队列完成,并添加一个bool last属性来停止消费,或者通过Slice在Unknown类型的向量中创建,并使用消费者块直到它已知(使用原子) ).
注意:因为表征是纯粹的,所以它是令人尴尬的并行.
4.更多并行化:投机工作
记住这个无辜的评论:max一旦积极就会in[i]变得积极.
假设我们可以(可靠地)猜测它Slice[j-1]会产生一个max负值,那么计算就会Slice[j]独立于它们之前的那个,我们就可以立即开始工作了!
当然,这是一个猜测,所以我们可能是错的......但是一旦我们完全表征了所有的切片,我们就有了空闲的内核,所以我们不妨将它们用于投机工作!如果我们错了？那么,消费者线程将简单地轻轻擦除我们的错误并用正确的值替换它.
推测性地计算a的启发式Slice应该很简单,并且必须进行调整.它也可能适应性......但这可能更难!
结论
分析您的数据集并尝试查找是否可能破坏依赖关系.如果它是你可以利用它,即使没有多线程.