EASTL から垣間見るゲームソフトウェア開発現場の現状その 1

(2016/02/10 追記: EASTL は長らく EAWebKit の一部としてライセンスが不明瞭なまま公開されていましたが、この日 BSD ライセンスで正式に公開されました https://github.com/electronicarts/EASTL)

若干古いものですが、2007 年に発表された、Electronic Arts によるゲーム開発向けの改良を加えた STL、"EASTL" の仕様。
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

仕様だけで実装が公開されてないのが非常に残念なのですが、それは別として、何故こんなものが必要なのか、どういう事情でこの機能が盛り込まれたのか、といったゲーム開発現場の事情が細かく解説されていて、とても参考になります。特に、既にある程度 C++ に習熟している人でこれから業界を目指す人には極めて貴重な情報だと思います。
私はこれをゲーム会社に入った後知りましたが、入る前じゃなかったのが悔やまれます (ゲーム機特有の事情が飲み込めなくて混乱した経験がしばしばあったので)。逆にいうと、この paper の内容を知っておけばコンシューマゲーム開発に携わるとき理解が早まる、というくらい突っ込んだ内容になっています

この paper が英語が障壁になって広まらないのはもったいないので、翻訳を試みてみます。重要ではない (と私が判断した) 部分はばっさり省略しています。誤訳の可能性もあります。興味が湧いたら是非原文を読んでみてください。
長いので複数回に記事を分けて訳していきます (途中で飽きなければ)。あと中括弧 [] の中は訳注です。

EASTL -- Electronic Arts Standard Template Library
Paul Pedriana
Electronic Arts
ppedriana at ea.com

Abstract

ゲームプログラムは大量のデータを取り扱うが、ゲーム機には非常に限られたメモリしか積まれていない。また、CPU のキャッシュの少なさ、処理能力の低さ、特殊なアライメント要求など、他にはない制限もある。
STL はゲームプログラムでも有用なものだが、いくつかの欠点により最適解とは言えなくなっている。最大の欠点はアロケータの貧弱さである。
Electronic Arts では、STL の欠点を改善した "EASTL" を実装し、問題解決に役立てている。
この paper では、ゲームソフトウェア開発で直面する問題と STL の欠点、それに対する EASTL による部分的な解決について説明する。

Introduction

[特に重要な話もない前置き。略]

Motivation for EASTL

現在の STL がゲーム開発に最適ではない理由を以下に挙げる。

STL のアロケータは極めて扱いづらいく、コードの肥大化を招き、効率も最適ではない。

いくつかの STL の実装には slist, hash_map, shared_ptr などの有用なものが用意されているが、これらはポータブルではない。用意されてない実装もあるし、バージョンの違いで互換性がなかったりもする。

intrusive_container など、多くのゲームプログラマーが望んでいるものの STL には存在しない機能がある。

STL は関数呼び出しの階層が深く、それによりインライン化が妨げられ、遅くなっている。

STL は非常にデバッグしづらい。例えば std::list は void* を使うためにデバッガで内容を見れないことがある。また、暗号めいた変数名やデータ構造だらけな上、コードに関するドキュメントがない。

STL のコンテナは、格納するオブジェクトのアライメントをサポートしていない。ゲーム開発では特殊なアライメントを要求されるケースが多いが、STL のアロケータはアライメントについて何も関知しない (コンパイラの拡張機能でなんとかできることもあるが)。アライメントに関するサポートが弱いのは C++ の欠点である。アライメントに関するサポートは C++09 で提案されている。

STL のコンテナは、要素を追加するときにコピー渡しする必要がある。これはコンストラクタのコストが高いオブジェクトで非効率的である。

PC / 家庭用ゲーム機のコンパイラベンダーが提供する STL の実装は効率に問題がある。EASTL はほとんどの場合により優れた効率を発揮する。これは、一部はアルゴリズムの改善によるものもあるが、ほとんどはコンパイラやハードウェアの特性に合わせた実践的な改良によるものである。

STL コンテナは private な実装を持ち、データ構造などをポータブルには弄れないようになっている。これができることが重要な場合もある (node pool など)。

STL の多くの現在の実装が、空のコンテナにメモリを割り当てることがある。これは最適化を妨げており、効率改善の大きな余地がある。空のコンテナはメモリを割り当てるべきではない。

STL のアルゴリズムの全ての実装は述語の参照をサポートしておらず、それが原因で非効率的なハックを強いられることがある。

STL は実用性、効率より正当性に重点を置いている。これは妥当なポリシーだが、std::allocator など、いくつかのケースではユーザビリティと効率を妨げている。

Differences between std STL and EASTL

1. EASTL は STL とほぼ同じインターフェースのコンテナ、イテレータ、アルゴリズムを提供する。唯一の例外はアロケータである。EASTL はよりシンプルで効率的な仕様のアロケータを持つ。std::allocator も eastl::allocator も下の方で説明されている。
EASTL は defect reports や TR1 もフォローしている。EASTL は TR1 のいくつかの機能も提供し、使用している (smart pointers, type traits, hashing containers など)。
2. EASTL は拡張機能を提供している。例えば push_back(void), set_capacity(size), validate() が eastl::vector に追加されている。拡張機能の多くは、高効率 (push_back(void))、明瞭性 (set_capacity(size))、デバッガビリティ (validate()) のために求められたものである。
3. EASTL は STL にはないコンテナやアルゴリズムを提供している。これには intrusive_list, vector_map, fixed_hash_set, slist, ring_buffer, radix_sort, has_trivial_relocate などが含まれる。
機能仕様によるものではない違いもある。これは、可読性、一貫性、限られたハードウェアでの最適性能、などのためによるものである。

EASTL functionality summary

[eastl の機能紹介。長いし、今回紹介したい内容の本質ではないので略…。fixed_list, fixed_vector などの固定長コンテナ、intrusive_list などの既にあるデータを参照するだけのコンテナなどは、ゲームソフトウェア特有の要求に応えた特徴的なものだと思います]

Game software issues

この項目では、EA が関わってきたゲームプラットフォームについて議論する。これには据え置き機、携帯機、PC が含まれる。
EA もそれ以外も、実質すべてのゲーム開発は C++ で行われおり、そしてこれは当分変わりそうにもない。
ゲームソフトウェアに要求されるものは、PC ソフトのそれと数々の点で異なる。

ゲームソフトウェアはネイサンの法則により、常にハードウェアを最大活用する

ソースコード、バイナリは肥大化しがちである

大量のデータを扱う

家庭用ゲーム機は、HDD より非常に遅い DVD ドライブから動く

ゲームソフトはスムースに動かねばならない。予期せぬ停止があってはならない

非 PC 環境にはページメモリがない。つまり、アプリケーションはメモリを使い果たしたら死ぬ

ページメモリがないということは、メモリの断片化はアプリケーションの死を招く

非 PC 環境ではメモリの容量は固定で、PC 環境より少ない

非 PC 環境には特殊なメモリがある。物理メモリ、非ローカルメモリ、キャッシュ不可メモリ、などである。

非 PC 環境の CPU は、PC のそれと比べてキャッシュに余裕がない

デバッグビルドはそれなりに早く動作する必要がある

環境によっては特殊なアライメントを要求されることがある

これらは以下の結果を導く

ゲーム機のスペックがいくら上がろうが、メモリや CPU パワーに余裕が出ることはない

ゲーム開発者は、効率や開発手順を強く気に掛ける

ゲームソフトウェアはブロック式 IO ではなく、非同期 IO を使う

メモリリークしてはならない。些細なリークがやがては死を招く

割り当てられたメモリは全て追跡可能にすべきである。リーク検出やメモリ予算見積りに役立つ

システムが提供するヒープを使うことはあまりない。代わりにカスタムヒープを用いる

メモリの断片化防止に多くの労力が費やされる

メモリ分析ツール作成やヒープのデバッグに多くの労力が費やされる

ソース/データのビルド時間改善のために多くの労力が費やされる

デバッグビルドでも動作が遅すぎてはいけない

任意の型のメモリ割り当ては可能な限り避ける

operator new (クラス側も global 側も) のオーバーライドは例外ではなく、ルールである

デフォルトの global operator new は禁止される

ライブラリ側で割り当てられるメモリもユーザ側でコントロールされるべきである

特殊なアライメント要求について深く理解している必要がある

断片化防止対策に、多少無駄があってもメモリプールが使われることがある

分岐 (if/else/while/for/do) は - 特に分岐予測ミスは - できるだけ避ける

virtual 関数は可能であれば避ける。特にボトルネックにおいては

例外は普通使わない

RTTI は普通使わない。少なくとも出荷時コードでは使わない

これらはほとんどがメモリと効率の制約に関連したものである。膨大な労力がメモリ使用効率の最適化に費やされる。
また、PC ソフトに対して行われた解析によると、メモリ断片化問題は完全には解決できていない。ゲーム開発におけるメモリの制約は問題をより難解にしている。EA ではこの難問に取り組む研究者を歓迎している。
C++ ゲームプログラマに関して、以下のような懸念もある。

C++ は大学では教えられなくなりつつある。C++ を理解している人材は少なく、STL のような template を理解している人材となるとさらに少ない

若い開発者にはジェネリックプログラミングは馴染みが薄い。STL のヘッダファイルは込み入っており、経験の浅いプログラマがこれを追うのは大変な作業になる。理解しやすい STL の実装を作ることは、熟練者が思っている以上に価値がある。

ゲーム開発者は STL のコンテナやアルゴリズムを調査し、トレースできる必要がある。これはコンテナ自身だけの問題ではなく、ユーザーのコンテナの使い方のデバッグまで含めた問題である。

C++ の template は「トリッキー」「煩雑」などの理由で嫌われる。あるプログラム言語を使うためにその言語の弁護人になるべきではない。
std::allocator

C++ 標準のセクション 20.1.5 は、allocator の要求について書かれている。それは下記のコードのようなものである。rebind は標準ははっきりとは要求していないが、実質必須である。
    template <typename T>
    class allocator
    {
    public:
        typedef size_t     size_type;
        typedef ptrdiff_t  difference_type;
        typedef T*         pointer;
        typedef const T*   const_pointer;
        typedef T&         reference;
        typedef const T&   const_reference;
        typedef T          value_type;
           
        allocator();
        allocator(const allocator<T>&);
       ~allocator();

        template <class U> allocator(const allocator<U>&);
        template <class U> struct rebind { typedef allocator<U> other; };
           
        T*        address(T&) const;
        const T*  address(const T&) const;
        T*        allocate(size_type, const void* = NULL);
        void      deallocate(T*, size_type);
        void      construct(T*, const T&);
        void      destroy(T*);
        size_type max_size() const;
    };
        
    bool operator ==(const allocator<T>&, const allocator<T>&);
    bool operator !=(const allocator<T>&, const allocator<T>&);
残念ながら、std::allocator のデザインとコンテナのアロケータの使い方は取り扱いを難しくし、効率は最適ではなくなり、コードを膨張させている。これはゲームソフトウェアでは重大な問題になりうる。以下はアロケータと、コンテナのアロケータの使い方についての問題点である。

Halpern proposal で説明されているように、std::allocator は、インスタンスベースではなくクラスベースである。これはアロケータをインスタンスベースで動かそうとしたときおかしな結果を招く。

アロケータは事実上 template である必要があり、rebind はメンバ template である必要がある。コンパイラのインライン化が優秀でないとき、template の爆発を引き起こし、コードは膨張し、効率は低下する。

アロケータはコンテナによって 1 つかそれ以上の型に rebind される。そして、その型をユーザーがポータブルに知る方法はない。なので、アロケータ実装者は何が割り当てられ、構築されるのかを知ることはできない。 - 皮肉なことに、ユーザーが提供したアロケータは、ユーザーが提供した型を割り当てない。この事実はアロケータの目的を覆すかもしれない。

アロケータはアライメントの要求を関知しない。std::allocator がアロケートするオブジェクトはデフォルトのアライメント (通常は sizeof(double) と同じ) であるか、アロケータ実装者がアライメントのことを知ってるものと仮定される。どちらの仮定も満たされないケースも起こりうる。

アロケータは、allocate() と同様に construct() や destroy() も要求される。このことは、アロケーションとコンストラクションの 2 つの別々なコンセプトの混合を強制する。

コンテナはコンストラクタを呼ぶときにアロケータを設定することを要求され、後から設定することはできない。

コンテナはアロケータへのアクセス手段を提供しておらず、同じ型のアロケータをコピーして受け取ることしかできない

libstdc++ などの現在の STL の実装は、空のコンストラクタやコピーコンストラクタが呼ばれる際、アロケータのコピーが発生したり一時オブジェクトが発生したりする。これは重いアロケータの際問題になり、アロケータは参照を持つだけにして実際のアロケーションは別のオブジェクトで行う、というような構造にすることをユーザーに強いることになる。これは不必要なコードと手間である。
eastl::allocator

EASTL のアロケータは std::allocator と似ているが、根本的な違いがある。アロケーションとコンストラクションを行うのではなく、メモリを割り当てる。EASTL のアロケータは new/delete より malloc()/free() に近い。
以下は EASTL のアロケータが要求されるインターフェースである。
    class allocator
    {
    public:
        allocator(const char* name = "EASTL");
        allocator(const allocator& x);
        allocator(const allocator& x, const char* name);

        allocator& operator=(const allocator& x);

        void* allocate(size_t n, int flags = 0);
        void* allocate(size_t n, size_t alignment, size_t offset, int flags = 0);
        void  deallocate(void* p, size_t n);

        const char* get_name() const;
        void        set_name(const char* name);
    };

    bool operator==(const allocator& a, const allocator& b);
    bool operator!=(const allocator& a, const allocator& b);
Notes:

アロケータは代入可能である。ユーザーはアロケータ用の swap() も定義するかもしれない。

アロケータは template である必要はなく、メンバ template を持つ必要もない。

flag パラメータはアロケーションのヒントになる (temporary / permanent など)。これは断片化防止などに役立つ。

allocate() の alignment と offset のパラメータは、アロケーションの際のアライメントとオフセットを指定する。これは特殊なアライメントを要求するプラットフォームで重要である。コンテナが、アロケータが事前にアライメント指定を知っていることを期待するのは適切ではない。アロケータはコンテナ間で共有されるかもしれず、アロケータは複数の型を割り当てるかもしれないからだ。

name 関連関数はユーザーがアロケータに名前をつけてタグづけできるようにする。これはゲームソフトウェアでは重要な機能で、これにより全てのアロケーションが識別可能になる。

名前は文字列そのものをコピーして持つのではなく、ポインタだけ保持する。

アロケータの比較は重要である。等価性 (==) は、比較元アロケータが割り当てたメモリを比較対象アロケータで開放できること、と定義される。

max_size() 関数は、固定サイズアロケータでは役立つかもしれないにも関わらず、なくなっている。

コピーされたアロケータは、コピー元と比較しても等値であり、同じように動作する
EASTL containers

全ての EASTL のコンテナは一貫した規約がある。以下に最低限必要の機能を備えた (non-adapter な) コンテナの実装例を示す。
    enum iterator_status_flag
    {
        isf_none            = 0x00,
        isf_valid           = 0x01,
        isf_current         = 0x02,
        isf_can_dereference = 0x04
    };

    template <class T, class Allocator = eastl::allocator>
    class container
    {
    public:
        typedef container<T, Allocator>            this_type;
        typedef T                                  value_type;
        typedef T*                                 pointer;
        typedef const T*                           const_pointer;
        typedef T&                                 reference;
        typedef const T&                           const_reference;
        typedef ptrdiff_t                          difference_type;
        typedef impl_defined                       size_type;
        typedef impl-defined                       iterator;
        typedef impl-defined                       const_iterator;
        typedef reverse_iterator<iterator>         reverse_iterator;
        typedef reverse_iterator<const_iterator>   reverse_const_iterator;
        typedef Allocator                          allocator_type;
        typedef impl-defined                       node_type;

        static const size_t kNodeAlignment       = impl-defined;
        static const size_t kNodeAlignmentOffset = impl-defined;

    public:

        container(const allocator_type& allocator = allocator_type());
        container(const this_type& x);

        this_type& operator=(this_type& x);
        void swap(this_type& x);
        void reset();

        allocator_type&       get_allocator();
        const allocator_type& get_allocator() const;
        void                  set_allocator(allocator_type& allocator);

        iterator       begin();
        const_iterator begin() const;
        iterator       end();
        const_iterator end() const;

        bool                 validate() const;
        iterator_status_flag validate_iterator(const_iterator i) const;
    };

    template <class T, class Allocator>
    bool operator==(const container<T, Allocator>& a, const container<T, Allocator>& b);

    template <class T, class Allocator>
    bool operator!=(const container<T, Allocator>& a, const container<T, Allocator>& b);
Notes:

EASTL は、STL の既存のコンテナと同じように扱えることを保証する。新規に追加されたメンバ関数でのみ、変更が加えられた機能を使える。これにより、STL と EASTL の間の変更を容易にしている。

get_allocator() 関数はアロケータへのアクセスを可能にする。これがない、場合ユーザーはコンストラクタを呼ぶときしかアロケータを設定できず、実用に耐えなくなるシチュエーションが出てくる。

注意すべき点として、アロケータはポインタではなく、値で指定される。ポインタ指定も検討されたが、これはポインタをたせたクラスを作ることで実現できるため、このような形になった。

swap() されたコンテナは、アロケータは交換しない。

list::splice() など、複数のコンテナを混ぜる操作はアロケータが異なる (等価ではない) コンテナ間では無効であり、例外が投げられる。

新規に構築された空のコンテナは一切メモリを割り当てない。STL のコンテナには初期ノードの割り当てを行うものもあるが、EASTL コンテナはこれを一切行わないように設計されている。コンテナに初期ノードが必要な場合、コンテナのメンバにするか、static な空のノードとすべきである。

空のコンテナは、構築されたオブジェクトを含まない (end() のノードなようなものも)。同様にユーザーオブジェクトも、ドキュメントに書かれたコンテナの設計やアルゴリズムの規約がそれを必要とするまでは構築されない。

reset() 関数は特別な拡張で、コンテナのメモリを開放することなく、コンテナを空っぽの状態に戻す。これはスクラッチメモリ上のコンテナを素早く破棄する場合などに役立つ。reset() ではメモリ解放は行われず、コンテナは reset() の後はアロケートされたメモリを持たない。non-trivial なオブジェクトに対しては危険である。

max_size() 関数は、固定サイズアロケータでは役立つかもしれないにも関わらず、なくなっている。理由は単純で、滅多に使われないからである。

validate(), validate_iterator() は、コンテナとイテレータの明示的な正当性チェックを行う。EASTL は暗黙にこれを行う方法もあるが、完全な妥当性チェックは暗黙に行うにはコストが高すぎる。そのため、明示的に行う手段を用意し、ユーザーがデバッグビルドでも最適化ビルドでも適切なタイミングで呼べるようにしている。

EASTL は out-of-memory 問題を解決していない。
EASTL flaws

EASTL には最適ではない部分もある。以下は変更すべき箇所である。

basic_string は std::basic_string と共に問題を拡大している。basic_string はメンバ関数が多すぎるし、end() は npos の代わりに使われるべきである。EASTL はどちらの問題も解決してない上、メンバ関数は増えている。より良い string はこれらの問題を解決し、copy-on-write などの挙動をポリシーで実装すべきである。

list::size() を O(1) にしたい人もいれば、O(n) にしたい人もいる。eastl::list はテンプレートパラメータでユーザーがそれを選択できるようにするはずだったが、現状そうなっていない。将来はそのようなポリシーを用意するだろう。

fixed-substring は現在 basic_string のサブクラスであり、安全ではないシチュエーションを生むことがある。これは修正可能な実装上の問題である。

コンテナの reset() 関数はもっと複雑な名前にすべきだったかもしれない。新規ユーザーが clear() と混同しかねない。

EASTL は STL と違い out-of-memory 問題を解決していない。STL の解決策 (例外) は EASTL でもサポートされているが、例外は好まれず、通常無効化されている。

EASTL のコンパイル時/ランタイム時チェックは、libstdc++ のそれほど徹底されていない。libstdc++ や他の一部の STL の実装は、コンパイル時の型要求チェック行っている。この部分は EASTL にも改善の余地がありそうである。