Есть только один способ оптимизировать код: выяснить, что вы делаете медленно, и делать меньше. Особый случай «делать меньше» - это делать что-то еще, а это быстрее.
Итак, прежде всего, вот что я делаю, основываясь на опубликованном вами коде:
#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;
}
(Правка: только что заметил, что «проекция» должна быть массивом 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 в этом примере довольно мало, поэтому мы выполняем много ненужной работы с массивом "count". Даже без профилирования, я предполагаю, что подсчет до 256 дважды (один раз для очистки массива и один раз для его суммирования) является довольно значительным по сравнению со счетом до 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
Hurray. Код почти в 4 раза быстрее первой версии и дает те же результаты. Все, что я сделал, это изменил порядок выполнения математики: мы еще даже не рассматривали многопоточность или предварительную выборку. И я не пытался выполнить техническую оптимизацию циклов, просто оставил ее компилятору. Так что это можно считать достойным началом.
Тем не менее, он по-прежнему занимает на порядок больше, чем 1 с, с которыми работает йота. Так что, вероятно, еще предстоит найти большой выигрыш. Одно из основных отличий заключается в том, что йота перебирает массив 1d в последовательном порядке, а не прыгает повсюду. Как я уже говорил в моем первом ответе, вы должны стремиться всегда использовать последовательный порядок на кубе.
Итак, давайте сделаем однострочное изменение, переключив циклы i и j:
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++) {
Это все еще не последовательный порядок, но это означает, что мы фокусируемся на одном кусочке нашего куба по миллиону за раз. Современный процессор имеет по крайней мере 4 МБ кэш-памяти, поэтому, если повезет, мы ударим по основной памяти только для каждой части куба один раз во всей программе. С еще лучшей локализацией мы могли бы также уменьшить трафик в и из кэша 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 (я думаю, что разница между «пользовательским» и «реальным» временем в приведенном выше описании в основном объясняется тем фактом, что мой антивирусный сканер Выполнение, чего раньше не было. «пользователь» - это количество времени, которое программа занимала ЦП, «реальное» - время, затраченное на приостановку (ожидание ввода-вывода или предоставление времени другому процессу).
Конечно, моя сортировка ведра основана на том факте, что все, что мы делаем со значениями в каждом столбце, является коммутативным и ассоциативным. Сокращение количества сегментов работало только потому, что все большие значения обрабатываются одинаково. Это может быть не верно для всех ваших операций, поэтому вам придется по очереди взглянуть на внутренний цикл каждого из них, чтобы выяснить, что с ним делать.
А код немного сложнее. Вместо того, чтобы обрабатывать данные, делая «бла» для каждого этапа, мы вычисляем все этапы одновременно за один проход данных. Если вы начнете выполнять вычисления строк и столбцов за один проход, как я рекомендовал в своем первом ответе, это ухудшится. Возможно, вам придется начать разбивать ваш код на функции, чтобы он был читабельным.
Наконец, большая часть моего прироста производительности была получена за счет оптимизации того, что «шагов» мало. С 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
Это не так уж плохо. С шагами = 100 исходный код, вероятно, занимает около 1400 секунд, хотя я не собираюсь запускать его, чтобы доказать это. Но стоит помнить, что я не полностью убрал зависимость времени от «шагов», просто сделал ее сублинейной.