There is only one way to optimize code: figure out what you're doing that's slow, and do less of it. A special case of "doing less of it" is to do something else instead that's faster.
So first of all, here's what I'm doing based on your posted code:
#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;
}
(Edit: just noticed that "projection" should be an array of int, not uchar. My bad. This will make a difference to some of the timings, but hopefully not too big of one.)
Then I copied result*.bin
to gold*.bin
, so I can check my future changes as follows:
$ 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
OK, so 100 seconds at the moment.
So, speculating that it's striding through the billion-item data array that's slow, let's try only going through once, instead of once per stage:
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;
It's a bit faster:
$ 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
Now, steps
is quite small in this example, so we're doing a lot of unnecessary work with the "counts" array. Without even profiling, I'm guessing that counting to 256 twice (once to clear the array and once to sum it) is quite significant compared with counting to 1000 (to run along our column). So let's change that:
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;
}
}
}
Now we're only using as many buckets as we actually need.
$ 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
Hurrah. The code is nearly 4 times as fast as the first version, and produces the same results. All I've done is change what order the maths is done: we haven't even looked at multi-threading or prefetching yet. And I haven't attempted any highly technical loop optimisation, just left it to the compiler. So this can be considered a decent start.
However it's still taking an order of magnitude longer than the 1s which iota runs in. So there are probably big gains still to find. One main difference is that iota runs over the 1d array in sequential order, instead of leaping about all over the place. As I said in my first answer, you should aim to always use sequential order on the cube.
So, let's make a one-line change, switching the i and j loops:
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++) {
This still isn't sequential order, but it does mean we're focussing on one million-byte slice of our cube at a time. A modern CPU has at least 4MB cache, so with a bit of luck we'll only hit main memory for any given part of the cube once in the entire program. With even better locality we could reduce the traffic in and out of L1 cache, too, but main memory is the slowest.
How much difference does it make?
$ 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
Not bad. In fact, this change alone brings the original code from 100s to 20s. So this is responsible for a factor of 5, and everything else I did is responsible for another factor of 5 (I think the difference between 'user' and 'real' time in the above is mostly accounted for by the fact my virus scanner is running, which it wasn't earlier. 'user' is how much time the program occupied a CPU, 'real' includes time spent suspended, either waiting on I/O or giving another process time to run).
Of course, my bucket sort relies on the fact that whatever we're doing with the values in each column is commutative and associative. Reducing the number of buckets only worked because large values are all treated the same. This might not be true for all your operations, so you'll have to look at the inner loop of each one in turn to figure out what to do with it.
And the code is a bit more complicated. Instead of running over the data doing "blah" for each stage, we're computing all the stages at the same time in a single run over the data. If you start doing row and column computations in a single pass, as I recommended in my first answer, this will get worse. You may have to start breaking your code into functions to keep it readable.
Finally, a lot of my performance gain came from an optimisation for the fact that "steps" is small. With steps=100
, I get:
$ 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
This isn't so bad. With steps=100 the original code probably takes about 1400 seconds, although I'm not going to run it to prove that. But it's worth remembering that I haven't completely taken away the time dependency on "steps", just made it sub-linear.