Реализация шаблона выражения не оптимизируется
Я пытаюсь понять концепцию шаблонов выражений в C ++, поэтому я собрал воедино куски примера кода и т. Д., Чтобы создать простую векторную и связанную инфраструктуру шаблонов выражений для поддержки только двоичных операторов (+, -, *).
Все компилируется, однако я заметил, что разница в производительности между стандартным рукописным циклом и вариантом шаблона выражения довольно велика. ET почти в два раза медленнее, чем написанная рука. Я ожидал разницу, но не так сильно.
Полный список кодов можно найти здесь:
https://gist.github.com/BernieWt/769a4a3ceb90bb0cae9e
(извиняюсь за грязный код.)
.
Короче говоря, я сравниваю следующие два цикла:
ET:
for (std::size_t i = 0 ; i < rounds; ++i)
{
v4 = ((v0 - v1) + (v2 * v3)) + v4;
total += v4[0];
}
HW:
for (std::size_t i = 0 ; i < rounds; ++i)
{
for (std::size_t x = 0; x < N; ++x)
{
v4[x] = (v0[x] - v1[x]) + (v2[x] * v3[x]) + v4[x];
}
total += v4[0];
}
Когда я разбираю вывод, получается следующее, разница явно в дополнительной memcpy и нескольких 64-битных нагрузках, возникающих при возврате варианта ET:
Standard Loop | Expression Template
----------------------------------------+--------------------------------
L26: | L12:
xor edx, edx | xor edx, edx
jmp .L27 | jmp .L13
L28: | L14:
movsd xmm3, QWORD PTR [rsp+2064+rdx*8] | movsd xmm3, QWORD PTR [rsp+2064+rdx*8]
L27: | L13:
movsd xmm2, QWORD PTR [rsp+1040+rdx*8] | movsd xmm1, QWORD PTR [rsp+1552+rdx*8]
movsd xmm1, QWORD PTR [rsp+16+rdx*8] | movsd xmm2, QWORD PTR [rsp+16+rdx*8]
mulsd xmm2, QWORD PTR [rsp+1552+rdx*8] | mulsd xmm1, QWORD PTR [rsp+1040+rdx*8]
subsd xmm1, QWORD PTR [rsp+528+rdx*8] | subsd xmm2, QWORD PTR [rsp+528+rdx*8]
addsd xmm1, xmm2 | addsd xmm1, xmm2
addsd xmm1, xmm3 | addsd xmm1, xmm3
movsd QWORD PTR [rsp+2064+rdx*8], xmm1 | movsd QWORD PTR [rsp+2576+rdx*8], xmm1
add rdx, 1 | add rdx, 1
cmp rdx, 64 | cmp rdx, 64
jne .L28 | jne .L14
| mov dx, 512
| movsd QWORD PTR [rsp+8], xmm0
| lea rsi, [rsp+2576]
| lea rdi, [rsp+2064]
| call memcpy
movsd xmm3, QWORD PTR [rsp+2064] | movsd xmm0, QWORD PTR [rsp+8]
sub rcx, 1 | sub rbx, 1
| movsd xmm3, QWORD PTR [rsp+2064]
addsd xmm0, xmm3 | addsd xmm0, xmm3
jne .L26 | jne .L12
Мой вопрос: на данный момент я застрял о том, как идти об удалении копии, я по сути хочу обновить v4 на месте без копия. Есть идеи, как это сделать?
Note1: Я пробовал GCC 4.7 / 9, Clang 3.3, VS2010 / 2013 — у меня примерно одинаковый профиль производительности на всех упомянутых компиляторах.
Заметка 2: Я также попытался объявить bin_exp для vec, а затем добавить следующий оператор присваивания и удалить оператор преобразования из bin_exp:но безрезультатно:
template<typename LHS, typename RHS, typename Op>
inline vec<N>& operator=(const bin_exp<LHS,RHS,Op,N>& o)
{
for (std::size_t i = 0; i < N; ++i) { d[i] = o[i]; }
return *this;
}
ОБНОВИТЬ Решение, представленное в ПРИМЕЧАНИЕ 2, действительно является правильным. и заставляет компилятор генерировать код, почти идентичный рукописному циклу.
.
С другой стороны, если я переписываю вариант использования для варианта ET следующим образом:
auto expr = ((v0 - v1) + (v2 * v3)) + v4;
//auto& expr = ((v0 - v1) + (v2 * v3)) + v4; same problem
//auto&& expr = ((v0 - v1) + (v2 * v3)) + v4; same problem
for (std::size_t i = 0 ; i < rounds; ++i)
{
v4 = expr
total += v4[0];
}
Происходит сбой, поскольку временные значения (значения), которые создаются во время создания экземпляра ET, уничтожаются до назначения. Мне было интересно, есть ли способ использовать C ++ 11, чтобы вызвать ошибку компилятора.
Решение
Смысл шаблонов выражений заключается в том, что оценка подвыражений может привести к временным затратам, которые повлекут за собой затраты и не принесут никакой пользы. В вашем коде вы не сравниваете яблоки с яблоками. Две альтернативы для сравнения:
// Traditional
vector operator+(vector const& lhs, vector const& rhs);
vector operator-(vector const& lhs, vector const& rhs);
vector operator*(vector const& lhs, vector const& rhs);
С этими определениями для операций, выражение, которое вы хотите решить:
v4 = ((v0 - v1) + (v2 * v3)) + v4;
Становится (предоставляя имена всем временным жителям):
auto __tmp1 = v0 - v1;
auto __tmp2 = v2 * v3;
auto __tmp3 = __tmp1 + __tmp2;
auto __tmp4 = __tmp3 + v4;
// assignment is not really part of the expression
v4 = __tmp4;
Как вы видите, существует 4 временных объекта, которые, если вы используете шаблоны выражений, сводятся к минимуму: один временный, поскольку любая из этих операций генерирует неуместное значение.
В вашей ручной версии кода вы не выполняете одни и те же операции, вы скорее развертываете весь цикл и используете знания о полной операции, а не действительно одну и ту же операцию, поскольку зная, что вы назначите в конце выражения к одному из элементов, вы преобразовали выражение в:
v4 += ((v0 - v1) + (v2 * v3));
Теперь рассмотрим, что произойдет, если вместо присвоения одному из векторов, которые принимают участие в выражении, вы создаете новый вектор v5, Попробуйте выражение:
auto v5 = ((v0 - v1) + (v2 * v3)) + v4;
Волшебство шаблонов выражений заключается в том, что вы можете обеспечить реализацию для операторов, которые работают с шаблоном, который столь же эффективный как ручная реализация, так и пользовательский код намного проще и менее подвержены ошибкам (нет необходимости перебирать все элементы векторов с возможностью ошибок или затрат на обслуживание, поскольку внутреннее представление векторов должно быть известно в каждое место, где выполняется арифметическая операция)
Я по сути хочу обновить v4 на месте без копии
С шаблонами выражений и вашим текущим интерфейсом для вектора вы будете платить за временный и копию. Причина в том, что во время (концептуальной) оценки выражения создается новый вектор, хотя для вас может показаться очевидным, что v4 = ... + v4; эквивалентно v4 += ...это преобразование не может быть выполнено компилятором или шаблоном выражения. Вы могли бы, с другой стороны, обеспечить перегрузку vector::operator+= (может быть даже operator=), который принимает шаблон выражения и выполняет операцию на месте.
Предоставление оператора присваивания, который присваивает из шаблона выражения и сборка с g ++ 4.7 -O2, это сгенерированная сборка для обоих циклов:
call __ZNSt6chrono12system_clock3nowEv | call __ZNSt6chrono12system_clock3nowEv
movl $5000000, %ecx | movl $5000000, %ecx
xorpd %xmm0, %xmm0 | xorpd %xmm0, %xmm0
movsd 2064(%rsp), %xmm3 | movsd 2064(%rsp), %xmm3
movq %rax, %rbx | movq %rax, %rbx
.align 4 | .align 4
L9: |L15:
xorl %edx, %edx | xorl %edx, %edx
jmp L8 | jmp L18
.align 4 | .align 4
L32: |L16:
movsd 2064(%rsp,%rdx,8), %xmm3 | movsd 2064(%rsp,%rdx,8), %xmm3
L8: |L18:
movsd 1552(%rsp,%rdx,8), %xmm1 | movsd 1040(%rsp,%rdx,8), %xmm2
movsd 16(%rsp,%rdx,8), %xmm2 | movsd 16(%rsp,%rdx,8), %xmm1
mulsd 1040(%rsp,%rdx,8), %xmm1 | mulsd 1552(%rsp,%rdx,8), %xmm2
subsd 528(%rsp,%rdx,8), %xmm2 | subsd 528(%rsp,%rdx,8), %xmm1
addsd %xmm2, %xmm1 | addsd %xmm2, %xmm1
addsd %xmm3, %xmm1 | addsd %xmm3, %xmm1
movsd %xmm1, 2064(%rsp,%rdx,8) | movsd %xmm1, 2064(%rsp,%rdx,8)
addq $1, %rdx | addq $1, %rdx
cmpq $64, %rdx | cmpq $64, %rdx
jne L32 | jne L16
movsd 2064(%rsp), %xmm3 | movsd 2064(%rsp), %xmm3
subq $1, %rcx | subq $1, %rcx
addsd %xmm3, %xmm0 | addsd %xmm3, %xmm0
jne L9 | jne L15
movsd %xmm0, (%rsp) | movsd %xmm0, (%rsp)
call __ZNSt6chrono12system_clock3nowEv | call __ZNSt6chrono12system_clock3nowEv
Другие решения
C ++ 11 представлен переместить семантику уменьшить количество ненужных копий.
Ваш код довольно запутанный, но я думаю, что это должно сработать
В вашем struct vec замещать
value_type d[N];
с
std::vector<value_type> d;
и добавить d(N) в список инициализации конструктора. std::array это очевидный выбор, но это будет означать перемещение каждого элемента (то есть копии, которую вы пытаетесь избежать).
затем добавьте конструктор перемещения:
vec(vec&& from): d(std::move(from.d))
{
}
Конструктор перемещения позволяет новому объекту «украсть» содержимое старого. Другими словами, вместо копирования всего вектора (массива) копируется только указатель на массив.