Оптимизация циклов C для получения диагонали массива

Великий Бог Google так и не представил мне объяснений некоторых проблем оптимизации цикла. Итак, с сожалением о том, что у меня недостаточно Google-fu, я обращаюсь к вам, StackOverflow.

I ' m оптимизация программы на языке C для решения конкретной системы дифференциальных уравнений. В процессе поиска численного решения я вызываю функцию, которая устанавливает линейную систему уравнений, а затем функцию, которая ее решает.

Функция решения изначально имела узкое место во время доступа к элементам на диагонали массива что определяет линейную систему. Поэтому я включил одномерный массив, который задается во время инициализации системы, в которой хранятся значения по диагонали массива.

Ради удовольствия я продолжил играть с кодом, который инициализировал диагональные элементы, измеряя время, которое они взяли и пытались постоянно улучшать код. Версии, которые я пробовал, вызвали несколько вопросов:

Примечание: Я поместил все версии, которые я пробовал, в одну функцию и профилировал эту функцию, чтобы увидеть, на что тратится время. Я сообщу время выполнения версии в процентах от общего времени работы. Функция оценивалась несколько миллионов раз. Чем меньше число, тем лучше.

Соответствующие объявления данных, используемые в коде:

/* quick definitions of the relevant variables, data is a struct */

static const int sp_diag_ind[98] = {2,12,23,76,120,129,137,142,.../* long list */};

double *spJ = &(data->spJ[0]);
/* data has double spJ[908] that represents a sparse matrix stored in triplet
*  form, I grab the pointer because I've found it to be more 
*  efficient than referencing data->spJ[x] each time I need it
*/

int iter,jter;
double *diag_data = NV_DATA_S(data->J_diag);
/* data->J_diag has a content field that has an array double diag_data[150]
*  NV_DATA_S is a macro to return the pointer to the relevant data
*/

Мой исходный цикл для инициализации diag_data. Время составляло 16,1% от оценки (см. Примечание).

/* try 1 */
for (iter = 0; iter<3; iter++) {
    diag_data[iter] = 0; 
}
jter = 0;
for (iter = 3; iter<101; iter++) { // unaligned loop start
    diag_data[iter] = spJ[sp_diag_ind[jter]];
    jter++; // heavy line for loop
}

for (iter = 101; iter<150; iter++) {
    diag_data[iter] = 0; 
}

Подводя итог, мы берем указатель на диагональ, устанавливаем некоторые компоненты в ноль (это не обязательно в зависимости от алгоритма, который я использую), затем захватываем значения которые находятся на диагонали «массива», представленного в разреженной форме символом spJ. Поскольку spJ представляет собой одномерный массив из 908 ненулевых (в основном нулевых) массива размером 150x150, мы должны использовать поиск, чтобы найти положения диагональных элементов в spJ. Этот поиск определяется массивом из 98 элементов sp_diag_ind.

Я попытался исключить использование jter, потому что он оказался не свободным для увеличения. Средний цикл , моя вторая попытка:

for (iter = 0; iter<98; iter++) { // unaligned loop start
    diag_data[iter+3] = spJ[sp_diag_ind[iter]];
}

Это немного улучшило ситуацию. Время для этой версии составило 15,6%. Но когда я смотрю на анализ Shark этого кода (инструмент, который поставляется с XCode на Mac), он предупреждает меня, что это невыровненный цикл.

Третья попытка улучшить заключалась в удалении "обнуление" циклов и использование memset для обнуления diag_data:

memset(diag_data, '\0', sizeof(diag_data));

for (iter = 0; iter<98; iter++) { // unaligned loop start
    diag_data[iter+3] = spJ[sp_diag_ind[iter]];
}

Это было рассчитано на 14,9%. Не зная, что такое невыровненный цикл, я продолжал возиться. Я нашел улучшенную четвертую реализацию , выполняющую смещение выравнивания между diag_data и spJ [сумасшедший индекс] с помощью указателя:

realtype * diag_mask = &diag_data[3];
for (iter = 0; iter<98; iter++) { // unaligned loop start
    diag_mask[iter] = spJ[sp_diag_ind[iter]];
}

Использование diag_mask позволило немного улучшить скорость. Он составил 13,1%.

Изменить: Оказалось, что этот раздел был глупее, чем я думал изначально. Использование iter не определено. Реквизит @caf и @rlibby за то, что они его поймали .

Наконец, я тогда попробовал кое-что, что мне показалось глупым:

memset(diag_data, '\0', sizeof(diag_data));

for (iter = 0; iter<98;) {
    diag_mask[iter] = spJ[sp_diag_ind[iter++]];
}

Это было рассчитано на 10,9%. Кроме того, Shark не выдает предупреждение о невыровненном цикле, когда я смотрю на аннотированный исходный код. Конец глупого раздела

Итак, мои вопросы:

1. Что такое невыровненный цикл?
2. Почему пятая реализация выровнена, а четвертая нет?
3. Имеется ли выровненный цикл, отвечающий за повышение скорости выполнения между моей четвертой и пятой реализациями, или встраивает шаг приращения в поиск значения sp_diag_ind ответственный?
4. Видите ли вы какие-нибудь другие улучшения, которые я могу сделать?

Спасибо за помощь.

- Эндрю