Dynamic dispatch
Encyclopedia
In computer science
, dynamic dispatch (also known as dynamic binding) is the process of mapping a message
to a specific sequence of code (method
) at runtime. This is done to support the cases where the appropriate method can't be determined at compile-time (i.e. statically). Dynamic dispatch is only used for code invocation and not for other binding
processes (such as for global variables) and the name is normally only used to describe a language feature where a runtime decision is required to determine which code to invoke.
This Object-Oriented
feature allows substituting a particular implementation using the same interface, and therefore it enables polymorphism
.
contain different implementations of the same method (for example foo). If the class of an object x is not known at compile-time, then when x.foo is called, the program must decide at runtime which implementation of foo to invoke, based on the runtime type of object x. This case is known as single dispatch because an implementation is chosen based on a single type—that of the type of the instance
. Single dispatch is supported by many object-oriented languages, including statically typed languages such as C++
and Java
, and dynamically typed languages such as Smalltalk
and Objective-C
.
In a small number of languages such as Common Lisp
and Dylan, methods or functions can also be dynamically dispatched based on the type of arguments. Expressed in pseudocode, the code manager.handle(y) could call different implementations depending on the type of object y. This is known as multiple dispatch.
Normally, in a typed language, the dispatch mechanism will be performed based on the type of the arguments (most commonly based on the type of the receiver of a message). This might be dubbed 'per type dynamic dispatch'. Languages with weak or no typing systems often carry a dispatch table as part of the object data for each object. This allows instance behaviour as each instance may map a given message to a separate method.
Some languages offer a hybrid approach.
Dynamic dispatch will always incur an overhead so some languages offer the option to turn dynamic dispatch off for particular methods.
Although the overhead involved in this dispatch mechanism is low, it may still be significant for some application areas that the language was designed to target. For this reason, Bjarne Stroustrup
, the designer of C++, elected to make dynamic dispatch optional and non-default. Only functions declared with the virtual keyword
will be dispatched based on the runtime type of the object; other functions will be dispatched based on the object's static type.
As it is possible to store function pointers as part of an object's data, instance behaviour can be used within a C++ program.
Type overloading does not produce dynamic dispatch in C++ as the language considers the types of the message parameters part of the formal message name. This means that the message name the programmer sees is not the formal name used for binding.
, and as such method lookup must search the method dictionaries of parent prototype objects. Caching strategies allow this to perform well.
There is a separate mechanism that allows a class template to be created with a single constructor and to have default methods attached to it. These default methods will then be available to every instance of that type.
A naive implementation of Smalltalk's mechanism would seem to have a significantly higher overhead than that of C++ and this overhead would be incurred for each and every message that an object receives.
In real Smalltalk implementations, a technique known as inline caching is often used that makes method dispatch very fast. Inline caching basically stores the previous destination method address and object class of this call site (or multiple pairs for multi-way caching). The cache method is initialized with the most common target method (or just the cache miss handler), based on the method selector. When the method call site is reached during execution, it just calls the address in the cache (in a dynamic code generator, this call is a direct call as the direct address is back patched by cache miss logic). Prologue code in the called method then compares the cached class with the actual object class, and if they don't match, execution branches to a cache miss handler to find the correct method in the class. A fast implementation may have multiple cache entries and it often only takes a couple instructions to get execution to the correct method on an initial cache miss. The common case will be a cached class match, and execution will just continue in the method.
Out-of-line caching can also be used in the method invocation logic, using the object class and method selector. In one design, the class and method selector are hashed, and used as an index into a method dispatch cache table.
As Smalltalk is a reflective language, many implementations allow mutating individual objects into objects with dynamically generated method lookup tables. This allows altering object behavior on a per object basis. A whole category of languages known as prototype based language
s has grown from this, the most famous of which are Self and JavaScript
. Careful design of the method dispatch caching allows even prototype based languages to have high performance method dispatch.
Many other dynamically typed languages, including Python
, Ruby, Objective-C
and Groovy use similar approaches.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, dynamic dispatch (also known as dynamic binding) is the process of mapping a message
Message passing
Message passing in computer science is a form of communication used in parallel computing, object-oriented programming, and interprocess communication. In this model, processes or objects can send and receive messages to other processes...
to a specific sequence of code (method
Method (computer science)
In object-oriented programming, a method is a subroutine associated with a class. Methods define the behavior to be exhibited by instances of the associated class at program run time...
) at runtime. This is done to support the cases where the appropriate method can't be determined at compile-time (i.e. statically). Dynamic dispatch is only used for code invocation and not for other binding
Name binding
In programming languages, name binding is the association of objects with identifiers. An identifier bound to an object is said to reference that object. Machine languages have no built-in notion of identifiers, but name-object bindings as a service and notation for the programmer is implemented...
processes (such as for global variables) and the name is normally only used to describe a language feature where a runtime decision is required to determine which code to invoke.
This Object-Oriented
Object-oriented programming
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
feature allows substituting a particular implementation using the same interface, and therefore it enables polymorphism
Polymorphism in object-oriented programming
Subtype polymorphism, almost universally called just polymorphism in the context of object-oriented programming, is the ability to create a variable, a function, or an object that has more than one form. The word derives from the Greek "πολυμορφισμός" meaning "having multiple forms"...
.
Single and multiple dispatch
Dynamic dispatch is needed when multiple classesClass (computer science)
In object-oriented programming, a class is a construct that is used as a blueprint to create instances of itself – referred to as class instances, class objects, instance objects or simply objects. A class defines constituent members which enable these class instances to have state and behavior...
contain different implementations of the same method (for example foo). If the class of an object x is not known at compile-time, then when x.foo is called, the program must decide at runtime which implementation of foo to invoke, based on the runtime type of object x. This case is known as single dispatch because an implementation is chosen based on a single type—that of the type of the instance
This (computer science)
In many object-oriented programming languages, this is a keyword that is used in instance methods to refer to the object on which they are working. C++ and languages which derive in style from it generally use this...
. Single dispatch is supported by many object-oriented languages, including statically typed languages such as C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
and Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
, and dynamically typed languages such as Smalltalk
Smalltalk
Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
and Objective-C
Objective-C
Objective-C is a reflective, object-oriented programming language that adds Smalltalk-style messaging to the C programming language.Today, it is used primarily on Apple's Mac OS X and iOS: two environments derived from the OpenStep standard, though not compliant with it...
.
In a small number of languages such as Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
and Dylan, methods or functions can also be dynamically dispatched based on the type of arguments. Expressed in pseudocode, the code manager.handle(y) could call different implementations depending on the type of object y. This is known as multiple dispatch.
Dynamic dispatch mechanisms
A language may be implemented with different dynamic dispatch mechanisms. The choices of the dynamic dispatch mechanism offered by a language to a large extent alter the programming paradigms that are available or are most natural to use within a given language.Normally, in a typed language, the dispatch mechanism will be performed based on the type of the arguments (most commonly based on the type of the receiver of a message). This might be dubbed 'per type dynamic dispatch'. Languages with weak or no typing systems often carry a dispatch table as part of the object data for each object. This allows instance behaviour as each instance may map a given message to a separate method.
Some languages offer a hybrid approach.
Dynamic dispatch will always incur an overhead so some languages offer the option to turn dynamic dispatch off for particular methods.
C++ Implementation
C++ uses a virtual table that defines the message to method mapping for a given class. Instances of that type will then store a pointer to this table as part of their instance data. This is complicated when multiple inheritance is used. The virtual table in a C++ object cannot be modified at run-time, which limits the potential set of dispatch targets to a finite set chosen at compile-time.Although the overhead involved in this dispatch mechanism is low, it may still be significant for some application areas that the language was designed to target. For this reason, Bjarne Stroustrup
Bjarne Stroustrup
Bjarne Stroustrup ; born December 30, 1950 in Århus, Denmark) is a Danish computer scientist, most notable for the creation and the development of the widely used C++ programming language...
, the designer of C++, elected to make dynamic dispatch optional and non-default. Only functions declared with the virtual keyword
Keyword (computer programming)
In computer programming, a keyword is a word or identifier that has a particular meaning to the programming language. The meaning of keywords — and, indeed, the meaning of the notion of keyword — differs widely from language to language....
will be dispatched based on the runtime type of the object; other functions will be dispatched based on the object's static type.
As it is possible to store function pointers as part of an object's data, instance behaviour can be used within a C++ program.
Type overloading does not produce dynamic dispatch in C++ as the language considers the types of the message parameters part of the formal message name. This means that the message name the programmer sees is not the formal name used for binding.
JavaScript Implementation
JavaScript stores the methods as part of the normal instance data. When an object is defined, methods are loaded into it at any point and may be changed at any time. This allows for great flexibility in the object models used to implement systems with the object definitions being determined at runtime. JavaScript is in the family of prototype-based languagesPrototype-based programming
Prototype-based programming is a style of object-oriented programming in which classes are not present, and behavior reuse is performed via a process of cloning existing objects that serve as prototypes. This model can also be known as classless, prototype-oriented or instance-based programming...
, and as such method lookup must search the method dictionaries of parent prototype objects. Caching strategies allow this to perform well.
There is a separate mechanism that allows a class template to be created with a single constructor and to have default methods attached to it. These default methods will then be available to every instance of that type.
Smalltalk Implementation
Smalltalk uses a type based message dispatcher. Each instance has a single type whose definition contains the methods. When an instance receives a message, the dispatcher looks up the corresponding method in the message-to-method map for the type and then invokes the method.A naive implementation of Smalltalk's mechanism would seem to have a significantly higher overhead than that of C++ and this overhead would be incurred for each and every message that an object receives.
In real Smalltalk implementations, a technique known as inline caching is often used that makes method dispatch very fast. Inline caching basically stores the previous destination method address and object class of this call site (or multiple pairs for multi-way caching). The cache method is initialized with the most common target method (or just the cache miss handler), based on the method selector. When the method call site is reached during execution, it just calls the address in the cache (in a dynamic code generator, this call is a direct call as the direct address is back patched by cache miss logic). Prologue code in the called method then compares the cached class with the actual object class, and if they don't match, execution branches to a cache miss handler to find the correct method in the class. A fast implementation may have multiple cache entries and it often only takes a couple instructions to get execution to the correct method on an initial cache miss. The common case will be a cached class match, and execution will just continue in the method.
Out-of-line caching can also be used in the method invocation logic, using the object class and method selector. In one design, the class and method selector are hashed, and used as an index into a method dispatch cache table.
As Smalltalk is a reflective language, many implementations allow mutating individual objects into objects with dynamically generated method lookup tables. This allows altering object behavior on a per object basis. A whole category of languages known as prototype based language
Prototype-based programming
Prototype-based programming is a style of object-oriented programming in which classes are not present, and behavior reuse is performed via a process of cloning existing objects that serve as prototypes. This model can also be known as classless, prototype-oriented or instance-based programming...
s has grown from this, the most famous of which are Self and JavaScript
JavaScript
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
. Careful design of the method dispatch caching allows even prototype based languages to have high performance method dispatch.
Many other dynamically typed languages, including Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
, Ruby, Objective-C
Objective-C
Objective-C is a reflective, object-oriented programming language that adds Smalltalk-style messaging to the C programming language.Today, it is used primarily on Apple's Mac OS X and iOS: two environments derived from the OpenStep standard, though not compliant with it...
and Groovy use similar approaches.
See also
- Function overloading
- Late bindingLate bindingLate binding is a computer programming mechanism in which the method being called upon an object is looked up by name at runtime. This is informally known as duck typing or name binding....
- Message passingMessage passingMessage passing in computer science is a form of communication used in parallel computing, object-oriented programming, and interprocess communication. In this model, processes or objects can send and receive messages to other processes...
- Method overriding
- Name bindingName bindingIn programming languages, name binding is the association of objects with identifiers. An identifier bound to an object is said to reference that object. Machine languages have no built-in notion of identifiers, but name-object bindings as a service and notation for the programmer is implemented...