Verse のトランザクショナル メモリ セマンティクスを C++ に導入する

Phil Pizlo

2024年3月15日
Verse
エンジン
プログラミング
技術ブログ
機能
フォートナイト バージョン 28.10 以降、Epic Games の一部のサーバー (Unreal Engine ベースの大規模な C++ 実行可能ファイル) は、Verse と互換性のある C++ トランザクショナル メモリ セマンティクスを提供する新しいコンパイラでコンパイルされます。これは、Verse のセマンティクスを保持しながら、さらに多くの Unreal Engine の機能を Verse に公開するための第一歩です。

Verse プログラミング言語には、「トランザクショナル メモリ」という非常に優れた機能があります。以下に例を示します。 

var X = 0
if:
    set X = 42      # これは、次の行により
                    # ロールバックされます
    X > 100         # これは失敗し、ロールバックが発生します
X = 0               # X はロールバックにより 0 に戻ります

この動作は、Verse の set 処理だけでなく、どのエフェクトにも該当します。たとえば、代わりに C++ 関数を呼び出し、C++ を使用して可変変数を変更 (つまり、ポインタに格納) してから、他の C++ 関数を使用して、その可変変数を読み取ることができます。

SetSomething(0)            # C++ で実装され、C++ 変数を
                           # 設定します
if:
    SetSomething(42)       # これは、次の行により
                           # ロールバックされます
    GetSomething() > 100   # これは失敗して、ロールバックが発生し
GetSomething() = 0         # ロールバックにより 0 に戻ります

そのため、適切な Verse のセマンティクスをサポートするためには、すべてのエフェクトをロールバックできるように記録することで、C++ を Verse のトランザクション ルールに準拠させる必要があります。

Verse のコードは常にトランザクション内で実行され、トランザクションは正常に完了するか、アボート (中断) します。中断するトランザクションは「不可視」です。つまり、何も行われなかったかのように、そのエフェクトをすべてアンドゥ (取り消し) します。同時実行への影響は別として、Verse のトランザクション モデルでは、次のように規定されています。
  • Verse のランタイム エラーはトランザクション全体を中断する必要がある。これは、Verse では成功しなかったトランザクションをコミットできないためです。
  • if 文の条件などの Verse の失敗コンテキストはネスティングされているトランザクションであり、条件が成功の場合はコミットし、失敗の場合は、中断する。条件式には、エフェクトを含むことができます。条件が失敗した場合、そのエフェクトは一切発生しなかったかのように処理されます。
  • すべてのエフェクトは、ネイティブ コードで発生したものであっても、トランザクション化される。Verse プログラムが C++ に何らかの処理の実行を要求し、同じトランザクションでランタイム エラーが発生した場合、C++ が行った処理はすべて取り消される必要があります。Verse プログラムが失敗コンテキストから C++ に何らかの処理を実行するように要求し、その条件が失敗した場合、C++ が行った処理もすべて取り消される必要があります。
  • Verse のトランザクションは粒度が低い。Verse のコードは、デフォルトで常にトランザクション内にあり、そのトランザクションのスコープは、Verse への最も外側の呼び出し元によって決定されます。ほとんどの Verse の API は C++ で実装されているため、Verse のトランザクションを中断すると、ほとんどの場合、C++ の状態変更を元に戻す必要があります。

初期の Verse の実装では、次の方法でこれに対処していました。
  • Verse ランタイム エラーのセマンティクスをパントする。現在、Verse ランタイム エラーは、中断したトランザクションを正しくロールバックしません。これは修正する必要があります。
  • Verse のセマンティクスに反して、多くの API を失敗コンテキストで呼び出すことができません。この言語では、この問題に <no_rollback> エフェクトで対処していますが、問題が修正され次第、<no_rollback> エフェクトは非推奨となります。
  • トランザクションをサポートする C++ コードでは、実行するすべてのエフェクトに対して手動でアンドゥ ハンドラを登録する必要があります。これにはかなり扱いづらく、スケールされない (そのため、<no_rollback> エフェクト) うえに、エラーが発生しやすく、削除されたエフェクトに対してアンドゥ ハンドラが登録された場合など、デバッグが困難なクラッシュにつながります。

フォートナイト バージョン 28.10 から、Epic Games の一部のサーバーは clang ベースの新しい C++ コンパイラでコンパイルされます。これは AutoRTFM (障害メモリの自動ロールバック トランザクション) と呼ばれています。このコンパイラは、C++ コードを自動的に変換して、各エフェクト (すべてのストア命令を含む) のアンドゥ ハンドラを正確に登録し、Verse でロールバックが発生した場合に、結果を元に戻せるようにします。AutoRTFM は、トランザクション内部で実行されていないすべての C++ コードに対して、「パフォーマンスのオーバーヘッドなし」でこれを実現します。これは、同じ C++ 関数がトランザクション内とトランザクション外の両方で使用されている場合にも当てはまります。オーバーヘッドが発生するのは、実行中のスレッドがトランザクション スコープ内にある場合のみです。さらに、一部の C++ コードは AutoRTFM 内で動作するように変更する必要がありますが、C++ コードを AutoRTFM に適応させるためにフォートナイトのコードベースに「合計 94 個のコード変更」を加えるだけで済みました。この記事で紹介しますが、その変更は驚くほど簡単です。

この記事では、このコンパイラとランタイムがどのように機能するのかを詳しく説明し、これが Verse のエコシステムにどのような影響を与えるかについて、Epic Games のビジョンの概要を簡単に説明します。

AutoRTFM コンパイラとランタイム

AutoRTFM は、トランザクション セマンティクスを含むように一切設計されていない既存の C++ コードを、別のコンパイラを使用するだけで簡単にトランザクション化できるように設計されています。たとえば、AutoRTFM を使用すると、次のようなコードを書くことができます。

void Foo()
{
    TArray<int> Array = {1, 2, 3};
    AutoRTFM::Transact([&] ()
    {
        Array.Push(42);
        // 配列は {1, 2, 3, 42} ここです。
        AutoRTFM::Abort();
    });
    // 配列は、中断により {1, 2, 3} ここです。
}

これは TArray に変更を加えることなく動作します。これは、TArray が Push の内部でバッキング ストアを再割り当てする必要がある場合でも機能します。TArray は、この点では特殊ではありません。AutoRTFM は、std::vector/std::map だけでなく、Unreal Engine や C++ の標準ライブラリの他のデータ構造や関数の多くに対してこれを行うことができます。これを実現するために必要な唯一の変更は、AutoRTFM と低レベルのメモリ アロケータおよびガベージ コレクタ (GC) との統合です。このセクションで説明しますが、これらも小規模な変更です (これらは純粋に加算的なわずか数行の変更です。Epic Games では、Unreal Engine の多数の malloc、Unreal Engine の GC、およびシステムの malloc/new のすべてにこれらを追加しました)。さらに、AutoRTFM は、トランザクション外 (つまり、Transact 呼び出しの動的スコープの外側) で実行されるそれらのコード パスの「パフォーマンスを低下させることなく」これを実現します。重要なのは、(TArray をはじめとするその他多くの) コードパスがトランザクション内から使用される場合でも、トランザクション外での使用にコストが発生しないということです。コードがトランザクション内部で実行されている場合、オーバーヘッドは高い (一部の内部ベンチマークで 4 倍が確認されている) ものの、フォートナイト サーバーのティック レートが損なわれるほどではありません。

このセクションでは、この仕組みについて説明します。まず、全体的なアーキテクチャについて説明します。次に、LLVM コンパイラの新しいパスについて説明します。このパスでは、コードを直接インスツルメンテーションするのではなく、トランザクションに参加する可能性のあるすべてのコードの「トランザクションのクローン」を作成し、そのクローンだけをインスツルメンテーションします。次に、AutoRTFM を既存の C++ コード (アロケータなど、より楽しい部分を含む) に簡単に統合できるランタイムとその API について説明します。次の 2 つのセクションでは、これら 2 つのコンポーネントについてそれぞれ説明します。
 

AutoRTFM アーキテクチャ

長期的には、トランザクショナル メモリを使用して並列性を実現したいと考えています。並列性を実現するトランザクショナル メモリの実装では、「読み取り-書き込みセット」を維持する傾向があります。これはトランザクションが実行されているヒープの状態のスナップショットを追跡します。つまり、書き込みおよび読み取りの両方をインスツルメンテーションする必要があります。これを行わない場合、特定の場所を読み取るのみのトランザクションで、同時コミットによる競合が発生したかどうかを把握できなくなります。

ただし、短期的には次の 2 つの目標を達成する必要があります。
  • その Verse コードが C++ を呼び出す場合でも、Verse コードにトランザクション セマンティクスを適用すること。これには、並列性は必要ありませんが、トランザクショナル メモリが必要です。
  • トランザクショナル メモリのセマンティクスを追加する新しいコンパイラで、非常に大規模で成熟した C++ コードであるフォートナイト サーバーのコンパイルを正規化する。

そのため、最初のステップは AutoSTM (ソフトウェア トランザクショナル メモリ) ではなく、AutoRTFM (障害メモリ用ロールバックトランザクション) です。これは、シングルスレッド トランザクションを実装するだけです。AutoRTFM は、厳密にはよりシンプルな問題に対処します。同時並行性がないため (Verse が呼び出すゲームプレイ コードはすでにメインスレッド専用であることが想定されている)、必要なのは、書き込みの記録だけです。読み取りの無視は、初期起動時のオーバーヘッドを軽減し、バグを減らすことになります。これは、ヒープを読み取るだけのすべてのコードが AutoRTFM で機能するためです。

AutoRTFM のアーキテクチャは概念的にはシンプルです。AutoRTFM ランタイムは、メモリの位置とその古い値のログを保持します。コンパイラは、メモリが書き込まれるたびに、AutoRTFM ランタイムで関数を呼び出すようにコードをインスツルメンテーションします。次の 2 つのセクションでは、コンパイラとランタイムの詳細について説明します。
 

LLVM コンパイラ パス

AutoRTFMPass の役割は、Verse のトランザクション セマンティクスを遵守できるように、すべてのコードをインスツルメンテーションすることです。ただし、フォートナイトの同じコードが、スタック上に Verse のコードがなく Verse のセマンティクスが不要な場所と、スタック上に Verse がありロールバックが可能な場所で使用される可能性があります。

AutoRTFTM コンパイラは、「現在のスレッドがトランザクション中である場合は、ログを書き込む」といったコードを生成するのではなく、クローンを中心に構築されています。トランザクション中であることは、トランザクション クローンで実行されることで表現されます。事実上、bCurrentThreadIsInTransaction ビットは、プログラム カウンタにエンコードされます。コンパイラの観点では、これはシンプルです。つまり、コードをすべてクローンし、クローンした関数に修飾名を付け、クローンのみをインスツルメンテーションするだけです。元のコードにはインスツルメンテーションは行われず、ログ記録やその他の特別な処理は行いません。そのため、そのコードを実行させるために、コストは一切発生しません。クローンされたコードはインスツルメンテーションを取得し、トランザクション内であることを確実に認識します。これにより、代替呼び出しルールを使用するなど、VM のような手法を実行することもできます。

コードがクローンされるため、クローン内の間接関数コードもインスツルメンテーションする必要があります。関数が間接呼び出しを実行する場合、呼び出しそうとしているポインタは、呼び出される側の元のバージョンへのポインタになります。そのため、クローンされたコード内では、間接呼び出しはすべて、まず AutoRTFM ランタイムにその関数のクローンされたバージョンを問い合わせます。AutoRTFM の他のすべてのインスツルメンテーションと同様に、これにより、クローンされたコードの負荷は高くなりますが、元のコードには何の影響もありません。

AutoRTFMPass は、LLVM パイプラインのサニタイザーと同じ時点で実行されます。つまり、IR の最適化がすべて完了した後、バックエンドにコードを送信する直前に実行されます。これは重要な意味を持ちます。たとえば、インスツルメンテーションされたクローン内でも、インスツルメンテーションを取得するロードとストアは、最適化後に存続しているロードとストアのみです。つまり、C++ での非エスケープ ローカル変数への割り当ては抽象的には「ストア」であるものの (clang では clang 用に最適化されていない LLVM IR を作成するときに、この方法で表現する)、AutoRTFMPass が処理を行う時点では、ストアは完全に存在しなくなっています。ほとんどの場合、ストアは SSA データフローに置き換えられます。これは AutoRTFM で処理する必要はありません。また、Epic Games では、既存の LLVM の静的分析に基づくいくつかの細かい最適化を実装し、その必要がないことを証明できる場合には、ストアのインスツルメンテーションを回避しています。

関数のクローンを使用するということは、コンパイラで C++ コードをコンパイルしても、AutoRTFM のランタイム API を呼び出すことがなければ、クローンが呼び出されることはないということです。そのため、大量のデッド コードを含む大規模なバイナリを作成するためにかかるコスト以外にオーバーヘッドが発生することはありません (正確にはゼロではありませんが、ほぼゼロです)。

次のセクションでは、AutoRTFM ランタイムがどのようにインスツルメンテーションされたクローンを動作させるかについて説明します。
 

AutoRTFM ランタイム

AutoRTFM のランタイムは Unreal Engine Core に統合されているため、フォートナイトなどの Unreal Engine のプログラムの観点では常に利用可能です。この魔法を実現する AutoRTFM の重要な関数は、AutoRTFM::Transact です。この関数をラムダを使用して呼び出すと、ランタイムはログ データ構造とその他のトランザクション状態を含むトランザクション オブジェクトをセットアップします。次に、Transact がラムダのクローンを呼び出します。これは、ラムダとまったく同様であるものの、トランザクション インスツルメンテーションを含んでおり、AutoRTFM ABI を遵守しています。

現在のところ、Verse が if 条件などの失敗コンテキストに入ったときに Transact を呼び出します。将来的には、Verse の実行に入る前に、Transact を呼び出します。

このランタイムは、以下のケースを処理するための API を提供する必要があります。
  • Transact に渡されたラムダ、または Transact が過渡的に呼び出す関数にクローンがない場合はどうなるのでしょうか？このケースはシステム ライブラリ関数や AutoRTFM でコンパイルされていないモジュールの関数で発生します。
  • トランザクション化されたコードが、物理コマンド バッファへのコマンドのロックフリーの追加を実行するためにアトミックを使用するなど、トランザクションセーフではない処理を実行する必要がある場合はどうなるでしょうか？AutoRTFM は、トランザクションを手動で制御するための複数の API を提供します。この問題で最もよく実行されるインスタンスは、malloc/free と関連する関数 (カスタム アロケータなど) です。

AutoRTFM がクローンされた関数のルックアップを要求され、クローンが見つからなかった場合はそのたびに、AutoRTFM はエラーでトランザクションを中断します。これにより、トランザクションセーフでないコードを誤って呼び出すことが不可能になり、安全性が確保されます。呼び出される側がトランザクション化され、クローンが存在して呼び出されるか、呼び出される側が存在せず、関数が見つからないために中断されます。そのため、トランザクション内で WriteFile などの関数を呼び出すと、デフォルトでエラーになります。これは望ましいデフォルトの動作です。WriteFile は確実に取り消すことができないからです。後で書き込みを取り消そうと試みても、(自分のプロセス内または別のプロセス内の) 他のスレッドがその書き込みを認識して、それに基づいて回復不可能な別の処理を実行している可能性があるからです。このため、実践的なのは、既存の C++ プログラムを AutoRTFM でコンパイルし、Transact を実行することです。これが正しく動作するか、トランザクションセーフでない関数を呼び出したというエラーが表示され、その関数と呼び出しサイトの検索方法に関するメッセージが表示されます。

適切に動作させるのが最も難しいのは、malloc とその関連関数です。AutoRTFM は、malloc の実装をトランザクション化せず、呼び出し元が malloc への呼び出しを AutoRTFM API でラップすることを強制するというアプローチをとっています。これは、実際の malloc 実装をラップするファサード API がすでにある Unreal Engine などのプログラムでは特に簡単です。コードを確認して、どのような処理が行われているのかを理解することをお勧めします。AutoRTFM 以前の FMemory::Malloc は次のようなコードでした。
 
void* FMemory::Malloc(SIZE_T Count, uint32 Alignment)
{
    return GMalloc->Malloc(Count, Alignment);
}

なお、重要な部分だけを表示するために、詳細部分は削除しています。

AutoRTFM では、代わりに以下を実行します。
 
void* FMemory::Malloc(SIZE_T Count, uint32 Alignment)
{
    void* Ptr;
    UE_AUTORTFM_OPEN(
    {
        Ptr = GMalloc->Malloc(Count, Alignment);
    });
    AutoRTFM::OnAbort([Ptr]
    {
        Free(Ptr);
    });
    return AutoRTFM::DidAllocate(Ptr, Count);
}

では、どのような処理が行われているのか、順を追って確認しましょう。
  1. UE_AUTORTFM_OPEN を使用することで、囲まれたブロック (ラムダに変換される) がトランザクション インスツルメンテーションなしで実行する必要があることを指定します。これは、ランタイムとコンパイラが実装するのが簡単で、元の (クローンされていない) バージョンのラムダを呼び出すだけであることを意味するからです。つまり、GMalloc->Malloc はトランザクションの内部で実行されるものの、トランザクション インスツルメンテーションは行われません。これを「オープンで実行する」といいます。(クローズドで実行するのとは対照的に、トランザクション化されたクローンを実行することを意味します)。つまり、この UE_AUTORTFM_OPEN が戻った後、malloc 呼び出しは、ロールバックが登録されることなく、直ちに完了するまで実行されます。これにより、トランザクション セマンティクスが維持されます。malloc はすでにスレッドセーフであるため、このスレッドが malloc を実行したという事実は、malloc されたオブジェクトへのポインタがトランザクションからリークするまで、他のスレッドからは確認できないためです。ポインタは、コミットするまでトランザクション外にリークしません。これは、Ptr が格納される場所が、新しく割り当てられた他のメモリか、AutoRTFM が書き込みをログに記録してトランザクション化するメモリのみであるからです。
  2. 次に、AutoRTFM::OnAbort を使用してオブジェクトを解放するための中断時ハンドラを登録します。トランザクションがコミットすると、このハンドラは実行されないため、malloc されたオブジェクトが存続します。しかし、トランザクションが中断した場合は、オブジェクトを解放します。これにより、中断によるメモリ リークが発生しないことが保証されます。
  3. 最後に、AutoRTFM にこのメモリ スラブが「新しく割り当てられた」ことを知らせます。つまり、ランタイムはこのメモリへの書き込みを記録する必要がないということです。メモリへの書き込みをログに記録しないことで、OnAbort を実行しやすくなります。これは、すでに解放したオブジェクトの内容を、AutoRTFM が上書きして以前の状態に戻そうとする心配がなくなるからです。また、新しく割り当てられたメモリへの書き込みをログに記録しないことも、有用な最適化です。

このコードがトランザクションの外で実行される (つまり、このコードはすべてオープンから呼び出された) 場合、以下のように処理されます。
  • UE_AUTORTFM_OPEN は、単にコード ブロックを実行します。
  • AutoRTFM::OnAbort は、何も実行しません。渡されたラムダは無視されます。
  • AutoRTFM::DidAllocate は何も実行しません。

次に、解放時にどのような処理が行われるかを確認しましょう。ここでも、この説明に関係のない詳細部分は削除しています。

void FMemory::Free(void* Original)
{
    UE_AUTORTFM_ONCOMMIT(
    {
        GMalloc->Free(Original);
    });
}
 
UE_AUTORTFM_ONCOMMIT 関数の動作は次のとおりです。
  • トランザクション化されたコードでは、これは、指定されたラムダをオープンで呼び出すコミット時ハンドラを登録します。つまり、トランザクションがコミットすると、オブジェクトは解放されます。直ちに解放されるわけではありません。トランザクションが中断した場合、オブジェクトは解放されません。
  • オープン コードでは、ラムダを直ちに実行するため、オブジェクトはすぐに解放されます。

このスタイルのインスツルメンテーション (malloc は直ちに malloc を実行するものの、on-aborts で free を実行する一方で、free は on-commits で free を実行する) は、すべてのアロケータに適用されます。AutoRTFM ランタイムは、関数ルックアップやコンパイラ ハックによって malloc/free/new/delete の独自のハンドラを導入するため、システム アロケータを使用していても正しい動作を得ることができます。Unreal Engine GC の動作も同様ですが、free 関数がないことと、トランザクション外でレベル ティックの終了時に GC インクリメントを実行する点が異なります。

コンパイラ、ランタイム、および Open/OnCommit/OnAbort API を使用した malloc/GC インスツルメンテーションを組み合わせることで、アトミック、ロック、システム呼び出し、またはトランザクション化しないことを選択した Unreal Engine のコードベース部分 (現在のところ、レンダリング エンジンや物理エンジンなど) への呼び出しを使用しない限り、トランザクションで C++ コードを実行するために必要な要素がすべて揃います。このことが、フォートナイト全体で合計 94 個の Open API の使用につながりました。これらを使用するには、アルゴリズムやデータ構造を変更するのではなく、適切な粒度で既存のコードを Open および friend でラップする必要があります。

Verse エコシステムへの影響

AutoRTFM は、UEFN により多くの Verse セマンティクスを公開するための第一歩です。AutoRTFM を使用すると、以下が可能になります。
  • よりクリーンなランタイム エラー動作を実装し、エラーが発生した後でもゲームを実行し続けられるようにします。AutoRTFM により、ランタイム エラーが C++ コードの奥深くで検出された場合でも、既知の状態に復元できるようになります。
  • <no_rollback> エフェクトを削除し、if および for からより多くのコードを呼び出せるようになりました。ほとんどの C++ コードがトランザクション化に対応できないため、このエフェクトは、多くの関数シグネチャを汚染しているだけです。AutoRTFM がこの問題を解決します。
  • グローバル トランザクション セマンティクスを公開し、データベース アクセスを Verse コードとグローバル変数だけで記述できるようにします。AutoRTFM は、Verse コードを投機的に実行できることを意味します。投機的実行を行えるようになることで、リモート データ アクセスのコストを償却できるため、ネットワークをまたぐトランザクションに Verse が参加するなど、興味深い機会が生まれます。

今すぐ Unreal Engine をダウンロードしましょう！

Unreal Engine は、世界で最もオープンで高度な制作ツールです。
あらゆる機能を備え、完全なソースコードにアクセスできる Unreal Engine を使用すれば、すぐに制作を開始できます。