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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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