The whole Enchilada

This blog has suffered from some low traffic lately but for a good reason.

I've have done some eleborate micro-benchmarking in various languages / runtimes on Enchilada's most important data structure: a purely functional binary tree. Next to that, I've benchmarked another important feature: the efficient implementation of infinite precision integers.

In the end I will choose a language / runtime that can serve as the most efficient backend for Enchilada.

I've benchmarked the binary tree implementation (5.000.000 concats) in java (JVM), ocaml and scheme and got the following results on my iBook G4:

- Java 1.5: 70 seconds

- Ocaml (functional style): 40 seconds

- Ocaml (OO style): 60 seconds

- Scheme (macros + gambitc): 92 seconds

So the JVM isn't so bad after all, which is surprising because I'm only using immutable objects.

Nevertheless, I'm starting to like Ocaml - it is very clean and mature language.

Here is the java code:

public abstract class Node
{
  public abstract Node left();
  public abstract Node right();
  public abstract Object size();
  
  public final Node concat(Node n)
  {
    Object ts = size();
    Object ns = n.size();
    
    if (Number.cmp(Number.add(ts, ts), ns) <= 0)
    {
      Node nl = n.left();
      Node nr = n.right();
      if (Number.cmp(nl.size(), (nr.size())) > 0)
      {
        // right rotation
        return new TreeNode(concat(nl.left()), new TreeNode(nl.right(), nr));
      }
      return new TreeNode(concat(nl), nr);
    }
    
    if (Number.cmp(Number.add(ns, ns), ts) <= 0)
    {
      Node tl = left();
      Node tr = right();
      if (Number.cmp(tr.size(), tl.size()) > 0)
      {
        // left rotation
        return new TreeNode(new TreeNode(tl, tr.left()), tr.right().concat(n));
      }
      return new TreeNode(tl, tr.concat(n));
    }
    return new TreeNode(this, n);
  }
  
  public static void main(String[] s)
  {
    Node n = LeafNode.create("singleton");
    Node t = n;
    
    for (int i = 1; i < 5000000; i++)
    {
      t = t.concat(n);
      if ((i % 100000) == 0)
      {
        System.out.println("i: " + i);
      }
    }
  }
}

final class NullNode extends Node
{
  public static final NullNode inst = new NullNode();
  
  private NullNode() {}
  
  public final Node left() { return null; }
  public final Node right()  { return null; }
  public final Object size() {return Number.zero; }
}

final class LeafNode extends Node
{
  private final Object value;
  
  private LeafNode(Object v) { value = v; }
  
  public static final Node create(Object v) { return new LeafNode(v); }
  
  public final Node left() { return NullNode.inst; }
  public final Node right() { return NullNode.inst; }
  public final Object size() { return Number.one; }
}

final class TreeNode extends Node
{
  private final Object size;
  private final Node left;
  private final Node right;
  
  public TreeNode(Node l, Node r)
  {
    left = l;
    right = r;
    size = Number.add(l.size(), r.size());
  }
  
  public final Object size() { return size; }
  public final Node left() { return left; }
  public final Node right() { return right; }
}

final class Number
{
  public static final int c_s = 65535;
  public static final int _c_s = -c_s;
  
  public static final Object[] cache = new Object[(int)c_s * 2];
  
  static
  {
    for (int i = _c_s; i < c_s; i++)
    {
      int[] v = {i};
      cache[(int)(i + c_s)] = v;
    }
  }
  
  public static final int[] one = {1};
  public static final int[] zero = {0};
  
  public final static int[] create(int i)
  {
    if (_c_s < i && i < c_s)
    {
      return (int[])cache[(int)(i + c_s)];
    }
    int[] n = {i};
    return n;
  }
  
  public static final Object add(Object n1, Object n2)
  {
    int[] nn1 = (int[])n1;
    int[] nn2 = (int[])n2;
    if (nn1.length > 1 || nn2.length > 1)
    {
      // bignum
      throw new RuntimeException("BIGNUM not yet supported");
    }
    return create(nn1[0] + nn2[0]);
  }
  
  public static final Object sub(Object n1, Object n2)
  {
    int[] nn1 = (int[])n1;
    int[] nn2 = (int[])n2;
    if (nn1.length > 1 || nn2.length > 1)
    {
      // bignum
      throw new RuntimeException("BIGNUM not yet supported");
    }
    return create(nn1[0] - nn2[0]);
  }
  
  public static final int cmp(Object n1, Object n2)
  {
    int[] nn1 = (int[])n1;
    int[] nn2 = (int[])n2;
    if (nn1.length > 1 || nn2.length > 1)
    {
      // bignum
      throw new RuntimeException("BIGNUM not yet supported");
    }
    if (nn1[0] == nn2[0])
    {
      return 0;
    }
    if (nn1[0] > nn2[0])
    {
      return 1;
    }
    return -1;
  }
  
  public static final String toString(Object n1)
  {
    int[] nn1 = (int[])n1;
    return "" + nn1[0];
  }
}

I dare anyone to prove that their favourite language can improve the above code, both in performance and in succintness! (but remember: your solution needs to have dynamic dispatch on left(), right() and size()).

Read more...

Read more...