Шаблон выражения профилирования
Я пытаюсь профилировать шаблон выражения, похожий на тот, что приведен в книге Дэвида Вандевурде «Шаблон C ++». Ниже приведен мой теоретический анализ, который, вероятно, неверен, потому что тест показывает неожиданные результаты.
Предположим, что тест о:
R = A + B + C;
где A, B, C, R — массивы, выделенные в куче. Размер массива равен 2. Поэтому будет выполнено следующее:
R[0] = A[0] + B[0] + C[0]; // 3 loads + 2 additions + 1 store
R[1] = A[1] + B[1] + C[1];
примерно с 12 инструкциями (по 6 для каждого).
Теперь, если шаблон выражения включен (показан в самом низу), после того, как во время компиляции будет выполнен вывод типа, будет выполнено следующее во время выполнения, прежде чем будет выполнена такая же оценка, как и выше:
A + B --> expression 1 // copy references to A & B
expression 1 + C --> expression 2 // copy the copies of references to A & B
// + copy reference to C
Следовательно, перед оценкой есть всего 2 + 3 = 5 инструкций, что составляет около 5 / (5 + 12) = 30% от общего количества инструкций. Так что я должен видеть эти издержки, особенно когда размер вектора невелик.
Но результат показывает, что стоимость этих двух почти одинакова. Я повторяю тест 1E + 09 раз. Коды сборки для этих двух, конечно же, одинаковы. Но я не мог найти часть для этой «строительной» части, которая стоит какое-то время или инструкции.
movsdq (%r9,%rax,8), %xmm0
addsdq (%r8,%rax,8), %xmm0
addsdq (%rdi,%rax,8), %xmm0
movsdq %xmm0, (%rcx,%rax,8)
У меня нет хорошего опыта в CS, поэтому этот вопрос может быть таким глупым. Но я почесал голову в течение нескольких дней по этому поводу. Так что любая помощь оценивается!
— Мой шаблон выражения —
template< typename Left, typename Right >
class V_p_W // stands for V+W
{
public:
typedef typename array_type::value_type value_type;
typedef double S_type;
typedef typename traits< Left >::type V_type;
typedef typename traits< Right >::type W_type;
V_p_W ( const Left& _v, const Right& _w ) : V(_v), W(_w)
{}
inline value_type operator [] ( std::size_t i ) { return V[i] + W[i]; }
inline value_type operator [] ( std::size_t i ) const { return V[i] + W[i]; }
inline std::size_t size () const { return V.size(); }
private:
V_type V;
W_type W;
};
где traits ничего не делает, кроме как решить, следует ли брать значение ссылки на объект. Например, значение копируется для целого числа, а ссылка берется для массива.
Решение
Мой домашний сваренный тест. В идеале шаблоны выражений сохраняют дополнительные выделения, требуемые временными векторами в простом случае.
expr.cpp:
#include <vector>
#include <stdlib.h>
#include <iostream>
#include <ctime>
using namespace std;
typedef vector<int> Valarray;
template<typename L, typename R>
struct BinOpPlus {
const L& left;
const R& right;
BinOpPlus(const L& l, const R& r)
: left(l), right(r)
{}
int operator[](int i) const { return left[i] + right[i]; }
};
template<typename L, typename R>
BinOpPlus<L, R> operator+(const L& left, const R& right){
return BinOpPlus<L, R>(left, right);
}
int main() {
int size = 10000000;
Valarray v[3];
for(int n=0; n<3; ++n){
for(int i=0; i<size; ++i){
int val = rand() % 100;
v[n].push_back(val);
}
}
std::clock_t start = std::clock();
auto tmp = v[0] + v[1];
auto out = tmp + v[2];
int sum = 0;
for(int i=0; i<size; ++i)
sum += out[i];
std::clock_t stop = std::clock();
cout << "Sum: " << sum << endl;
cout << "Time: " << (stop-start) << endl;
return 0;
}
vala.cpp:
#include <vector>
#include <stdlib.h>
#include <iostream>
#include <ctime>
using namespace std;
class Valarray : public vector<int> {
public:
Valarray operator+(const Valarray& r) const {
Valarray out;
out.reserve(r.size());
for(size_t i=0; i<r.size(); ++i)
out.push_back((*this)[i] + r[i]);
return out;
}
Valarray operator+(Valarray&& r) const {
for(size_t i=0; i<r.size(); ++i)
r[i] = (*this)[i] + r[i];
return r;
}
};
int main() {
int size = 10000000;
Valarray v[3];
for(int n=0; n<3; ++n){
for(int i=0; i<size; ++i){
int val = rand() % 100;
v[n].push_back(val);
}
}
std::clock_t start = std::clock();
Valarray out = v[0] + v[1] + v[2];
int sum = 0;
for(int i=0; i<size; ++i)
sum += out[i];
std::clock_t stop = std::clock();
cout << "Sum: " << sum << endl;
cout << "Time: " << (stop-start) << endl;
return 0;
}
Командная строка:
g++ -Wfatal-errors -std=c++11 -Wall -Werror vala.cpp -o vala
g++ -Wfatal-errors -std=c++11 -Wall -Werror expr.cpp -o expr
~/example$ ./vala
Sum: 1485274472
Time: 680000
~/example$ ./expr
Sum: 1485274472
Time: 130000
С оптимизацией:
g++ -Wfatal-errors -std=c++11 -Wall -Werror vala.cpp -o vala -O3
g++ -Wfatal-errors -std=c++11 -Wall -Werror expr.cpp -o expr -O3
na:~/example$ ./vala
Sum: 1485274472
Time: 290000
na:~/example$ ./expr
Sum: 1485274472
Time: 10000
Массовое улучшение с помощью шаблонов выражений, потому что это позволяет избежать лишних векторов.
Другие решения