欒 添, 趙 奎

1(中國科學院大學,北京 100049)

2(中國科學院 沈陽計算技術研究所,沈陽 110168)

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

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

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

1 技術概述

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

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

圖1 典型三維引擎內(nèi)存管理結構

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

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

本文針對以上問題,旨在和C++標準庫共存的前提下實現(xiàn)用戶態(tài)的垃圾回收.

2 系統(tǒng)設計

2.1 需求分析

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

(1) 能和C++標準內(nèi)存模型共存的非侵入式設計

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

(2) 保證和標準庫的兼容性

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

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

(3) 回收內(nèi)存同時調用析構函數(shù)

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

2.2 整體架構設計

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

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

(1) 托管堆： 用戶通過調用托管堆提供的接口激活分配器分配內(nèi)存. 托管堆持有存儲所有托管對象的內(nèi)存空間、提供構造托管對象的接口.

(2) 托管指針類： 托管堆返回給用戶的操作對象都是托管指針. 這個類的對象保存所指向對象的真實地址,類型簽名,對象占用內(nèi)存大小等元信息. 需要和指針類型兼容(重載指針運算的相關運算符). 根的集合由托管指針的構造/析構函數(shù)維護.

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

(4) 回收器： 被分配器激活后負責遞歸搜索對象間引用關系,執(zhí)行回收動作時遞歸標記可達對象并回收其余內(nèi)存.

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

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

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

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

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

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

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

托管堆的負責分配內(nèi)存和存儲對象,同時,對象間的引用關系也由托管堆記錄. 托管堆提供的操作是用戶申請/釋放托管對象的唯一方式. 托管堆工作的方式如下：

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

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

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

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

3.5 核心算法描述

本設計的核心點為根的判定,因為標記-清除算法沒有給出根的普適判定方式. 為了解決這個問題,在本設計中,托管指針自身的內(nèi)存地址在托管堆外(程序運行的棧和程序員手動申請的堆中)被視為根結點.

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

4 實驗與結果分析

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

表1 測試機配置

本實驗測試目的是對比托管指針相對shared_ptr的額外開銷,同時測試系統(tǒng)的可行性. 實驗測試使用C++11標準庫提供的high_resolution_clock計時,對于每個測試,運行50次取平均.

對于一個int對象,構造新的托管指針和shared_ptr時間對比如表2.

表2 構造共享指針開銷對比

分別構造shared_ptr和GcPtr指向對象,測試指針置空并調用回收動作運行的時間,結果如表3.

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

表3 指針置空回收共享對象開銷對比

5 結語

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

實驗結果表明,本系統(tǒng)可以有效地回收循環(huán)引用的對象,同時整個系統(tǒng)能夠調用被回收對象的析構函數(shù).

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

1陳凱. 三維游戲引擎的設計與實現(xiàn)[碩士學位論文]. 杭州：浙江大學,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張濤,白瑞林,鄒駿宇. 基于生命期預測的分代式垃圾收集算法. 計算機工程,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李少華. 基于虛擬機的軟件動態(tài)保護系統(tǒng)解釋器的優(yōu)化[碩士學位論文]. 西安： 西安電子科技大學,2016.

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