Editing Dynamic dispatch (section)

===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). 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 static dispatch for particular methods.

====C++ implementation====
C++ uses early binding and offers both dynamic and static dispatch. The default form of dispatch is static. To get dynamic dispatch the programmer must declare a method as {{mono|virtual}}.

C++ compilers typically implement dynamic dispatch with a data structure called a [[virtual method table|virtual function table]] (vtable) that defines the name-to-implementation mapping for a given class as a set of member function pointers. This is purely an implementation detail, as the C++ specification does not mention vtables. Instances of that type will then store a pointer to this table as part of their instance data, complicating scenarios when [[multiple inheritance]] is used. Since C++ does not support late binding, the virtual table in a C++ object cannot be modified at runtime, which limits the potential set of dispatch targets to a finite set chosen at compile time.

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.

====Go, Rust and Nim implementation====
In [[Go (programming language)|Go]], [[Rust (programming language)|Rust]] and [[Nim (programming language)|Nim]], a more versatile variation of early binding is used. 
{{anchor|Fat pointer}}Vtable pointers are carried with object references as 'fat pointers' ('interfaces' in Go, or 'trait objects' in Rust<ref name="Klabnik-Nichols_2023"/><ref>{{cite web |title=Trait objects |url=https://doc.rust-lang.org/reference/types/trait-object.html |website=The Rust Reference |access-date=27 April 2023}}</ref>).

This decouples the supported interfaces from the underlying data structures. Each compiled library needn't know the full range of interfaces supported in order to correctly use a type, just the specific vtable layout that they require. Code can pass around different interfaces to the same piece of data to different functions. This versatility comes at the expense of extra data with each object reference, which is problematic if many such references are stored persistently.

The term ''fat pointer'' simply refers to a [[pointer (computer programming)|pointer]] with additional associated information. The additional information may be a vtable pointer for dynamic dispatch described above, but is more commonly the associated object's size to describe e.g. a ''slice''.{{cn|date=July 2022}} {{See also|Smart pointer}}

====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.

Because a type can have a chain of base types, this look-up can be expensive. 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 every message that an object receives.

Real Smalltalk implementations often use a technique known as [[inline caching]]<ref name="Mueller_1995"/> that makes method dispatch very fast. Inline caching basically stores the previous destination method address and object class of the call site (or multiple pairs for multi-way caching). The cached 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 of 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 programming|prototype-based language]]s has grown from this, the most famous of which are [[Self (programming language)|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 (programming language)|Python]], [[Ruby (programming language)|Ruby]], [[Objective-C]] and [[Groovy (programming language)|Groovy]] use similar approaches.