HN 日本語サマリー

← 一覧へ戻る
プログラミング

Playdate向けC言語のダーティな最適化テクニック

Dirty Optimization Secrets (C for Playdate) (devforum.play.date)

52 pointsby ibobev6 コメント

要約

この記事は、Playdate向けのゲームエミュレータ開発中に発見された、高度なC言語最適化テクニックを紹介しています。CPUは高速だがキャッシュアクセスが遅いというPlaydateの特性を踏まえ、命令キャッシュ(ICache)に収まるようにコードを圧縮すること、カスタムリンカースクリプトでコード配置を制御すること、シンボル情報を検査してコードサイズを確認すること、そしてTCM(Tightly-Coupled Memory)領域をデータやコードの高速化に活用する方法が解説されています。これらのテクニックは、エミュレータやシミュレーションなど、高いパフォーマンスが求められるアプリケーションに特に有効です。

全文翻訳

Dirty Optimization Secrets (C for Playdate)

これらは、@stonerl と私がフルスピードのゲームボーイエミュレータを開発中に発見した、高度な最適化トリックです。これらは一般的なゲーム最適化のヒントとは異なり、既存のテクニックに慣れていない方にはあまり役立たないかもしれません。

これらの最適化手法は、エミュレータ、大規模シミュレーション(Factorioライクなものなど)、3Dレンダラー、コーデックなど、非常に高いパフォーマンスのコードが必要な場合に最も役立つでしょう。

1. 高速CPU、低速キャッシュ

これは@StiNKz の調査から得られたもので、その結果はDiscordでこちらで見ることができます。PlaydateのCPUは非常に高速なCPUですが、メモリ、特にキャッシュにないメモリへのアクセスは遅いと考えるべきです。これは、コードが主にレジスタで動作し、大量のデータをロードしない場合、多くのループや分岐予測ミスがあっても、驚異的な速度で動作する可能性が高いことを意味します。

2. 命令キャッシュ

-O3 が必ずしも最速とは限りません。-Os の方がはるかに良い場合があります。Playdateは命令キャッシュが小さいです(Rev Aではわずか4キロバイト)。そのため、コアコード(エミュレータのインタープリターループ、フラグメントレンダラー、物理エンジンなど)が4キロバイト(Rev Bでは16キロバイトらしい?)に収まらない場合、より圧縮されたコード(CPU操作が多くても)よりもパフォーマンスが低下する可能性があります。ゲームボーイエミュレーションのパフォーマンスを向上させるために最初に行ったことは、20キロバイトのエミュレータコアを、巨大なswitchテーブルを削除し、わずかな分岐でコード量を大幅に削減することで、わずか2キロバイトに圧縮することでした(そして-Osを使用しました)。動作は同じでしたが、結果として大幅に高速になりました。

ここで重要なのは、この4キロバイトのキャッシュに収まる必要があるのはコアコードだけだということです。まれな操作(ほとんど発生しないオペコードや、シミュレーションで発生する可能性が非常に低いエッジケースなど)は、別の場所に配置できます。

理想的には、リンカによって4キロバイトのコアコード全体が連続したアドレスに配置されるべきです。これを達成するにはどうすればよいでしょうか?コア関数ごとに__attribute__((section(".text.<your-section-name-here>")))を使用すると、リンカがそれらを1つの連続したセクションに配置することを保証できます。リンカマップ(次のセクションを参照)を使用すると、さらに高度なトリックを実行できます。

3. カスタムリンカマップ

C_API/buildsupportフォルダからlink_map.ldをプロジェクトにコピーし、common.mkをインクルードする前にMakefileにこの行を追加します。

override LDSCRIPT=./link_map.ld

これにより、カスタムリンカスクリプトをポータブルに使用できます。リンカスクリプトを編集したことがない場合(ほとんどの人がそうでしょう)、心配はいりません。それほど複雑なものではありません。特定のファイルからのすべてのコードを特定の場所に配置するように指定できます(.oファイルがbuild/に配置されていると仮定します)。

/* カスタムコードセクション (例: __attribute__((section(".text.blah"))) */
*(.text.blah)

/* foo.c からのすべて */
build/foo.o(.text)
build/foo.o(.text.*)

/* 32バイトにアライン */
. = ALIGN(32);

/* 上記で明示的に言及されていないコード */
*(.text)
*(.text.*)

例のリンカスクリプト。

4. シンボルの検査

このコマンドを常に手元に置いておきましょう。

nm Source/pdex.elf | sort > syms.txt

これにより、すべてのシンボル(関数、変数など)とその関連アドレスのリストが生成されます。コアコードのサイズを簡単に確認し、命令キャッシュに収まるかどうかを確認できます。

出力例(一部):

00019361 t write_cart_ram_file /* <-- これは関数です */
00019420 t $d
00019440 t $t
00019441 t gb_error
000194dc t $d
00019500 t $t
00019501 t PGB_GameScene_menu
00019638 t $d
0001965c t $t
00019a04 t $d
00019a30 t $t
00019a31 T PGB_LibraryConfirmModal
00019a44 t $d
00019a50 t $t
00019a51 t gb_save_to_disk.isra.0
00019aa8 t $d
00019ac0 t $t
00019ac1 T __gb_write_vram
00019b10 t $t
00019b11 t PGB_GameScene_free
00019b9c t $d
00019bc0 t $t
00019bc1 T PGB_GameScene_new

5. DTCMアクセラレーション

タイトリーカップルドメモリ(TCM)と呼ばれる小さなメモリ領域があり、通常のメモリよりも高速です。スタックはこのTCM領域に配置されるため、スタックに割り当てられたオブジェクトは、ヒープ上のオブジェクトや静的変数よりも一般的に高速になります。

実際、特定の構造体でしばらく操作を行う場合は、それをスタックにmemcpyし、そこで操作してから、再度コピーバックする価値があります。@RPDev はこれをPlayGBに実装し、大幅なパフォーマンス向上を得ました。

// 遅い --
long_operation(&global_var);

// より速い --
some_type copy;
memcpy(&copy, &global_var, sizeof(global_var));
long_operation(&copy);
memcpy(&global_var, &copy, sizeof(global_var));

しかし、さらに改善できます!なぜ変数をヒープではなく、永続的にスタック上に置いておけないのでしょうか?そうすれば、2回のmemcpyをスキップできます。これをできない理由があります――mainを制御できないため、スタック上に永続的に何かを保持できません。しかし、回避策があります――スタックの反対側(つまり、低アドレス、スタックオーバーフローのリスクを冒して決して到達すべきではない部分)に格納しましょう。eventHandlerのkEventInitで__builtin_frame_address(0)を使用してスタックの高アドレス端を特定し、10キロバイト未満(0x2180が安全だとわかりました)を減算して低アドレス領域に到達できます。もしこの機能が最終的に追加されれば、スタックの低アドレス領域を見つけるより良い方法になります。

この低領域(dtcm_mempoolと呼びます)に何かを格納すると、更新ごとに永続化されるはずです。dtcm_mempoolの開始と終了にカナリアを配置し、少なくとも1回の更新ごとにチェックして、スタックオーバーフローがdtcm_mempoolを破損していないことを確認してください。

ちなみに、Playdateのフレームバッファなど、TCM領域にある他のメモリ部分もあります。スタック領域が不足している場合は、効率的なアクセス用にそこにデータを配置できます(ただし、画面に表示されるデータになるため、その事実に対処する必要があります)。

6. ITCMアクセラレーション

データだけでなく、スタック(またはdtcm_mempool)に配置できるのはコードでもあります。Rev Bでパフォーマンスが向上するかどうかは不明ですが、さらなる研究が必要です。しかし、Rev Aでは、ゲームボーイエミュレーションを効率化するための秘密のソースです。

PlaydateはコードをTCM領域に自動的に配置しないため、.textから手動でコピーする必要があります。Cでこのマクロを定義して、関数をitcm領域に属するものとしてマークします。

#define _itcm __attribute__((section(".itcm"))) __attribute__((short_call))

_itcmを関数定義の前に配置すると、itcmに属するものとしてマークできます。

次に、リンカマップで次のように指定します。

__itcm_start = .; 
*(.itcm)
__itcm_end = .;

これにより、Cから2つのシンボル(.itcmコードの開始と終了)が公開されます。これを使用して、.itcmコード全体を好きな場所に(TCMにコピーすることも含めて)memcpyできます。重要: コピー先のアドレスが元のアドレスとmod 2で合同であることを確認してください。Cortex M7は関数ポインタの最下位ビットを使用して、コードがThumbかARMかを示します。また、関数アドレスから直接memcpyすることはできません。関数アドレスは実際には関数の開始から1バイト後になるためです。ARMは奇妙です。

extern char __itcm_start, __itcm_end;

char dst_itcm_region[(uintptr_t)__itcm_end - (uintptr_t)__itcm_start];
memcpy(&dst_itcm_region, &__itcm_start, &__itcm_end - &__itcm_start);

// 関数のITCMコピーを呼び出す
((fn_ptr_t)((void*)some_itcm_fn - __itcm_start + dst_itcm_region))(args...);

考慮事項:

  • -fPICを有効にしないでください。なぜなら、逆説的ですが、コードがこのように再配置されると、再配置テーブルが機能しなくなるからです。
  • .itcmコードにはshortcall属性を使用してください(上記マクロのように)。itcm関数が別のitcm関数を呼び出す場合、相対ジャンプを行う必要があるためです(そうしないと、元の非再配置位置にジャンプする可能性があります)。
  • .itcmコードが呼び出す.itcm領域外の関数は、__attribute__((longcall))でマークする必要があります。これにより、絶対ジャンプが行われます(そうしないと、未知の場所への相対ジャンプになります)。
  • コードを変更/コピーした後は、命令キャッシュをフラッシュしてください。Playdate APIに関数があります。

これを正確に設定しないと、最初に試したときにクラッシュする可能性が高いです。したがって、これには小さく始めてください。たとえば、数値を返すだけの単一関数をコピーすることを試み、そこから進めてください。大きな関数をitcmに移植する際は非常に注意してください。それらはshortcallで他の関数を呼び出す可能性があり(そのため、ほぼ確実にクラッシュします)。

7. パフォーマンスの乱数(Performance Lottery)

コードを変更すると、明らかなパターンなしに、ビルドが遅くなったり速くなったりすることに気づくでしょう(時には50%速くなることもあります)。これには多くの原因がありますが、特に顕著な原因として特定したものが2つあります。キャッシュのずれと分岐予測テーブルです。

キャッシュのずれ

キャッシュラインのサイズは32バイトです。これは、アプリケーションが一度に32バイトの命令をロードすることを意味します。サイズがそれぞれ16バイトの2つの関数があり、それらが隣接しており、最初の関数のアドレスが32で正確に割り切れる場合、一方の関数をロードすると、もう一方の関数もキャッシュに入ることになります。逆に、一方の関数が32バイトの長さであっても、その開始アドレスが32で割り切れない場合、2つのキャッシュラインの境界をまたぐことになり(これは悪いことです)。

これがパフォーマンスの乱数効果を引き起こすのはなぜでしょうか?それは、32バイトで割り切れないサイズの関数をコードの早い段階に追加すると、他のすべての関数が下にシフトされ、それらのアドレスが元の mod 32 のアドレスと一致しなくなる可能性があることを意味します。この時点で、速くなるか遅くなるかは運次第です。

この効果を最小限に抑えるにはどうすればよいでしょうか?コードのあちこちに、32バイトにアラインされるように強制します。Cでは__attribute__((aligned(32)))で、リンカマップでは. = ALIGN(32);で実行できます。リンカマップからこれを行う利点は、手動で32バイトからのオフセットを指定できることです。例: . = ALIGN(32); . += 0xC。最も最近の高速ビルド(パフォーマンスの乱数でうまく機能した最後のビルド)のnm(セクション4)の出力を確認して、手動オフセットを決定する必要があります。私は、各ソースファイルとセクションをリンカマップに入れる前に. = ALIGN(32)を配置するのが好きです。これにより、キャッシュラインに関してそれらが互いに隔離されることが保証されます。

ちなみに、コンパイラオプション-falign-loops=32を使用すると、ループがコード内で32バイトにアラインされることが保証され、これも役立つ可能性があります。

分岐予測テーブル

Cortex M7 CPUでの分岐予測の仕組みの詳細は公開されていません。私の推定では(完全に間違っている可能性もあります!)、1024個の一意な命令アドレスの予測値のテーブルがあります。平易な言葉で言えば、2つのif文が互いに1024バイトの倍数離れている場合、分岐予測器はそれらを同じように扱い、多くの誤予測を引き起こします。したがって、リンカマップでは、varying値の0-1024の範囲で. = ALIGN(1024); . += n;をいくつか散りばめます。(さらに良いのは、最後の良好なビルドでの最初のシンボルのアドレスに基づいてnを選択することです。)ただし、これは4キロバイト以上の無駄なスペースなので、あまり多く行わないでください。

分岐予測がこの二次的なパフォーマンスの乱数の原因であるかどうかは間違っているかもしれませんが、いずれにせよ、ALIGN(1024)トリックは、1024が32で割り切れるという事実を超えて役立ちました。

これらのトリックを実装して以来、パフォーマンスの乱数はほとんどなくなったことに気づきました。

8. プリフェッチング

プリフェッチングを使用してもパフォーマンスの向上は観察されていませんが、賢く行っていないだけかもしれません。@FReDs72 は、このDiscordスレッドでプリフェッチングが役立ったケースを説明しています。プリフェッチングによるパフォーマンス向上は、おそらく非常に細かい粒度で行われるため、通常のFPSゲージではなく、高精度タイマーでフレーム時間を測定するとよいでしょう。

理論的には、プリフェッチングは間接参照がある場合に役立ちます。たとえば、ポインタのリストを反復処理する場合(int** list)、(a)リスト全体を事前に反復処理して各list[n]をプリフェッチする、または(b)list[i]を処理する前にlist[i+1]をプリフェッチする、という利点があるかもしれません。