microbenchmark with an expression tree

ExprBuilder.c

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

struct Expr
{
	enum { VAL, ADD, MUL } type;
	union {
		double val;
		struct Expr *args[2];
	} data;
}; 

double value(struct Expr *expr)
{
	switch (expr->type)
	{
		case VAL:
			return expr->data.val;
		case ADD:
			return value(expr->data.args[0]) + value(expr->data.args[1]);
		case MUL:
			return value(expr->data.args[0]) * value(expr->data.args[1]);
	}
}

int main ()
{
	int i, j;
	int n = 10 * 1000;

	clock_t tic, toc;

	double total;

	struct Expr *init = (struct Expr*) malloc (3 * sizeof(struct Expr))
                  , *step = init + 1
                  , *iter = init + 2
		  , *temp;

	init->type = VAL;
	init->data.val = 1.0;

	step->type = VAL;
	step->data.val = 1.0;

	iter->type = ADD;
	iter->data.args[0] = init;
	iter->data.args[1] = step;

	printf("init is %g\n", value(init));
	printf("step is %g\n", value(step));
	printf("iter is %g\n", value(iter));

	for (i=0; i<n; i++)
	{
		temp = (struct Expr*) malloc (sizeof (struct Expr));
		temp->type = ADD;
		temp->data.args[0] = iter;
		temp->data.args[1] = step;
		iter = temp;
	}

	printf("iter is %g\n", value(iter));

	init->data.val = 101.0;
	printf("iter is %g\n", value(iter));

	step->data.val = 2.0;
	printf("iter is %g\n", value(iter));

	for (j=0, total=0.0; j<10; j++)
	{
		tic = clock();
		for (i=0; i<n; i++)
		{
			init->data.val = j * 1.0;
			total += value(iter);
		}
		toc = clock();
		printf("%d %g\n", j, (toc - tic) / ((double) CLOCKS_PER_SEC));
	}
		
	printf("total %g\n", total);
	
	return 0;
}

ExprBuilder.cpp

#include <ctime>
#include <iostream>

static int calls = 0;

void inc_n_calls() {
	calls += 1;
}

class Expr {
	public:
		inline virtual double value() = 0;
};

class N : public Expr {
	double x;
	public:
	N(double x_) { x = x_; };
	inline double value() { 
		inc_n_calls();
		return x; 
	};
	void setValue(double x_) {
		x = x_;
	};
};

class BinOp : public Expr {
	public:
	Expr *left, *right;
	BinOp(Expr *left_, Expr *right_) {
		left = left_;
		right = right_;
	};
};

class Add : public BinOp {
	public:
	Add(Expr *left_, Expr *right_) : BinOp(left_, right_) {};
	inline double value() {
		inc_n_calls();
		return left->value() + right->value();
	};
};

class Mul : public BinOp {
	public:
	Mul(Expr *left_, Expr *right_) : BinOp(left_, right_) {};
	inline double value() {
		inc_n_calls();
		return left->value() * right->value();
	};
};


int main () {

	int n = 10 * 1000;
	std::clock_t tic, toc;

	N *init = new N(1.0);
	N *step = new N(1.0);
	Add *iter = new Add(init, step);

	std::cout << "init is " << init->value() << std::endl;
	std::cout << "step is " << step->value() << std::endl;
	std::cout << "iter is " << iter->value() << std::endl;
	for (int i=0; i<n; i++) {
		iter = new Add(iter, step);
	}
	std::cout << "iter is " << iter->value() << std::endl;

	init->setValue(101.0);
	std::cout << "iter is " << iter->value() << std::endl;

	step->setValue(2.0);
	std::cout << "iter is " << iter->value() << std::endl;

	// skip warming

	std::cout << "running..." << std::endl;
	for (int j=0; j<10; j++) {
		tic = std::clock();
		for (int i=0; i<n; i++) {
			init->setValue(j * 1.0);
			iter->value();
		}
		toc = std::clock();
		std::cout << j << " " << (toc - tic) / ((double) CLOCKS_PER_SEC) << std::endl;
	}
	return 0;
}

ExprBuilder.go

package main

import "fmt"

type Expr interface {
	Value() float64
}

type Val struct {
	val float64
}

func (v Val) Value() float64 {
	return v.val
}

type Add struct {
	l *Expr
	r *Expr
}

func (a Add) Value() float64 {
	return a.l.Value() + a.r.Value()
}

func main () {
	i := 10 * 1000

	init := Val{val=0.0}
	step := Val{val=1.0}

	fmt.Printf("hello %d\n", i)
}

ExprBuilder.hs

-- continuing a simple benchmark on evaluating expression trees, now in Haskell..
data Expr = Value Double | Add Expr Expr deriving (Show)

-- instaed of disparate methods on classes, single function for evaluating
eval :: Expr -> Double
eval (Value x) = x
eval (Add x y) = (eval x) + (eval y)

-- in C++/Java, we mutated root of expression tree but in Haskell use partial 
-- application:
step1 :: Expr -> Expr
step1 = Add (Value 1.0)
-- step1 (Value 1.0) -> 2.0

-- iterate the partially applied function 10k times
eval10k :: Double -> Double
eval10k x = eval $ iter10k (Value x)
    where 
        iter10k = iter step1 id (10 * 1000)
        iter f g 0 = g
        iter f g n = iter f (f . g) (n - 1)

main = do
    print $ foldl (+) 0.0 [eval10k (1.0 * (fromInteger i)) | i <- [1..10000]]

ExprBuilder.java

package fr.univ_amu.ins.jode.sandbox;

public class ExprBuilder {
    static int calls = 0;
    public static void inc_n_calls() {
        calls += 1;
    }

    public interface Expr {
        public double value();
    }

    public class N implements Expr {
        double x;
        public N(double x) {
            this.x = x;
        }
        public double value() {
            inc_n_calls();
            return x;
        }
        public void setValue(double x) {
            this.x = x;
        }
    }

    public class BinOp {
        Expr left, right;
        public BinOp(Expr left, Expr right) {
            this.left = left;
            this.right = right;
        }
    }

    public class Add extends BinOp implements Expr {
        public Add(Expr left, Expr right) {
            super(left, right);
        }

        public double value() {
            inc_n_calls();
            return left.value() + right.value();
        }
    }

    public class Mul extends BinOp implements Expr {
        public Mul(Expr left, Expr right) {
            super(left, right);
        }

        public double value() {
            inc_n_calls();
            return left.value() * right.value();
        }
    }

    public ExprBuilder() {
        // max value is stack size dependent
        int n = 10 * 1000;

        Expr init = new N(1.0);
        Expr step = new N(1.0);
        Expr iter = new Add(init, step);

        System.out.println("init is " + init.value());
        System.out.println("step is " + step.value());
        System.out.println("iter is " + iter.value());
        for (int i=0; i<n; i++) {
            iter = new Add(iter, step);
        }
        System.out.println("iter is " + iter.value());

        /* In fact, iter represents a tree. since we still have the reference to the
            root values, changing those and asking for the value is rather easy:
         */
        ((N) init).setValue(101.0);
        System.out.println("iter is " + iter.value());

        ((N) step).setValue(2.0);
        System.out.println("iter is " + iter.value());

        // now the benchmark
        p("warming up...");
        for (int i=0; i<n; i++) iter.value();

        p("running");
        for (int j=0; j<10; j++) {
            double tic = System.nanoTime();
            for (int i = 0; i < n; i++) {
                ((N) init).setValue(i);
                iter.value();
            }
            double toc = System.nanoTime();
            p(j + " " + (toc - tic) / 1e9);
        }
    }

    void p(String msg) {
        System.out.println(msg);
    }

    public static void main(String[] args) {
        ExprBuilder eb = new ExprBuilder();
    }
}

ExprBuilder.ml

type expr = Value of float | Add of expr * expr

let rec eval ex = match ex with 
  | Value (f) -> f
  | Add (l, r) -> let l, r = eval l, eval r in l +. r;;

(* no currying as in Haskell *)
let rec iter f g n = match n with
  | 0 -> (fun x -> g x)
  | n -> iter f (fun x -> f (g x)) (n - 1);;

let _ = 
  let step start = Add (Value 1.0, start) in
  let iter10k = iter step step 10000 in
  let run10k x = eval (iter10k (Value x)) in
  for i=1 to 10000 do
    run10k (float_of_int i);
  done;

ExprBuilder.py

calls = [0]

def inc_n_calls():
    calls[0] += 1

class N(object):
    def __init__(self, x):
        self.x = x
    def value(self):
        return self.x

class BinOp(object):
    left, right = None, None
    def __init__(self, left, right):
        self.left = left
        self.right = right

class Add(BinOp):
    def __init__(self, left, right):
        super(Add, self).__init__(left, right)
    def value(self):
        inc_n_calls()
        return self.left.value() + self.right.value()

class Mul(BinOp):
    def __init__(self, left, right):
        super(Mul, self).__init__(left, right)
    def value(self):
        inc_n_calls()
        return self.left.value() * self.right.value()

import sys, time

n = 10 * 1000
sys.setrecursionlimit(n * 2)

init = N(1.0)
step = N(1.0)
iter = Add(init, step)

print 'init is ', init.value()
print 'step is ', step.value()
print 'iter is ', iter.value()
for i in range(n):
    iter = Add(iter, step)
print 'iter is ', iter.value()

init.x = 101.0
print 'iter is ', iter.value()

step.x =  2.0
print 'iter is ', iter.value()

# skip warm up

print 'running..'
for j in range(10):
    tic = time.time()
    for i in range(n):
        init.x = float(i)
        iter.value()
    toc = time.time()
    print j, (toc - tic)

ExprBuilder2.c

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

struct Expr
{
	double (*value)(struct Expr *);
};

struct Val
{
	struct Expr e;
	double val;
};

struct Add
{
	struct Expr e;
	struct Expr *l, *r;
};

struct Mul
{
	struct Expr e;
	struct Expr *l, *r;
};

double Val_value(struct Val *e)
{
	return e->val;
}

double Add_value(struct Add *e)
{
	return e->l->value(e->l) + e->r->value(e->r);
}

#define new(type, name) struct type * name = (struct type *) malloc (sizeof(struct type));\
name -> e.value = (double (*)(struct Expr *)) &type##_value

int main ()
{
	int i, j;
	int n = 10 * 1000;

	clock_t tic, toc;

	new(Val, init);
	init->val = 1.0;

	new(Val, step);
	step->val = 1.0;

	new(Add, iter);
	iter->l = init->e;
	iter->r = step->e;

	struct Add *temp;

	printf("init is %g\n", init->e.value(init));
	printf("step is %g\n", step->e.value(step));
	printf("iter is %g\n", iter->e.value(iter));

	for (i=0; i<n; i++)
	{
		temp = (struct Add*) malloc (sizeof (struct Expr));
		temp->e.value = Add_value;
		temp->l = iter;
		temp->r = step;
		iter = temp;
	}

	printf("iter is %g\n", iter->e.value(iter));

	init->val = 101.0;
	printf("iter is %g\n", iter->e.value(iter));

	step->val = 2.0;
	printf("iter is %g\n", iter->e.value(iter));

	for (j=0; j<10; j++)
	{
		tic = clock();
		for (i=0; i<n; i++)
		{
			init->val = j * 1.0;
			iter->e.value(iter);
		}
		tic = clock();
		printf("%d %g\n", j, (toc - tic) / ((double) CLOCKS_PER_SEC));
	}
		
	
	return 0;
}

java is like this

/usr/lib/jvm/java-7-openjdk-amd64/bin/java fr.univ_amu.ins.jode.sandbox.ExprBuilder
init is 1.0
step is 1.0
iter is 2.0
iter is 10002.0
iter is 10102.0
iter is 20103.0
warming up...
running
0 0.655811778
1 0.653269823
2 0.652671865
3 0.652922242
4 0.653077405
5 0.652776348
6 0.652843868
7 0.652621976
8 0.652722974
9 0.652812737

where as C++ is a slightly slower

$ g++ -O3 ExprBuilder.cpp -o ExprBuilder
ExprBuilder.cpp:12:25: warning: inline function ‘virtual double Expr::value()’ used but never defined
   inline virtual double value() = 0;
                         ^
$ ./ExprBuilder
init is 1
step is 1
iter is 2
iter is 10002
iter is 10102
iter is 20103
running...
0 1.25227
1 1.05512
2 1.05711
3 1.0591
4 1.05352
5 1.05298
6 1.05141
7 1.05081
8 1.05406
9 1.05307

and Python is more slower..

$ python ExprBuilder.py
init is  1.0
step is  1.0
iter is  2.0
iter is  10002.0
iter is  10102.0
iter is  20103.0
running..
0 66.3638138771
^C

New VM seems faster?

"C:\Program Files\Java\jdk1.8.0_31\bin\java" fr.univ_amu.ins.jode.sandbox.ExprBuilder
init is 1.0
step is 1.0
iter is 2.0
iter is 10002.0
iter is 10102.0
iter is 20103.0
warming up...
running
0 0.568742864
1 0.5773847
2 0.568933723
3 0.565987459
4 0.581211474
5 0.567516886
6 0.578105468
7 0.580668412
8 0.572833952
9 0.584340895

ghc -O3 ExprBuilder.hs
time ./ExprBuilder
user    0m2.443s
sys     0m0.016s

ocamlopt ExprBuilder.ml -o ExprBuilder.opt
time ./ExprBuilder.opt
user    0m2.852s
sys     0m0.012s

Translation from Haskell to OCaml was no-brainer once I figured out that partial application should be explicit. With respect to performance and memory use, OCaml is more obvious, because of strict evaluation: with Haskell, the bang patterns were required to avoid laziness and stack overflow.

This a really stupid benchmark, in fact: it is simply measuring the cost of function calls. A better benchmark would build out an expression tree reflecting an actual application, etc.