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

遅くなりましたが、前回の続きです。これで全部です。Appendix の訳で、前回よりも具体的＆実践的な内容になっています。

また、yakiimo02 さんの記事で知りましたが、現在 EASTL は EA のゲーム用 WebKit のソースの一部として公開されているようです (このパッケージの EAWebKitSupportPackages/EASTLEAWebKit/local/include/EASTL など)。ライセンスも割と緩めで、使用を考えてみるのも面白そうです。しかし、WebKit をゲーム用に移植する、というのもすごい話です…。

Appendix

この Appendix には、ドキュメント本体の参考資料が含まれ、多くの場合、ドキュメント本体で触れた内容の詳細を解説している。話が本筋から外れないようにするため、ここに分離している。

1 - (removed)
2 - A debuggable list container

list コンテナの中身をデバッガで追えるようにするため、EASTL では Curiously Recurring Template パターンを用いた。
    template <typename LN>
    struct ListNodeBaseProxy
    {
        LN* mpNext;
        LN* mpPrev;
    };

    template <typename T>
    struct ListNode : public ListNodeBaseProxy< ListNode<T> >
    {
        T mValue;
    };

    template <typename T, typename Allocator>
    class ListBase  // Typically the list class inherits from a base class such as this.
    {
    public:
        typedef T value_type;
        typedef ListNode<T> node_type;
        typedef ListNodeBaseProxy< ListNode<T> > base_node_type;

    protected:
        base_node_type mNode;
        . . .
    };
3 - Algorithm type preservation problem

以下のコードは STL の問題点を例示している。TableBasedSorter が行うことは意味を成さない。
    struct TableBasedSorter {
        TableBasedSorter(const int values[128]) {
            for(int i = 0; i < 128; ++i)
                mTable[i] = ((values[i] ^ 0xff80) + 128) - i;
        }

        bool operator()(int a, int b) const {
            return mTable[b] < mTable[a];
        }

        int mTable[128];
    };


    std::sort(v, v + 128, TableBasedSorter(values));
問題は、STL は比較関数オブジェクトを内部でも値渡しすることだ。さらに、デバッグ版で比較オブジェクトをチェックする STL ( !(Compare(x, y) && Compare(y, x)) のように双方向チェックする)の場合、問題は悪化する。この場合コピーコンストラクタは O(n log(n)) 回呼ばれることになる。
以下のようにすれば解決できると思うかもしれない。
    HuffmanHistoSorter compare;
    std::sort<int*, TableBasedSorter&>(v, v + 128, compare);
だが、これでは上手くいかない。sort() は渡された比較オブジェクトを無視して内部でコピーを作るからだ。
この問題への古典的な回避策は、比較対象データへのポインタなどを保持するプロキシ比較オブジェクトを作ることだ。しかしそれは面倒だし、メモリの間接参照により効率も落ちる。なぜユーザーの要求に従わないのだろうか？C++ 標準がユーザーの要求を尊重するようにしているかは謎だが、そうであれば良いことだろう。EASTL はそうしている。
4 - (removed)

5 - Game source and binary sizes

PC ゲームや HD ゲーム機のソフトウェアは大規模になることがある。

大作 PC ゲームのソースコードは 50万〜200万行に及ぶことが普通である

バイナリは 5〜20MB に及ぶ

データ (グラフィック、マップ、探索グラフ、UI、動画、アニメーション、スクリプト) のソース (編集データ) は 5〜50GB に及ぶ

コンパイルしたデータは 500MB〜4GB に及ぶ (動画抜きで)

ゲームソフトウェアのソースコードには、ツールやパイプラインのものが大量に含まれることがある。ゲームは大量のデータを持つため、データの生成や加工のための専用ツールが作られる。これらのツールのソースコードがゲームアプリケーション自体のそれより多くなることもありうる。
ツール類は通常ゲーム本体ほどシビアに効率は求められないため、C++ 以外の言語が用いられることも多い (C#, Python, C++, Perl が多くを占める)。

6 - Garbage collected allocators

世代別ガベージコレクション (iterative generational garbage collection) はよくできているが、GC は現在ゲーム開発の選択肢には入らない。これに関する考察はそれだけで論文が書けそうだが、要するに、ゲームにおけるメモリの容量制限、特殊メモリ、リアルタイム要求などは GC には向いていない。しかし、EA はこの分野の研究に興味があり、この分野で共同で研究する研究者にも興味がある。
7 - Permanent and temporary memory

メモリ断片化の予防策としてゲーム開発者が使う手法に、temporary memory と permanent memory に領域を分けておく、というものがある。EA のゲームにはこの手法なしにはメモリを使い果たしてしまうものもある。この手法は、まずゲーム起動時に割り当てられたメモリは permanently allocated とする。同様に、レベル開始時に 1 回だけ割り当てられるようなものも permanently allocated とする。動的に割り当てられ、開放のタイミングが不定だったり out-of-order だったりするものは temporarily allocated とする。permanent なものは領域の終端から後ろへ割り当てていき、temporary なものは先頭から前へ割り当てていく。
    [temporary memory -->            (free space)             <-- permanent memory]
    (low memory)                                                      (high memory)
結果、permanent なものはメモリの終端の方に隙間なく詰められ、無駄な空白が発生しなくなる。この手法は "high and low memory" と呼ばれることもある。この手法は固定メモリのシステムでも、Windows のような仮想メモリのシステムでも役立つ。EA で使われているカスタムヒープもこの手法をサポートしている。
8 - (removed)

9 - Debug builds can't be slow

ゲームソフトウェアはテストが難しいことで悪名高く、テストの自動化は極めて難しい。個々のモジュールは自動テスト可能だが、ゲームプレイとなると難しくなる。これには現在有効な解決手段がなく、解決できそうな気配もない。これは研究する価値がある領域であり、いつの日か解決できるまでは、ゲームのテストの多くは人間の手で行われるだろう。
ゲームのインタラクティブ性は、遅いデバッグビルドでテストを難しくし、テスターの時間を浪費させる。テストの多くがゲームのインタラクティブ性のテストを含み、遅いゲームはそれを不可能にしてしまう。また、プログラマがゲームをある特定の状況に持って行くのにも時間がかかり、プログラマーの時間も浪費する。このような待ち時間はどんなアプリケーションのプログラマにも発生しうるが、ゲームの場合、目的の状況に持っていくための手順が長くなる可能性があり、しかもそれはチートやショートカットでは再現できない可能性もある。
EA の以前の STLPort を使用した PC ゲームでは、デバッグビルドでもインライン化を有効にして余計な関数呼び出しを避けていた。インライン化はデバッグを難しくするため望ましくはないが、ゲームの応答性は良くなった。
10 - Function call avoidance

EASTL のコンテナは、可能な限り関数呼び出しを避けている。関数呼び出しを避けることはコンパイラに最適化をさせやすくし、ユーザーが実行時にトレースするのを楽にする。ベンチマークで EASTL が STL に勝る多くの点は、STL の関数がインライン化されなかったことが原因だった。コンパイラのインライン化の弱点は Appendix 15 で考察されている。加えて、インライン化を無効化にすると、まともにテストできないほど遅いアプリケーションが生成される。 (Appendix 9 参照)
関数呼び出しを避けることの問題としては、コンテナの作成とメンテナンスを難しくする。 EASTL が従おうとしている格言がある：「第一にユーザー、第二に同僚、最後に自分自身」
以下のコードは、関数呼び出しを含む vector::resize() の、libstdc++ と EASTL の例である。EASTL はいくつかの計算を行ない、insert() か erase() を呼んでいる。libstdc++ では大量のメンバ関数の呼び出しが行われている。resize() はインライン化されるかもしれないが、このような深い関数呼び出しはインライン化の重い足かせになるだろう。
EASTL vector::resize
    void resize(size_type n)
    {
        if(n > (mpEnd - mpBegin))
            insert(mpEnd, n - (mpEnd - mpBegin), value_type());
        else
            erase(mpBegin + n, mpEnd);
    }
libstdc++ vector::resize
    void resize(size_type __new_size)
    {
        resize(__new_size, value_type());
    }

    void resize(size_type __new_size, const value_type& __x)
    {
        if(__new_size < size())
            erase(begin() + __new_size, end());
        else
            insert(end(), __new_size - size(), __x);
    }

    size_type size() const
    {
        return size_type(end() - begin());
    }

    const_iterator begin() const
    {
        return const_iterator(this->_M_impl._M_start);
    }

    const_iterator end() const
    {
        return const_iterator(this->_M_impl._M_finish);
    }

    __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
11 - Argument-dependent lookup safety

STL の関数を呼んだとき、参照可能な他の namespace に STL が呼ぼうとする std の関数と同じ名前のものがある場合、STL はどの関数を呼ぶべきだろう？このような場合、通常は std の関数を呼ぶべきで、swap() などのオーバーライドされることを意図した一部の関数だけが例外である。
以下のコードは、std::sort の実装が無資格 (unqualified) の min() を呼ぶような実装になっている場合、コンパイルが通らないかもしれない。この場合コンパイラは ADL を使い、test::min() を見つける。
    namespace test
    {
        int min(int x, int y);

        class X { };
    }

    std::sort(XArray, XArray + 10);
少なくとも一つの商用 STL 実装は現状 ADL-safe ではない。ベンダはこの問題を知っており、将来のリリースでは修正することを承諾している。
12 - Memory tagging

メモリのタグ付けはアロケートの際に役立つ情報を付加しておくことで、いくつかの方法がある。

1. file / line - __FILE__ と __LINE__ マクロの値をアロケートの際に保持しておく

これは軽量だが、STL などの共有ライブラリでは上手くいかない。さらに、誰が、何のためにアロケートしたのかなどがわからないという問題もある。

2. call stack - アロケートのリクエストが来た時のコールスタックを保持しておく

これは強力だが、file / line ほど軽量ではない。どこからリクエストされてるのかは分かるが、他は file / line 同様あまり多くの情報は得られない。

3. name - アロケーションに名前を付ける (例: "VehicleInfo")

この方法だと、何のためのアロケートなのかが分かる。カテゴリ化やメモリ予算見積りのため、名前を階層化しておくこともできる (例: "Automata/VehicleInfo")。名前は他にも多くのケースで役立ち、どこでアロケートが発生したかも分かる。メモリのタグ付けと組み合わせてヒープの分析を行うと、使用されたメモリが物理的に近いかもわかる。

この方法の弱点は、ユーザー側のサポートが必要なことである。コールスタックのように自動的に名前をつけることはできない。

どれも利点と弱点があり、ユーザーはどれか一つを使うことを好む。しかし、これらは相容れないものではなく、file/line と名前付け、コールスタックと名前付けはよく組み合わせて使われ、名前付けは他の二つの弱点を補う。EASTL は名前付けをサポートしている。EA ではこれら 3 つをサポートしている他、アロケートした時間、数、グループ ID、任意のユーザーデータなどもサポートしている。

13 - wchar_t portability

大部分の商用ゲームソフトウェアは、8 bit の UTF8 エンコードのテキストか、16 bit の UCS2 エンコードのテキストを使っている。OS 毎に異なる文字コードの慣習があるが、これはゲームにどの文字コードを使えばいいのかという問題をもたらす。文字コードの優劣についてはこのドキュメントの扱う範囲外だが、ライブラリの文字コードのサポートに関する議論は関連がある。
char16_t と char32_t は、uint16_t や uint32_t のような、サイズ指定つきの文字型である。これらは EA により定義された拡張で、文字コード/文字データをよりポータブルにする。しかしながら、文字列リテラルの問題は解決できない。wchar_t はポータブルではない。8 bit かもしれないし (BEOS)、16 bit かもしれないし (Windows)、 32 bit かもしれない (Linux)。Unicode 標準はこの理由により、wchar_t の使用を推奨していない (version 4, section 5.2, paragraph 2)。
アプリケーションが 16 bit 文字列を扱う場合、コンパイラが wchar_t を 32 bit と定義していたら、コンパイラが提供する文字列の標準ライブラリは使えない。文字列の標準ライブラリを 16 bit で再コンパイルできるとしても、32 bit の wchar_t を扱おうとするコードがあると破綻してしまう。さらに、16 bit 文字列のリテラルを宣言する方法がないという問題もある。同様に、 wchar_t が 8 bit UTF-8 エンコードである場合、大量の文字列を扱うのは困難を極めるだろう (これは断言できる。何故なら我々が過去に経験したからだ)。故に我々は char8_t, char16_t, char32_t を定義し、これらをサポートする標準文字列ライブラリを書き直した。これには、とあるコンパイラが提供する標準文字列ライブラリより効率が良くなったという副次的な利点もあった (Appendix 14)。
サイズ指定版文字タイプは、マルチプラットフォームで文字列をポータブルに扱えるようにしてくれる。ワイド文字列リテラルの 'L' のプリフィックスの代わりに、'L16' や 'L32' を使うのはどうだろう？C++09 ではこのような提案がなされている。

14 - Why replace standard library functions?

ゲームプログラマはしばしば C++ 標準ライブラリを使わず、独自実装のものを使う。この理由は場合によりけりだが、大抵は効率の問題である。以下によく再実装される標準関数とその理由を列挙する。これがライブラリ設計者のゲームソフトウェアの要求への理解の助けになれば幸いである。

memcpy, memmove, memset

PC の場合 memcpy() はよく最適化されており、置き換えられることはあまりない。しかし、新しいハードウェアの場合、初期の実装は十分な最適化がなされていないことがある。また、アライメントがページサイズやキャッシュラインサイズに揃っている場合に最適化の余地が残っていることも多く、このようなケース向けの特殊化された実装が用意されることもある。

printf, sprintf

sprintf() は再実装されることが多い関数である。典型的な理由は以下のようなものである。

内部で mutex の lock が発生したり locale 情報を読み込んだりするため、遅い

cell などの環境ではコードが肥大化する

wsprintf() は 16 bit 文字列を扱えるとは限らない (Appendix 13)

ある実装ではグローバルヒープからメモリを確保する。

ある実装 (PS2 など) では、double の計算により非常に遅い。

int32_t などのサイズ付きタイプを明確にはサポートしていない。C99 の PRId32 は貧弱な回避策であり、難読化を招くしポータブルでもない。

10 進数表記 (%d)、8 進数表記 (%o)、16 進数表記 (%x) の出力はサポートするが、2 進数表記 (%b) はサポートしていない。

そもそもコンパイラベンダからは提供されないことがある。もっとあるケースでは、vsnprintf() のような役立つバリエーションが提供されないことがある。

wcscpy, wcslen, etc.

Appendix 13 で説明されたように、wchar_t は実質ポータブルではない。16 bit UCS の文字コードを使う場合 (多くがそうする)、標準ライブラリのワイド文字列関数はあてにできない。このため、よりポータブルな文字列ライブラリを再実装することは一般的に行われる。標準ライブラリは通常うまく実装されており、これは不幸な事態である。

fopen, fstream

FILE 系のファイルを扱う標準関数は多くのケースで役立つが、ゲームの場合はあまり適していない。fopen()/fread() のような同期系の関数で問題ない場合でも、ゲームではほとんどの場合より低レベルの OS が提供する機能を使う。PC でもゲーム機でも、FILE を使うことは稀である。これには主に以下のような理由がある。

FILE 系 IO はブロック動作である。ゲームでは非同期、優先度つき、head proximity-driven のものが好まれる。

FILE 系 IO はバッファリングする。これはゲームでは望まれないことが多い。

FILE 系 IO は遅い (mutex locking を伴ったりする)。OS が提供する機能を使う方が早いし、通常より多機能である。

rand

rand() の問題点はよく知られており、より良い乱数ジェネレータの実現が TR1 に望まれている。rand() の弱点を以下に端的に挙げる。

16 bit の値しか生成できない

乱数の質が悪い

非公開にできない

効率が悪い

atoi, strtol, etc.

atoi() や strtol() の問題は、long や wchar_t のようなポータブルでない型を扱うことだ。long は非効率的な型かもしれない (PS2 など)。uint32_t や uint64_t のようなサイズ指定の型を使う API がより好まれる。これらはポータブルな挙動を保証してくれるし、int や long 程度には効率的に動くだろう。(Appendix 21)

strncpy, strncat

これらは安全に使うのは難しすぎる。我々はこれらや strlcpy(), strlcat() を再実装したが、多くのゲームソフトウェアはこれらを使っている。また、fixed_string, fixed_substring はこれらの安全な代替手段として使える。

strftime, set_locale

C 標準ライブラリのロケールの機能は、ポータブル性や柔軟性の欠如に苦しんでいる。コンパイラのロケールの実装方法が違う場合、どのロケールを使えばいいかを知るポータブルな方法はない。マクロにより違いを隠蔽することはできるかもしれないが、個々の API まではカバーできないかもしれない。例えば strftime() は time/date フォーマットのローカライズはしてくれず、ユーザー側で行うようになっている。このような API の挙動を目的に沿ったものに変える手段はなく、この結果、ゲームソフトウェアでは多くの場合 strftime() のようなものは再実装される。

new/delete, malloc()/free()

システムが提供するヒープに比べ、カスタムヒープはメモリの断片化を減らし、アライメントの問題に対処し、メモリをより効果的に使える。さらに、タグ付けや正当性チェックなどのデバッグ機能も組み込める。また、プラットフォームによっては特殊なメモリの扱いを要求され、これらはポータブルな API ではカバーできない。

assert

assert() の根本的な問題は、それをオーバーライドしたりアプリケーションの機能にリダイレクトする手段がないことだ。assert() はアプリケーションを外側から操作し、通常は強制終了させる。このため、assert() の使用は禁止される。これは標準ライブラリの目的に反することであり、不幸な事態である。

我々が C++ 標準に望むのは、assert() をオーバーライドして挙動を変えるポータブルな手段である。

15 - Compiler inlining problems

gcc は優れたコンパイラである。しかし、STL のようなテンプレートライブラリを扱う上で重大な弱点がある。インライン化が不得意なことだ。インライン化を調節するコンパイルオプションが多数あるが、コンパイラに望んだ動作をさせるのは極めて難しい。これは既知の問題で、将来のバージョンでは改善されていくと望まれている。マイクロソフトの C++ コンパイラはより優れたインライン化を行い、リファレンスを使う価値がある。
コンパイラのインライン化の特性はこのドキュメントが扱う範囲ではないが、gcc のインライン化の問題に関するインターネット上の議論は以下のページなどに見られる。

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/b74eed16bd48d42e

http://groups.google.com/group/fa.linux.kernel/browse_frm/thread/1861b2634cdfa68a/

http://www.pixelglow.com/lists/archive/macstl-dev/2005-September/000154.html
16 - EASTL intrusive_list

intrusive container の例として、eastl::intrusive_list のインターフェースを示す (実際には、非 template の関数を隔離するために intrusive_list_base と intrusive_list に分かれている。このような設計は intrusive_hash_map などの他コンテナでも使われている)。intrusive container の主な利点は、ユーザーがノードのメモリを渡せることである。
    struct intrusive_list_node      // Users can use this or provide their own.
    {
        intrusive_list_node* pNext;
        intrusive_list_node* pPrev;
    };
       

    template <typename T, typename Pointer, typename Reference>
    class intrusive_list_iterator
    {
        public:
        typedef intrusive_list_iterator<T, Pointer, Reference> this_type;
        typedef intrusive_list_iterator<T, T*, T&>             iterator;
        typedef intrusive_list_iterator<T, const T*, const T&> const_iterator;
        typedef T                                              value_type;
        typedef T                                              node_type;
        typedef ptrdiff_t                                      difference_type;
        typedef Pointer                                        pointer;
        typedef Reference                                      reference;
        typedef bidirectional_iterator_tag                     iterator_category;

    public:
        intrusive_list_iterator();
        explicit intrusive_list_iterator(pointer pNode);
        intrusive_list_iterator(const iterator& x);

        reference operator*() const;
        pointer operator->() const;

        intrusive_list_iterator& operator++();
        intrusive_list_iterator& operator--();

        intrusive_list_iterator operator++(int);
        intrusive_list_iterator operator--(int);
    };


    template <typename T = intrusive_list_node>
    class intrusive_list
    {
    public:
        typedef intrusive_list<T>                              this_type;
        typedef T                                              node_type;
        typedef T                                              value_type;
        typedef eastl_size_t                                   size_type;
        typedef ptrdiff_t                                      difference_type;
        typedef T&                                             reference;
        typedef const T&                                       const_reference;
        typedef T*                                             pointer;
        typedef const T*                                       const_pointer;
        typedef intrusive_list_iterator<T, T*, T&>             iterator;
        typedef intrusive_list_iterator<T, const T*, const T&> const_iterator;
        typedef eastl::reverse_iterator<iterator>              reverse_iterator;
        typedef eastl::reverse_iterator<const_iterator>        const_reverse_iterator;

    public:
        intrusive_list();
        intrusive_list(const this_type& x);
        this_type& operator=(const this_type& x);

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

        reverse_iterator       rbegin();
        const_reverse_iterator rbegin() const;
        reverse_iterator       rend();
        const_reverse_iterator rend() const;
         
        reference       front();
        const_reference front() const;
        reference       back();
        const_reference back() const;

        bool empty() const;
        eastl_size_t size() const;
        void clear();
        void reverse();

        void push_front(T& x);
        void pop_front();
        void push_back(T& x);
        void pop_back();

        iterator locate(T& x);
        const_iterator locate(const T& x) const;

        iterator insert(iterator pos, T& x);
        iterator erase(iterator pos);
        iterator erase(iterator pos, iterator last);
        void swap(intrusive_list&);

        static void remove(T& value); // Erases an element from a list without having the list; O(1).

        void splice(iterator pos, T& x);
        void splice(iterator pos, intrusive_list& x);
        void splice(iterator pos, intrusive_list& x, iterator i);
        void splice(iterator pos, intrusive_list& x, iterator first, iterator last);

        void merge(this_type& x);

        template <typename Compare>
        void merge(this_type& x, Compare compare);

        void unique();

        template <typename BinaryPredicate>
        void unique(BinaryPredicate);

        void sort();

        template<typename Compare>
        void sort(Compare compare);

        bool validate() const;
        int  validate_iterator(const_iterator i) const;
    };
17 - Disabling of exception handling

ゲームソフトウェアでは、例外は通常無効化される。ゲームソフトウェアにおける例外の利点/弱点の分析はこのドキュメントが扱う範囲の外だが、ここに示すいくつかのコメントは問題を明瞭にする助けになるだろう。

例外は、どのコンパイラの実装でも相応のコストがかかる。

例外は、関数からの広域脱出の手段として望まれることがある。

しかし、広域脱出が必要になるような関数を作らない方が、例外を使うより良い解決策である。

例外を正しく使うのは、複雑なソフトウェアでは極めて難しくなる

例外の throw と catch は極めて高いコストになりうる

例外は、C++ の「使わないものにはコストをかけない」("don't-pay-for-what-you-don't-use") のデザインに反する。(例外を使う場合、スタックオブジェクトを破壊しうるすべての関数にオーバーヘッドが生じる)

ゲームソフトウェアが通常用いる手段は、例外を使う必要がある状況を可能な限り避けることである。例えば、あるサブシステムを実行するのに十分なメモリがあるかを事前に検証しておくことで、後から例外などの問題に対処することの代わりにする。
しかし、それでもいくつかのゲームライブラリは例外を役立てている。例外をライブラリ内部で使うに留め、アプリケーション全体が使うことを強いるようにしていないのであれば、それはベストだろう。

18 - Out of memory

EASTL は、out-of-memory 問題を STL と違う方法では解決していない。STL の解決法 (例外) は EASTL でもサポートしているが、例外は好まれず、通常は無効化されている (Appendix 17)。ゲームでは、ライブラリの内部で out-of-memory 状態に陥ったとき 4 つの一般的な対処法がある。

例外を投げる

これはめったに使われない。例外はオーバーヘッドを生じるし、安全に使うのは難しい。ユーザーが try 節を一つ忘れただけでアプリケーションはクラッシュする。

アロケータがユーザーが提供するコールバックを呼ぶ。コールバックはアプリケーション固有の方法でメモリを開放する

この方法はより堅実である。失敗を一箇所でハンドリングでき、ユーザーはそれ以外の部分を気にしなくて済む。

十分なメモリがあることをユーザーが保証する

これは最も単純かつ堅実な方法で、最も使われている。メモリの有効性を保証する一般的な方法は、十分な量を事前に割り当て、必要量を評価することである。

エラー値を返し、呼び出し側に伝播する

この方法は、特に複数の値を返さないといけない場合などで、最適ではない。この方法よりは例外の方がまだ良いと考えられることもある。

コンテナのユーザー側で例外を扱うのは冗長でエラーを起こしやすく、アロケータ側でエラーハンドリングする方がより簡単で堅実である。例外で out-of-memory に安全に対策するのは困難である。これは C++ の例外への批判というよりは、STL の例外の使い方への意見である。

19 - Benchmarks often miss cache effects

関数のベンチマークは、キャッシュの影響による結果の汚染を無くすようにしていないことがある。これはキャッシュの効果が同等である場合には良いアプローチである。このようなベンチマークでは、一度関数を呼び、タイマーを開始し、1000 回関数を呼び、タイマーを止める。しかし、これはキャッシュの影響が同等ではない場合にミスリードを招く結果を出すかもしれない。ベンチマークでは、最初の関数呼び出しで起きたキャッシュミスは意図的に無視される。しかし、現実にはベンチマークのように 1000 回同じ関数を連続して呼び出すようなことはなく、キャッシュミスは効率に大きな影響を及ぼしうる。より良い測定方法は、1000 個の別々の関数を次々に呼び出し、通常のアプリケーションの同じようなコードとキャッシュの使い方を試すことである。
The Technical Report on C++ Performance では、キャッシュの影響について触れている部分もあるが、測定結果や結論では考慮されていないようだ。例えば、仮想関数のタイミング解析は単純で、関数呼び出しのコストは「固定数の機械語命令」("a fixed number of machine instructions") と結論づけている。この分析は「キャッシュミスはない」もしくは「キャッシュは十分に大きく、キャッシュミスはプログラム開始時に一回しか起こらない」などの前提が必要で、いくらかミスリードを招く (レポート section 7.2.1 を参照)。ゲームソフトウェアでの仮想関数の使用についての議論はこのドキュメントが扱う範囲の外だが、仮想関数のコストはキャッシュの影響により Technical Report on C++ Performance で述べられているよりは大きくなりがちである。

20 - Performance comparison

EASTL と、業務でよく使われている STL の実装との比較を示す。EASTL の方が概ね早いが、ほとんどの場合違いは些細なものである。いくつかのケースでは高速化は重要ではない (min_element() が 10% 早く/遅くなったところで気にする人はまずいないだろう)。しかし、sort() などの特定のケースでは、高速化は重要である。ベンチマークのソースコードはこのドキュメントと共に配布されている。結果の 1.40 は、EASTL が 40% 早いことを意味しており、0.75 は EASTL が 33% (1/.75) 遅いことを意味している。
現実には、gcc の場合 EASTL はベンチマークより若干良好な結果を示す。これは　EASTL がインライン化されやすいためである。ベンチマークのコードはシンプルで、比較的インライン化もされやすいが、現実世界のコードはもっとインライン化されにくいだろう。
[比較結果は超長いので略…。原文参照]
21 - int is not a machine word

int は元々は機械ワードに相当するデータを意図したものである。C99 標準にはこう記載されている
プレーンな int は、実行環境のアーキテクチャに合ったサイズである。(A ‘‘plain’’ int object has the natural size suggested by the architecture of the execution environment (C99 6.2.5 p5) )
しかし実際には、64 bit や 128 bit のプラットフォームでもほとんどの場合 4 byte である。
22 - How do you make a node pool for a linked list?

std::list で固定サイズのノードプールを使用したい場合、それをポータブルに実現する方法はない。アロケータは何を割り当てればいいのかを知らない。
    template <size_t allocSize, size_t nodeCount>
    class NodePool{ };

    std::list<int, NodePool<???, 100> > someList;
EASTL の場合、以下のようにできる。
    const size_t allocSize = sizeof eastl::list<int>::node_type;
    eastl::list<int, NodePool<allocSize, 100> > someList;
23 - Algorithmic optimization vs. hardware optimization

アルゴリズムを設計＆実装するとき、ロジックの最適化と同様にハードウェアに合わせた最適化も考慮するとより良い結果を得られる。優れたロジックのアルゴリズムが実機では良い結果を出さないこともある。アルゴリズムを設計するとき、ロジックそのものには変更を加えず効率を改善できる点を見つけられることもある。このような現象はゲーム機、組み込みハードウェアなどではよく増幅され、EASTL にも見られた。以下は考慮すべき点である。

分岐予測ミスによる低速化

コンパイラは if 文を条件が真となる前提の最適化を行う。そのため、できるだけそのように書いたほうが良い。より良いのは、できるだけ分岐を避けることだ。eastl::min の例を参照

いくつかの CPU 命令は高価である

例えば、PowerPC　ではほとんどの場合変数による整数のシフトは非常に遅い。

テーブル探索はキャッシュミスを招く

isdigit(x) よりも ((unsigned)(x - '0') <= 9) の方が早いかもしれない。isdigit(x) はキャッシュミスを引き起こすかもしれず、これは分岐予測ミスよりも悪い。

関数呼び出しはキャッシュミスを招く

他の関数を大量に呼ぶ関数は、キャッシュミスを引き起こすかもしれない。

割り算は掛け算よりずっと遅い

割り算はできるだけ掛け算で代用する。

整数と浮動小数点が混じった演算は遅い

問題は、値がレジスタ間を行き来する必要があることだ。この問題は PowerPC では悪化する。PowerPC では整数レジスタと浮動小数点レジスタを直接移動させる手段がなく、システムメモリを介する必要がある。

コンパイラは適切にインライン化してくれないかもしれない

インライン化が弱いコンパイラもある。inline 指定の関数は必ずインライン化されるわけではない。

高価なデータタイプがある

例えば、16 bit 整数は多くの RISC プロセッサでは著しく遅い。

浮動小数点の定数は安くないかもしれない

PowerPC プロセッサは、浮動小数点の定数を変数と同様にメモリから読み込む。そのため、予想よりも遅いかもしれず、予想外のキャッシュミスを引き起こすかもしれない。

変数の書き込み直後の読み込みは高価かもしれない

PowerPC アーキテクチャには弱点があり、変数をメモリに書き込み、直後にそれを読み込もうとすると多くのクロックを浪費する。

ベクトル計算は、通常の計算より非常に効率的かもしれない

VMX, SIMD, Cell は、並列化された浮動小数点演算を非常に高速に行う。ダミーを加えたベクトル演算の方が非ベクトル演算よりも高速なこともある。
24 - The swap trick

vector::reserve() は capacity を増加させることはあるが、減らすことはない。また、指定した量よりも大きな量を設定することもある。しかし、ユーザーは capacity を減らしたい場合や、指定した量ぴったりのサイズにしたい場合もあるかもしれない。このような要求は swap() トリックで実現できる。
    std::vector<int>(v).swap(v); // Clear the excess capacity of v.
    std::vector<int>().swap(v);  // Clear v and v's capacity.
このような機能を std::vector と std::string の標準機能に加えるように提案したい。上記の記述は覚えにくく、一つの関数にした方がより柔軟である。EASTL では set_capacity() を実装している。前述のワークアラウンドはよく知られ、インターネット上にはこれを紹介する何百のページがある。これは標準ライブラリで実現されるべきだと思われる。
25 - random_access_iterator != pointer

ランダムアクセスイテレータは、C のポインタと同じ操作を提供するイテレータである。しかし、ポインタにしかない仕様もある、要素の連続性 (element contiguity) である。ランダムアクセスイテレータには、指してる要素がメモリ上で連続しているかを知るすべがない。std::vector は連続しているが、std::deque は大抵そうではなく、イテレータからこれを知ることはできない。メモリの連続性に関する最適化をしたい場合、type traits を使うしかない。しかしそれでも、コンパイラはポインタを使う方がより効率的なコードを生成することがある。これは、イテレータの抽象性や type traits がインライン化を難しくするという問題と、ポインタの場合値を byte offset に保つことで不要な割り算を除去できることに因る (イテレータの場合、element offset を使わざるを得ない)。

26 - Memory allocators used in game software

ゲームソフトウェアで使われる典型的なアロケータのタイプのテーブルを以下に示す。non-local アロケータは例外的だが、他は色々なタイプのソフトウェアで見られる。

Name Description

generalized allocator malloc()/free() の代替となる一般的なアロケータ。

fixed-size allocator 一定サイズの領域を割り当てるアロケータ。コンテナのノードプールを実装するのに役立つ

small block allocator 小さいサイズの要求に特化したアロケータ。外部断片化 (external fragmentation) の抑止に役立つ。

stack allocator (a.k.a. linear allocator, obstack) メモリチャンクを、単純にポインタを前方に移動させながら割り当てていくアロケータ。この場合、ユーザーは割り当てた領域を個別に開放することはできない

page protected allocator メモリブロックを返すアロケータ。メモリブロックは write-protect がかかったメモリページに隣接しており、境界を超えて書き込もうとするとハードウェア例外を引き起こす。

non-local allocator グラフィックメモリなど、CPU からの読み出しが遅いメモリの扱いに最適化したアロケータ。メモリの管理領域は通常のシステムメモリにあるが、返されるメモリは他の場所にある

handle allocator handle ベースのインターフェースを持つアロケータ。確保されたメモリは、ユーザーがアンロックしたときリロケートできる。

page allocator システムページを割り当てるアロケータ。Unix の mmap() や Windows の VirtualAlloc() に相当する。

27 - Game platform memory metrics

代表的なゲームプラットフォームのメモリ容量のテーブルを以下に示す。これは、 Wikipedia などの公に公開されている資料に基づくものである。ゲーム機のメモリはデスクトップ PC やサーバー PC のそれと比べて少なく、スワップメモリがない制約もある。また、メモリが複数のシステムで分かれている場合、表記が単純化過ぎていることもある。ゲームではグラフィックデータに多くのメモリが割かれ、多くの場合アプリケーションが使うメモリの半分ほどを占める。

Platform System memory Video memory

Nintendo DS 4 MiB 656 KiB

Sony PlayStation 2 32 MiB 4 MiB

Sony PSP 36 MiB 2 MiB

Nintendo GameCube 40 MiB 3 MiB

Microsoft XBox 64 MiB shared system / video

Nintendo Wii 88 MiB 3 MiB

Sony Playstation 3 256 MiB 256 MiB

Microsoft XBox 360 512 MiB shared system / video

PC / Macintosh 128 MiB - 4 GiB 32 MiB - 512 MiB

28 - How game console processors are weaker than desktop and server processors

以下は、ゲーム機の CPU およびそのキャッシュの、デスクトップPC/サーバーPC のそれより弱い点のリストである。このリストは主に CPU に関するもので、GPU に関するものではない。また、すべての項目がすべてのゲーム機の CPU に適合するわけではない。

out-of-order 実行の欠如

投機的実行 (peculative execution) の欠如

分岐予測能力の欠如

倍精度浮動小数点計算サポートの欠如

アライメントされていないメモリの read/write の欠如 (代わりに unhandled exceptions を発生させる)

いくつかの命令はマイクロコード化され、著しく遅くなる

キャッシュの小ささ

intelligent caches の少なさ

memory management unit の欠如

mapped memory の欠如
29 - A small problem with LWG #431 option #3

LWG (Library Working Group) issue #431 は、アロケータが異なるコンテナ間の swap 問題について議論している。この問題には完全な解決策がない。提出者は 3 つの選択肢を提案している。

1. イリーガルとすべきである。この場合、チェックして例外を投げるような実装にするかもしれないし、未定義動作とするかもしれない。

2. 遅い交換を行う。(例: 各アロケータを元のコンテナに残し、3 回の operator= を呼ぶ。これは O(n) の操作になる)

3. vector の内容とアロケータ両方を交換する。これは O(1) の操作になる。

1. は何も要求を満たせないため、他 2 つより不評である。
2. は、同じアロケータを持つコンテナ間 / 異なるアロケータを持つコンテナ間で動作が異なる問題がある。
3. は、アロケータの生存期間を予測不能にしうるという問題がある。CodeWarrior で問題なく実装された事例があるが、既存のゲームで問題を起こす可能性がある。以下ような、ゲームソフトウェアでよくあるパターンのコードを考えてみよう。
    struct X {
        X() : myList(BufferAlloc(myBuffer)) { }

        char myBuffer[512];
        std::list<int, BufferAlloc> myList;
    };

    void DoSomething(X& x1, X& x2) {
        std::swap(x1.myList, x2.myList);
    }
swap() は warning　も出ずコンパイルが通るが、x1 と x2 が同じものを指しているとき、大抵の場合はクラッシュするだろう。
2. には若干の問題はあるが、用心深いユーザーにも受け入れられるだろう。一方 3. が持つ問題は対処が難しく、ハイパフォーマンスプログラミングパターンで一般的な使い方を妨げる。
30 - Problems created by global memory allocators

ゲームソフトウェアは operator new や malloc() などでグローバルにメモリを確保するのをできるだけ避ける。ここでは、グローバルに確保する場合の問題点を考察する。

global operator new や malloc() は、それがどこから要求されたものなのかを伝えるすべを持たず、すべての要求は平等に扱わねばならない。

その結果、メモリ要求のカテゴライズなどはできず、サブシステム別のメモリ使用量を計測、制限するのは難しくなる。

確保されたメモリ領域は、メモリスペースにばらばらに散らばることになり、キャッシュミスを引き起こす。

テンポラリ領域がどのように割り当てられるのかが分からず、メモリの断片化が容易に起こる。

グローバルヒープをスレッド間衝突や false sharing から守る必要がある。Hoard などが解決に役立つかもしれないが、メモリ使用量のオーバーヘッドが大きすぎて受け入れられないかもしれない。

他のシステムのフリーブロックまで処理するため、アロケート速度は遅くなる。システム X が N サイズの領域を多数割り当て、システム Y が M サイズの領域を多数割り当てる場合、これらを同じ pool で扱おうとすると分別に余計な手間がかかることになる。

サブシステムのユーザーは、アロケータの挙動をそのサブシステム向けにチューニングすることができない。チューニングした場合、全サブシステムの挙動を変えることになる。

Name	Description
generalized allocator	malloc()/free() の代替となる一般的なアロケータ。
fixed-size allocator	一定サイズの領域を割り当てるアロケータ。コンテナのノードプールを実装するのに役立つ
small block allocator	小さいサイズの要求に特化したアロケータ。外部断片化 (external fragmentation) の抑止に役立つ。
stack allocator (a.k.a. linear allocator, obstack)	メモリチャンクを、単純にポインタを前方に移動させながら割り当てていくアロケータ。この場合、ユーザーは割り当てた領域を個別に開放することはできない
page protected allocator	メモリブロックを返すアロケータ。メモリブロックは write-protect がかかったメモリページに隣接しており、境界を超えて書き込もうとするとハードウェア例外を引き起こす。
non-local allocator	グラフィックメモリなど、CPU からの読み出しが遅いメモリの扱いに最適化したアロケータ。メモリの管理領域は通常のシステムメモリにあるが、返されるメモリは他の場所にある
handle allocator	handle ベースのインターフェースを持つアロケータ。確保されたメモリは、ユーザーがアンロックしたときリロケートできる。
page allocator	システムページを割り当てるアロケータ。Unix の mmap() や Windows の VirtualAlloc() に相当する。

Platform	System memory	Video memory
Nintendo DS	4 MiB	656 KiB
Sony PlayStation 2	32 MiB	4 MiB
Sony PSP	36 MiB	2 MiB
Nintendo GameCube	40 MiB	3 MiB
Microsoft XBox	64 MiB shared system / video
Nintendo Wii	88 MiB	3 MiB
Sony Playstation 3	256 MiB	256 MiB
Microsoft XBox 360	512 MiB shared system / video
PC / Macintosh	128 MiB - 4 GiB	32 MiB - 512 MiB