Working notes - Expression evaluator

From Eigen
Revision as of 07:08, 20 March 2011 by Ggael (Talk | contribs)

Jump to: navigation, search


Goals

The goal here is to refactor our expression template mechanism such that the construction of the expression tree and its evaluation is 100% decoupled. Basically, at construction time, we should only assemble stupid *Expression* objects that only brings the proper API. Then, at evaluation time, via partial specialization, we would recursively create *Evaluator* objects reflecting how the considered sub expressions can and have to be evaluated. In between we could then implement *TreeOptimizer* objects that would reorganize and optimize the expression tree through partial specialization.

Expression

An expression as to be as simple as possible. Here is a list of elements to take into account for the new design:

One unique expression class semantic operation

For instance, this means that the expression type of the linear product of two abstract expressions A and B will always be Product<A,B>.

Bring the correct API

In practice this means that the expression as to know about both its StorageKind (Dense, Sparse, Band, etc.) and XprKind (Matrix versus Array) such that it can inherit from the right base class (MatrixBase, ArrayBase, SparseMatrixBase, etc.). This is already achieved via a per expression intermediate FooImpl class, e.g.:

  Transpose<Xpr> <- TransposeImpl<Transpose<Xpr>,Xpr::StorageKind>
  TransposeImpl<TransposeXpr,Dense> <- dense_xpr_base<Transpose<TransposeXpr> >::type
  TransposeImpl<TransposeXpr,Sparse> <- SparseMatrixBase<TransposeXpr>

After this evaluator refactoring, these FooImpl classes should not bring any implementation details anymore, and so they could be renamed, and maybe even factorized into a unique dispatcher helper class. Note that the way we select whether the expression itself is, e.g., Sparse or Dense, it still specific to the expression semantic and is not always trivial (e.g., for binary operations), nevertheless, it still seems cleaner and simpler to me to decouple this bit of logic from the dispatcher mechanism such that later one can be implemented once for all per storage/xpr kinds.

Operations that should still be done by the expression

The fact that the expressions do not have to bring any implementation details does not means they have to be as stupid as possible. Indeed, they know about the semantic of the operation they represent, and so they should still be responsible for some basic stuffs like:

  • the computation of the scalar type,
  • computation of the sizes,
  • sanity checks (sizes, scalar types),
  • ...

On the other hand, they should not, and cannot, determine whether they are "vectorizable", "linear", if it has to be evaluated or not, etc. They cannot do any of this because:

  1. this depends on the StorageKind,
  2. this depends on the sub expressions that will be evaluated into temporary and we cannot know this information at construction time (e.g., D = A + B*C won't produce a temporary once processed by the evaluator),
  3. ...

Evaluator

TreeOptimizer