www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - multiple dispatch using run & compile time reflection

reply Christian Kamm <kamm.incasoftware shift-at-left-and-remove-this.de> writes:
I was experimenting with the new __traits and used it to create a
RTTI-dispatched visitor here:
http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=digitalmars.D.announce&artnum=9348

I've extended the code to allow multiple dispatch and be a bit more generic.
The code is attached, an example is inline:

----
import multipledispatch, std.stdio;

class A {}
class B : A {}

class Foo
{
  void bar(A a1, A a2)
  { writefln("AA"); }

  void bar(A a, B b)
  { writefln("AB"); }
  
  void bar(B a, B b)
  { writefln("BB"); }

  // generates void dispatch(Object,Object)
  // that uses RTTI to call one of the overloads
  // defined above
  mixin MultipleDispatch!("bar", _0, _1);
}

void main()
{
  A a = new A;
  A b = new B;

  auto foo = new Foo;

  foo.dispatch(a, a); // writes AA
  foo.dispatch(a, b); // writes AB
  foo.dispatch(b, b); // writes BB
  
  foo.dispatch(b, a); // throws error
}
----

I have also included a MultipleDispatchFallthrough template that'll call the
best match instead of throwing an error if there's no exact match. However,
the implementation is pretty inefficient. (feel free to optimize)

Here are some rough benchmarks, relative to a virtual function call:

virtual function call: 1
MultipleDispatch with one DispatchArg: 2.5
MultipleDispatch with three DispatchArgs: 2.9
MultipleDispatch with one DispatchArg and Fallthrough: 10

As you can see, a call through MultipleDispatch will take roughly three
times as long as a virtual function call. Since a call to dispatch will
contain two virtual function calls, that's almost optimal.

Regards,
Christian
Jul 24 2007
next sibling parent reply Pragma <ericanderton yahoo.removeme.com> writes:
Christian Kamm wrote:

 I was experimenting with the new __traits and used it to create a
 RTTI-dispatched visitor here:
 http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=digitalmars.D.announce&artnum=9348
 
 I've extended the code to allow multiple dispatch and be a bit more generic.
 The code is attached, an example is inline:
 
 ----
 import multipledispatch, std.stdio;
 
 class A {}
 class B : A {}
 
 class Foo
 {
   void bar(A a1, A a2)
   { writefln("AA"); }
 
   void bar(A a, B b)
   { writefln("AB"); }
   
   void bar(B a, B b)
   { writefln("BB"); }
 
   // generates void dispatch(Object,Object)
   // that uses RTTI to call one of the overloads
   // defined above
   mixin MultipleDispatch!("bar", _0, _1);
 }
 
 void main()
 {
   A a = new A;
   A b = new B;
 
   auto foo = new Foo;
 
   foo.dispatch(a, a); // writes AA
   foo.dispatch(a, b); // writes AB
   foo.dispatch(b, b); // writes BB
   
   foo.dispatch(b, a); // throws error
 }
 ----
 
 I have also included a MultipleDispatchFallthrough template that'll call the
 best match instead of throwing an error if there's no exact match. However,
 the implementation is pretty inefficient. (feel free to optimize)
 
 Here are some rough benchmarks, relative to a virtual function call:
 
 virtual function call: 1
 MultipleDispatch with one DispatchArg: 2.5
 MultipleDispatch with three DispatchArgs: 2.9
 MultipleDispatch with one DispatchArg and Fallthrough: 10
 
 As you can see, a call through MultipleDispatch will take roughly three
 times as long as a virtual function call. Since a call to dispatch will
 contain two virtual function calls, that's almost optimal.
 
 Regards,
 Christian
 


Neat.

I gather that since you're using near-trival function bodies for testing, these
timings represent the relative call 
dispatch overhead?  If so, then that's great research - thanks.

-- 
- EricAnderton at yahoo
Jul 24 2007
parent Christian Kamm <kamm.incasoftware shift-at-left-and-remove-this.de> writes:
 Neat.


Thanks! Experimenting with the new functionality was fun.


 I gather that since you're using near-trival function bodies for testing,
 these timings represent the relative call
 dispatch overhead?


I hope so. For testing I used empty function bodies (they weren't optimized
away; the empty loop finished significantly faster) and an average over ten
million calls.

It might get worse if there are a lot of overloads, but I don't think by
much.
Jul 24 2007
prev sibling parent "Craig Black" <cblack ara.com> writes:
This is very cool!  Is it necessary to place all methods inside a single 
class?  It is sometimes necessary to allow multimethods to be extended in 
multiple classes.  I figure there's probably a way to do this with an 
approach similar to this.

-Craig

"Christian Kamm" <kamm.incasoftware shift-at-left-and-remove-this.de> wrote 
in message news:f84ufe$27e3$1 digitalmars.com...

I was experimenting with the new __traits and used it to create a
 RTTI-dispatched visitor here:
 http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=digitalmars.D.announce&artnum=9348

 I've extended the code to allow multiple dispatch and be a bit more 
 generic.
 The code is attached, an example is inline:

 ----
 import multipledispatch, std.stdio;

 class A {}
 class B : A {}

 class Foo
 {
  void bar(A a1, A a2)
  { writefln("AA"); }

  void bar(A a, B b)
  { writefln("AB"); }

  void bar(B a, B b)
  { writefln("BB"); }

  // generates void dispatch(Object,Object)
  // that uses RTTI to call one of the overloads
  // defined above
  mixin MultipleDispatch!("bar", _0, _1);
 }

 void main()
 {
  A a = new A;
  A b = new B;

  auto foo = new Foo;

  foo.dispatch(a, a); // writes AA
  foo.dispatch(a, b); // writes AB
  foo.dispatch(b, b); // writes BB

  foo.dispatch(b, a); // throws error
 }
 ----

 I have also included a MultipleDispatchFallthrough template that'll call 
 the
 best match instead of throwing an error if there's no exact match. 
 However,
 the implementation is pretty inefficient. (feel free to optimize)

 Here are some rough benchmarks, relative to a virtual function call:

 virtual function call: 1
 MultipleDispatch with one DispatchArg: 2.5
 MultipleDispatch with three DispatchArgs: 2.9
 MultipleDispatch with one DispatchArg and Fallthrough: 10

 As you can see, a call through MultipleDispatch will take roughly three
 times as long as a virtual function call. Since a call to dispatch will
 contain two virtual function calls, that's almost optimal.

 Regards,
 Christian
Jul 24 2007