表达式模板(Expression Templates)-摩杜云开发者社区

C++表达式为立即求值，例如x + y - z表达式，x + y会产生一个临时变量进行存储；对应向量表达式同时具有可读性(重载operator)，在C++中我们容易得到以下实现：

template<typename T>
class Array {
public:
    T &operator[](size_t index)
    {   
        return m_arr[index];
    }   

    T operator[](size_t index) const
    {
        return m_arr[index];
    }   

    size_t Size() const
    {   
        return m_arr.size();
    }   

    Array(size_t size, const T& val) : m_arr(size, val)
    {   
        // DBG_LOG("");
    }   

private:
    std::vector<T> m_arr;
};

template<typename T>
Array<T> operator+(const Array<T>& a1, const Array<T>& a2) 
{
    Array<T> result(a1.Size(), 0); 
    for (int i = 0; i < a1.Size(); i++) {
        result[i] = a1[i] + a2[i];
    }   
    return result;
}

template<typename T>
Array<T> operator-(const Array<T>& a1, const Array<T>& a2) 
{
    Array<T> result(a1.Size(), 0); 
    for (int i = 0; i < a1.Size(); i++) {
        result[i] = a1[i] + a2[i];
    }
    return result;
}

Array<int> a1(SIZE, 2); 
        Array<int> a2(SIZE, 2); 
        Array<int> a3(SIZE, 1); 
        (a1 + a2 - a3); // 构造了临时向量, 带来了性能和内存上的开销

立即求值的方式存在额外开销，对应向量规模大的情况下，临时变量的产生对性能和内存都是不小的代价；

在函数式编程中表达式的计算通常是延迟的，这样可以按需组合表达式同时不会带来性能和内存上的开销【1】。C++中表达式模板利用模板元编程技术达到计算延迟的效果；

表达式模板是由 Todd Veldhuizen在 1995年 6月在一篇文章中给出的。

表达式模板是一种 C++模板元编程 (template metaprogramming)技术。典型情况下，表达式模板自身代表一种操作，模板参数代表该操作的操作数。

模板表达式可将子表达式的计算推迟，这样有利于优化 (特别是减少临时变量的使用 )。表达式模板也可以作为参数传递给一个函数。

向量延迟计算

先看代码再展开分析实现：

namespace ExpTemplates {
template<typename Derive>
class ExpBase {
public:
    operator const Derive&() const // (const Derive&) (Xxx), 类型转换
    {   
        return static_cast<const Derive&>(*this);
    }   
};

template<typename T>
class Array : public ExpBase<Array<T>> {
public:
    T &operator[](size_t index)
    {   
        return m_arr[index];
    }   

    T operator[](size_t index) const
    {   
        return m_arr[index];
    }   

    size_t Size() const
    {   
        return m_arr.size();
    }   
    
    Array(size_t size, const T& val) : m_arr(size, val)
    {   
        // DBG_LOG("");
    }   

    template<typename Derive>
    Array(const ExpBase<Derive>& e)
    {   
        const Derive& d = e;
        m_arr.resize(d.Size());
        for (int i = 0; i < d.size(); i++) {
            m_arr[i] = d[i];
        }
    }   

private:
    std::vector<T> m_arr;
};

template<typename T1, typename T2>
class ArrayAdd : public ExpBase<ArrayAdd<T1, T2>> {
public:
    ArrayAdd(const ExpBase<T1>& e1, const ExpBase<T2>& e2): m_arr1(e1), m_arr2(e2)
    {
    }
    auto operator[](size_t index) const
    {
        return (m_arr1[index] + m_arr2[index]);
    }
private:
    const T1& m_arr1;
    const T2& m_arr2;
};

template<typename T1, typename T2>
class ArrayDiff : public ExpBase<ArrayDiff<T1, T2>> {
public:
    ArrayDiff(const ExpBase<T1>& e1, const ExpBase<T2>& e2): m_arr1(e1), m_arr2(e2)
    {
    }
    auto operator[] (size_t index) const
    {
        return (m_arr1[index] - m_arr2[index]);
    }
private:
    const T1& m_arr1;
    const T2& m_arr2;
};

template<typename T1, typename T2>
auto operator+(const ExpBase<T1>& e1, const ExpBase<T2>& e2)
{
    return ArrayAdd(e1, e2);
}

template<typename T1, typename T2>
auto operator-(const ExpBase<T1>& e1, const ExpBase<T2>& e2)
{
    return ArrayDiff(e1, e2);
}
}

此时(a1 + a2 - a3)表达式的类型为

ExpTemplates::ArrayDiff<ExpTemplates::ArrayAdd<ExpTemplates::Array<int>, ExpTemplates::Array<int> >, ExpTemplates::Array<int> >

在编译期记录了哪些操作，每个操作对应的对象参数，例如上述代码中将加法作为一个操作对象记录在最终的表达式类型中，最终的表达式对象并没有立即对参数进行求和或者相减，而是在调用operatore[]时才真正开始计算，性能上通过表达式模板也会有比较明显的提升；

|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|        3,310,100.00 |              302.11 |    4.8% |      0.04 | `operator overload impl`
|          619,400.00 |            1,614.47 |    2.2% |      0.01 | `expression templates impl`

运行态分析

这里简单补充下运行时的分析，便于读者快速理解上述代码：

表达式模板(Expression Templates)_cpp

上述代码中使用的容器为vector，可以改进为更加泛化的实现；

template<typename T1, typename T2, typename Operation>
struct ExpBase {
    ExpBase(const T1& left, const T2& right, const Operation& op)
        : m_left(left), m_right(right), m_op(op)
    {};

protected:
    const T1 &m_left;
    const T2 &m_right;
    Operation m_op;
};

template<typename T1, typename T2, typename Operation>
struct ExpTemplates : private ExpBase<T1, T2, Operation> {
    using Base = ExpBase<T1, T2, Operation>;
    using Base::Base;
    auto operator[](size_t index)
    {
        return Base::m_op(Base::m_left[index], Base::m_right[index]);
    }
};

template<typename T1, typename T2>
auto operator+(const T1& left, const T2& right)
{
    auto add = [](auto l, auto r){ return l + r; };
    return ExpTemplates<T1, T2, decltype(add)>(left, right, add);
}

参考资料

【1】C++20高级编程

【2】C++ Templates