CSC/ECE 517 Fall 2010/ch5 5c ck: Difference between revisions

From Expertiza_Wiki
Jump to navigation Jump to search
 
(82 intermediate revisions by the same user not shown)
Line 1: Line 1:
<div class="usermessage hideme" align="center" style="font-size:16pt"><b>Dynamic Dispatch</b></div>
<div class="usermessage hideme" align="center" style="font-size:16pt"><b>Dynamic Dispatch</b></div>
== Introduction ==
== Introduction ==
Dynamic means there is a determination of which method to execute at run time, when a class and one of it's subclasses have the same method signature. This occurs when a class is downcast to one of its super classes and a method is called on the super class object.
Dynamic dispatch means there is a determination of which method to execute at run time, when a class and one of it's subclasses have the same method signature. [http://hal.archives-ouvertes.fr/docs/00/07/22/18/PDF/RR-4370.pdf Evaluation of Control Structures for Dynamic Dispatch in JAVA (pg 5)][1]<br/>
<br/>
Dynamic dispatch occurs when a class is downcast to one of its super classes and a method is called on that super class object.
<br/><br/>
See the Generic Example for an explanation of downcasting.
<br/>
<br/>


== Delegation ==
== Generic Example ==
The mechanism for implementation of prototyping is called Delegation.<sup>[2]</sup><br/>
=== Using Dynamic Dispatch ===
We have a set of objects that can be rendered to the display.<br/>
Each object implements the IRenderable interface as seen below:<br/>
<br/>
<br/>
'Operationally, delegation is the redirection of field access and method invocation from an object or prototype to another, in such a way that an object can be seen as an extension of another.'&nbsp<sup>[7]</sup><br/>
[[Image:Ch5ckRenderable.png]]<br/>
<br/>
Utilizing the ability of dynamic dispatch it is very simple to render a collection of IRenderable[] objects for the display:<br/>
<pre>
IRenderable[] irCollection = {new Circle(0,0,.5), new Polygon(0,0,1,1,2,2,0,0)}
foreach (IRenderable ir in irCollection)
{
  ir.render();
}
</pre>
In the above example, when ir is a Circle it is dynamically downcast to Circle to call Circle.render() and when ir is a Polygon it is dynamically downcast to Polygon to call Polygon .render();
<br/><br/>
'''Note:''' This example would be the same if IRenderable were a class or abstract class object.<br/>
<br/>
<br/>
Delegation is a process whereby an existing object dynamically searches for properties and methods first within itself, then if an match is not found, it delegates that search to its parent object. The parent then repeats the exact same delegation process until a match is found. Once a match is found the result is returned to the requester. <br/><br/>
'''Simple Example'''<br>
This example demonstrates two objects that I always want aligned on the same y axis, however I want them to be independent on the x axis.<br/>
[[Image:ch2ckdelegation1.jpg]]<br/>
Box remains as is but Point is changed<br>
[[Image:Ch2ckdelegation2.JPG]]<br/>
'''NOTE:''' In the above example Box.GetPoint() would also return [10,10]. When GetPoint() searches for X it starts at the original requestors level and uses delegation just like the method search for Box.GetPoint().<br><br/>
While delegation is simple in its design, we will see that it is also elegant. In that it opens the door for several different techniques which allow software developers to morph an existing object, into a much larger and more robust object. While still retaining the original objects simplicity.


==Competing Approaches==
===Class Approach===
New objects are made from predefined classes. A class definition must exist to create an instance of a class. When a class is changed, existing objects must be reconstructed and we also need to ensure that nothing else in the application requires the prior classes constructed behavior.<br/>
===Prototype Approach===
New objects are constructed by copying an existing object. After copying we are safe to change the class behavior knowing that we are independent of all other objects. Prototyping is dynamic allowing us to create a real world object as a single instance and then refactor it at run time.<br>
* We can add to it.<br/>
* We can remove parts from it.<br/>
* We can break parts out and move to a different location in the same delegation tree. Thereby extending the original behavior to more objects in the same object hierarchy.<br/>




=== Static Simulation of Dynamic Dispatch ===
Without dynamic dispatch we would have to test the type of the object, cast it to a subtype and make the call.<pre>
IRenderable[] irCollection = {new Circle(0,0,.5), new Polygon(0,0,1,1,2,2,0,0)}
foreach (IRenderable ir in irCollection)
{
  if (ir is Circle) ((Circle)ir).render();
  if (ir is Polygon) ((Polygon)ir).render();
}
</pre>
This is more complicated than using dynamic dispatch and it also requires us to alter this code every time we add a new class.


== Inside View of Dynamic Dispatch ==
A non dispatched method call is simply a jump to a pointer that is stored inside of the object that the message is sent to.
<br/> In the simplest single dispatch case, a dispatched method call has to look up the location of where to jump in a table.
<br/>In a more complex case, such as double or multiple dispatch, it may have to calculate the table location before looking it up.<br/>
For an in-depth article of how some languages implement dynamic dispatch, read this [http://en.wikipedia.org/wiki/Virtual_table virtual method table] wiki.<br/>
==Single and Multiple Dispatch==
I will start with an example to make it easier to explain.
===Example===
<pre>
class Thing{
  function defeats(Thing t) {throw SingleDispatchException}
}
class Rock extends Thing{
  function defeats(Rock r){throw tryagain}
  function defeats(Scissors s){return t}
  function defeats(Paper p){return f}
}
class Paper extends Thing{
  function defeats(Rock r){return t}
  function defeats(Scissors s){return f}
  function defeats(Paper p){throw tryagain}
}
class Scissors extends Thing{
  function defeats(Rock r){return f}
  function defeats(Scissors s){throw tryagain}
  function defeats(Paper p){return t}
}
Rock r = new Rock();
Thing rt = new Rock();
Thing pt = new Paper();
pt.defeats(rt);
pt.defeats(r);
</pre>
In a single dispatch language: <br/>
* pt has a dynamic type of paper so pt. will call the methods in the paper object.
* pt.defeats(rt); would throw SingleDispatchException because the parameter rt is of static type Thing.<br/>
* pt.defeats(r); would return true because the parameter r is of static type Rock<br/>
<br/>
In a multiple dispatch language:<br/>
* pt has a dynamic type of paper so pt. will call the methods in the paper object.
* pt.defeats(rt); would return true because the parameter rt is of dynamic type Rock.<br/>
* pt.defeats(r); would return true because the parameter r is of dynamic type Rock<br/>
<br/>
===Single Dispatch===
At a minimum, all Object Oriented languages implement a dynamic dispatch process known as [http://www.laputan.org/reflection/Foote-Johnson-Noble-ECOOP-2005.pdf single dispatch (pg2)][2].<br/>
In single dispatch:
* A method call considers the dynamic type of only the class that the message is sent to.
* All parameters are treated as static types.
===Double Dispatch===
<br/>
[[Image:Ch5ckjpgs2.png]]<br/>
<br/>
<pre>
Polygon p = new Square(pt1, pt2, pt2, pt4);
3dObject o = new Pyramid(pt3d1,pt3d2,pt3d3,pt3d4,pt3d5);
o.AddPoints(p,plane);
In double dispatch the above would correctly determine that is needs to call Pyramid.AddPoints(Square, Plane).
</pre>
This method uses single dispatch and the [http://en.wikipedia.org/wiki/Visitor_pattern visitor pattern pg(526-530)][3] to simulate a special form of multiple dispatch where the run time types of two arguments are taken into account.
===Multiple Dispatch===
A few Object Oriented languages implement a more complete dynamic dispatch process known as [http://www.laputan.org/reflection/Foote-Johnson-Noble-ECOOP-2005.pdf multiple dispatch (pg2)][2].<br/>
In multiple dispatch:
* Like single dispatch, a method call considers the dynamic type of the class that the message is sent to.
* One or more parameters are dynamically accessed at run time.
'''Note: When multiple dispatch is implemented, the above double dispatch method with be a part of multiple dispatch.
===Multiple Dispatch Simulation===
[http://www.laputan.org/reflection/Foote-Johnson-Noble-ECOOP-2005.pdf Efficient multimethods in a single dispatch Language][2] is a paper that describes several methods that can be used to simulate multi dispatch in a single dispatch language. It also compares the relative performance of each method.
==Performance==
According to [http://www.open-std.org/jtc1/sc22/wg21/docs/TR18015.pdf Technical Report on C++ Performance (pg 26)][4] "Calling a virtual function is roughly equivalent to calling a function through a pointer stored in an array"<br/>
I interpret this to mean that the speed of single dispatch is roughly the same as the speed of calling a non dispatched method.<br/>
<br/>
[http://www.laputan.org/reflection/Foote-Johnson-Noble-ECOOP-2005.pdf Efficient multimethods in a single dispatch Language (pg 16,17)][2] tested the performance of their simulated multiple dispatch methods showing (pg 17):
'''Performanace Comparison'''
{| class="wikitable" border="1" style="width: 300px; margin-left:60px;"
|- style="text-align: center; "
! Method
! Speed
|-
| Single Dispatch
| 0.20
|-
| Double Dispatch
| 1.00
|-
| Multidispatch (3 args)
| 1.35
|-
| Multidispatch (7 args)
| 2.32
|-
|}
It also shows that other methods such as case statements or dictionary lookup are significantly slower.<br/>
<br/>
MultiJava is a Java language that support multiple dispatch. [http://www.rose-hulman.edu/~clifton/papers/Clifton01.pdf MultiJava: Design, implementation, and evaluation (pg 89 table 6)][5] shows that in MultiJava the native multiple dispatch methods are 62% faster than simulated double dispatch and 59% faster than simulated multiple dispatch.<br/>


==Conclusion==
==Conclusion==
The debate over which is better, class based OOD or prototype based OOD, has been around since the beginning of OOD. Prototype OOD appears to be gaining some mainstream ground, but it is still a long way from taking over traditional class based OOD. It is this authors opinion that this debate is ongoing and will exist in one form or another into the future. I believe that in the past 15 years, neither has proven to be advantagous in all circumstances over the other. I also believe that the evolution of some hybrid language features that attempt to bridge the gap will continue to evolve. I beleive that the future will at times lean in the direction of one or in the direction of the other, bull will never quite cuminate on one or the other.
The information presented in this article covered all of the different types of run time dispatch. It also demonstrated that the trade off between simulated multiple dispatch and native multiple dispatch is only a factor in an application where a very large number of iterations involving multiple dispatch operations are present.


==References==
==References==
[1] [http://education.yahoo.com/reference/dictionary/entry/prototype Yahoo Online Dictionary - Prototype]<br/>
[1] [http://hal.archives-ouvertes.fr/docs/00/07/22/18/PDF/RR-4370.pdf Evaluation of Control Structures for Dynamic Dispatch in Java by Inira Lorraine and Karel Drieson(pg 5)]<br/>
<br/>
[2] [http://www.laputan.org/reflection/Foote-Johnson-Noble-ECOOP-2005.pdf Efficient Multimethods in a single dispatch Language Brian Foote, Ralph E. Johnson and James Noble]<br/>
[3] [http://objectmentor.com/resources/articles/visitor.pdf Visitor by Robert C. Martin 2002 pg(526-520)]<br/>
[4] [http://www.open-std.org/jtc1/sc22/wg21/docs/TR18015.pdf Technical Report on C++ Performance ISO/IEC TR 18015:2006(E) 2006-02-15 (pg. 26)]<br/>
[5] [http://www.rose-hulman.edu/~clifton/papers/Clifton01.pdf MultiJava: Design, implementation, and evaluation Curtis Charles Clifton November 2001(pg 89 table 6)]<br/>

Latest revision as of 01:16, 22 November 2010

Dynamic Dispatch

Introduction

Dynamic dispatch means there is a determination of which method to execute at run time, when a class and one of it's subclasses have the same method signature. Evaluation of Control Structures for Dynamic Dispatch in JAVA (pg 5)[1]

Dynamic dispatch occurs when a class is downcast to one of its super classes and a method is called on that super class object.

See the Generic Example for an explanation of downcasting.

Generic Example

Using Dynamic Dispatch

We have a set of objects that can be rendered to the display.
Each object implements the IRenderable interface as seen below:



Utilizing the ability of dynamic dispatch it is very simple to render a collection of IRenderable[] objects for the display:

IRenderable[] irCollection = {new Circle(0,0,.5), new Polygon(0,0,1,1,2,2,0,0)}
foreach (IRenderable ir in irCollection)
{
   ir.render();
}

In the above example, when ir is a Circle it is dynamically downcast to Circle to call Circle.render() and when ir is a Polygon it is dynamically downcast to Polygon to call Polygon .render();

Note: This example would be the same if IRenderable were a class or abstract class object.


Static Simulation of Dynamic Dispatch

Without dynamic dispatch we would have to test the type of the object, cast it to a subtype and make the call.

IRenderable[] irCollection = {new Circle(0,0,.5), new Polygon(0,0,1,1,2,2,0,0)}
foreach (IRenderable ir in irCollection)
{
   if (ir is Circle) ((Circle)ir).render();
   if (ir is Polygon) ((Polygon)ir).render();
}

This is more complicated than using dynamic dispatch and it also requires us to alter this code every time we add a new class.

Inside View of Dynamic Dispatch

A non dispatched method call is simply a jump to a pointer that is stored inside of the object that the message is sent to.
In the simplest single dispatch case, a dispatched method call has to look up the location of where to jump in a table.
In a more complex case, such as double or multiple dispatch, it may have to calculate the table location before looking it up.
For an in-depth article of how some languages implement dynamic dispatch, read this virtual method table wiki.

Single and Multiple Dispatch

I will start with an example to make it easier to explain.

Example

class Thing{
   function defeats(Thing t) {throw SingleDispatchException}
}
class Rock extends Thing{
   function defeats(Rock r){throw tryagain}
   function defeats(Scissors s){return t}
   function defeats(Paper p){return f}
}
class Paper extends Thing{
   function defeats(Rock r){return t}
   function defeats(Scissors s){return f}
   function defeats(Paper p){throw tryagain}
}
class Scissors extends Thing{
   function defeats(Rock r){return f}
   function defeats(Scissors s){throw tryagain}
   function defeats(Paper p){return t}
}

Rock r = new Rock();
Thing rt = new Rock();
Thing pt = new Paper();

pt.defeats(rt);
pt.defeats(r);

In a single dispatch language:

  • pt has a dynamic type of paper so pt. will call the methods in the paper object.
  • pt.defeats(rt); would throw SingleDispatchException because the parameter rt is of static type Thing.
  • pt.defeats(r); would return true because the parameter r is of static type Rock


In a multiple dispatch language:

  • pt has a dynamic type of paper so pt. will call the methods in the paper object.
  • pt.defeats(rt); would return true because the parameter rt is of dynamic type Rock.
  • pt.defeats(r); would return true because the parameter r is of dynamic type Rock


Single Dispatch

At a minimum, all Object Oriented languages implement a dynamic dispatch process known as single dispatch (pg2)[2].
In single dispatch:

  • A method call considers the dynamic type of only the class that the message is sent to.
  • All parameters are treated as static types.

Double Dispatch




Polygon p = new Square(pt1, pt2, pt2, pt4);
3dObject o = new Pyramid(pt3d1,pt3d2,pt3d3,pt3d4,pt3d5);
o.AddPoints(p,plane);

In double dispatch the above would correctly determine that is needs to call Pyramid.AddPoints(Square, Plane).

This method uses single dispatch and the visitor pattern pg(526-530)[3] to simulate a special form of multiple dispatch where the run time types of two arguments are taken into account.

Multiple Dispatch

A few Object Oriented languages implement a more complete dynamic dispatch process known as multiple dispatch (pg2)[2].
In multiple dispatch:

  • Like single dispatch, a method call considers the dynamic type of the class that the message is sent to.
  • One or more parameters are dynamically accessed at run time.

Note: When multiple dispatch is implemented, the above double dispatch method with be a part of multiple dispatch.

Multiple Dispatch Simulation

Efficient multimethods in a single dispatch Language[2] is a paper that describes several methods that can be used to simulate multi dispatch in a single dispatch language. It also compares the relative performance of each method.

Performance

According to Technical Report on C++ Performance (pg 26)[4] "Calling a virtual function is roughly equivalent to calling a function through a pointer stored in an array"
I interpret this to mean that the speed of single dispatch is roughly the same as the speed of calling a non dispatched method.

Efficient multimethods in a single dispatch Language (pg 16,17)[2] tested the performance of their simulated multiple dispatch methods showing (pg 17): Performanace Comparison

Method Speed
Single Dispatch 0.20
Double Dispatch 1.00
Multidispatch (3 args) 1.35
Multidispatch (7 args) 2.32

It also shows that other methods such as case statements or dictionary lookup are significantly slower.

MultiJava is a Java language that support multiple dispatch. MultiJava: Design, implementation, and evaluation (pg 89 table 6)[5] shows that in MultiJava the native multiple dispatch methods are 62% faster than simulated double dispatch and 59% faster than simulated multiple dispatch.

Conclusion

The information presented in this article covered all of the different types of run time dispatch. It also demonstrated that the trade off between simulated multiple dispatch and native multiple dispatch is only a factor in an application where a very large number of iterations involving multiple dispatch operations are present.

References

[1] Evaluation of Control Structures for Dynamic Dispatch in Java by Inira Lorraine and Karel Drieson(pg 5)
[2] Efficient Multimethods in a single dispatch Language Brian Foote, Ralph E. Johnson and James Noble
[3] Visitor by Robert C. Martin 2002 pg(526-520)
[4] Technical Report on C++ Performance ISO/IEC TR 18015:2006(E) 2006-02-15 (pg. 26)
[5] MultiJava: Design, implementation, and evaluation Curtis Charles Clifton November 2001(pg 89 table 6)