注：這篇文章基于我在布達(dá)佩斯的RuPy大會(huì)上所作的演講。我覺得與其直接將幻燈片發(fā)布出來(lái)，不如在我還有印象的時(shí)候?qū)⑺鼘懗刹┛蛠?lái)的更有意義。同樣，我會(huì)在將來(lái)發(fā)布RuPy大會(huì)的視頻鏈接。我計(jì)劃將在RubyConf大會(huì)上發(fā)表類似的演講，除了有關(guān)于Python的部分，并且將對(duì)比MRI，JRuby以及Rubinius的垃圾回收器是怎樣工作的。

如果想要對(duì)Ruby垃圾回收器以及內(nèi)部原理有更加深入的了解，你可以在我即將出版的新書《Ruby Under a Microscope》中找到答案。

如果算法和業(yè)務(wù)邏輯是一個(gè)人的大腦，那么垃圾回收機(jī)制是人體的哪個(gè)器官呢?

在”Ruby Python”大會(huì)上，我想對(duì)比Ruby和Python內(nèi)部的垃圾回收機(jī)制是一件很有意思的事情。在開始之前，我們?yōu)槭裁匆懻摾厥諜C(jī)制呢?畢竟這是一個(gè)最迷人的，最令人激動(dòng)的主題，不是嗎?你們有多少人對(duì)垃圾回收機(jī)制感到興奮?(許多的大會(huì)參與者竟然舉起了雙手!)

最近，在Ruby社區(qū)中有一篇帖子，關(guān)于怎樣通過(guò)修改Ruby GC的設(shè)置來(lái)提高單元測(cè)試的速度。這棒極了!通過(guò)減少GC垃圾回收的處理來(lái)提高測(cè)試的速度，這是一件很好的事情，但是不怎的，GC不會(huì)真正的讓我感到興奮。就如咋一看就感覺令人厭煩，枯燥的技術(shù)帖子。

事實(shí)上，垃圾回收是一個(gè)令人著迷的主題：垃圾回收算法不僅是計(jì)算機(jī)科學(xué)歷史一個(gè)重要的部分，更是前沿研究的一個(gè)主題。例如，MRI Ruby解釋器使用的”Mark Sweep”算法已經(jīng)超過(guò)了50年的歷史，與此同時(shí)，在Rubinius解釋器中使用的一種垃圾回收算法，是在Ruby中的另一種實(shí)現(xiàn)方式，這種算法僅僅是在2008才被研究出來(lái)。

然而，”垃圾回收”的這個(gè)名稱，是非常的不恰當(dāng)?shù)摹?/p>

應(yīng)用程序的心臟

垃圾回收系統(tǒng)要做的不僅僅是”回收垃圾”。事實(shí)上，它主要完成三個(gè)重要任務(wù)：

為新的對(duì)象分配內(nèi)存

標(biāo)記垃圾對(duì)象

回收垃圾對(duì)象占用的內(nèi)存

想象你的應(yīng)用程序是一個(gè)人的身體：所有你寫的優(yōu)雅的代碼，你的商業(yè)邏輯，你的算法，將會(huì)成為你的應(yīng)用程序的大腦或智能。與此類似的，你認(rèn)為垃圾回收器會(huì)成為身體的哪一個(gè)部分呢?(我從大會(huì)的聽眾中得到了很多有趣的答案：腎，白細(xì)胞)

我認(rèn)為垃圾回收器是一個(gè)應(yīng)用的心臟。正如心臟為身體的其他部分提供血液和養(yǎng)料一樣，垃圾回收器提供內(nèi)存和對(duì)象供程序使用。如果你的心臟停跳，你將活不了幾秒。如果垃圾回收器停止運(yùn)行或者變慢，就像動(dòng)脈阻塞一樣，你的程序?qū)⒆兊穆聛?lái)最后死掉!

一個(gè)簡(jiǎn)單的例子

通過(guò)例子來(lái)驗(yàn)證理論是一種很好的方式。這里有一個(gè)簡(jiǎn)單的類，用Python和Ruby寫成，我們可以將它們作為一個(gè)簡(jiǎn)單的例子：

于此同時(shí)，兩種代碼如此相似讓我感到非常吃驚：Python和Ruby在表達(dá)相同的語(yǔ)義時(shí)幾乎沒(méi)有差別。但是，兩種語(yǔ)言的內(nèi)部實(shí)現(xiàn)方式是否相同呢?

空閑對(duì)象鏈表

在上面的代碼中，當(dāng)我們調(diào)用了Node.new(1)之后，ruby將會(huì)做什么?也就是說(shuō)，Ruby怎樣創(chuàng)建一個(gè)新的對(duì)象?

令人驚訝的是，Ruby做的事情非常少!事實(shí)上，在代碼運(yùn)行之前，Ruby解釋器會(huì)提前創(chuàng)建成千上萬(wàn)的對(duì)象放置到一個(gè)鏈表中，這個(gè)鏈表被稱為”空閑對(duì)象鏈表”(free list)。空閑對(duì)象鏈表(`free list`)在概念上看起來(lái)像下面的樣子：

每一個(gè)白色方塊可以想象成一個(gè)預(yù)創(chuàng)建的，沒(méi)有使用的Ruby對(duì)象。當(dāng)我們調(diào)用Node.new，Ruby簡(jiǎn)單的使用一個(gè)對(duì)象，并且將它的引用返回給我們：

在上圖中，左邊的灰色方塊代表一個(gè)活躍的Ruby對(duì)象，被我們的代碼所使用，而其余的白色方塊代碼沒(méi)有使用的對(duì)象。(注意：當(dāng)然，圖中是一種簡(jiǎn)化的實(shí)現(xiàn)版本。事實(shí)上，Ruby將會(huì)使用另外一個(gè)對(duì)象保存字符串”ABC”，使用第三個(gè)對(duì)象保存Node的定義，以及其他的對(duì)象保存代碼處理過(guò)的抽象語(yǔ)法數(shù)”AST”，等待。)

如果我們?cè)俅握{(diào)用Node.new，Ruby僅僅返回另外一個(gè)對(duì)象的引用。

約翰麥卡錫在1960年在Lisp中首次實(shí)現(xiàn)了垃圾回收機(jī)制

這中使用預(yù)創(chuàng)建對(duì)象鏈表的簡(jiǎn)單算法發(fā)明于50多年前，它的作者是傳說(shuō)中的計(jì)算機(jī)科學(xué)家，約翰麥卡錫，正是他實(shí)現(xiàn)了最初的Lisp解釋器。Lisp不僅是第一個(gè)函數(shù)式編程語(yǔ)言，并且包含了計(jì)算機(jī)科學(xué)中許多突破性的進(jìn)展。其中之一便是通過(guò)垃圾回收機(jī)制自動(dòng)管理內(nèi)存。

標(biāo)準(zhǔn)版Ruby，也就是”Matz’s Ruby Interpreter”(MRI)，使用了一種類似于約翰麥卡錫在1960年實(shí)現(xiàn)的Lisp的垃圾回收算法。就像Lisp一樣，Ruby會(huì)預(yù)先創(chuàng)建對(duì)象并且在你創(chuàng)建對(duì)象或值的時(shí)候返回對(duì)象的引用。

在Python中分配對(duì)象內(nèi)存

從上面我們可以看出，Ruby會(huì)預(yù)先創(chuàng)建對(duì)象，并且保存在空閑對(duì)象鏈表(free list)中。那么Python呢?

當(dāng)然Python內(nèi)部也會(huì)由于各種原因使用空閑對(duì)象鏈表(它使用鏈表循環(huán)確定對(duì)象)，Python為對(duì)象和值分配內(nèi)存的方式常常不同于Ruby。

假設(shè)我們創(chuàng)建一個(gè)Node對(duì)象使用Python：

Python不同于Ruby，當(dāng)你創(chuàng)建對(duì)象的時(shí)候，Python會(huì)立即向操作系統(tǒng)申請(qǐng)分配內(nèi)存。(Python 事實(shí)上實(shí)現(xiàn)了自己的內(nèi)存分配系統(tǒng)，它在操作系統(tǒng)內(nèi)存堆上提供了另外一層抽象，但是今天沒(méi)有事件深入探討。 )

當(dāng)我們創(chuàng)建第二個(gè)對(duì)象時(shí)，Python將再次向操作系統(tǒng)申請(qǐng)更多的內(nèi)存：

看起來(lái)相當(dāng)簡(jiǎn)單，當(dāng)我們創(chuàng)建Python對(duì)象的時(shí)刻，將花費(fèi)事件申請(qǐng)內(nèi)存。

Ruby將沒(méi)有用的對(duì)象扔的到處都是，直到下一個(gè)垃圾回收過(guò)程

Ruby開發(fā)者生活在一個(gè)臟亂的房間

回到Ruby，由于我們分配越來(lái)越多的對(duì)象，Ruby將繼續(xù)為我們從空閑對(duì)象鏈表(free list)獲取預(yù)分配對(duì)象。因此，空閑對(duì)象鏈表將變得越來(lái)越短：

或者更短：

請(qǐng)注意，我將一個(gè)新的值賦給了n1，Ruby會(huì)遺留下舊的值。”ABC”, “JKL”和”MNO”等結(jié)點(diǎn)對(duì)象會(huì)依然保留在內(nèi)存中。Ruby不會(huì)立即清理舊的對(duì)象盡管程序不再使用!作為一名Ruby開發(fā)者就像生活在一個(gè)臟亂的房間，衣服隨意的仍在地板上，廚房的水槽中堆滿了臟盤子。作為一個(gè)Ruby開發(fā)者，你必須在一大堆垃圾對(duì)象中去工作。

當(dāng)你的程序不在使用任何對(duì)象的時(shí)候，Python會(huì)立刻進(jìn)行清理。

Python開發(fā)者生活在一所整潔的房子

垃圾回收機(jī)制在Python和Ruby中迥然不同，讓我們回到前面三個(gè)Python中Node對(duì)象的例子：

內(nèi)部的，每當(dāng)我們新建一個(gè)對(duì)象，Python將在對(duì)象對(duì)應(yīng)的C語(yǔ)言結(jié)構(gòu)中保存一個(gè)數(shù)字，叫做引用技術(shù)。最初，Python將它的值設(shè)為1。

值為1表明每個(gè)對(duì)象有一個(gè)指針或引用指向它。假設(shè)我們創(chuàng)建一個(gè)新的對(duì)象，JKL：

正如前面所說(shuō)，Python將”JKL”的引用計(jì)數(shù)設(shè)置為1。同樣注意到我們改變n1指向了”JKL”，不再引用”ABC”，同時(shí)將”ABC”的引用計(jì)數(shù)減少為0。

通過(guò)這一點(diǎn)，Python垃圾回收器將會(huì)立即執(zhí)行!無(wú)論何時(shí)，只要一個(gè)對(duì)象的引用計(jì)數(shù)變?yōu)?，python將立即釋放這個(gè)對(duì)象，并且將它的內(nèi)存返回給操作系統(tǒng)。

上圖中，Python將回收”ABC”對(duì)象的內(nèi)存。記住，Ruby只是將舊的對(duì)象遺留在那里并且不去釋放它們占用的內(nèi)存。

這種垃圾回收算法被稱為”引用計(jì)數(shù)”，由喬治柯林斯發(fā)明于1960年。非常巧合的是在同一年約翰麥卡錫大叔發(fā)明了”空閑對(duì)象鏈表算法”。正如Mike Bernstein在Ruby Conference大會(huì)上所說(shuō)”1960年是屬于垃圾回收器的…”。

作為一個(gè)Python開發(fā)者，就像生活在一個(gè)整潔的房間中。你知道，你的室友有些潔癖，他會(huì)把你使用過(guò)的任何東西都清洗一遍。你把臟盤子，臟杯子一放到水槽中他就會(huì)清洗。

現(xiàn)在看另外一個(gè)例子，假設(shè)我們讓n2和n1指向同樣的結(jié)點(diǎn)：

上圖左邊可以看到，Python減少了”DEF”的引用計(jì)數(shù)并且立即回收了”DEF”對(duì)象。同時(shí)可以看到，由于n1和n2同時(shí)指了”JKL”對(duì)象，所以它的引用計(jì)數(shù)變?yōu)榱?。

標(biāo)記回收算法

最終臟亂的房間將堆慢垃圾，生活不能總是如此。Ruby程序在運(yùn)行一段時(shí)間之后，空閑對(duì)象鏈表最終將被用盡。

上圖中所有的預(yù)分配對(duì)象都被用盡(方塊全部變成了灰色)，鏈表上沒(méi)有對(duì)象可用(沒(méi)有剩余的白色方塊)。

此時(shí)，Ruby使用了一種由約翰麥卡錫發(fā)明的被稱為”標(biāo)記回收”的算法。首先，Ruby將停止程序的執(zhí)行，Ruby使用了”停止這個(gè)世界，然后回收垃圾”的方式。然后，Ruby會(huì)掃描所有的指向?qū)ο蠛椭档闹羔樆蛞?。同樣，Ruby也會(huì)迭代虛擬機(jī)內(nèi)部使用的指針。它會(huì)標(biāo)記每一個(gè)指針?biāo)艿竭_(dá)的對(duì)象。在下圖中，我使用了”M”指出了這些標(biāo)記：[!--empirenews.page--]

上面三個(gè)”M”標(biāo)記的對(duì)象為活躍對(duì)象，依然被我們的程序使用。在Ruby解釋器內(nèi)部，通常使用”free bitmap”的數(shù)據(jù)結(jié)構(gòu)來(lái)保存一個(gè)對(duì)象是否被標(biāo)記：

Ruby將”free bitmap”保存在一個(gè)獨(dú)立的內(nèi)存區(qū)域，以便可以更好的利用Unix的”copy-on-write”特性。更詳細(xì)的信息，請(qǐng)參考我的另一篇文章《為什么Ruby2.0的垃圾回收器讓我們?nèi)绱伺d奮》。

如果活躍對(duì)象被標(biāo)記了，那么其余的便是垃圾對(duì)象，意味著它們不再會(huì)被代碼使用。在下圖中，我使用白色的方塊表示垃圾對(duì)象：

接下來(lái)，Ruby將清理沒(méi)有使用的，垃圾對(duì)象，將它們鏈入空閑對(duì)象鏈表(free list)：

在解釋器內(nèi)部，這個(gè)過(guò)程非常迅速，Ruby并不會(huì)真正的將對(duì)象從一個(gè)地方拷貝到另一個(gè)地方。相反的，Ruby會(huì)將垃圾對(duì)象組成一個(gè)新的鏈表，并且鏈入空閑對(duì)象鏈表(free list)。

現(xiàn)在，當(dāng)我們要?jiǎng)?chuàng)建一個(gè)新的Ruby對(duì)象的時(shí)候，Ruby將為我們返回收集的垃圾對(duì)象。在Ruby中，對(duì)象是可以重生的，享受著多次的生命!

標(biāo)記回收算法 vs. 引用計(jì)數(shù)算法

咋一看，Python的垃圾回收算法對(duì)于Ruby來(lái)說(shuō)是相當(dāng)讓人感到驚訝的：既然可以生活在一個(gè)整潔干凈的房間，為什么要生活在一個(gè)臟亂的房間呢?為什么Ruby周期性的強(qiáng)制停止程序的運(yùn)行去清理垃圾，而不使用Python的算法呢?

然而，引用計(jì)數(shù)實(shí)現(xiàn)起來(lái)不會(huì)像它看起來(lái)那樣簡(jiǎn)單。這里有一些許多語(yǔ)言不愿像Python一樣使用引用計(jì)數(shù)算法的原因：

首先，實(shí)現(xiàn)起來(lái)很困難。Python必須為每一個(gè)對(duì)象留有一定的空間來(lái)保存引用計(jì)數(shù)。這會(huì)導(dǎo)致一些細(xì)微的內(nèi)存開銷。但更遭的是，一個(gè)簡(jiǎn)答的操作例如改變一個(gè)變量或引用將導(dǎo)致復(fù)雜的操作，由于Python需要增加一個(gè)對(duì)象的計(jì)數(shù)，減少另一個(gè)對(duì)象的計(jì)數(shù)，有可能釋放一個(gè)對(duì)象。

其次，它會(huì)減慢速度。盡管Python在程序運(yùn)行過(guò)程中垃圾回收的過(guò)程非常順暢(當(dāng)你把臟盤子放到水槽后，它立馬清洗干凈)，但是運(yùn)行的并不十分迅速。Python總是在更新引用計(jì)數(shù)。并且當(dāng)你停止使用一個(gè)巨大的數(shù)據(jù)結(jié)構(gòu)時(shí)，例如一個(gè)包含了大量元素的序列，Python必須一次釋放許多對(duì)象。減少引用計(jì)數(shù)可能是一個(gè)復(fù)雜的，遞歸的過(guò)程。

最后，它并不總是工作的很好。在我演講的下一部分，也就是下一篇帖子中能看到，引用計(jì)數(shù)不能處理循環(huán)引用數(shù)據(jù)結(jié)構(gòu)，它包含循環(huán)引用。

下一次…

下周我將發(fā)布演講的其他部分。我將討論P(yáng)ython怎樣處理循環(huán)引用數(shù)據(jù)結(jié)構(gòu)，以及在即將到來(lái)的Ruby2.1中，垃圾回收器是怎樣工作的。