コードを最適化する唯一の方法があります。それは、実行していることが遅いことを理解し、それを少なくすることです。「それを少なくする」という特別な場合は、代わりにもっと速い何かをすることです。
まず、投稿されたコードに基づいて私が行っていることは次のとおりです。
#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; //ranges from 1 to 255
typedef unsigned char uchar;
uchar *partMap = new uchar[cubesize];
// dummy data. I timed this separately and it takes about
// a second, so I won't worry about its effect on overall timings.
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;
}
（編集：「射影」はucharではなくintの配列である必要があることに気づきました。私の悪いことです。これはいくつかのタイミングに違いをもたらしますが、大きすぎないことを願っています。）
次に、にコピー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秒です。
したがって、低速な10億アイテムのデータ配列を通過していると推測して、ステージごとに1回ではなく、1回だけ通過してみましょう。
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まで2回（配列をクリアするために1回、合計するために1回）カウントすることは、1000までカウントする（列に沿って実行する）ことと比較して非常に重要だと思います。それでは、それを変更しましょう。
for (int j = 0; j < dim; j++) {
for (int i = 0; i < dim; i++)
{
// steps+1, not steps. I got this wrong the first time,
// which at least proved that my diffs work as a check
// of the answer...
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秒よりも桁違いに長い時間がかかります。したがって、おそらくまだ大きなメリットがあります。主な違いの1つは、iotaが、あちこちを飛び回るのではなく、1d配列を順番に実行することです。最初の回答で述べたように、キューブでは常に順番を使用することを目指す必要があります。
それでは、iループとjループを切り替えて、1行の変更を行いましょう。
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++) {
これはまだ順番ではありませんが、一度に100万バイトのキューブスライスに焦点を合わせていることを意味します。最新のCPUには少なくとも4MBのキャッシュがあるため、運が良ければ、プログラム全体で1回だけキューブの特定の部分のメインメモリにアクセスできます。さらに優れたローカリティを使用すると、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倍の原因です（上記の「ユーザー」と「リアルタイム」の時間の違いは、私のウイルススキャナーが'user'は、プログラムがCPUを占有した時間であり、'real'には、I / Oの待機中、または別のプロセスの実行時間を与えるために中断された時間が含まれます。
もちろん、私のバケットソートは、各列の値で行っていることはすべて可換で連想的であるという事実に依存しています。大きな値はすべて同じように扱われるため、バケットの数を減らすことだけが機能しました。これはすべての操作に当てはまるとは限らないため、各操作の内部ループを順番に調べて、それをどのように処理するかを理解する必要があります。
そして、コードはもう少し複雑です。各ステージで「何とか」を実行してデータを実行する代わりに、データを1回実行するだけですべてのステージを同時に計算しています。最初の回答で推奨したように、1回のパスで行と列の計算を開始すると、これはさらに悪化します。読みやすくするために、コードを関数に分割し始める必要があるかもしれません。
最後に、私のパフォーマンスの向上の多くは、「ステップ」が小さいという事実の最適化からもたらされました。で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秒かかりますが、それを証明するために実行するつもりはありません。しかし、「ステップ」への時間依存性を完全に取り除いたわけではなく、劣線形にしたことを覚えておく価値があります。