- 1993年当時の高性能PCクラスである IBM PS/1 486-DX2 66MHz では、オリジナルの DOOM は
demo1 基準で 21.5fps だったのに対し、fastDOOM は同条件で 30.1fps まで向上し、DOS ポート最適化の差を示した
- fastDOOM は、Linux DOOM コア、Heretic I/O、APODMX、
DOOM.EXE の逆アセンブルを基にした Mode Y グラフィック I/O を組み合わせた PCDOOM v2 から出発した
- 52件のリリースと 3,042件のコミットをビルド・ベンチマークした結果、性能向上は単一の現代的コンパイラではなく、小さな最適化の積み重ねから生まれていた
- 大幅な改善には、ステータスバー描画の省略、
FixedDiv のインライン化、BSP 走査の最適化、visplane 描画の省略、ポインタ間接参照の削減、レンダラー別の実行ファイル分離が含まれる
- グラフィックモードは CPU とバスによって向き不向きがあり、遅い CPU では Mode Y が有利で、高速な CPU・VLB/PCI 環境では Mode 13h や VESA direct が有利な場合もあるが、VESA 2.0 のような制約は残る
486-DX2で明らかになった性能差
- IBM PS/1 486-DX2 66MHz “Mini-Tower” モデル 2168 でオリジナルの DOOM を
doom.exe -timedemo demo1 で実行すると、1710 gametics in 2783 realtics が出力される
- DOOM は fps を直接表示しないため、
1710/2783*35 で計算する必要があり、結果は 21.5fps となる
- 同じマシンで
fdoom.exe -timedemo demo1 を実行すると、1710 gametics in 1988 realtics となり、30.1fps が確認できる
doom2 の demo1 のようなより重いマップでは、オリジナルの 16.8fps から fastDOOM の 24.9fps へ向上し、48% 高速化している- ただし joystick と network gameplay のサポートは削除されており、すべての機能をそのまま保持したポートではない
fastDOOM に至るコードの系譜
- DOOM はもともと NeXT Workstation 上で開発されており、コアコードの大部分と小さな I/O サブシステムに分かれた、移植しやすい構造を持っていた
- 商用 DOS 版は id Software が書いた DOS I/O を使っていたが、proprietary sound library である DMX への依存のため、1997年にそのままオープンソース化することはできなかった
- 公開されたコードは、Bernd Kreimeier がエンジン解説書プロジェクトを進める中で整備した Linux 版である
- DOS 版 PCDOOM v2 は次の組み合わせで再構成された
- Linux DOOM の コア
- Heretic の I/O
- DMX を模倣するための APODMX
DOOM.EXE の逆アセンブルからリバースエンジニアリングされた i_ibm.c グラフィック I/O
- fastDOOM はこの PCDOOM v2 を出発点としている
リリースとコミットで追った性能変化
- Victor “Viti95” Nieto は fastDOOM を高頻度でリリースし、各リリースにタグを付け、1つのコミットが1つの仕事をするように管理していた
- fastDOOM の Git 履歴は 3,042件のコミットで構成されており、コミットごとの性能変化を追跡できた
- 52件の fastDOOM リリース、PCDOOM v2、オリジナルの
DOOM.EXE をダウンロードし、-timedemo demo1 を実行する RUN.BAT を Go プログラムで生成して、mTCP NETDRIVE でマウントしてテストした
- 条件は
DOOM.WAD、sound on、screen size 10
- スイート全体を5回実行し、平均 fps をグラフ化した
- PCDOOM v2 は OpenWatcom 2 でビルドされていたにもかかわらず、オリジナルの
DOOM.EXE に対する改善幅は大きくなく、fastDOOM の向上は 現代的なコンパイラを使っただけでは説明しにくい
- ファイルサイズのグラフでは、初期作業はコード整理と削除によってより軽量化する方向だった
性能を引き上げたリリースごとの変更
- 全 3,042 ビルドをすべて timedemo すると約9日かかる可能性があるため、速度向上が大きかった
v0.1, v0.6, v0.8, v0.9.2, v0.9.7 を中心に、コミット単位のベンチマークが行われた
-
fastDOOM v0.1
v0.1 は 220件のコミットで構成される- 最大のパッチは build 36 の e16bab8
- “Crispy optimization” は、ステータスバーのパーセンテージが変わっていない場合に描画を no-op にして、scrap buffer 描画と画面 blit を回避する
- この変更1つで 2fps の向上が確認された
- build 167 の a9359d5 は
FixedDiv をマクロとしてインライン化した
- build 207 の 9bd3f20 は PSX Doom の最適化を取り込み、BSP 走査方式を改善した
- build 212 の dc0f48e は水平面描画関数
R_MakeSpans をインライン化した
- 全コミット中、削除コミットが100件あり、約半分が コード削除だった
-
fastDOOM v0.6
v0.6 は 33件のコミットで構成される- build 342 の 22819fd は不要な visplane 描画をスキップする
- build 359 の 40e0d4b と build 360 の ccd296f は player pointer の間接参照を減らした
- build 369 の f29e665 は screenspace line splitter をインライン化した
-
fastDOOM v0.8
v0.8 は 282件のコミットで構成される- sound system が不安定だったため、sound なしで timedemo を実行した後に fps を補正した
- このリリースは text-mode renderer に焦点を当てており、build 670 と build 730 では Crispy optimization が外れて回帰が発生した
- 主な改善は次のとおり
- f279b7d:
FDOOM.EXE, FDOOM13H.EXE など、レンダラーごとに実行ファイルを分離
- 1874ee8: コンパイラデバッグを無効化
- 6aae724: Crispy optimization を復元
- 1366ebf: 可能な場合はより少ないコードだけをコンパイル
-
fastDOOM v0.9.2 と v0.9.7
v0.9.2 は 110件のコミットで、skyflatnum 比較の最適化、Mode Y 向け R_DrawColumn 最適化、R_DrawSpan のコード整理が主な変更v0.9.7 は 293件のコミットとして紹介されたが、コマンド出力では 294件と表示された- このリリースは何度ベンチマークしてもノイズを減らせなかった
- 主な変更は、x86 ASM 変更テスト、386SX 向け CPU 選択と CR2 最適化、
R_DrawSpan386SX 向け ESP 最適化、ASM fuzz column rendering ベースのコード、ループごとの CMP 比較削減など
Mode 13h、Mode Y、VESA direct の選択基準
- fastDOOM は 386、486、Pentium、Cyrix と、ISA、VLB、PCI のような多様な CPU・ビデオバスの組み合わせを対象に、さまざまな最適化を探っている
- IBM PS/1 486-DX2 66MHz では、Mode Y の代わりに Mode 13h を使う最適化はむしろ遅かった
-
Mode 13h
- VGA の4つの VRAM bank へのデータ分配をハードウェアが処理するため、CPU からは単一の線形 320x200 framebuffer のように見える
- VRAM 上で double buffering ができないため、RAM でバッファリングしてから VRAM へ再コピーする必要があり、バイトを2回書くことになる
- エンジンは VSYNC でブロックされなければならない
-
Mode Y
- VGA bank に個別アクセスできるため、VRAM triple buffering が可能で、バイトを直接 VRAM に1回だけ書けばよい
- bank 選択には遅い
OUT 命令が必要
- latch によって2つの VGA bank に同時書き込みすると、水平方向のピクセル複製が可能になり、low-detail mode を実現できる
- invisible Specter の描画では VRAM readback が必要になるため、はるかに遅い
- John Carmack の説明では、DOOM は 320×200×256 VGA モードで Mode X に近い interleaved planar mode を使い、3つの display page を循環させていた
- video memory へ直接 texture mapping することで、多くのビデオカードで 10%〜15% の追加速度が得られた
- main memory buffering よりもティアリングのない page flip も可能だった
- Heretic は 1994年に発売され、その頃のハードウェア変化により Mode 13h がより魅力的な選択肢となり、Raven は DOOM エンジンをこの方向に修正した
- fastDOOM はユーザーに複数の実行ファイルを提供している
FDOOM.EXEFDOOM13H.EXEFDOOMVBD.EXE
-
fastDOOM の Mode 13h と VESA direct
- fastDOOM の Mode 13h は、RAM の単一 framebuffer にレンダリングしてから、シーン全体が終わった時点で VRAM にコピーする
- VSYNC を強制しないため、flickering が発生することがある
- 低速な 8-bit ISA bus では、変更されたピクセルだけを転送する differential copy が使われる
- 16-bit ISA、VLB、PCI などの高速な bus では、
REP MOVS によって backbuffer 全体をコピーする
- Viti95 のテストでは、486 CPU に最適なモードは 320×200 向けの VESA direct mode である
FDOOMVBD.EXE
- Mode Y の利点と Heretic の最適化されたレンダリングコードを組み合わせている
- バッファ切り替え時のフレームあたり1回の
OUT を除けば、OUT 命令を避けられる
- LFB が有効な VLB または PCI グラフィックカードと VESA 2.0 対応が必要で、low-detail と potato-detail mode では遅い
- IBM 2168 は VESA 2.0 をサポートしていないため、
FDOOMVBP.EXE と FDOOMVBD を実行するとエラーになる
うまくいかなかった試みと全体的な印象
- OpenWatcom のプロセッサ別フラグである
4r/4s と 3r/3s も試されたが、中止された
- wcc386 の 386 フラグと 486 フラグの両方が試され、結果として 386 版のほうが常に速く見えた
- Viti95 は fastDOOM のコンパイラを OpenWatcom v2 から DJGPP、つまり GCC に切り替える目標も持っている
- 同じソースでも GCC のほうがより高速なコードを生成することが分かったためである
- あるいは OpenWatcom v2 側が改善されて性能差を縮めることも、望ましい選択肢として残っている
- fastDOOM の性能は、Crispy、PSX、GBA、Lee Killough の既存改善を活用しつつ、新たな最適化を大量に追加した結果である
- Ken Silverman のアイデアと一部コードも UMC Green CPU 向けレンダリング関数に取り込まれ、そのハードウェアで大きな速度向上を生んだ
- fastDOOM は1つの魔法のような変更ではなく、何千もの小さな最適化が積み重なって、オリジナル DOOM より高速な DOS ポート になった事例である
1件のコメント
Hacker News のコメント
ボトルネックはたいてい予想した場所にはないので、プロファイリングと計測が必要だという好例
ステータスバーのパーセント表示のレンダリングだなんて、Doom の構造をよく知る専門家には比較的自明だったかもしれないが、事前には絶対にボトルネックだとは推測できなかったと思う
https://www.granola.ai/blog/dont-animate-height
最悪の場合、ステータスバーにスコアを表示するだけでフレーム全体の 1/6 近くを使ってしまい、遅くなるしきい値が低くなっていた。パッチではスコアの保存・表示方式をほぼ定数時間に近いものへ変え、従来の最良ケースよりも少し速くした
https://www.smwcentral.net/?p=section&a=details&id=35746
透明度、レイヤリング、再描画、とくにメモリ割り当ての誘発によって UI レンダリングが致命的になり得るし、再描画の前に以前の値と新しい値を比較する方法が大きく役立つ
CSS でもレイヤーと透明度がボトルネックだったプロジェクトがあり、そのときはレイヤー数を減らすことが肝だった
6分かかっていたロードを2分未満に短縮した
https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
https://news.ycombinator.com/item?id=10974929
実際の対象読者ではないのかもしれないが、mTCP の NETDRIVE は興味深かった
そんな昔にも使い物になるネットワークストレージの選択肢があったとは知らなかったが、調べてみると https://www.brutman.com/mTCP/mTCP_NetDrive.html が出てきて、本当にすばらしい
NetDrive は、別のマシンがホストするリモートのディスクイメージを、DOS 上でドライブ文字の付いたローカルデバイスのようにアクセスできるようにするデバイスドライバだという
ものすごく遅く、学生たちは授業開始時にワープロを起動するだけで5〜10分ずつ無駄にしていたし、Xerox Alto もドライブにネットワークマウントを使っていた
ネットワークがあれば、誰かがすぐファイルコピーを望むようになり、最も便利な方法はローカルファイルシステムのように見せることだ
DOS には内蔵ネットワーク機能がなかったので、このあたりで遅れを取り、自分でやらなければならないことが多かった
DOS 側のドライバや設定なしにネットワークブロックデバイスへ読み書きアクセスできるようになるが、共有のように使うとすぐ壊れるし、ブロックデバイスに近い
魔法のように感じるが、iPXE が BIOS にパッチを当ててディスクアクセスを iSCSI に送っているのだと思う
FTP や telnet のようなものは当然あっただろうが、リモートマウントが実際に使われていたのか、それとも低帯域のせいで不可能だったのか気になる
Ken Silverman が参加している GitHub スレッドは宝物のようだ
FastDOOM の作者と Ken が難解な 486 レジスタとクロックサイクル効率を掘り下げていく過程を見るのは驚きだ
Doom が今も性能改善を受けられるよう気にかけている人がいるのはうれしい
あのスクリプティングが文字どおり初めての「コーディング」で、ある意味では自分のキャリアと財産のすべてを KenS に負っているようなものなので、すばらしい
とくにメモリアクセスが非常に遅い 386SX と、キャッシュのない 386DX で CR2 と CR3 をスクラッチパッドレジスタのように使うアイデアがよかった
割り込みを切らずに ESP をループカウンタとして使う手法も天才的で、常に有効なスタック位置を指すよう保証する方式だ
FastDOOMでここではあまり触れられていない機能は、ありとあらゆる奇妙なビデオモードだと思う
IBM MDAテキストモード: https://www.youtube.com/watch?v=Op2tr2lGK6Y
EGA & Plantronics ColorPlus: https://www.youtube.com/watch?v=gxx6lJvrITk
古典的な青・ピンクのCGA: https://youtu.be/rD0UteHi2qM
「ANSI from Hell」ハックを使ったCGA 320x200x16: https://www.youtube.com/watch?v=ut0V1nGcTf8
Hercules: https://www.youtube.com/watch?v=EEumutuyBBo
ほとんどは色の再マッピングのような処理のせいで、VGAよりも遅く動くようだ
CGAで動かさなければならないなら嫌だし、もしまだ手元に残っていたならTandy 1000 TL/2向けに286ビルドが必要だったと思う
バックエンドアプリケーションにおける「モダン」なClean Architectureを思い出す
「IBM PS/1 486-DX2 66Mhz、『Mini-Tower』、model 2168。十代の頃ずっと欲しかったが買えなかったコンピューター」という部分が印象的だった
1992年ごろには自作の4台目のPCを使っていて、マサチューセッツ州マールボロのKCSコンピューターショーは、いじり回す人たちにとってものすごい資源だったと思う
部品を買ってPCを組み、しばらく使って売り、また部品を買う、という感じだった
1992年末にはULSI 487数値演算コプロセッサ付きの486-DX3 100を動かしていて、しばらくの間はキャンパスで最速のPC、ひょっとすると最速のコンピューターだったと言える
複数のPentiumモデルより速く、数値演算のエラーも出さなかった
最後のビルドは、優等論文用にガス/ディーゼル熱電併給プラントを21ページのExcelスプレッドシートでシミュレーションしていて、再計算時間が長すぎたため正当化できた
専攻は環境科学だったが、キャリアは完全にコンピューターになった
1992年にそういうコンピューターを買えなかった人に、わざわざつらい思いをさせる必要があったのだろうか
それに「DX3」というものは存在せず、最初の100MHz 486であるDX4は1994年3月に出たので、1992年末に動かしていたというのは正しくなさそうだ
うちの最初のコンピューターは、1992年ごろにもらった、すでに古すぎたXTを除けば、1995年初めに買った66MHz 486-DX2だった
何十年もたった今でも、3年のハンデがあったのに自分のコンピューターより速かったという不可能なコンピューターを妙に自慢されるのを見ると、なぜかプライドが傷つく
1992年ごろは貧乏な大学生で、信用組合から約2,000ドルを借りて486 DX2-50を買った
今の金額にすると、かなり基本的なコンピューターに4,000ドル以上を使ったことになり、そいつにDOSとLinuxをデュアルブートしていた
調べてみると、標準の487はもともと486SXを無効化して置き換える完全な486DXだったらしい
もしかして、自分が知らなかった別のすごいコプロセッサだったのだろうか
きっちり圧倒している
頻繁にリリースしただけでなく、Viti95は1コミットが1つのことを行い、各リリースにタグを付けるという優れたGit規律を示していた
https://fabiensanglard.net/fastdoom/#:~:text=one%20commit%20...
「fastDOOMを知るまでは、Ibuprofenを飲みながらプレイするしかないと諦めていた」のIbuprofenがどういう意味なのか分からない
著者が見ているなら、文書全体でJohn Carmackの姓が「Carnmack」と誤記されている
現代のソフトウェアが遅く、こうした最適化が入らない理由を皮肉抜きで見るなら、標準化/最適化仮説で説明できる
何かが標準になると、最適化が後からついてくる
標準のテストをすべて通過しながら、最速になりたくなるからだ
Doomも今では、新しいCPUであれトースターであれ、どこにでも移植される標準的なゲームになっており、メールプロトコルやブラウザー標準であるWebRTC、QUICなども似ている
最新のWebアプリやElectronアプリが速くない理由は、探索段階にあるからだ
毎日新しいユーザー要求に合わせて更新され、性能面では邪魔にならない程度に速ければ十分だ
だからIRCアプリは非常に速いが、SlackとTeamsは常に遅くならざるを得ない
バージョンをさかのぼって改善とリグレッションを確認するのは些細なことではない
ある最適化は後で見つかるバグを生むことがあり、必須の機能が性能を落とすこともある
だから各リリース前に自動で走る性能テストを用意しておくと楽になり、性能問題が見つかったら普段どおりリグレッションテストを書けばよい
言いたいことは結局、性能テストをしようということだ