C++ Un esempio di base che illustra i modelli di espressione


Esempio

Un modello di espressione è una tecnica di ottimizzazione in fase di compilazione utilizzata principalmente nel calcolo scientifico. Lo scopo principale è evitare temporanei inutili e ottimizzare i calcoli del loop usando un singolo passaggio (in genere quando si eseguono operazioni su aggregati numerici). Modelli di espressione sono stati inizialmente concepiti per aggirare le inefficienze naive sovraccarico operatore nell'attuazione numerici Array o Matrix tipi. Una terminologia equivalente per i modelli di espressione è stata introdotta da Bjarne Stroustrup, che li chiama "operazioni fuse" nell'ultima versione del suo libro, "Il linguaggio di programmazione C ++".

Prima di entrare effettivamente nei modelli di espressione, dovresti capire perché ne hai bisogno in primo luogo. Per illustrare questo, considera la semplice classe Matrix fornita di seguito:

template <typename T, std::size_t COL, std::size_t ROW>
class Matrix {
public:
    using value_type = T;

    Matrix() : values(COL * ROW) {}

    static size_t cols() { return COL; }
    static size_t rows() { return ROW; }

    const T& operator()(size_t x, size_t y) const { return values[y * COL + x]; }
    T& operator()(size_t x, size_t y) { return values[y * COL + x]; }

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

template <typename T, std::size_t COL, std::size_t ROW>
Matrix<T, COL, ROW>
operator+(const Matrix<T, COL, ROW>& lhs, const Matrix<T, COL, ROW>& rhs)
{
    Matrix<T, COL, ROW> result;

    for (size_t y = 0; y != lhs.rows(); ++y) {
        for (size_t x = 0; x != lhs.cols(); ++x) {
            result(x, y) = lhs(x, y) + rhs(x, y);
        }
    }
    return result;
}

Data la definizione della classe precedente, ora puoi scrivere espressioni Matrix come:

const std::size_t cols = 2000;
const std::size_t rows = 1000;

Matrix<double, cols, rows> a, b, c;

// initialize a, b & c
for (std::size_t y = 0; y != rows; ++y) {
    for (std::size_t x = 0; x != cols; ++x) {
        a(x, y) = 1.0;
        b(x, y) = 2.0;
        c(x, y) = 3.0;
    }
}  

Matrix<double, cols, rows> d = a + b + c;  // d(x, y) = 6 

Come illustrato sopra, essere in grado di sovraccaricare l' operator+() fornisce una notazione che riproduce la notazione matematica naturale per le matrici.

Sfortunatamente, l'implementazione precedente è anche altamente inefficiente rispetto a una versione equivalente "realizzata a mano".

Per capire perché, devi considerare cosa succede quando scrivi un'espressione come Matrix d = a + b + c . Questo infatti si espande in ((a + b) + c) o operator+(operator+(a, b), c) . In altre parole, il ciclo all'interno operator+() viene eseguito due volte, mentre potrebbe essere facilmente eseguito in un singolo passaggio. Ciò comporta anche la creazione di 2 provini, che peggiorano ulteriormente le prestazioni. In sostanza, aggiungendo la flessibilità per usare una notazione vicina alla sua controparte matematica, hai anche reso la classe Matrix altamente inefficiente.

Ad esempio, senza il sovraccarico dell'operatore, è possibile implementare una sommatoria Matrix molto più efficiente utilizzando un singolo passaggio:

template<typename T, std::size_t COL, std::size_t ROW>
Matrix<T, COL, ROW> add3(const Matrix<T, COL, ROW>& a,
                         const Matrix<T, COL, ROW>& b,
                         const Matrix<T, COL, ROW>& c)
{
    Matrix<T, COL, ROW> result;
    for (size_t y = 0; y != ROW; ++y) {
        for (size_t x = 0; x != COL; ++x) {
            result(x, y) = a(x, y) + b(x, y) + c(x, y);
        }
    }
    return result;
}

L'esempio precedente tuttavia ha i suoi svantaggi perché crea un'interfaccia molto più complessa per la classe Matrix (dovresti considerare metodi come Matrix::add2() , Matrix::AddMultiply() e così via).

Facciamo un passo indietro e vediamo come possiamo adattare l'overloading dell'operatore per eseguire in modo più efficiente

Il problema deriva dal fatto che l'espressione Matrix d = a + b + c viene valutata troppo "appassionatamente" prima di aver avuto l'opportunità di costruire l'intero albero delle espressioni. In altre parole, ciò che si vuole veramente ottenere è di valutare a + b + c in un solo passaggio e solo quando effettivamente si ha bisogno di assegnare l'espressione risultante a d .

Questa è l'idea alla base dei modelli di espressione: invece di avere operator+() valuta immediatamente il risultato dell'aggiunta di due istanze Matrix, restituirà un "modello di espressione" per la valutazione futura una volta che l'intero albero di espressioni è stato creato.

Ad esempio, ecco una possibile implementazione per un modello di espressione corrispondente alla somma di 2 tipi:

template <typename LHS, typename RHS>
class MatrixSum
{
public:
    using value_type = typename LHS::value_type;

    MatrixSum(const LHS& lhs, const RHS& rhs) : rhs(rhs), lhs(lhs) {}
    
    value_type operator() (int x, int y) const  {
        return lhs(x, y) + rhs(x, y);
    }
private:
    const LHS& lhs;
    const RHS& rhs;
};

Ed ecco la versione aggiornata di operator+()

template <typename LHS, typename RHS>
MatrixSum<LHS, RHS> operator+(const LHS& lhs, const LHS& rhs) {
    return MatrixSum<LHS, RHS>(lhs, rhs);
}

Come si può vedere, l' operator+() non restituisce più una "valutazione entusiasta" del risultato dell'aggiunta di 2 istanze Matrix (che sarebbe un'altra istanza Matrix), ma invece di un modello di espressione che rappresenta l'operazione di aggiunta. Il punto più importante da tenere a mente è che l'espressione non è stata ancora valutata. Mantiene semplicemente i riferimenti ai suoi operandi.

In effetti, nulla ti impedisce di MatrixSum<> un'istanza del modello di espressione MatrixSum<> come segue:

MatrixSum<Matrix<double>, Matrix<double> > SumAB(a, b);

Tuttavia, in una fase successiva, quando è effettivamente necessario il risultato della somma, valutare l'espressione d = a + b come segue:

for (std::size_t y = 0; y != a.rows(); ++y) {
    for (std::size_t x = 0; x != a.cols(); ++x) {
        d(x, y) = SumAB(x, y);
    }
}

Come si può vedere, un altro vantaggio di utilizzare un modello di espressione, è che si è praticamente riuscito a valutare la somma di a e b e assegnarlo a d in un unico passaggio.

Inoltre, nulla ti impedisce di combinare più modelli di espressioni. Ad esempio, a + b + c risulterebbe nel seguente modello di espressione:

MatrixSum<MatrixSum<Matrix<double>, Matrix<double> >, Matrix<double> > SumABC(SumAB, c);

E anche qui puoi valutare il risultato finale con un solo passaggio:

for (std::size_t y = 0; y != a.rows(); ++y) {
    for (std::size_t x = 0; x != a.cols(); ++x) {
        d(x, y) = SumABC(x, y);
    }
}

Infine, l'ultimo pezzo del puzzle è quello di collegare effettivamente il modello di espressione alla classe Matrix . Ciò si ottiene essenzialmente fornendo un'implementazione per Matrix::operator=() , che prende il modello di espressione come argomento e lo valuta in un passaggio, come fatto "manualmente" prima:

template <typename T, std::size_t COL, std::size_t ROW>
class Matrix {
public:
    using value_type = T;

    Matrix() : values(COL * ROW) {}

    static size_t cols() { return COL; }
    static size_t rows() { return ROW; }

    const T& operator()(size_t x, size_t y) const { return values[y * COL + x]; }
    T& operator()(size_t x, size_t y) { return values[y * COL + x]; }

    template <typename E>
    Matrix<T, COL, ROW>& operator=(const E& expression) {
        for (std::size_t y = 0; y != rows(); ++y) {
            for (std::size_t x = 0; x != cols(); ++x) {
                values[y * COL + x] = expression(x, y);
            }
        }
        return *this;
    }

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