working with expressions: how to minimize runtime construction time

Question

I have two classes, a single expression (SE) and a bundle of two expressions (ME). The bundle is an expression itself, hence it can be an element of another bundle.

struct SE {
    SE(char id, char n) : id(id), n(n) {}

    size_t size() const { return n; }
    char *eval(char *b) const { b[0]=id; return b+1; }

    char id, n;
};

template <typename LHS>
struct ME {
    ME(const LHS& l, const SE& r) : lhs(l), rhs(r) { }

    size_t size() const { return rhs.size(); }
    char *eval(char *b) const { *b++='('; b=lhs.eval(b); *b++=','; b=rhs.eval(b); *b++=')'; return b; }

    LHS lhs;
    SE rhs;
};

The construction of the bundle performs a simple validity check based on the data member n, accessible in ME via the method size. An eval method does some claculations using the data member id. Neither n nor id are known at compile time.

For both classes I override the comma operator, so that it performs the recursive bundling of multiple single expression into a nested bundle.

auto SE::operator,(const SE& r) { return ME<SE>(*this, r); }
auto ME<LHS>::operator,(const SE& r) { return ME<ME<LHS>>(*this, r); }

I want that, after the whole bundle has been constructed, the method eval is triggered on the whole bundle. Example:

SE('a',1);                        // prints 'a'
SE('a',1), SE('b',1);             // prints '(a,b)'
SE('a',1), SE('b',1), SE('c',1);  // prints '((a,b),c)'

A possible way to achieve that is to use the destructors of the classes and add a flag is_outer which is updated appropriately during contruction of SE and ME. When any of these class is destructed, if the flag indicates this is the outermost class, then eval is triggered. A full demo is given below.

Testing on godbolt the simple demo function below, it seems to me the compiler generates more code than strictly necessary. Although id and n are not known at compile time, the final type of the expression should be. I would expect the entire construction of the bundle to reduce to just moving a few numbers in the correct place, then check the assertions, but it seems to actually do much more copies.

Is it possible to obtain that more of the contruction part is produced at compile time?

#include <iostream>
#include <cassert>
#include <string>
#include <sstream>
using namespace std;

// forward declaration
template <typename LHS> struct ME;

struct SE {
    SE(char id, char n) : id(id), n(n), outer(true)  {}
    SE(const SE& expr) : id(expr.id), n(expr.n), outer(false) {}

    ME<SE> operator,(const SE& r);

    size_t size() const { return n; }
    char *eval(char *b) const { b[0]=id; return b+1; }

    ~SE() { if(outer) { char b[20] = {}; char *p=eval(b); *p++='\n'; cout << b; } }

    char id, n;
    mutable bool outer;
};

template <typename LHS>
struct ME {
    ME(const LHS& l, const SE& r)
        : lhs(l), rhs(r), outer(true)  // tentatively set to true
    { l.outer = r.outer = false;  assert(l.size() == r.size()); } // reset flag for arguments
    ME(const ME<LHS>& expr)
        : lhs(expr.lhs), rhs(expr.rhs), outer(false) {}

    size_t size() const { return rhs.size(); }
    char *eval(char *b) const { *b++='('; b=lhs.eval(b); *b++=','; b=rhs.eval(b); *b++=')'; return b; }

    auto operator,(const SE& r) { return ME<ME<LHS>>(*this, r); }

    ~ME() { if(outer) { char b[20] = {}; char *p=eval(b); *p++='\n'; cout << b; } }

    LHS lhs;
    SE rhs;
    mutable bool outer;
};

ME<SE> SE::operator,(const SE& r) { return ME<SE>(*this, r); }

void demo(char a, char na, char b, char nb, char c, char nc) {
    SE(a, na), SE(b,nb), SE(c,nc);   // prints '((a,b),c)'
}

int main() {
    demo('a',1,'b',1,'c',1);
    return 0;
}

Answer 1

The general pattern you are following is expression templates. Reading up on how others do it will help.

Usually expression templates use CRTP heavily, and do not store copies.

I believe I see bugs due to the copies.

Generally take T&& and store T& or T&&.

Usually expression templates terminate (and execute) when they are assigned to a target; you don't want to that. As C++ lacks move-from-and-destroy, you have to check the "should not be executed" at (nominally) runtime.

Instead of references/values and a bool, you could store pointers and use null as the "don't run" case.

I cannot figure out how to make the work to determine what to run constexpr. It might be possible however.