7

Возникла следующая проблема: имеется вот такой участок кода

start = clock();
LLTWithBlock(n, 4, a);
end = clock();
duration = (double)(end - start);
std::cout << "Alltime: " << duration << std::endl;

Время выполнения 8 секунд. После чего заменяю константу "4" на переменную "r" (тоже равную 4, считывается из файла)

LLTWithBlock(n, r, a);

И новое время выполнения становится 22 секунды. Я отдаленно понимаю, что в ассемблерном коде будут создаваться разные экземпляры функции, но откуда такая разница во времени выполнения?

P.S. Время замерялось не один раз, данная ситуация повторяется при каждом запуске программы.

upd: меняется конкретно время выполнения следующей функции (вызываемой внутри)

void A_LLT(unsigned n, unsigned r, unsigned numBlock, double *b, double *bb, double *a){
unsigned adr;
unsigned cnt = r*(numBlock + 1);//номер 1 строки в текущем блоке(прямоугольном) в  большой матрице
unsigned nb = (n - cnt) / r, end;//n/r число целых блоков размера р в матрице.
                                 //Отнимаем 1(мы его раскладываем) и нумблок(число уже разложенных блоков) 

for (unsigned ib = 0; ib < nb; ib++)//ход по квадратным блокам
{
    end = ib * r + r;
    for (unsigned i = ib * r; i < end; i++)//по строкам в блоке
    {
        adr = (cnt + i) * (cnt + i + 1) / 2 + cnt;
        for (unsigned j = 0; j <= i; j++, adr++)//по строкам 
        {
            for (unsigned k = 0; k < r; k += 4)
            {
                a[adr] -= b[i*r + k] * b[j*r + k];
                a[adr] -= b[i*r + k + 1] * b[j*r + k + 1];
                a[adr] -= b[i*r + k + 2] * b[j*r + k + 2];
                a[adr] -= b[i*r + k + 3] * b[j*r + k + 3];
            }
        }
    }
}

for (unsigned i = nb * r, end = i + n % r; i < end; i++)//по строкам в блоке  n - r - numBlock * r
{
    adr = (cnt + i) * (cnt + i + 1) / 2 + cnt;
    for (unsigned j = 0; j <= i; j++, adr++)//по строкам 
    {
        for (unsigned k = 0; k < r; k += 4)
        {
            a[adr] -= b[i*r + k] * b[j*r + k];
            a[adr] -= b[i*r + k + 1] * b[j*r + k + 1];
            a[adr] -= b[i*r + k + 2] * b[j*r + k + 2];
            a[adr] -= b[i*r + k + 3] * b[j*r + k + 3];
        }
    }
}}
16
  • 2
    А считываете из файла в r после строчки start = ...?
    – gil9red
    29 мар 2016 в 6:13
  • нет, до блока замера врмени 29 мар 2016 в 6:14
  • Это шаблонная функция или нет? Хотелось бы на нее посмотреть, но, судя по времени выполнения, код там не самый маленький... Ее код вам доступен? Попробовать вставить в разных местах вывод времени и посмотреть, что именно резко увеличивается?
    – Harry
    29 мар 2016 в 6:17
  • Функция не шаблонная, привести я ее могу конечно, но в ней идет вызов множества других функций, поэтому докопаться до истины будет сложно 29 мар 2016 в 6:19
  • 1
    Тогда как минимум совет дизассемблировать ее вызов ничего не дает. Глупый вопрос - значение r точно равно 4? отлладочный вывод делали?
    – Harry
    29 мар 2016 в 6:23

3 ответа 3

6

Код просмотрен в дизассемблере, совершенно разный. Очень сильная оптимизация кода и очень активное использование SSE.

На моей машине разница получилась примерно той же - в 3 раза.

4

Код конечно есть, но нет явной заготовки для бенчмарка, пришлось ручками "угадывать". Но даже беглый анализ кода показывает явные оптимизации, которые может сделать компилятор. Например, в коде много вызовов вида b[i*r + k]. Если значение всех переменных компилятору неизвестны, он вынужден вычислять одно умножение, потом сложение, потом ещё одно умножение и сложение(вычисленный индекс умножается на размер элемента и складывается с начальным адресом массива). А это не такая уж и тривиальная задача. Если же компилятор может доказать, что r = 4, то он может это все заменить одной инструкцией lea ( и просмотр исходного кода показывает, что похоже это так и происходит).

Дальше посмотрим на некоторые участки кода, которые это все может затронуть.

// внутри Dot
int m = n % 4;
for (unsigned i = 0; i < m; i++)
    sum += a[i] * b[i];
for (unsigned i = m; i<n; i += 4)
    sum += a[i] * b[i] + a[i + 1] * b[i + 1] + a[i + 2] * b[i + 2] + a[i + 3] * b[i + 3];

Тут происходит классическая раскрутка цикла ручками (хотя компилятор это умеет сделать и сам, но добавив такого кода, Вы лишили его этой возможности. Но у этого кода есть одна бага - вначале идет обработка начала, а только потом тела. А правильно делать вначале тело, а потом хвост. Но это все правильно, если массив "выровнен". А так эта раскрутка вообще лишена смысла.

Если Вам важна скорость и работы этого кода, то есть смысл посмотреть на функции SSE. К примеру, есть функция _mm256_mul_pd которая умеет перемножать 4 пары вещественных 64 битных чисел. По моему опыту, использование подобных функций позволяет ускорить в 2-2.5 раза подобные участки кода.

2
  • по поводу b[i*r + k] соглашусь с вами, не дошли руки поправить этот момент. А вот по поводу развертки, я слышал, что компилятор умеет это сам делать, но на практике, у меня этой разверткой работает быстрее, чем без нее. 29 мар 2016 в 9:50
  • 1
    Есть такое правильно - не пытайся обмануть компилятор, иначе он поймет это и жестоко накажет. То есть, современные компиляторы достаточно умны, что бы делать много оптимизаций, но только если код "явный". А когда обычный цикл размазан по двум - тут он говорит "ок, я даже не буду пытаться понять, почему так написано".
    – KoVadim
    29 мар 2016 в 9:52
3

Соберите программу с выводом ассемблерного листинга (для gcc это флаг -s), и сравните код между вызовами clock()

Если компилятор все время выдает одинаковый код, как с переменной, так и с константой - проблемы где-то в условиях эксперимента, так как чудес не бывает.

Если же код разный, а производительность важна - у вас два варианта

  • добиваться нужной скорости, изменяя параметры компиляции
  • написать огромное количество if на все возможные значения переменной, которые будут вызывать код с константой.
1

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.