方法調(diào)用的編譯和運(yùn)行:static dispatch和dynamic dispatch

背景

靜態(tài)分派(static dispatch)和動(dòng)態(tài)分派(dynamic dispatch)是用來處理編程語言語言方法調(diào)用的兩種計(jì)算機(jī)制.
一個(gè)方法是如何被調(diào)用的,這兩種機(jī)制在編譯期和運(yùn)行時(shí)分別做了什么,他們各自的優(yōu)缺點(diǎn)是什么,分別適用于什么樣的場(chǎng)景,讓我們帶著問題看下去吧.

dispatch介紹

我們都知道一個(gè)方法會(huì)在運(yùn)行時(shí)被調(diào)用,一個(gè)方法被喚起,是因?yàn)榫幾g器有一個(gè)計(jì)算機(jī)制,用來選擇正確的方法,然后通過傳遞參數(shù)來喚起它.
這個(gè)機(jī)制通常被成為分派(dispatch). 分派就是處理方法調(diào)用的過程.
分派在處理方法調(diào)用的時(shí)候,可能會(huì)存在多個(gè)合理的可被調(diào)用的方法列表,此時(shí)就需要去選擇最正確的方法.選擇正確方法的整個(gè)過程,就是人們熟知是分派(dispatch).
每種編程語言都需要分派機(jī)制來選擇正確的喚起方法.

方法從書寫完成到調(diào)用完成,概括上會(huì)經(jīng)歷編譯期和運(yùn)行期兩個(gè)階段,而前面說的確定哪個(gè)方法被執(zhí)行,也是在這兩個(gè)時(shí)期進(jìn)行的.
選擇正確方法的階段,可以分為編譯期和運(yùn)行期,而分派機(jī)制通過這兩個(gè)不同的時(shí)期分為兩種: 靜態(tài)分派(static dispatch)和 動(dòng)態(tài)分派(dynamic dispatch).

static dispatch

static dispatch是在編譯期就完全確定調(diào)用方法的分派方式.它是一種方法分派形式.用于描述一個(gè)語言或者環(huán)境是如何選擇被調(diào)用的方法的實(shí)現(xiàn)的.
例如結(jié)合了函數(shù)重載的C++的模板和其他語言的泛型,都是這樣實(shí)現(xiàn)的.

用于在多態(tài)情況下,在編譯期就實(shí)現(xiàn)對(duì)于確定的類型,在函數(shù)調(diào)用表中推斷和追溯正確的方法,包括列舉泛型的特定版本,在提供的全部函數(shù)定義中選擇的特定實(shí)現(xiàn).

與static dispatch相反的dymanic dispatch,是基于運(yùn)行期的給定信息來確定調(diào)用方法的,可能通過虛函數(shù)表實(shí)現(xiàn),也可能借助其他的運(yùn)行期的信息.dynamic dispatch的細(xì)節(jié)我們會(huì)在下面進(jìn)行詳細(xì)說明.
static dispatch可以確保某個(gè)方法只有一種實(shí)現(xiàn).static dispatch明顯的快于dynamic dispatch,因?yàn)?code>dynamic dispatch本身就意味著較高的性能開銷.

何時(shí)使用static dispatch

static dispatch在編譯期確定需要調(diào)用的方法,在運(yùn)行期進(jìn)行調(diào)用.所有的編程語言都是支持static dispatch的,不同語言默認(rèn)的分派方式不同,有的默認(rèn)為static dispatch,有的默認(rèn)是dynamic dispatch.
有的語言可以通過聲明關(guān)鍵字,來標(biāo)明使用static dispatch,比如final或private或static等.這樣用于避免基類的方法屬性等不被子類修改.

static dispatch如何實(shí)現(xiàn)

在編譯器確定使用static dispatch后,會(huì)在生成的可執(zhí)行文件內(nèi),直接指定包含了方法實(shí)現(xiàn)內(nèi)存地址的指針.在運(yùn)行時(shí),直接通過指針調(diào)用特定的方法.這是static dispatch的標(biāo)準(zhǔn)做法.
static dispatch還可以進(jìn)行進(jìn)一步優(yōu)化,優(yōu)化的一種實(shí)現(xiàn)方式叫做內(nèi)聯(lián)(inline:inline expansion).inline是指編譯期從指定被調(diào)用的方法指針,改為將方法的實(shí)現(xiàn)平鋪在調(diào)用方的可執(zhí)行文件內(nèi).下面就講一下inline具體是如何實(shí)現(xiàn)的,它有什么優(yōu)缺點(diǎn).

inline

inline也叫內(nèi)聯(lián)展開,它可以人為聲明,也可以通過編譯器優(yōu)化來實(shí)現(xiàn).inline是將被調(diào)用方法的指針替換為方法實(shí)現(xiàn)體.inline的具體實(shí)現(xiàn)其實(shí)就是內(nèi)聯(lián)展開,它和宏展開(macro expansion很像.
內(nèi)聯(lián)展開和宏展開的區(qū)別在于,內(nèi)聯(lián)發(fā)生在編譯期,并且不會(huì)改變?cè)次募?但是宏展開是在編譯前就完成的,會(huì)改變?cè)创a本身,之后再對(duì)此進(jìn)行編譯.
內(nèi)聯(lián)是一種非常重要的優(yōu)化方式,但是內(nèi)聯(lián)對(duì)于性能的影響比較復(fù)雜.從經(jīng)驗(yàn)法則來講,有些內(nèi)聯(lián)可以通過很小的內(nèi)存消耗來提升運(yùn)行速度.但是無節(jié)制的內(nèi)聯(lián),也可能會(huì)降低速度,因?yàn)閮?nèi)聯(lián)的代碼需要大量的CPU 緩存,并且也會(huì)消耗內(nèi)存空間.

內(nèi)聯(lián)方法的運(yùn)行比傳統(tǒng)的方法調(diào)用要快一些,因?yàn)楣?jié)省了指針到方法實(shí)現(xiàn)體的調(diào)用的消耗,但是會(huì)帶來一些內(nèi)存損失.如果一個(gè)方法被內(nèi)聯(lián)10次,那么會(huì)出現(xiàn)10份方法的副本.所以內(nèi)聯(lián)適用于會(huì)被頻繁調(diào)用的比較小的方法.在C++中,如果方法通過class去定義,默認(rèn)使用內(nèi)聯(lián)(不需要inline關(guān)鍵字).其他情況想要使用內(nèi)聯(lián),需要標(biāo)明inline的關(guān)鍵字.
但是如果一個(gè)方法特別大,被inline關(guān)鍵字修飾的話,編譯器也可能會(huì)選擇不適應(yīng)內(nèi)聯(lián)實(shí)現(xiàn).
所以inline關(guān)鍵字是一個(gè)desire聲明而非require.只能告訴編譯器傾向使用內(nèi)聯(lián)方式,但是最終實(shí)現(xiàn)是編譯器決定的.

內(nèi)聯(lián)的作用
內(nèi)聯(lián)可以用于消減方法被調(diào)用的時(shí)間.非常適用于會(huì)被頻繁調(diào)用的方法.如果方法本身很小的話,可以降低內(nèi)存上的消耗.內(nèi)聯(lián)還為進(jìn)一步的編譯優(yōu)化提供了基礎(chǔ).program optimization
編譯器一般會(huì)將陳述式進(jìn)行內(nèi)聯(lián).
在[函數(shù)式編程語言]
內(nèi)聯(lián)在性能方面會(huì)有提升,而且還可以基于內(nèi)聯(lián),做進(jìn)一步的編譯優(yōu)化,感興趣的可以參考內(nèi)聯(lián)文章的Effect on performance,Compiler support和Implementation部分,這里就不展開說了.

dynamic dispatch

在計(jì)算機(jī)科學(xué)中,dynamic dispatch是 用于在運(yùn)行期選擇調(diào)用方法的實(shí)現(xiàn)的流程.
dynamic dispatch被廣泛應(yīng)用,并且被認(rèn)為是面向?qū)ο笳Z言(Object-Oriented programming:OOP)的基本特性.

OOP是通過名稱來查找對(duì)象和方法的.但是多態(tài)就是一種特殊情況了,因?yàn)榭赡軙?huì)出現(xiàn)多個(gè)同名方法,但是內(nèi)部實(shí)現(xiàn)各不相同.如果把OOP理解為向?qū)ο蟀l(fā)送消息的話.在多態(tài)模式下,就是程序向不知道類型的對(duì)象發(fā)送了消息,然后在運(yùn)行期再將消息分派給正確的對(duì)象.之后對(duì)象再確定執(zhí)行什么操作.

與static dispatch在編譯期確定最終執(zhí)行不同,dynamic dispatch的目的是為了支持在編譯期無法確定最終最合適的實(shí)現(xiàn)的操作.這種情況一般是因?yàn)樵谶\(yùn)行期才能通過一個(gè)或多個(gè)參數(shù)確定對(duì)象的類型.例如 B繼承自A, 聲明var obj : A = B(),編譯期會(huì)認(rèn)為是A類型,但是真正的類型B,只能在運(yùn)行期確定.

dynamic dispatch和late binding(也叫做dynamic binding)不同,程序使用Name binding通過名字去關(guān)聯(lián)操作.在多態(tài)操作中,會(huì)有多個(gè)不同的操作關(guān)聯(lián)同一個(gè)方法名.這個(gè)綁定關(guān)系可以在編譯期或者運(yùn)行期確定.在dynamic dispatch中,是在運(yùn)行期去選擇方法的實(shí)現(xiàn)的.
雖然late binding的綁定實(shí)現(xiàn)也是在運(yùn)行期才能確定,但是dynamic dispatch并不意味著late binding,late binding也不等同于dynamic dispatch.之后會(huì)詳細(xì)講解late binding,這里先挖個(gè)坑.

single and multiple dispatch

通過對(duì)象類型去選擇調(diào)用方法的模式,叫做single dispatch,這是面向?qū)ο笳Z言普遍支持的一種方式,比如C++,Java,Objective-C,Swift,JavaScript,Python等.
在下面示例的方法調(diào)用中,參數(shù)divisor是可選類型.

dividend.divide(divisor)  # dividend / divisor

我們是向?qū)ο骴ividend發(fā)送一個(gè)包含參數(shù)divisor的名為divide消息.在選擇方法實(shí)現(xiàn)時(shí),只會(huì)通過dividend,也就是消息對(duì)象的類型來進(jìn)行選擇.忽略參數(shù)divisor的類型.這種方式叫做single dispatch.
與此相反,一些語言(比如Common Lisp, Dylan, Julia)在方法分派時(shí),會(huì)根據(jù)組合的信息進(jìn)行判斷.拿上面例子來說,是通過接收對(duì)象dividend和參數(shù)divisor一起來決定那個(gè)divide方法會(huì)被調(diào)用.這種方式就成為multiple dispatch

multiple dispatch
Multiple dispatch和single dispatch不同之處在于,multiple dispatch也會(huì)根據(jù)方法名結(jié)合方法的參數(shù),一起來判斷需要執(zhí)行的方法.
在命名方法的時(shí)候,一般會(huì)使用符合方法目的的描述.當(dāng)方法目的相似時(shí),我們也會(huì)使用同名但是不同入?yún)⒌姆绞竭M(jìn)行命名.這種情況時(shí),只使用方法名去查找實(shí)現(xiàn)的方式就不夠充分了.這時(shí)候也需要用到入?yún)?通過入?yún)⒌膫€(gè)數(shù)和類型去進(jìn)行判斷.
對(duì)于single dispatch語言來說,在調(diào)用方法時(shí),參數(shù)會(huì)被特殊處理用于去選擇方法實(shí)現(xiàn),在很多語言中,這種特殊參數(shù)是在語法上就進(jìn)行指明的.例如,很多語言會(huì)把特殊參數(shù)放在調(diào)用語言之前special.method(other, arguments, here)
但是在multiple dispatch中,選擇方法時(shí),也會(huì)對(duì)參數(shù)的個(gè)數(shù)和類型進(jìn)行匹配.沒有特殊參數(shù)去持有方法調(diào)用.

dynamic dispatch的實(shí)現(xiàn)機(jī)制

一種語言可能有多種dynamic dispatch的實(shí)現(xiàn)機(jī)制.語言的特性不同,動(dòng)態(tài)分派的實(shí)現(xiàn)也各有差異.下面我們只針對(duì)一種實(shí)現(xiàn)虛函數(shù)表(vtable: virtual function table)來進(jìn)行詳細(xì)說明.
這里提一句,因?yàn)閯?dòng)態(tài)分派經(jīng)常會(huì)引起高性能消耗,所以很多語言對(duì)某些特定的方法,提供了靜態(tài)分派的方式.

虛函數(shù)表

虛函數(shù)表是用于支持動(dòng)態(tài)分派的一種實(shí)現(xiàn)機(jī)制.
當(dāng)一個(gè)類定義了虛函數(shù)virtual function之后,大部分編譯器會(huì)對(duì)類增加一個(gè)隱藏的屬性,屬性指向一個(gè)包含了虛函數(shù)表,表內(nèi)包含被收納了調(diào)用方法的指針數(shù)組.這些方法指針用于在運(yùn)行期來調(diào)用正確的方法實(shí)現(xiàn).
用來實(shí)現(xiàn)動(dòng)態(tài)分派的方式有很多,虛函數(shù)是在C類語言,例如C++中最普遍的實(shí)現(xiàn)方式.

Java所有的實(shí)例方法都默認(rèn)使用虛函數(shù)表實(shí)現(xiàn).因?yàn)樗蟹椒ǘ伎梢员蛔宇愔剌d使得類變得特別復(fù)雜.當(dāng)類不可被繼承時(shí),理論上是不需要虛函數(shù)表的.所以當(dāng)使用final或private等靜態(tài)修飾符去修飾時(shí),編譯器就可以放心的去使用static dispatch.

Python是不支持static dispatch的.實(shí)際上Python所有的方法和屬性的實(shí)現(xiàn)都使用了late binding.

虛函數(shù)表實(shí)現(xiàn)
對(duì)象的虛函數(shù)表包含對(duì)象綁定的方法地址.方法的調(diào)用需要從虛函數(shù)表內(nèi)獲取方法地址.同一個(gè)類的所有對(duì)象,生成的虛函數(shù)表都是一樣的.屬于同一系列的派生類,他們對(duì)象的虛函數(shù)表都有相同的布局.同一個(gè)方法在表內(nèi)的位移都是相同的.所以,在知道了方法的位移之后,就可以通過虛函數(shù)表直接獲取正確的方法.

編譯器會(huì)為每個(gè)類創(chuàng)建單獨(dú)的虛函數(shù)表.當(dāng)對(duì)象創(chuàng)建后,會(huì)生成一個(gè)隱藏對(duì)象,對(duì)象是一個(gè)指向虛函數(shù)表的指針.編譯器也會(huì)生成包含了虛函數(shù)表指針的代碼.
在不同的語言中,虛函數(shù)表可能在對(duì)象的最后或者第一個(gè)屬性內(nèi),這不影響實(shí)際的功能實(shí)現(xiàn).

虛函數(shù)表示例
以C++為例.

class B1 {
public:
  virtual ~B1() {}
  void f0() {}
  virtual void f1() {}
  int int_in_b1;
};

class B2 {
public:
  virtual ~B2() {}
  virtual void f2() {}
  int int_in_b2;
};

下面是它們的派生類D的聲明

class D : public B1, public B2 {
public:
  void d() {}
  void f2() {}  // override B2::f2()
  int int_in_d;
};

之后創(chuàng)建對(duì)象

B2 *b2 = new B2();
D  *d  = new D();

GCC的g++3.4.6編譯之后,b2生成了如下的32位內(nèi)存結(jié)果

b2:
  +0: pointer to virtual method table of B2
  +4: value of int_in_b2

virtual method table of B2:
  +0: B2::f2()

分析一波內(nèi)存分布.b2的起始位置是B2類虛函數(shù)表的指針.占4個(gè)字節(jié).之后是一個(gè)int類型.

下面看看d的內(nèi)存分布

d:
  +0: pointer to virtual method table of D (for B1)
  +4: value of int_in_b1
  +8: pointer to virtual method table of D (for B2)
 +12: value of int_in_b2
 +16: value of int_in_d

Total size: 20 Bytes.

virtual method table of D (for B1):
  +0: B1::f1()  // B1::f1() is not overridden

virtual method table of D (for B2):
  +0: D::f2()   // B2::f2() is overridden by D::f2()

d是通過多繼承,B1和B2的派生類.可以看到內(nèi)存中,前面幾個(gè)部分和父類的內(nèi)存結(jié)構(gòu)完全一樣.后面添加了自定義的屬性.
需要注意的是,沒有通過virtual關(guān)鍵字聲明的方法f0()和d(),都沒有出現(xiàn)在虛函數(shù)表內(nèi).可能對(duì)于缺省構(gòu)造函數(shù)會(huì)有一些特殊操作,這里不展開說.
通過D重載的B2的f2()方法,是在B2的虛函數(shù)表內(nèi),將過去的B2::f2()的指針替換為D::f2()的指針.

多繼承和thunks
可以看到g++編譯器實(shí)現(xiàn)通過使用B1和B2兩個(gè)虛函數(shù)表來實(shí)現(xiàn)多繼承.每個(gè)表用來說明每個(gè)基類.這里就需要說到指針修正,也叫做thunks

D  *d  = new D();
B1 *b1 = d;
B2 *b2 = d;

代碼執(zhí)行后,d和b1會(huì)指向同一個(gè)內(nèi)存地址,但是b2會(huì)指向d+8.所以b2所指向的d的內(nèi)存范圍會(huì)"看起來"像是B2的實(shí)例.也就是說,和B2擁有相同的內(nèi)存布局.

方法調(diào)用,在多繼承中的實(shí)現(xiàn)
在單繼承中,調(diào)用一個(gè)d->f1()方法.可以分解為如下的偽代碼

(*((*d)[0]))(d)

*d是D的虛函數(shù)表.[0]代表虛函數(shù)表內(nèi)的一個(gè)方法.參數(shù)d為對(duì)象的this指針.
在多繼承情況下,調(diào)用B1::f1()和D::f2()就會(huì)復(fù)雜很多.

(*(*(d[+0]/*pointer to virtual method table of D (for B1)*/)[0]))(d)   /* Call d->f1() */
(*(*(d[+8]/*pointer to virtual method table of D (for B2)*/)[0]))(d+8) /* Call d->f2() */

方法d->f1(0的調(diào)用會(huì)把B1當(dāng)做參數(shù)傳入.方法d->f2(0的調(diào)用會(huì)把B2當(dāng)做參數(shù)傳入.第二個(gè)調(diào)用,就會(huì)用到指針修正來指向正確的指針.因?yàn)?code>B2::f2的地址并不在D的虛函數(shù)表中.
比較來看,d->f0()的調(diào)用就簡(jiǎn)單很多

(*B1::f0)(d)

虛函數(shù)表的性能分析
相比非虛函數(shù)調(diào)用的直接跳轉(zhuǎn)到編譯指針,虛函數(shù)表調(diào)用至少需要一次額外的索引重定向,有時(shí)還需要進(jìn)行指針修正.所以虛函數(shù)表的調(diào)用一定是慢于非虛函數(shù)調(diào)用的.
此外,在不能使用即時(shí)編譯的環(huán)境中,虛函數(shù)調(diào)用一般是不能夠inline的.雖然有一些不常見的內(nèi)聯(lián)方式,這里就不展開了.
為了避免額外的性能消耗,編譯器會(huì)通過計(jì)算,如果調(diào)用可以在編譯期確定,那么就不會(huì)創(chuàng)建虛函數(shù)表.
所以,對(duì)于上面示例中f1的調(diào)用就可以不需要查表操作.因?yàn)榫幾g器可以分辨d只會(huì)持有D類型的指針,而D沒有重載f1.或者編譯器(或優(yōu)化器)也可以發(fā)現(xiàn)B1的所有子類都沒有重載f1.所以B1::f1 或 B2::f2的調(diào)用因?yàn)榭梢源_定它的最終實(shí)現(xiàn),就可以不用查表.(雖然仍需要對(duì)'thsi'指針進(jìn)行修正).

late binding

美國(guó)計(jì)算機(jī)科學(xué)家Alan Kay曾經(jīng)說過,OOP對(duì)我來說,意味著幾個(gè)方面:消息,本地存儲(chǔ),保護(hù)機(jī)制,狀態(tài)流的隱藏,和極致的late binding of all things.

后期微軟又大程度的對(duì)他們面向OOP的COM庫進(jìn)行了升級(jí),COM也同樣提升了early binding和late binding,要知道,很多語言在語法層面是同時(shí)支持這兩種特性的.
什么是late binding呢?
late binding(也叫dynamic binding或dynamic linkage)是一種用于處理在運(yùn)行時(shí)通過對(duì)象調(diào)用方法或者通過函數(shù)名去調(diào)用包含參數(shù)的方法的一種編程機(jī)制.
對(duì)于OOP語音的early binding或 static binding來說,在編譯階段就處理了所有的變量和表達(dá)式.通常這些數(shù)據(jù)存儲(chǔ)在編譯程序的虛函數(shù)表內(nèi),通過位移的方式獲取,非常高效.對(duì)于late binding而言,編譯器不會(huì)解讀足夠的信息去確認(rèn)方法是否存在也不會(huì)將其綁定到虛函數(shù)表內(nèi).late binding是在運(yùn)行時(shí)通過方法名去查找的.

在組件對(duì)象模型編程中,使用late binding的最大優(yōu)勢(shì)在于,不要求編譯器在編譯期間去引用包含對(duì)象的庫.這使得編譯過程可以更有效的去避免類的虛函數(shù)表突然更改帶來的沖突.

late binding的實(shí)現(xiàn)
大部分的動(dòng)態(tài)類型
)語言都可以在運(yùn)行時(shí)去修改對(duì)象的方法列表,因此就需要late binding.

說說OC運(yùn)行時(shí)
蘋果官方對(duì)于OC dynamic binding文檔中指出,dynamic binding就是在運(yùn)行期來決定方法調(diào)用的實(shí)現(xiàn).dymanic binding也叫做late binding.在OC中所有的方法都是在運(yùn)行期動(dòng)態(tài)判斷的.真正執(zhí)行的方法是通過方法名和接收對(duì)象一起來確定的.

參考資料

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容