C++ Question
expression templates - bad_alloc
For the original question pls scroll down.
So to explain my problem a bit more detailed and to prove the need of references in my case, i'll use now the code from sehe (btw thank you for your efforts).
The operands (variables) inside your
std::tuple< L, R, Op>BinaryExprL,RRunning the example, you will notice the
BinaryExprHowever the use of expression templates is exactly in order to avoid copies or temporaries of about the vector size...
#include <iostream>
#include <tuple>
#include <typeinfo>
namespace ETL {
template <typename T>
struct Literal {
T value;
T get() const { return value; }
};
/*
*template <typename T>
* static inline std::ostream& operator<<(std::ostream& os, ETL::Literal<T> const& lit) {
* return os << __PRETTY_FUNCTION__ << "\n actual: lit.value = " << lit.value;
* }
*/
template <class L, class R, class Op>
struct BinaryExpr : std::tuple<L, R, Op> { // tuple optimizes for empty element types
BinaryExpr(L l, R r, Op op)
: std::tuple<L, R, Op> { l, r, op }
{}
L const& get_lhs() const { return std::get<0>(*this); }
R const& get_rhs() const { return std::get<1>(*this); }
Op const& get_op() const { return std::get<2>(*this); }
};
template <class L, class R, class Op> auto cured(BinaryExpr<L,R,Op> _) { return _; }
template <class T> auto cured(Literal<T> l) { return std::move(l); }
template <class T> Literal<T> cured(T&& v) { return {std::forward<T>(v)}; }
template <class Op, class L, class R>
BinaryExpr<L, R, Op> make_binexpr(L&& l, R&& r) { return { std::forward<L>(l), std::forward<R>(r), Op{} }; }
template <class L, class R> auto operator +(L&& l, R&& r)
{ return make_binexpr<std::plus<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
template <class L, class R> auto operator -(L&& l, R&& r)
{ return make_binexpr<std::minus<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
template <class L, class R> auto operator *(L&& l, R&& r)
{ return make_binexpr<std::multiplies<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
template <class L, class R> auto operator /(L&& l, R&& r)
{ return make_binexpr<std::divides<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
template <class L, class R> auto operator %(L&& l, R&& r)
{ return make_binexpr<std::modulus<>>(cured(std::forward<L>(l)), std::forward<R>(r)); }
template <typename T> auto val(T const& v)
{ return cured(v); }
namespace impl {
template <class T>
static constexpr auto is_indexable(T const&) -> decltype(std::declval<T const&>()[0], std::true_type{}) { return {}; }
static constexpr auto is_indexable(...) -> decltype(std::false_type{}) { return {}; }
struct {
template <class T> size_t operator()(T const& v) const { return (*this)(v, is_indexable(v)); }
template <class T> size_t operator()(T const& v, std::true_type) const { return v.size(); }
template <class T> size_t operator()(T const&, std::false_type) const { return 0; }
template <class T> size_t operator()(Literal<T> const& l) const { return (*this)(l.value); }
template <class L, class R, class Op>
size_t operator()(BinaryExpr<L,R,Op> const& be) const { return (*this)(be.get_lhs()); }
} size;
struct {
template <class T>
auto operator()(size_t i, T const& v) const { return (*this)(i, v, is_indexable(v)); }
template <class T>
auto operator()(size_t i, T const& v, std::true_type) const { return v[i]; }
template <class T>
auto operator()(size_t, T const& v, std::false_type) const { return v; }
template <class T> auto operator()(size_t i, Literal<T> const& l) const { return (*this)(i, l.value); }
template <class L, class R, class Op>
auto operator()(size_t i, BinaryExpr<L,R,Op> const& be) const {
return be.get_op()((*this)(i, be.get_lhs()), (*this)(i, be.get_rhs()));
}
} eval_at;
}
template <typename T> size_t size(T const& v) { return impl::size(v); }
template <typename T> auto eval_at(size_t i, T const& v) { return impl::eval_at(i, v); }
}
#include <vector>
template <class value_t>
struct Vector : std::vector<value_t> {
using data_t = std::vector<value_t>;
typedef value_t value_type;
using data_t::data_t;
template <typename Expr>
Vector(Expr const& expr) { *this = expr; }
template <typename Expr>
Vector& operator=(Expr const& expr) {
this->resize(ETL::size(expr));
for (size_t i = 0; i < this->size(); ++i)
this->at(i) = ETL::eval_at(i, expr);
return *this;
}
friend std::ostream &operator<<(std::ostream &os, const Vector &v) {
for (auto& el : v) os << " " << el;
return os;
}
};
#include <ctime>
int main() {
Vector<double> aSmall(size_t(1e1));
Vector<double> aBig(size_t(1e7));
using ETL::operator+;
using ETL::operator*;
//std::cout << typeid(a + a * 4 / 2).name() << "\n";
//#define DD(x) std::cout << typeid(x).name() << " size: " << ETL::size(x) << " result:" << (x) << "\n"
//DD(a * -100.0);
std::clock_t clock;
clock = std::clock();
auto bSmall = aSmall + aSmall + aSmall;
auto cSmall = aSmall;
std::cout << "Time took to make \"evaluation rules (BinaryExpr's)\" for small vector " << float(std::clock() - clock)/CLOCKS_PER_SEC << std::endl;
clock = std::clock();
auto bBig = aBig + aBig + aBig;
auto cBig = aBig;
std::cout << "Time took to make \"evaluation rules (BinaryExpr's)\" for big vector " << float(std::clock() - clock)/CLOCKS_PER_SEC << std::endl;
/*
std::cout << size(b) << "\n";
std::cout << (a + a + a + a) << "\n";
std::cout << a * 4.0 << "\n";
std::cout << b + c << "\n";
std::cout << (a + a + a + a) - 4 * a << "\n";
*/
}
i am currently working on a c++ project and now i am stuck already for a while. It's about delayed evaluation with expression templates and (for me at least) a strange bad_alloc.
If you try the code below, you'll notice runtime error bad_alloc due to the very last addition b+c. So thats the point where the delayed evaluation is done. Furthermore the code below compiles and runs fine if you remove the references of the members of "Expression" (left,right). But i need references there, due to performance, etc. . However i also dont see, why i cant use references there.
I've already spent a lot of time with it. Please let me know if somebody can help me.
Best Regards.
#include <iostream>
#include <vector>
template<typename value_t, typename left_t, typename right_t, typename op_t>
class Expression
{
public:
typedef value_t value_type;
explicit Expression(const left_t &left,
const right_t &right,
const op_t &op) :
left(left),
right(right),
op(op)
{
}
value_t operator [](const size_t &i) const
{
return op(left[i],right[i]);
}
size_t size() const { return left.size();}
private:
const left_t &left;
const right_t &right;
//const left_t left;
//const right_t right;
const op_t &op;
};
template<class left_t,
class right_t,
class value_t = typename left_t::value_type,
class op_t = std::plus<value_t>>
const Expression<value_t, left_t, right_t, op_t> operator +(const left_t &left,
const right_t &right)
{
return Expression<value_t,left_t,right_t,op_t>(left, right, op_t());
}
template<typename value_t, typename data_t = std::vector<value_t>>
class Vector : public data_t
{
public:
typedef value_t value_type;
using data_t::size;
Vector(const std::initializer_list<value_t> &list) :
data_t(list)
{
}
Vector(const size_t &n) :
data_t(n)
{
}
Vector(const Vector &v) :
data_t(v)
{
}
template<typename left_t, typename right_t, typename op_t>
Vector(const Expression<value_t,left_t,right_t,op_t> &v) :
data_t(v.size())
{
operator =(v);
}
template<typename vec_t>
Vector(const vec_t &v) :
data_t(v.size())
{
operator =(v);
}
template<typename vec_t>
Vector &operator =(const vec_t &v)
{
for(size_t i = 0; i < data_t::size(); ++i)
data_t::operator [](i) = v[i];
return (*this);
}
friend std::ostream &operator <<(std::ostream &os, const Vector &v)
{
if(v.size())
os << v[0];
for(size_t i = 1; i < v.size(); ++i)
os << " " << v[i];
return os;
}
};
int main()
{
Vector<double> a{0,1,2};
auto b = a+a+a;
auto c = a;
std::cout << a+a+a+a << std::endl;
std::cout << b+c << std::endl; // gives bad_alloc
return 0;
}
Recommended for you: Get network issues from WhatsUp Gold. Not end users.
Answer Source
"But i need references there, due to performance, etc."
Prove it.
In expression templates, all¹ the information should be compile-time.
You can see my example here for a simple expression template:
// we have lazy placeholder types:
template <int N> struct placeholder {};
placeholder<1> _1;
placeholder<2> _2;
placeholder<3> _3;
// note that every type here is stateless, and acts just like a more
// complicated placeholder.
// We can have expressions, like binary addition:
template <typename L, typename R> struct addition { };
template <typename L, typename R> struct multiplication { };
// here is the "factory" for our expression template:
template <typename L, typename R> addition<L,R> operator+(L const&, R const&) { return {}; }
template <typename L, typename R> multiplication<L,R> operator*(L const&, R const&) { return {}; }
///////////////////////////////////////////////
// To evaluate/interpret the expressions, we have to define "evaluation" for each type of placeholder:
template <typename Ctx, int N>
auto eval(Ctx& ctx, placeholder<N>) { return ctx.arg(N); }
template <typename Ctx, typename L, typename R>
auto eval(Ctx& ctx, addition<L, R>) { return eval(ctx, L{}) + eval(ctx, R{}); }
template <typename Ctx, typename L, typename R>
auto eval(Ctx& ctx, multiplication<L, R>) { return eval(ctx, L{}) * eval(ctx, R{}); }
///////////////////////////////////////////////
// A simple real-life context would contain the arguments:
#include <vector>
struct Context {
std::vector<double> _args;
// define the operation to get an argument from this context:
double arg(int i) const { return _args.at(i-1); }
};
#include <iostream>
int main() {
auto foo = _1 + _2 + _3;
Context ctx { { 3, 10, -4 } };
std::cout << "foo: " << eval(ctx, foo) << "\n";
std::cout << "_1 + _2 * _3: " << eval(ctx, _1 + _2 * _3) << "\n";
}
So what you need is a literal type that holds a reference to the associated value, and defer all other evaluation to evaluation time.
I might prefer to add the size() operation as a free function, so that you don't have to encumber all the expression types with it (Separation Of Concerns).
¹ nearly, nl. except when encoding literals
Proof Of Concept
Using the stragey outlined:
#include <iostream>
#include <tuple>
namespace ETL {
template <typename T>
struct Literal {
T value;
T get() const { return value; }
};
/*
*template <typename T>
* static inline std::ostream& operator<<(std::ostream& os, ETL::Literal<T> const& lit) {
* return os << __PRETTY_FUNCTION__ << "\n actual: lit.value = " << lit.value;
* }
*/
template <class L, class R, class Op>
struct BinaryExpr : std::tuple<L, R, Op> { // tuple optimizes for empty element types
BinaryExpr(L l, R r, Op op)
: std::tuple<L, R, Op> { l, r, op }
{}
L const& get_lhs() const { return std::get<0>(*this); }
R const& get_rhs() const { return std::get<1>(*this); }
Op const& get_op() const { return std::get<2>(*this); }
};
template <class L, class R, class Op> auto cured(BinaryExpr<L,R,Op> _) { return _; }
template <class T> auto cured(Literal<T> l) { return std::move(l); }
template <class T> Literal<T> cured(T&& v) { return {std::forward<T>(v)}; }
template <class Op, class L, class R>
BinaryExpr<L, R, Op> make_binexpr(L&& l, R&& r) { return { std::forward<L>(l), std::forward<R>(r), Op{} }; }
template <class L, class R> auto operator +(L&& l, R&& r)
{ return make_binexpr<std::plus<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
template <class L, class R> auto operator -(L&& l, R&& r)
{ return make_binexpr<std::minus<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
template <class L, class R> auto operator *(L&& l, R&& r)
{ return make_binexpr<std::multiplies<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
template <class L, class R> auto operator /(L&& l, R&& r)
{ return make_binexpr<std::divides<>>(cured(std::forward<L>(l)), cured(std::forward<R>(r))); }
template <class L, class R> auto operator %(L&& l, R&& r)
{ return make_binexpr<std::modulus<>>(cured(std::forward<L>(l)), std::forward<R>(r)); }
template <typename T> auto val(T const& v)
{ return cured(v); }
namespace impl {
template <class T>
static constexpr auto is_indexable(T const&) -> decltype(std::declval<T const&>()[0], std::true_type{}) { return {}; }
static constexpr auto is_indexable(...) -> decltype(std::false_type{}) { return {}; }
struct {
template <class T> size_t operator()(T const& v) const { return (*this)(v, is_indexable(v)); }
template <class T> size_t operator()(T const& v, std::true_type) const { return v.size(); }
template <class T> size_t operator()(T const&, std::false_type) const { return 0; }
template <class T> size_t operator()(Literal<T> const& l) const { return (*this)(l.value); }
template <class L, class R, class Op>
size_t operator()(BinaryExpr<L,R,Op> const& be) const { return (*this)(be.get_lhs()); }
} size;
struct {
template <class T>
auto operator()(size_t i, T const& v) const { return (*this)(i, v, is_indexable(v)); }
template <class T>
auto operator()(size_t i, T const& v, std::true_type) const { return v[i]; }
template <class T>
auto operator()(size_t, T const& v, std::false_type) const { return v; }
template <class T> auto operator()(size_t i, Literal<T> const& l) const { return (*this)(i, l.value); }
template <class L, class R, class Op>
auto operator()(size_t i, BinaryExpr<L,R,Op> const& be) const {
return be.get_op()((*this)(i, be.get_lhs()), (*this)(i, be.get_rhs()));
}
} eval_at;
}
template <typename T> size_t size(T const& v) { return impl::size(v); }
template <typename T> auto eval_at(size_t i, T const& v) { return impl::eval_at(i, v); }
}
#include <vector>
template <class value_t>
struct Vector : std::vector<value_t> {
using data_t = std::vector<value_t>;
typedef value_t value_type;
using data_t::data_t;
template <typename Expr>
Vector(Expr const& expr) { *this = expr; }
template <typename Expr>
Vector& operator=(Expr const& expr) {
this->resize(size(expr));
for (size_t i = 0; i < this->size(); ++i)
this->at(i) = eval_at(i, expr);
return *this;
}
friend std::ostream &operator<<(std::ostream &os, const Vector &v) {
for (auto& el : v) os << " " << el;
return os;
}
};
int main() {
Vector<double> a { 1, 2, 3 };
using ETL::operator+;
using ETL::operator*;
//std::cout << typeid(a + a * 4 / 2).name() << "\n";
#define DD(x) std::cout << typeid(x).name() << " size: " << ETL::size(x) << " result:" << (x) << "\n"
DD(a * -100.0);
auto b = a + a + a;
auto c = a;
std::cout << size(b) << "\n";
std::cout << (a + a + a + a) << "\n";
std::cout << a * 4.0 << "\n";
std::cout << b + c << "\n";
std::cout << (a + a + a + a) - 4 * a << "\n";
}
Prints
ETL::BinaryExpr<ETL::Literal<Vector<double>&>, ETL::Literal<double>, std::multiplies<void> > size: 3 result: -100 -200 -300
3
4 8 12
4 8 12
4 8 12
0 0 0
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download