优化代码的唯一方法是找出减慢速度的原因,然后尽量少做这些事情。“少做这些事情”的一个特例是改为做其他更快的事情。
所以首先,根据您发布的代码,这是我正在做的事情:
#include <fstream>
#include <sstream>
using std::ios_base;
template<typename Iterator, typename Value>
void iota(Iterator start, Iterator end, Value val) {
while (start != end) {
*(start++) = val++;
}
}
int main() {
const int dim = 1000;
const int cubesize = dim*dim*dim;
const int squaresize = dim*dim;
const int steps = 7;
typedef unsigned char uchar;
uchar *partMap = new uchar[cubesize];
iota(partMap, partMap + cubesize, uchar(7));
uchar *projection = new uchar[squaresize];
for (int stage = 1; stage < steps; stage++) {
for (int j = 0; j < dim; j++) {
for (int i = 0; i < dim; i++)
{
int sum = 0;
for (int k = 0; k < dim; k++)
if (partMap[(((i * dim) + k) * dim) + j] >= stage)
sum++;
projection[(j*dim) + i] = sum;
}
}
std::stringstream filename;
filename << "results" << stage << ".bin";
std::ofstream file(filename.str().c_str(),
ios_base::out | ios_base::binary | ios_base::trunc);
file.write((char *)projection, squaresize);
}
delete[] projection;
delete[] partMap;
}
(编辑说明:刚刚注意到“projection”应该是int数组,而不是uchar。我的错。这会对一些计时产生影响,但希望不会太大。)
然后我将
result*.bin
复制到
gold*.bin
,以便按以下方式检查我的未来更改:
$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++ -O3 -pedantic -Wall big.cpp -o big
real 1m41.978s
user 1m39.450s
sys 0m0.451s
好的,目前是100秒。
所以,如果猜测遍历十亿项数据数组是慢的原因,那么让我们尝试只进行一次遍历,而不是每个阶段都进行一次:
uchar *projections[steps];
for (int stage = 1; stage < steps; stage++) {
projections[stage] = new uchar[squaresize];
}
for (int j = 0; j < dim; j++) {
for (int i = 0; i < dim; i++)
{
int counts[256] = {0};
for (int k = 0; k < dim; k++)
counts[partMap[(((i * dim) + k) * dim) + j]]++;
int sum = 0;
for (int idx = 255; idx >= steps; --idx) {
sum += counts[idx];
}
for (int stage = steps-1; stage > 0; --stage) {
sum += counts[stage];
projections[stage][(j*dim) + i] = sum;
}
}
}
for (int stage = 1; stage < steps; stage++) {
std::stringstream filename;
filename << "results" << stage << ".bin";
std::ofstream file(filename.str().c_str(),
ios_base::out | ios_base::binary | ios_base::trunc);
file.write((char *)projections[stage], squaresize);
}
for (int stage = 1; stage < steps; stage++) delete[] projections[stage];
delete[] partMap;
它会更快一些:
$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++ -O3 -pedantic -Wall big.cpp -o big
real 1m15.176s
user 1m13.772s
sys 0m0.841s
现在,在这个示例中,
steps
很小,因此我们在 "counts" 数组上做了很多不必要的工作。即使没有进行性能分析,我猜测两次计算到 256(一次清空数组,一次求和)与沿列运行到 1000 相比是相当显著的。所以让我们来改变它:
for (int j = 0; j < dim; j++) {
for (int i = 0; i < dim; i++)
{
int counts[steps+1] = {0};
for (int k = 0; k < dim; k++) {
uchar val = partMap[(((i * dim) + k) * dim) + j];
if (val >= steps)
counts[steps]++;
else counts[val]++;
}
int sum = counts[steps];
for (int stage = steps-1; stage > 0; --stage) {
sum += counts[stage];
projections[stage][(j*dim) + i] = sum;
}
}
}
现在我们只使用实际需要的桶。
$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++ -O3 -pedantic -Wall big.cpp -o big
real 0m27.643s
user 0m26.551s
sys 0m0.483s
欢呼!这个代码的速度几乎比第一个版本快了4倍,而且产生了相同的结果。我所做的只是改变了数学计算的顺序:我们甚至还没有考虑多线程或预取功能。我也没有尝试过任何高度技术的循环优化,只是留给了编译器。因此,这可以被认为是一个不错的开始。
然而,它仍然比iota运行的1秒慢一个数量级。因此,可能仍然有很大的收益空间。一个主要的区别是iota按顺序在1d数组上运行,而不是到处跳跃。正如我在第一个答案中所说,您应该始终在立方体上使用顺序。
因此,让我们进行一行更改,交换i和j循环的顺序:
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++) {
这仍然不是顺序的顺序,但它意味着我们一次只关注100万字节的立方体切片。现代CPU至少有4MB的缓存,所以运气好的话,我们在整个程序中对于任何给定的立方体部分只需要一次命中主内存。如果局部性更好,我们也可以减少进出L1缓存的流量,但主内存是最慢的。
这会带来多大的差异呢?
$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++ -O3 -pedantic -Wall big.cpp -o big
real 0m8.221s
user 0m4.507s
sys 0m0.514s
不错。事实上,仅这个更改就将原始代码的时间从100秒缩短到20秒。因此,这对应了一个5的因素,而我所做的其他一切则对应另一个5的因素(我认为上面的“用户”和“实际”时间之间的差异主要是由于我的病毒扫描程序正在运行,而之前没有运行。“用户”是程序占用CPU的时间,“实际”包括挂起的时间,无论是等待I/O还是给另一个进程运行的时间)。
当然,我的桶排序依赖于每列中对值执行的操作是可交换且可结合的事实。减少桶的数量之所以有效是因为所有大值都被视为相同。这可能并不适用于您的所有操作,因此您需要逐个查看每个内部循环以找出该怎么处理它。
而且代码有点复杂。我们不再在数据上运行“blah”来执行每个阶段,而是在单次运行数据时同时计算所有阶段。如果您开始在单次遍历中执行行和列计算,就像我在第一个答案中建议的那样,情况会变得更糟。您可能需要开始将代码拆分成函数以保持可读性。
最后,我获得了很多性能提升,这是因为“步骤”很小的优化。使用
steps=100
时,我得到:
$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++ -O3 -pedantic -Wall big.cpp -o big
real 0m22.262s
user 0m10.108s
sys 0m1.029s
这并不算太糟糕。使用steps=100,原始代码可能需要大约1400秒的时间,虽然我不会运行它来证明这一点。但值得记住的是,我并没有完全消除对“步骤”时间依赖性,只是使其次线性。