跳至內容

動態分派

維基百科,自由的百科全書

計算機科學中,動態分派(Dynamic dispatch)是指運行時選擇哪一個多態實現(具體的方法或函數)來調用的過程。動態分派通常被應用於面向對象編程(OOP)的語言和系統,並被認為是一個主要特點[1]

面向對象的系統把一個問題看作是一系列通過名字引用來制定操作的相互影響的物體。多態性是指一些可互換的物體雖有相同名字但卻在行為上不同的現象。例如,一個文件對象和一個數據庫對象都有一個儲存記錄的方法來記錄需要存儲的的個人記錄,但是二者的實現卻不同。一個程序可以有對文件或數據庫的訪問。當一個程序調用對象的存儲記錄時,有一些東西需要來決定採取哪種行為。如果有人認為OOP僅僅指給對象發送信息,那麼在這個例子中程序僅僅把一條存儲記錄信息發送給了一個未知類型的對象,而把如何將這條信息發送給正確對象交給運行支持系統來處理。這個對象來決定它執行哪些行為。

與動態分派成對比的是靜態分派,在靜態分派中,對一個多態操作的實現是在編譯時間就選擇好的。動態分派的目的在於支持那些當在編譯時間內無法決定一個多態操作的合適的實現因為這個決定取決於這個操作的一個或多個實際參數的運行類型的情形。

動態分派和動態綁定不同。在選擇操作的上下文中,綁定把名稱和操作相關聯,而分派則在確定名稱所引用的操作之後選擇操作的實現。通過使用動態分派,名稱可以在編譯時被綁定到多態操縱中,但是直到運行時才執行該實現。雖然動態分派不暗示後期綁定,但後期綁定意味着動態分派,因為綁定決定了什麼可以分派。

單一與多重分派

選擇調用方法的具體版本的決定可以基於單個對象或者對象的組合。前者被稱為單一分派,並直接由常見的面向對象語言如C++JavaSmalltalkObjective-CSwiftJavaScriptPython所支持。在這些和與其相類似的語言中,我們可以調用類似於語法的劃分的方法。其參數是可選的。這被認為是發送一個名為divide,帶有除數參數的信息來做除法。

相比之下,一些語言(例如Common LispDylanJulia)採用基於操作數的組合的分派方法或函數;在除法情況下,被除數和除數的類型一起確定將執行哪個除法運算。這就叫做多重分派。

動態分派機制

語言可以用不同的動態分派機制來實現。 由語言提供的動態分派機制的選擇在很大程度上改變了在給定語言內可用或最自然使用的編程範例。

通常,在類型語言中,會基於參數的類型(最常見地基於消息的接收者的類型)來執行分派機制。 這可能被稱為「單類型動態分派」。具有較弱或無打字系統的語言通常攜帶分派表作為每個對象的對象數據的一部分。這允許實例行為因為每個實例可以將給定消息映射到單獨的方法。而有些語言提供混合方法。

動態分派總會產生開銷,因此一些語言為特定方法提供靜態分派。

C++實現

C ++使用早期綁定,並提供動態和靜態分派。 分派的默認形式是靜態的。 為了獲得動態分派,程序員必須將一個方法聲明為virtual。

C ++編譯器通常使用稱為虛擬表(vtable)的數據結構來實現動態分派,該表定義給定類(C ++本身沒有vtable的概念)的消息到方法映射。 然後,該類型的實例將存儲指向此表的指針作為其實例數據的一部分。 當使用多重繼承時,這是複雜的因為C ++不支持後期綁定,C ++對象中的虛擬表不能在運行時修改,這將分派目標的潛在集限制為在編譯時選擇的有限集。

類型重載不會在C ++中產生動態分派,因為語言將消息參數的類型視為正式消息名稱的一部分。 這意味着程序員看到的消息名不是用於綁定的正式名稱。

Go和Rust實現

在Go和Rust中使用了一種更多樣化的早期綁定。 Vtable指針會攜帶對象引用作為一種'fat指針'(go中的接口,或Rust中的'trait對象')。

這使得支持的接口與底層數據結構分離。 為了正確使用類型,每個編譯庫不需要知道所有的接口範圍,只需要知道他們所需要的具體vtable布局即可。 代碼可以將不同接口的同一塊數據傳遞給不同的函數。 這種多功能性以每個對象引用的額外數據為代價,如果許多這樣的引用被持久存儲會出問題。

Smalltalk實現

Smalltalk使用基於類型的消息分派器。每個實例都有一個類型,其定義包含方法。當實例接收到消息時,分派器在消息到方法映射中查找該類型的相應方法,然後調用該方法。

因為一個類型可以有一個基本類型鏈,這個查找可能是非常昂貴的。 一個不成熟的Smalltalk機制的實現似乎比C++有更高的開銷,並且這種開銷將會發生在對象接收的每個消息里。

真正的Smalltalk實現通常使用一種稱為內聯緩存的技術,這種技術使得方法分派非常迅速。內聯緩存基本上存儲調用站點的前一個目標方法地址和對象類(或者多對緩存的多個對)。緩存方法使用最常見的基於方法選擇器的目標方法(或僅緩存缺失處理程序)來進行初始化。當在執行期間到達方法調用站點時,它只調用緩存中的地址。(在動態代碼生成器中,此調用是直接調用,因為直接地址由緩存缺失邏輯負責回填)。被調用方法中的前序代碼將緩存的類與實際對象類進行比較,如果它們不匹配,程序到緩存缺失處理程序分支中尋找正確的方法。一個快速實現可以具有多個高速緩存條目,並且它通常僅需要幾個指令就可以在初始高速緩存未命中時執行正確的方法。常見的情況是一個緩存的類匹配,並且執行只會在該方法中繼續。

外部緩存也可以通過使用對象類和方法選擇器來實現在方法調用邏輯中的使用。在一個設計中,類和方法選擇器被哈希並且用作到方法分派高速緩存表中的索引。

由於Smalltalk是一種反射語言,許多實現允許使用動態生成方法查找表的方法將單個對象變成對象。這允許在每個對象的基礎上更改對象行為。一個被稱為基於原型語言的語言類別已經從這裡生根發芽,其中最著名的是SelfJavaScript。方法分派緩存的細心的設計甚至允許基於原型的語言具有高性能分派方法。

許多其他動態類型的語言,包括PythonRubyObjective-CGroovy都使用類似的方法。

參見

參考文獻

2.Driesen, Karel; Hölzle, Urs; Vitek, Jan (1995). Message Dispatch on Pipelined Processors. ECOOP.

3.Müller, Martin (1995). Message Dispatch in Dynamically-Typed Object-Oriented Languages (Master thesis). University of New Mexico. pp. 16–17.

  1. ^ Milton, Scott; Schmidt, Heinz W. Dynamic Dispatch in Object-Oriented Languages (技術報告). TR-CS-94-02. Australian National University. 1994. CiteSeerX 10.1.1.33.4292可免費查閱.