Channels ▼
RSS

Parallel

Expression Generics


From C++ to C#

The key reason for fast operation of the C++ expression templates is the inline implementation of the iterator functions, operator*() and operator++(). The compiler produces code similar to a hand-crafted loop without operator overloading. In .NET, interface IEnumerator<> immediately comes to mind as a conceptual equivalent of a forward iterator. However, if I were to use it in my C# implementation of binary and unary operators, I would have introduced traversal of the expression tree in each iteration of the loop and most of the performance gains would have been lost. My plan is to imitate the effect of inlining by doing extra work in the constructors of the binary and unary expression classes, DVBinExpr<> and DVUnaryExpr<>.

First, I implement the iterator increment function. A .NET multicast delegate is a construct that holds the promise of advancing the iterator positions of all input Vector objects without traversing the expression tree. While executing the constructors, I need to locate the appropriate functions of the input Vectors and gather them with a delegate variable at the root node. In the evaluation loop I simply invoke the delegate and increment the iterators of the input variables directly, without the cost of traversal. This delegate is defined as:


delegate bool NextOp();

The Boolean return value is True, unless the end of the container has been reached. Next, all operand types, DVBinExpr<>, DVUnaryExpr<>, and Vector, must provide a way to add their iterator increment function to the multicast delegate passed in from the root of the expression tree. To follow the rules of .NET generics to specify type parameter constraints, I define interface IIter with an iterator increment function:


void AddNextOp(ref NextOp nextOp);

and have the three classes implement it. All non-leaf nodes, in their constructors, call AddNextOp() on their operands and accumulate the result in a member variable. Example 4 is the DVBinExpr<> implementation. When the parent node calls AddNextOp() on its operand, the node's delegate is added to the parent's delegate. The unary nodes are similar, except they only have one operand. The implementation of AddNextOp() at the leaf nodes (that are input Vector objects) appends the actual iterator increment function to the caller's delegate. In my case, the double values are stored in a data member of type List<double>, and all I have to do is get its enumerator instance and append function IEnumerator<double>.MoveNext(). The same Vector object may appear in the expression more than once. Therefore, I take the necessary precaution to add its iterator increment function only once.

Next, I need to tackle "inline" calculation of the expression value at the current positions of the iterators. Each DVBinExpr<> and DVUnaryExpr<> node in the tree knows the operation it must apply to its operands. Consequently, I cannot short-circuit the nodes with a multicast delegate trick. Nonetheless, the same strategy to do extra processing before the evaluation loop executes works here. The LINQ expression facility looks promising with its ability to operate on expressions as data. As the overloaded operators are called and the expression tree is traversed during constructor execution, a System.Linq.Expressions.Expression object representing the tree is assembled. Before the evaluation loop is executed, this object is compiled into executable code, resulting in an equivalent of C++ inlining. How does it work? Every node in the expression tree has a data member of type Expression initialized in the constructor. To make this expression object available to the parent node to use as operand, I add function:


Expression Value();

to the IIter interface that I have introduced for the iterator increment support. A brief design note is in order. This function is an accessor, which I allowed in this simple program. When developing commercial products, I would look for a correct design choice, with behavior co-located with state, on which it depends.

Initialization of the node's Expression data member is delegated to the applicative function that the node receives as a constructor argument. In the C++ implementation, the scope resolution operator is used to invoke static function apply() provided by the applicative classes. In C#, delegates would be a good fit for this purpose. The applicative functions take two forms, for the binary and unary operations, defined by the two delegates BinOp and UOp. With these declarations in hand, I can construct a node's expression (Example 5) for the binary expression.


delegate Expression BinOp(Expression exprA, Expression exprB);
delegate Expression UOp(Expression expr);

class DVBinExpr <IterA, IterB> : IIter
    where IterA : IIter
    where IterB : IIter
{
    public DVBinExpr(IterA ia, IterB ib, BinOp op)
    {
        . . . . . 
        _valExpr = op(ia.Value(), ib.Value());
    }
    . . . . . . 
    private Expression _valExpr;
}

Example 5: Initialization of the node's Expression in C#

Class DVUnaryExpr<> follows the same pattern, with a single operand. Now, I must define the applicative classes for all binary and unary operations, and the mathematical functions. Example 6 shows the multiplication applicative and the invocation of the logarithm function.


public class DVOpMultiply
{
    public static Expression apply(
        Expression exprA, Expression exprB)
    { return Expression.MakeBinary(
        ExpressionType.Multiply, exprA, exprB); }
};
public class DVOpLog
{
    public static Expression apply(Expression expr)
    { return Expression.Call(
        typeof(Math).GetMethod("Log"), expr); }
};

Example 6: Creation of Expression objects in C#

To complete the solution, I need to write operator overloads that construct DVBinExpr<> and DVUnaryExpr objects. In the C++ implementation, the template parameters of the overloaded operators define a nested iterator type Iter. The scope resolution operator :: cannot be applied to parameters in .NET generics. The alternative is to remove the extra level of indirection and explicitly combine the expression and its iterator in a single class. Furthermore, overloaded operators must be defined as static functions in the scope of a class, and at least one of the operands must have the type of the enclosing class. It becomes necessary to define three sets of operators, for Vector, DVBinExpr<>, and DVUnaryExpr<>. A simple wrapper class can be created for the binary and unary expression classes to reduce duplication. The overloaded operators are not templatized in C#. Instead, I rely on the fact that all operands implement IIter. Although the end result is a less generalized construct, compared to C++, it does not contradict the main intent of expression templates. The definition of DVBinExpr<>.operator+() (Example 7) and the rest of the operators are similar.


public static DVBinExpr<DVBinExpr<IterA, IterB>, IIter>
    operator+(DVBinExpr<IterA, IterB> a, IIter b)
{
    return new DVBinExpr<DVBinExpr<IterA, IterB>, IIter>(
        a, b, DVOpAdd.apply);
}

Example 7: Overloaded operator+() in C#

The actual evaluation of the expression takes place in implicit conversion operators defined for DVBinExpr<> (Example 8) and DVUnaryExpr<> that is almost identical. Before entering the loop the Expression instance of the root node is compiled, as I mentioned earlier, with the effect similar to C++ inlining.


public static implicit operator Vector(
    DVBinExpr<IterA, IterB> ex)
{
    Vector result = new Vector(ExpressionGenerics._size);
    ValueOp valOp = 
        Expression.Lambda<ValueOp>(ex.Value()).Compile();
    while(ex._Next())
    {
        result.Add(valOp());
    }
    ex.Reset();
    return result;
}

Example 8: Evaluation of the expression in C#

One more detail I should point out is the scope of the mathematical functions, Log(), Sin(), and so on. In C++, I had them outside the class scope to ensure the desired expression syntax. In C#, these functions must be in a class scope. In the sample program I placed them in the "application" class, ExpressionGenerics, where they are used in an expression.

Test Results

My testing method is the same as in the C++ test described earlier. I have two sample programs complied with Visual C# 2008. One utilizes expression generics, the other usual operator overloading. Both programs evaluate the same expression as before and the rest of the details are the same.

Expression Generics

  • Peak memory utilization: 68Mb
  • Execution time: 1.8 seconds

Brute-force Operator

  • Peak memory utilization: 1.2Gb
  • Execution time: 6.4 seconds


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video