Интересная задача - 2

[Trotil]

Рассмотрим такой пример:

void f1 (int* x, int* y, int* sum, int* product, int* sum_product, int* even, size_t s)
{
 for (int i=0; i<s; i++)
 {
   sum[i]=x[i]+y[i];
   product[i]=x[i]*y[i];
   even[i]=i*2; // some dummy value
   sum_product[i]=sum[i]+product[i];
 };
};

По входным данным x и y вычисляются массивы sum, product, update_me, sum_product:

sum[i]=x[i]+y[i];
product[i]=x[i]*y[i];
even[i]=i*2;
sum_product[i]=sum[i]+product[i];

Компилятор генерирует ассемблерный код, суть которого сводится к следующему:

• вычислить следующий sum[i] и поместить в память это значение
• вычислить следующий product[i] и поместить в память это значение
• вычислить следующий even[i] и поместить в память это значение
• вычислить следующий sum_product[i] — на этой стадии придется снова загружать из памяти подсчитанные sum[i] и product[i].

Можно подумать, что четвёртый шаг не оптимальный. В самом деле: подсчитанные sum[i] и product[i] не обязательно снова загружать из памяти, ведь мы их только что подсчитали.
Но оказывается, что никакие ключи оптимизации для данного C-кода не позволят использовать значения, сохранённые в регистрах, полученные на шагах 1 и 2.

Вопрос 1: попробуйте объяснить такое "неоптимальное" поведение компилятора
Вопрос 2: попробуйте предложить решение (если оно есть), которое позволит избежать лишних чтений данных из памяти.

Comments

[CD_Eater]

компилятор тут не может ничего соптимизировать, а вдруг even == sum ?

[Trotil]

CD_Eater, да, это правильный ответ.
Более того, он для sum и product для раза загружает i и j!

Собственно, это избежать можно, пометив массивы ключевым словом restrict.

получится следующее:

mov esi, DWORD PTR [rcx+rax*4] ; загрузить a
mov r11d, DWORD PTR [rdx+rax*4]; загрузить b
mov DWORD PTR [r12+rax*4], r10d ; сохранить в even[]
add r10d, 2; еще одна оптимизация - к счётчику rax не привязаны, а умножение заменено сложением: r10d=0; r10d +=2;
lea ebx, [rsi+r11]
imul r11d, esi
mov DWORD PTR [r8+rax*4], ebx ; сохранить в sum[]
mov DWORD PTR [r9+rax*4], r11d ; сохранить в product[]
add r11d, ebx
mov DWORD PTR 0[rbp+rax*4], r11d ; сохранить в sum_product[]

код короче в 3 раза.

Потому что говоришь загружать из памяти, потому и загружает из памяти.
Задача изначально не особо корректна, ибо

Можно подумать, что четвёртый шаг не оптимальный. В самом деле: подсчитанные sum[i] и product[i] не обязательно снова загружать из памяти, ведь мы их только что подсчитали.

нельзя так подумать, эти действия (взять из памяти и взять из регистров) семантически различны, и то, что оно "только что посчитало" никакого значения не имеет.
Память может меняться за пределами функции (из другого потока, например) или как сказали выше - используемые области могут где-то пересекаться, соответственно компилятор не имеет права взять значение из регистров.

Ну а если сильно хочецца, то можно чуть хитрее.

 for (int i=0; i<s; i++)
 {
   sum_product[i]=(sum[i]=x[i]+y[i])+
                  (product[i]=x[i]*y[i]);
   even[i]=i*2; // some dummy value
 };

А самой прямолинейной оптимизацией будут банально временные переменные. Компилятор уловит семантику и эффективнее начнёт использовать регистры.