expression_tree

Table of Contents

• Introduction
• Technical considerations
• Optimizations
  • Branch caching
    • Caching-on-evaluation optimization
    • Caching-on-assignment optimization
    • Degenerate case of caching-on-assignment optimization
  • Parallel evaluation
• Future improvements
• Sample code
• License

Introduction

An expression tree is a tree that stores data in its leaf nodes and operations in its branch nodes. The tree's value can then be obtained by performing a postorder traversal, applying each branch's operation to its children.

For example, this tree evaluates to (2 * 1 + (2 - x)):

(2 * l + r)
 /       \
1      (l - r)
        /   \
      2      x

To build an expression tree with expression_tree::tree, you assign function objects to branch nodes and either constant values or pointers to variables to leaf nodes. When your tree is built, call its evaluate member function to get its value.

Technical considerations

This implementation:

• is contained in a single header file.
• uses templates heavily.
• specializes the branches and the leaves to reduce space overhead.
• is dependent on C++11's function<> class
• can take advantage of multithreading hardware if the <future> header is available.
• requires RTTI.
• has little in the way of safety checks.
• has been tested with GCC 4.2.1, GCC 4.5.0, GCC 4.6.3, VS 2008, VS 2010 and VS 11 Beta.
  • Note that, as of this writing, GCC up to version 4.7 does not implement std::async as one would expect. Thus, parallel evaluation will only truly be parallel when the implementation is corrected.

In order to be evaluated, the tree must be correctly formed. That is, all its branch nodes' children nodes must have been given a value.

Optimizations

Two policies are vailable as template parameters to expression_tree::tree. The first enables caching the value of certain branches to avoid unnecessary evaluation. The second enables multi-threaded evaluation.

Branch caching

Caching optimizations rely on the constness of branches. Once a constant branch has been evaluated, it is not required to evaluate it again. A branch is considered constant when all its children are constant, be they branches or leaves. A leaf is considered constant when its value is assigned a constant value rather than a variable value (i.e. a pointer).

The first optimization caches a branch's value when a it is first evaluated. The second, more aggressive optimziation, caches when a branch's children are assigned to. The default policy is no_caching which performs no caching.

Caching-on-evaluation optimization

By instantiating a tree with its second template parameter set to cache_on_evaluation , a tree's evaluation will be optimzed by caching-on-evaluation. Caching on evaluation simply consists on remembering a branch's value at the time it is evaluated, if that branch is considered constant.

Consider the following tree, where B_n is a branch, C_n is a constant value and x_n is a variable value:

  B1
 /  \
x1  B2
   /  \
  C2  C3

When that tree is evaluated, B₂'s value will be cached because its children are constant. If C₂ and C₃ don't change (i.e. if they are not assigned a different constant value), the second time the tree is evaluated, the evaluation of B₂ will return its cached value. It will not perform its operation on its children again.

Because one of B₁ children is not constant, evaluating B₁ will always perform its operation on its two children.

Caching-on-assignment optimization

By instantiating a tree with its second template parameter set to cache_on_assignment , a tree's evaluation will be optimzed by caching-on-assignment. Caching-on-assignment means that when a branch's children nodes are assigned to, and if those children are constant, the branch's value is evaluated and cached.

Consider the following tree, where B_n is a branch and C_n is a constant value:

  B1
 /  \
C1  B2
   /  \
  C2  C3

Let's assume that that tree is constructed in the following order: B₁, C₁, B₂, C₂, C₃.

Upon assignment of C₃, B₂ will be found to be of constant value and be pre-evaluated. This pre-evaluation will continue recursively up the tree for as long as a branch's both children are constant. In this case, B₁ will also be pre-evaluated.

If C₁ had instead been a variable (e.g. x), only B₂ will have been pre-evaluated. Evaluating B1 would then always perform its operation on its two children.

Degenerate case of caching-on-assignment optimization

Given the following tree:

  B1
 /  \
C1  B2
   /  \
  C2  B3
     /  \
    C3   B4
        / .
       C4  .
            .
            Bn
           /  \
          Cn  Cn+1

Let's assume that that tree is constructed in the following order: B₁, C₁, B₂, C₂, ..., B_n, C_n, C_n+1.

Before C_n+1 is assigned to, none of the tree has been pre-evaluated, given that none of its nodes' constness can be confirmed. When C_n+1 is assigned to, B_n will be found constant and be evaluated. B_n-1 will also be found constant and be evaluated. This will continue until entire tree is evaluated. Thus, a single assignment can trigger the equivalent of evaluate() .

Parallel evaluation

This optimization depends on the availability of C++11's <future> header. It is enabled automatically if your toolchain supports it. To benefit from parallel evaluation, a tree must be instantiated a tree with the parallel policy class.

When enabled, a branch will evaluate one of its children on the current thread and its other child on a separate, hardware permitting. The decision to actually spawn a seperate thread is left to std::async's implementation. For large enough tree's the hardware limit will be reached and branches will start evaluating their children sequentially regardless of their threading policy.

The default policy is sequential which evalutes the tree sequentially.

Future improvements

• I'll think of something. I can't help myself.

Sample code

#include "expression_tree.h"

#include <cassert>
#include <chrono>
#include <iostream>
#include <string>
#include <thread>

#if defined(_WIN32)
#include <Windows.h>
#elif defined(__linux__)
#include <sys/resource.h>
#include <sys/time.h>
#include <unistd.h>
#elif defined(__APPLE__)
#include <mach/mach_init.h>
#include <mach/task.h>
#include <mach/task_info.h>
#endif

using namespace std;

// This function keeps the thread it is run on busy for one second's worth of CPU time.
// Two implementations are provided, one for Windows, the other for Linux.
nullptr_t busy_1_sec(const nullptr_t&, const nullptr_t&)
{
#if defined(_WIN32)

    FILETIME a, b, kernel_ft, user_ft;
    GetThreadTimes(GetCurrentThread(), &a, &b, &kernel_ft, &user_ft);

    ULARGE_INTEGER kernel_start, kernel_elapsed, user_start, user_elapsed;

    kernel_start.HighPart = kernel_ft.dwHighDateTime;
    kernel_start.LowPart = kernel_ft.dwLowDateTime;

    user_start.HighPart = user_ft.dwHighDateTime;
    user_start.LowPart = user_ft.dwLowDateTime;

    do
    {
        short i = 0; while(++i);

        GetThreadTimes(GetCurrentThread(), &a, &b, &kernel_ft, &user_ft);

        kernel_elapsed.HighPart = kernel_ft.dwHighDateTime;
        kernel_elapsed.LowPart = kernel_ft.dwLowDateTime;

        user_elapsed.HighPart = user_ft.dwHighDateTime;
        user_elapsed.LowPart = user_ft.dwLowDateTime;
    }
    while(((kernel_elapsed.QuadPart + user_elapsed.QuadPart) - (kernel_start.QuadPart + user_start.QuadPart)) < 10000000);

#elif defined(__linux__)
    rusage r;
    getrusage(RUSAGE_THREAD, &r);

    double start, elapsed;
    start = r.ru_utime.tv_sec + r.ru_stime.tv_sec + ((r.ru_utime.tv_usec + r.ru_stime.tv_usec) / 1000000.);
    
    do
    {
        char c = 0; while(++c);

        getrusage(RUSAGE_THREAD, &r);

        elapsed = r.ru_utime.tv_sec + r.ru_stime.tv_sec + ((r.ru_utime.tv_usec + r.ru_stime.tv_usec) / 1000000.);
    }
    while(elapsed - start < 1.);
    
#elif defined(__APPLE__)
    task_thread_times_info info;
    mach_msg_type_number_t number = TASK_THREAD_TIMES_INFO_COUNT;
    task_info(mach_task_self(), TASK_THREAD_TIMES_INFO, (task_info_t)&info, &number);
    
    double start, elapsed;
    start = info.user_time.seconds + info.system_time.seconds + ((info.user_time.microseconds + info.system_time.microseconds) * 1e-6);
    
    do
    {
        char c = 0; while(++c);
        
        task_info(mach_task_self(), TASK_THREAD_TIMES_INFO, (task_info_t)&info, &number);
        
        elapsed = info.user_time.seconds + info.system_time.seconds + ((info.user_time.microseconds + info.system_time.microseconds) * 1e-6);
    }while(elapsed - start < 1.);
    
#endif

    return nullptr;
};

int main()
{
    // Create an int tree that will not cache values.
    expression_tree::tree<int, expression_tree::no_caching> tinc;

    // Let's build the simplest of trees, a singe leaf:
    //
    //        3

    tinc.root() = 3;

    cout << tinc.evaluate() << endl; // Prints "3".


    // Let's build a more complex tree:
    //
    //  (2 * l + r)
    //   /       \
    //  1      (l - r)
    //          /   \
    //        2      3

    tinc.root() = [](int i, int j){ return 2 * i + j; };

    tinc.root().left() = 1;
    tinc.root().right() = minus<int>();
    tinc.root().right().left() = 2;
    tinc.root().right().right() = 3;

    cout << tinc.evaluate() << endl; // Prints "1" (2 * 1 + (2 - 3)).

    // Re-evaluate the tree.
    // Because it is a non-caching tree, all nodes will be re-visited and all operations re-applied.
    cout << tinc.evaluate() << endl;

    // Let's change the tree a bit. Make one leaf a variable:
    //
    //  (2 * l + r)
    //   /       \
    //  1      (l - r)
    //          /   \
    //        2      x

    // Assign a variable to the rightmost leaf.
    int x = 1;
    tinc.root().right().right() = &x;

    cout << tinc.evaluate() << endl; // Prints "3" (2 * 1 + (2 - 1)).

    // Change the value of that variable and re-evaluate.
    x = 2;

    cout << tinc.evaluate() << endl; // Prints "2" (2 * 1 + (2 - 2)).


    // Create a string tree with caching-on-evaluation optimization.
    expression_tree::tree<string, expression_tree::cache_on_evaluation> tsce;
    
    // Let's build this tree:
    //
    //    (l + r)
    //  /         \
    // s        (l + r)
    //           /   \
    //         " "  "tree"

    string s = "expression";

    tsce.root() = plus<string>();
    tsce.root().left() = &s;
    tsce.root().right() = plus<string>();
    tsce.root().right().left() = string(" ");
    tsce.root().right().right() = string("tree");

    cout << tsce.evaluate() << endl; // Prints "expression tree".

    // Change the value of variable s and re-evaluate.
    // Because this is a caching tree, constant branches will not be re-evaluated.
    // For this tree, it means the concatenation of " " and "tree" will not be performed again.
    s = "apple";

    cout << tsce.evaluate() << endl; // Prints "apple tree".

    // But hwat happens if we do change the value of one the leaves that had a constant value?
    // The tree will do the right thing, and discard the previously cached value.

    tsce.root().right().right() = string("pie");

    cout << tsce.evaluate() << endl; // Prints "apple pie".


    // Demonstration of a caching-on-modification tree with its degenerate case.

    // Let's build this tree:
    //
    //
    // (l + r)
    //  /   \
    // 1   (l + r)
    //      /   \
    //     2   (l + r)
    //          /   \
    //         3     4

    expression_tree::tree<int, expression_tree::cache_on_assignment> tica;

    tica.root() = plus<int>();
    tica.root().left() = 1;
    tica.root().right() = plus<int>();
    tica.root().right().left() = 2;
    tica.root().right().right() = plus<int>();
    tica.root().right().right().left() = 3;
    tica.root().right().right().right() = 4; // Right here, the entire tree will be pre-evaluated.

    cout << tica.evaluate() << endl; // Prints "10". Even the first time this tree is evaluated, its value is already cached!

    tica.root().right().right().right() = 5; // Again, the entire tree will be pre-evaluated.

    cout << tica.evaluate() << endl; // Prints "11".


    // Here's an example of copying a tree (or sub-tree) to another tree's node.
    expression_tree::tree<int, expression_tree::cache_on_evaluation> tice;

    // We first build a simple tree:
    //
    //  (l + r)
    //  /    \
    // y      2

    int y = 2;

    tice.root() = plus<int>();
    tice.left() = &y;
    tice.right() = 2;

    cout << tice.evaluate() << endl; // Prints "4" (y + 2).

    // Then we build on it (using its own nodes!):
    //
    //     (l + r)
    //      /   \
    // (l + r)   2
    //  /   \
    // y     2

    expression_tree::node<int, expression_tree::cache_on_evaluation> n = tice.root();

    tice.left() = n;

    // Let's make it even bigger:
    //
    //     (l + r)
    //      /   \
    // (l + r)  (l + r)
    //  /   \    /   \
    // y     2  y     2

    tice.right() = n;

    cout << tice.evaluate() << endl; // Prints "8" ((y + 2) + (y + 2)).

    // Demonstration of parallel evaluation.
    //
    // We build two trees with the exact same morphology, one to be evaluated sequentially and another, parallely.
    // Nodes operation is to stay busy for one second.
    // Leaves have no value of consequence.
    //
    //              busy 1s              // Level 1
    //             /       \
    //      busy 1s         busy 1s      // Level 2
    //      /     \         /     \  
    // busy 1s busy 1s busy 1s busy 1s   // Level 3
    //  /   \   /   \   /   \   /   \ 
    // 0     0 0     0 0     0 0     0   // Level 4     (instantaneous evaluation)
    //
    // It should take 7 seconds to evaluate the sequential tree, but less time to evaluate the parallel one.
    // If one's hardware can execute two threads in parallel, level 3 can be evaluated in two seconds and level 2 in one second.
    // If one's hardware can execute four threads in parallel, level 3 and level 2 can each be evaluated in one second.

    // The sequential tree.
    expression_tree::tree<nullptr_t, expression_tree::no_caching, expression_tree::sequential> tnncl;
    tnncl.root() = &busy_1_sec;
    tnncl.left() = &busy_1_sec;
    tnncl.left().left() = &busy_1_sec;
    tnncl.left().left().left() = nullptr;

    tnncl.left().left().right() = tnncl.left().left().left();
    tnncl.left().right() = tnncl.left().left();
    tnncl.right() = tnncl.left();

    auto then = chrono::high_resolution_clock::now();
    tnncl.evaluate();
    cout << "Sequential tree evaluated in " << chrono::duration<float>(chrono::high_resolution_clock::now() - then).count() << " seconds.\n";    // 7 seconds.

    // The parallel tree.
    expression_tree::tree<nullptr_t, expression_tree::no_caching, expression_tree::parallel> tnncp;
    tnncp.root() = &busy_1_sec;
    tnncp.left() = &busy_1_sec;
    tnncp.left().left() = &busy_1_sec;
    tnncp.left().left().left() = nullptr;

    tnncp.left().left().right() = tnncp.left().left().left();
    tnncp.left().right() = tnncp.left().left();
    tnncp.right() = tnncp.left();

    then = chrono::high_resolution_clock::now();
    tnncp.evaluate();
    cout << "Parallel tree evaluated in " << chrono::duration<float>(chrono::high_resolution_clock::now() - then).count() << " seconds.\n";  // 3 seconds on my computer.

    // Misues.

    expression_tree::tree<float> crash;
    //crash.evaluate(); // The tree is empty.

    crash.root() = divides<float>();
    //crash.evaluate(); // This tree cannot be evaluated, its root node is an operation with no data children to operate on.

    crash.root() = 2.;
    //crash.root().left() = divides<float>(); // Assigning to a leaf node's children is undefined behavior.

    return 0;
}

License

Boost Software License - Version 1.0 - August 17th, 2003

Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.