基于垃圾回收的三維引擎內(nèi)存管理系統(tǒng)①

欒 添, 趙 奎

1(中國(guó)科學(xué)院大學(xué),北京 100049)

2(中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所,沈陽(yáng) 110168)

當(dāng)前,三維引擎被廣泛地應(yīng)用在各個(gè)重要行業(yè)中.為了滿足三維引擎的性能要求,開(kāi)發(fā)語(yǔ)言一般為C++.作為非托管語(yǔ)言,C++中內(nèi)存的釋放需要由程序員介入. 三維引擎的對(duì)象引用關(guān)系非常復(fù)雜,基于引用計(jì)數(shù)智能指針無(wú)法處理強(qiáng)循環(huán)引用的對(duì)象,目前業(yè)界尚沒(méi)有一個(gè)通用的、與標(biāo)準(zhǔn)庫(kù)兼容的解決方案.

現(xiàn)存的解決方案存在一些問(wèn)題,比如虛幻引擎通過(guò)重新實(shí)現(xiàn)C++運(yùn)行庫(kù)的方法來(lái)支持垃圾回收,不兼容標(biāo)準(zhǔn)C++; 而類似Unity邏輯腳本化的方式又存在與C++跨語(yǔ)言交互困難和腳本語(yǔ)言本身的運(yùn)行效率低下等問(wèn)題.

本設(shè)計(jì)針對(duì)目前三維引擎回收復(fù)雜對(duì)象的困難,使用標(biāo)準(zhǔn)C++,引入了垃圾回收算法輔助程序員釋放循環(huán)引用的資源. 本系統(tǒng)在程序員無(wú)需修改現(xiàn)有代碼和開(kāi)發(fā)環(huán)境的情況下實(shí)現(xiàn)了循環(huán)引用對(duì)象的回收、空間不足自動(dòng)回收內(nèi)存、自動(dòng)調(diào)用回收對(duì)象析構(gòu)函數(shù)等功能.

1 技術(shù)概述

1.1 傳統(tǒng)三維引擎的內(nèi)存管理

三維引擎由眾多模塊構(gòu)成. 內(nèi)存管理系統(tǒng)作為三維引擎的支持系統(tǒng),管理內(nèi)存的分配/釋放. 如圖,傳統(tǒng)三維引擎的內(nèi)存管理大致分為兩個(gè)部分： 面向性能的底層和回收內(nèi)存的上層[1]. 底層對(duì)開(kāi)發(fā)者透明,旨在優(yōu)化程序性能. 功能包括防止內(nèi)存碎片化、加速內(nèi)存分配速度等. 上層部分的功能是在合適的時(shí)機(jī)回收內(nèi)存,回收動(dòng)作的執(zhí)行和引擎運(yùn)行時(shí)邏輯有關(guān).

圖1 典型三維引擎內(nèi)存管理結(jié)構(gòu)

1.2 傳統(tǒng)內(nèi)存管理的不足

傳統(tǒng)三維引擎的底層內(nèi)存管理器主要面向內(nèi)存的分配,以加速分配/訪問(wèn)和防止碎片化為主[2]; 相對(duì)的,上層的內(nèi)存管理需要程序員手動(dòng)管理,對(duì)于比較復(fù)雜的引用關(guān)系無(wú)能為力. 業(yè)界的處理方式主要有兩種： 頂層邏輯全部腳本化[2],內(nèi)存回收時(shí)機(jī)交由腳本解釋器管理; 或者在C++的基礎(chǔ)上實(shí)現(xiàn)一個(gè)能被垃圾回收支持的基類,所有的類都繼承自該基類. 前者以Unity為代表,缺點(diǎn)是跨語(yǔ)言的交互很容易出現(xiàn)性能瓶頸并且難以調(diào)試; 后者以虛幻引擎為代表,既需要重寫整個(gè)C++標(biāo)準(zhǔn)庫(kù),又很難混用托管和非托管的對(duì)象,一定程度上損失了C++語(yǔ)言的靈活性.

本文針對(duì)以上問(wèn)題,旨在和C++標(biāo)準(zhǔn)庫(kù)共存的前提下實(shí)現(xiàn)用戶態(tài)的垃圾回收.

2 系統(tǒng)設(shè)計(jì)

2.1 需求分析

本文提出的內(nèi)存管理系統(tǒng)旨在輔助程序員回收三維引擎運(yùn)行中循環(huán)引用的對(duì)象,考慮到三維引擎的復(fù)雜度和性能要求,本系統(tǒng)需要有以下特性：

(1) 能和C++標(biāo)準(zhǔn)內(nèi)存模型共存的非侵入式設(shè)計(jì)

采用垃圾回收將造成一定的性能損失. 我們要保證這個(gè)系統(tǒng)只管理指定的對(duì)象而不干涉其他的部分.在虛幻引擎中,所有的類都繼承自UObject,因此虛幻引擎重寫了整個(gè)標(biāo)準(zhǔn)庫(kù). 本設(shè)計(jì)需要保證不影響程序的非托管部分.

(2) 保證和標(biāo)準(zhǔn)庫(kù)的兼容性

對(duì)于C++編寫的三維引擎,本管理系統(tǒng)需要保證兼容C++的類型系統(tǒng),兼容性體現(xiàn)在兩個(gè)方面： 迭代器和標(biāo)準(zhǔn)容器.

首先,本系統(tǒng)提供的指針類型應(yīng)該與C++迭代器行為相仿,由此來(lái)配合C++標(biāo)準(zhǔn)庫(kù)的交互. 其次,托管對(duì)象需要和C++標(biāo)準(zhǔn)容器兼容,本系統(tǒng)需要考慮到標(biāo)準(zhǔn)庫(kù)和標(biāo)準(zhǔn)容器使用的內(nèi)存分配器對(duì)系統(tǒng)的潛在影響.

(3) 回收內(nèi)存同時(shí)調(diào)用析構(gòu)函數(shù)

作為C++與C語(yǔ)言最重要的區(qū)別之一,編譯器保證了在對(duì)象離開(kāi)作用域后自動(dòng)調(diào)用的析構(gòu)函數(shù)[3]. 此時(shí),對(duì)象持有的資源將被安全地釋放,以滿足RAII原則. 本系統(tǒng)必須保證托管對(duì)象回收時(shí)能夠正確地完成析構(gòu)動(dòng)作,以保證C++的基本語(yǔ)義. 比如,引擎中的某個(gè)對(duì)象持有一個(gè)網(wǎng)絡(luò)連接,若對(duì)象析構(gòu),析構(gòu)函數(shù)中關(guān)閉鏈接的動(dòng)作必須被執(zhí)行.

2.2 整體架構(gòu)設(shè)計(jì)

本系統(tǒng)架構(gòu)如圖2所示,用戶使用托管堆提供的接口構(gòu)造托管對(duì)象,調(diào)用接口的返回值為一個(gè)托管指針對(duì)象. 剩余部分的動(dòng)作在托管對(duì)象的構(gòu)造和托管指針的析構(gòu)時(shí)分別激活.

本系統(tǒng)分為以下4部分.

(1) 托管堆： 用戶通過(guò)調(diào)用托管堆提供的接口激活分配器分配內(nèi)存. 托管堆持有存儲(chǔ)所有托管對(duì)象的內(nèi)存空間、提供構(gòu)造托管對(duì)象的接口.

(2) 托管指針類： 托管堆返回給用戶的操作對(duì)象都是托管指針. 這個(gè)類的對(duì)象保存所指向?qū)ο蟮恼鎸?shí)地址,類型簽名,對(duì)象占用內(nèi)存大小等元信息. 需要和指針類型兼容(重載指針運(yùn)算的相關(guān)運(yùn)算符). 根的集合由托管指針的構(gòu)造/析構(gòu)函數(shù)維護(hù).

(3) 內(nèi)存分配器： 由托管堆構(gòu)造對(duì)象時(shí)激活,嘗試分配足夠內(nèi)存供用戶使用,返回托管指針,空間不足則激活回收器回收. 分配器在托管堆持有的內(nèi)存中分配空間,兼容C++標(biāo)準(zhǔn)庫(kù)的內(nèi)存分配器(allocator)保證和標(biāo)準(zhǔn)庫(kù)的交互.

(4) 回收器： 被分配器激活后負(fù)責(zé)遞歸搜索對(duì)象間引用關(guān)系,執(zhí)行回收動(dòng)作時(shí)遞歸標(biāo)記可達(dá)對(duì)象并回收其余內(nèi)存.

各層組件交互的具體流程詳見(jiàn)系統(tǒng)實(shí)現(xiàn)中偽代碼部分的描述和注釋.

3 系統(tǒng)實(shí)現(xiàn)

作為三維引擎內(nèi)存管理系統(tǒng)中面向回收的部分,本系統(tǒng)基于標(biāo)準(zhǔn)C++11實(shí)現(xiàn),以頭文件的形式提供源碼庫(kù). 本系統(tǒng)的使用者按照接口調(diào)用即可保證循環(huán)引用對(duì)象被安全回收.

面向系統(tǒng)設(shè)計(jì)中提到的三點(diǎn)需求： (1) 本系統(tǒng)通過(guò)庫(kù)的方式實(shí)現(xiàn)提供服務(wù),保證了非侵入性的設(shè)計(jì); (2)在托管指針和內(nèi)存分配器中通過(guò)定義相關(guān)tag,滿足了迭代器和標(biāo)準(zhǔn)內(nèi)存分配器的兼容性; (3) 構(gòu)造托管對(duì)象時(shí)向管理系統(tǒng)注冊(cè)析構(gòu)函數(shù),滿足了回收對(duì)象時(shí)調(diào)用析構(gòu)函數(shù)的需求. 以下介紹各個(gè)組件的實(shí)現(xiàn)方式.

3.1 托管指針的實(shí)現(xiàn)

作為三維引擎的一部分,托管指針需要?jiǎng)偃蜟++指針的相關(guān)操作,為了保證托管指針的靈活性以及類型安全,本系統(tǒng)定義了一個(gè)泛型類GcPtr＜T>來(lái)指向各種指定類型的對(duì)象; 另一方面,本系統(tǒng)實(shí)現(xiàn)了一個(gè)GcPtrVoid類型,保證這個(gè)空類型能夠作為任意托管指針的退化,以此來(lái)模擬C++中的void*指針.

3.2 托管堆的實(shí)現(xiàn)

托管堆的負(fù)責(zé)分配內(nèi)存和存儲(chǔ)對(duì)象,同時(shí),對(duì)象間的引用關(guān)系也由托管堆記錄. 托管堆提供的操作是用戶申請(qǐng)/釋放托管對(duì)象的唯一方式. 托管堆工作的方式如下：

3.3 內(nèi)存分配器的實(shí)現(xiàn)

本系統(tǒng)的內(nèi)存分配器既可以和普通的三維引擎底層分配器配合以加速分配,也可以單獨(dú)使用.內(nèi)存分配器的工作以偽代碼表示如下：

3.4 回收器的實(shí)現(xiàn)

為了解決三維引擎面向的上層邏輯中的復(fù)雜引用關(guān)系,回收器的回收動(dòng)作采用垃圾回收算法實(shí)現(xiàn). 作為原型系統(tǒng),本系統(tǒng)目前采用“標(biāo)記-清除”算法[4]作為原型實(shí)現(xiàn). 回收器主要負(fù)責(zé)兩個(gè)操作： (1) 從存活的根出發(fā),遞歸標(biāo)記現(xiàn)有存活對(duì)象,得到死亡的對(duì)象并回收空間. (2) 調(diào)用被回收對(duì)象的析構(gòu)函數(shù),完成析構(gòu)動(dòng)作. 回收器以偽代碼表示如下：

3.5 核心算法描述

本設(shè)計(jì)的核心點(diǎn)為根的判定,因?yàn)闃?biāo)記-清除算法沒(méi)有給出根的普適判定方式. 為了解決這個(gè)問(wèn)題,在本設(shè)計(jì)中,托管指針自身的內(nèi)存地址在托管堆外(程序運(yùn)行的棧和程序員手動(dòng)申請(qǐng)的堆中)被視為根結(jié)點(diǎn).

此判定方式與標(biāo)準(zhǔn)容器結(jié)合會(huì)產(chǎn)生一個(gè)問(wèn)題： 托管對(duì)象如果保存在未修改標(biāo)準(zhǔn)容器中(如vector)會(huì)被視為一個(gè)根結(jié)點(diǎn)(保存于vector申請(qǐng)的空間,不在托管堆中). 循環(huán)引用表現(xiàn)為： 若容器沒(méi)有析構(gòu),容器中指針(根結(jié)點(diǎn))指向的對(duì)象不會(huì)析構(gòu); 如果容器內(nèi)有托管指針指向容器,容器內(nèi)的托管指針也不會(huì)析構(gòu). 為了解決這個(gè)問(wèn)題,對(duì)于可能存儲(chǔ)托管指針的容器,本系統(tǒng)重寫了內(nèi)存分配器(此分配器將內(nèi)存分配在托管堆中,不會(huì)被誤認(rèn)為根結(jié)點(diǎn)),分配器需要滿足標(biāo)準(zhǔn)庫(kù)中的內(nèi)存分配器的特性(Trait)[5],來(lái)保證和C++標(biāo)準(zhǔn)容器的兼容性.

4 實(shí)驗(yàn)與結(jié)果分析

本系統(tǒng)測(cè)試機(jī)配置如表1.

表1 測(cè)試機(jī)配置

本實(shí)驗(yàn)測(cè)試目的是對(duì)比托管指針相對(duì)shared_ptr的額外開(kāi)銷,同時(shí)測(cè)試系統(tǒng)的可行性. 實(shí)驗(yàn)測(cè)試使用C++11標(biāo)準(zhǔn)庫(kù)提供的high_resolution_clock計(jì)時(shí),對(duì)于每個(gè)測(cè)試,運(yùn)行50次取平均.

對(duì)于一個(gè)int對(duì)象,構(gòu)造新的托管指針和shared_ptr時(shí)間對(duì)比如表2.

表2 構(gòu)造共享指針開(kāi)銷對(duì)比

分別構(gòu)造shared_ptr和GcPtr指向?qū)ο?測(cè)試指針置空并調(diào)用回收動(dòng)作運(yùn)行的時(shí)間,結(jié)果如表3.

綜上,從根據(jù)運(yùn)行結(jié)果中我們可以看出,對(duì)于同一個(gè)對(duì)象,構(gòu)造/銷毀共享指針的情況和shared_ptr的性能差距在10倍以內(nèi),這大大優(yōu)于腳本語(yǔ)言的性能(數(shù)百到上千倍的開(kāi)銷)[6,7],此時(shí),可以認(rèn)為托管指針的開(kāi)銷是能夠接受的. 此外,構(gòu)造循環(huán)引用的測(cè)試表明,基于本系統(tǒng)構(gòu)建的托管指針仍然能夠回收無(wú)用對(duì)象,測(cè)試運(yùn)行結(jié)果證明了系統(tǒng)的可行性.

表3 指針置空回收共享對(duì)象開(kāi)銷對(duì)比

5 結(jié)語(yǔ)

面向三維引擎的復(fù)雜對(duì)象引用關(guān)系,本文討論并實(shí)現(xiàn)了一個(gè)基于垃圾回收的內(nèi)存管理系統(tǒng),在可接受的開(kāi)銷下解決了回收循環(huán)引用對(duì)象的問(wèn)題. 本系統(tǒng)面向三維引擎開(kāi)發(fā),但由于使用標(biāo)準(zhǔn)C++實(shí)現(xiàn),并且對(duì)于被托管對(duì)象透明,因此,不限于三維引擎,任何涉及到對(duì)象復(fù)雜引用關(guān)系的程序都可以使用.

實(shí)驗(yàn)結(jié)果表明,本系統(tǒng)可以有效地回收循環(huán)引用的對(duì)象,同時(shí)整個(gè)系統(tǒng)能夠調(diào)用被回收對(duì)象的析構(gòu)函數(shù).

本系統(tǒng)目前實(shí)現(xiàn)僅采用了標(biāo)記-清除算法作為原型實(shí)現(xiàn),下一步工作將考慮結(jié)合其他如復(fù)制算法、標(biāo)記-壓縮算法[4]等進(jìn)一步改進(jìn)該系統(tǒng)的性能.

1陳凱. 三維游戲引擎的設(shè)計(jì)與實(shí)現(xiàn)[碩士學(xué)位論文]. 杭州：浙江大學(xué),2007.

2Gregory J. Game Engine Architecture. Florida： CRC Press,2009.

3Stroustrup B. Programming： Principles and Practice Using C++. 2nd ed. Boston,Massachusetts： Addison-Wesley Professional,2014.

4張濤,白瑞林,鄒駿宇. 基于生命期預(yù)測(cè)的分代式垃圾收集算法. 計(jì)算機(jī)工程,2015,41(7)： 71-74,81.

5Heller T,Kaiser H,Diehl P. Closing the performance gap with modern C++. Taufer M,Mohr B,Kunkel J. High Performance Computing. Cham： Springer,2016. 18-31.

6李少華. 基于虛擬機(jī)的軟件動(dòng)態(tài)保護(hù)系統(tǒng)解釋器的優(yōu)化[碩士學(xué)位論文]. 西安： 西安電子科技大學(xué),2016.

7吳作順,竇文華. 幾個(gè)常用解釋器的性能分析. 計(jì)算機(jī)工程與科學(xué),2002,24(4)： 83-84,101.