TWiki . Doc . TreeVisitorIntermediateExample

The original MultiJava code for this benchmark, and the Java comparison code, is available from this Technical Report: "MultiJava: Design, implementation, and evaluation of a Java-compatible language supporting modular open classes and symmetric multiple dispatch", Curtis Clifton, Iowa State University TR #01-10, November 2001.

Curtis Clifton kindly gave permission for this use.

The benchmark results are similar to MultiJava. The Java Extensible Visitor pattern requires much more code, and more complex code, than Nice. The performance of the Java Extensible Visitor implementation degrades from the simple tree walk to the simple size calculation. For the slightly less-simple pretty print method the performance is worse than Nice.

Nice 0.9.2 beta 1,000,000 iterations

Tree Walk

// compilation unit dispatchTest.nice - Tree Walk
package openclassdispatch;

<T> void dispatchTest(Tree<T> t); 

dispatchTest(Tree this) { }

dispatchTest(Interior this) {

  5 Tree Nodes 7 Tree Nodes 341 Tree Nodes
Java Extensible Visitor 281ms 391ms 15,609ms
Nice 141ms 2,828ms 147,047ms
speedup 1.99 0.14 0.11


// compilation unit size.nice
package openclassdispatch;

<T> int size(Tree<T> t);

size(Tree t) = 1;

size(Interior t) = 1 + t.getLeft().size() + t.getRight().size();

  5 Tree Nodes 7 Tree Nodes 341 Tree Nodes
Java Extensible Visitor 657ms 750ms 30,234ms
Nice 172ms 2,828ms 146,828ms
speedup 3.82 0.27 0.21

Pretty Print

/ compilation unit prettyPrint.nice
package openclassdispatch;

public <T> String prettyPrint(Tree<T> t);

prettyPrint(Tree t) = t.prettyPrint( "" );

public <T> String prettyPrint(Tree<T> t, String prefix);

prettyPrint(Tree t, prefix) = prefix + t.value() + "\n";

prettyPrint(Interior t, prefix) {
   let result = new StringBuffer( prefix + t.value() + "\n" );
   let newPrefix = prefix + "| ";
   result.append( t.left().prettyPrint( newPrefix ) );
   result.append( t.right().prettyPrint( newPrefix ) );
   return result.toString();

  5 Tree Nodes 7 Tree Nodes 341 Tree Nodes
Java Extensible Visitor 12,453ms 15,609ms 915,703ms
Nice 7,609ms 12,672ms 764,750ms
speedup 1.64 1.23 1.20

Tree implementations

TreeVisitorClassesIntermediateExample gives implementations for the binary tree and n-ary tree.

-- IsaacGouy - 05 Sep 2003

----- Revision r1.3 - 24 Dec 2003 - 21:34 GMT - IsaacGouy
Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.