Nice TWiki > Doc > TreeVisitorIntermediateExample (r1.1 vs. r1.3) TWiki webs:
Dev | Doc | Main | TWiki | Sandbox
Doc . { Changes | Index | Search | Go }
 <<O>>  Difference Topic TreeVisitorIntermediateExample (r1.3 - 24 Dec 2003 - IsaacGouy)
Changed:
<
<

dispatchTest(this@Tree) { }

>
>

dispatchTest(Tree this) { }

Changed:
<
<

dispatchTest(this@Interior) {

>
>

dispatchTest(Interior this) {

Changed:
<
<

size(t@Tree) = 1;

>
>

size(Tree t) = 1;

Changed:
<
<

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

>
>

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

Changed:
<
<

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

>
>

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

Changed:
<
<

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

>
>

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

Changed:
<
<

prettyPrint(t@Interior, prefix) {

>
>

prettyPrint(Interior t, prefix) {


 <<O>>  Difference Topic TreeVisitorIntermediateExample (r1.2 - 05 Sep 2003 - IsaacGouy)
Changed:
<
<

Tree and Interior represent a simple binary tree; which is extended with a subclass representing n-ary trees and 3 separate external methods ExtendedTreeVisitorIntermediateExample.

>
>

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.
ftp://ftp.cs.iastate.edu/pub/techreprts/TR01-10/TR.pdf

Added:
>
>

Curtis Clifton kindly gave permission for this use.

Added:
>
>

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

Changed:
<
<

// compilation unit Tree.nice

>
>

// compilation unit dispatchTest.nice - Tree Walk

Changed:
<
<

public class Tree { private !T value;

>
>

void dispatchTest(Tree t);

Changed:
<
<

// internal implementation of prettyPrinting to // measure regular dispatch speed

>
>

dispatchTest(this@Tree) { }

Changed:
<
<

// Unlike MultiJava?, in Nice there's no difference // to methods defined externally - like prettyPrint

>
>

dispatchTest(this@Interior) { this.getLeft().dispatchTest(); this.getRight().dispatchTest(); }

Changed:
<
<

public String internalPrettyPrint(String prefix); internalPrettyPrint(prefix) = prefix + this.getValue().toString + "\n";

>
>

  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
Changed:
<
<

public String internalPrettyPrint(); internalPrettyPrint() = this.internalPrettyPrint("");

>
>

Size

Changed:
<
<

public !T getValue() = value; }

>
>

// compilation unit size.nice
package openclassdispatch;

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

size(t@Tree) = 1;

size(t@Interior) = 1 + t.getLeft().size() + t.getRight().size();
Added:
>
>

  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

Changed:
<
<

// compilation unit Interior.nice

>
>

/ compilation unit prettyPrint.nice

Changed:
<
<

public class Interior extends Tree { private Tree left; private Tree right;

>
>

public String prettyPrint(Tree t);

Changed:
<
<

// internal implementation of prettyPrinting to // measure regular dispatch speed

>
>

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

Deleted:
<
<

// Unlike MultiJava?, in Nice there's no difference // to methods defined externally - like prettyPrint

Changed:
<
<

internalPrettyPrint(prefix) { let result = new StringBuffer?( prefix + this.getValue() + "\n" ); let newPrefix = prefix + "| "; result.append( this.getLeft().internalPrettyPrint( newPrefix ) ); result.append( this.getRight().internalPrettyPrint( newPrefix ) ); return result.toString; }

>
>

public String prettyPrint(Tree t, String prefix);

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

Changed:
<
<

public Tree getLeft() = left; public Tree getRight() = right;

>
>

prettyPrint(t@Interior, 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();

Added:
>
>

  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.


 <<O>>  Difference Topic TreeVisitorIntermediateExample (r1.1 - 05 Sep 2003 - IsaacGouy)
Added:
>
>

%META:TOPICINFO{author="IsaacGouy" date="1062781980" format="1.0" version="1.1"}% %META:TOPICPARENT{name="CodeExamples"}% Tree and Interior represent a simple binary tree; which is extended with a subclass representing n-ary trees and 3 separate external methods ExtendedTreeVisitorIntermediateExample.

// compilation unit Tree.nice
package openclassdispatch;

public class Tree<T> {   
   private !T value;

// internal implementation of prettyPrinting to 
// measure regular dispatch speed

// Unlike MultiJava, in Nice there's no difference
// to methods defined externally -  like prettyPrint

   public String internalPrettyPrint(String prefix);
   internalPrettyPrint(prefix) = 
      prefix + this.getValue().toString + "\n";

   public String internalPrettyPrint();
   internalPrettyPrint() = this.internalPrettyPrint("");

   public !T getValue() = value;   
}

// compilation unit Interior.nice
package openclassdispatch;

public class Interior<T> extends Tree {
   private Tree<T> left;
   private Tree<T> right;

// internal implementation of prettyPrinting to 
// measure regular dispatch speed

// Unlike MultiJava, in Nice there's no difference
// to methods defined externally - like prettyPrint

   internalPrettyPrint(prefix) {
      let result = new StringBuffer( prefix + this.getValue() + "\n" );
      let newPrefix = prefix + "| ";
      result.append( this.getLeft().internalPrettyPrint( newPrefix ) );
      result.append( this.getRight().internalPrettyPrint( newPrefix ) );
      return result.toString;
   }

   public Tree<T> getLeft() = left;
   public Tree<T> getRight() = right;
}
-- IsaacGouy - 05 Sep 2003 %META:TOPICMOVED{by="IsaacGouy" date="1062782272" from="Doc.ExtensibleVisitorIntermediateExample" to="Doc.TreeVisitorIntermediateExample"}%

Topic TreeVisitorIntermediateExample . { View | Diffs | r1.3 | > | r1.2 | > | r1.1 | More }
Revision r1.1 - 05 Sep 2003 - 17:13 GMT - IsaacGouy
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.