基于垃圾回收的三維引擎內存管理系統①

欒 添, 趙 奎

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

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

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

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

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

1 技術概述

1.1 傳統三維引擎的內存管理

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

圖1 典型三維引擎內存管理結構

1.2 傳統內存管理的不足

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

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

2 系統設計

2.1 需求分析

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

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

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

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

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

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

(3) 回收內存同時調用析構函數

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

2.2 整體架構設計

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

本系統分為以下4部分.

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

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

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

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

各層組件交互的具體流程詳見系統實現中偽代碼部分的描述和注釋.

3 系統實現

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

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

3.1 托管指針的實現

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

3.2 托管堆的實現

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

3.3 內存分配器的實現

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

3.4 回收器的實現

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

3.5 核心算法描述

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

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

4 實驗與結果分析

本系統測試機配置如表1.

表1 測試機配置

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

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

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

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

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

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

5 結語

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

實驗結果表明,本系統可以有效地回收循環引用的對象,同時整個系統能夠調用被回收對象的析構函數.

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

1陳凱. 三維游戲引擎的設計與實現[碩士學位論文]. 杭州：浙江大學,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李少華. 基于虛擬機的軟件動態保護系統解釋器的優化[碩士學位論文]. 西安： 西安電子科技大學,2016.

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