Push-based evaluation

The release of XmlPrime 1.2 has introduced eager evaluation. We use the term eager to refer to an expression whose result is consumed in its entirety. Eager evaluation is an evaluation technique that produces the entire result before returning.

Any expression returning a sequence of items was previously evaluated with lazy evaluation. This method of evaluation returns an IEnumerator<T> instance which computes the values of an expression as they are needed, they are "pulled" from the result of the expression.

In XmlPrime 1.2 when an expression is eager (all its values will be read) the expression is evaluated with a push based strategy. Control flow remains with the expression being evaluated, and the results are "pushed" through to the caller, either by populating a list of values, or by passing the result to a callback function that perfoms further processing on each item.

A second form of eager evaluation has also been added. The purpose of this form of evaluation is to stream the result of a query to the serializer. Previously only complete nodes could be returned. This new method splits nodes into a series of events (very similar to the methods on XmlWriter). These are then passed directly to the serializer.

Both the previous methods treat an item as an atomic value. Historically that meant that for any XML data to be returned, a tree had to be constructed. The performance was worst with constructed nodes wrapping input nodes, like the following:

<results>{//result}</results>

The path expression itself returns a sequence of navigators, but in order to incorporate them in a result tree they have to be copied into an internal representation. This copying process effectively doubles the memory usage of the process, and causes a lot more work than is necessary, especially if the result is then going to be written out and discarded. With the new serialized evaluation, the copying is bypassed and the navigators are passed directly to the serializer.

Being able to write the result directly to the serializer is the most obvious benefit of eager evalution. Eager evaluation however is faster in almost all circumstances where all the values are consumed. To illustrate these benefits I will have to go into more depth with the implementation details.

The final pass of compilation transforms the query in to a tree of IEvalauator instances which provide methods to evaluate the expression. The IEvaluator interface provides all the different evaluation methods.

For this example I will consider the evaluation of a sequence of expressions that are concatenated together. This is implemented as an evaluator class in XmlPrime. The lazy evaluation method returns an instance of the following enumerator:

  internal sealed class FlattenSequenceEnumerator<T> : IEnumerator<T>
  {
    private readonly DynamicContext _context;
    private readonly IEvaluator<T>[] _subsequences;
    private ISeekableEnumerator<T> _currentEnumerator;
    private int _nextIndex;

    public FlattenSequenceEnumerator(IEvaluator<T>[] subsequences, 
                                     DynamicContext context)
    {
      _subsequences = subsequences;
      _currentEnumerator = _subsequences[0].EvaluateLazySequence(context);
      _nextIndex = 1;
      _context = context;
    }

    public override T Current
    {
      get
      {
        return _currentEnumerator.Current;
      }
    }

    public override bool MoveNext()
    {
      while (!_currentEnumerator.MoveNext())
      {
        if (_nextIndex >= _subsequences.Length)
          return false;
        _currentEnumerator =
           _subsequences[_nextIndex++].EvaluateLazySequence(_context);
      }

      return true;
    }
  }

Note: The code has been simplified and reformatted for this blog, and some members have been omitted.

Every time an item is retrieved, the MoveNext method and the Current property is retrieved. Both these calls pass execution to the next enumerator in the chain. However the MoveNext method then needs to check if the enumerator has been exhausted, and if so obtain the next enumerator in the sequence. The overhead of concatenating sequences is two virtual function calls and some state checking for every item returned. Whilst this doesn't sound like much remember that this is just a small part of a tree of evaluations and in more complicated expressions (for example the closures to lazy arguments to recursive functions) this can extend to hundreds of virtual calls for each item returned, from overhead from using enumerators.

Admittedly there are tricks that can be used to reduce the number of virtual calls, for example merging the MoveNext and Current method into one function, or introducing a method that allows a new enumerator to be returned, which would avoid the extra calls for the final argument. Whilst these would reduce the overhead, it would not reduce the fact that the overhead grows proportionally to both the complexity of the expression and the number of items returned.


Now let us consider the eager evaluation methods for this unit:

public override void EvaluateEagerSequence(List<T> items,
                                           DynamicContext context)
{
  for (var i=0; i<_evaluators.Length; i++)
    _evaluators[i].EvaluateEagerSequence(items, context);
}

public override void EvaluateEagerSequence(Action<T> action,
                                           DynamicContext context)
{
  for (var i = 0; i < _evaluators.Length; i++)
    _evaluators[i].EvaluateEagerSequence(action, context);
}

The overhead in this case of enumerating the sequence of items is just the cost of enumerating over an array. There are no per-item costs.

So why don't we use this evaluation method all the time? The main advantages of lazy evaluation is that the values are not computed until they are needed, and if they are not needed they are not computed. Lazy evaluation leaves the caller in full control of the program flow, but eager evaluation keeps control of the program flow and only returns it once all the values have been computed.

The costs are inherent in the IEnumerator model, and derive from the fact that the enumerator must be yield control of what it is doing and be able to continue where it left off.

The ability to abort computation from an eager evaluation could be implemented by raising an exception when the last item required has been processed (although this comes at a cost).

The most efficient way to implement the ability to halt and continue processing in eager evaluation is with coroutines. This would combine all the benifits of both eager and lazy evaluation. Support for coroutines have recently been added to Mono. They are not supported by the Microsoft .NET runtime however and will not be in the near future so it may be many years before we can try this approach.