改造ドンキーの可能性を追求する からあげラボ
English (トップへ)

時間計算量と空間計算量

処理にかかる時間と、処理に使うメモリの量の釣り合いを考えます。

2つの資源

プログラムが使える資源には、処理時間とメモリの2つがあります。SNESでは、どちらにもはっきりした上限があります。

資源上限の目安
処理時間1フレーム(NTSCで1364マスターサイクル × 262ライン、約35万7千マスターサイクル)。この中にメインの処理とNMI処理ルーチンの両方が収まる必要がある
WRAM128KB。このうちダイレクトページやスタックとして使えるのは、バンク0から見える先頭の8KBだけ
ROMカートリッジの容量しだい。WRAMよりはずっと大きい

命令1つにかかる時間は、命令サイクルの数と、アクセスするメモリの速さで決まります(メモリマップ)。このページでは、各命令のページの表にある命令サイクルの数で比べます。

同じ結果を得る方法が何通りもあるとき、多くの場合、処理時間を減らす方法はメモリを多く使い、メモリを減らす方法は処理時間が長くなります。
どちらを選ぶかは、その処理が何回実行されるか、どのメモリにどれだけ余裕があるかで決まります。

計算量

処理するものの数(オブジェクトの数、データのバイト数など)をnとしたとき、処理時間がnに対してどのように増えるかを時間計算量、使うメモリがどのように増えるかを空間計算量といいます。
増え方は、O(1)(nによらず一定)、O(n)(nに比例)、O(n²)(nの2乗に比例)のように書き表します。

たとえば、当たり判定を、すべてのオブジェクトの組について総当たりで行うと、組の数は n × (n − 1) ÷ 2 で、O(n²)です。

オブジェクトの数組の数
828
16120
32496
642016

オブジェクトの数が2倍になると、判定の回数はおよそ4倍になります。SNESのゲームではnがそれほど大きくないので、計算量の違いと同じくらい、1回あたりの命令サイクルの数も効いてきます。
それでも、毎フレーム実行する処理の中にO(n²)のものがあると、オブジェクトを少し増やしただけで1フレームに収まらなくなることがあります。

表引き(LUT)

計算の結果をあらかじめ表(ルックアップテーブル、LUT)にしておき、計算する代わりに表を引く方法は、もっともよく使われる最適化の1つです。メモリ(表の大きさ)を使って、処理時間を減らす方法です。

例として、8ビットの値の中で1になっているビットの数を数える処理を、3通りの方法で書きます。

; Aの値の、1になっているビットの数をAに返す(1ビットずつ調べる)
; A・X・Yは8ビットで呼ぶこと
CountBitsLoop:
    STZ $00
    LDX.b #$08
.loop
    LSR A           ; 最下位ビットをキャリーへ
    BCC .skip
    INC $00
.skip
    DEX
    BNE .loop
    LDA $00
    RTS

; 256個の表を引く
CountBitsTable:
    TAX
    LDA BitCount256,X
    RTS

skip align 256      ; 表をページの先頭に置く
BitCount256:
    for i = 0..256
        db (!i&1)+((!i>>1)&1)+((!i>>2)&1)+((!i>>3)&1)+((!i>>4)&1)+((!i>>5)&1)+((!i>>6)&1)+((!i>>7)&1)
    endfor

; 16個の表を、下位4ビットと上位4ビットで2回引く
CountBitsNibble:
    PHA
    AND.b #$0F
    TAX
    LDA BitCount16,X ; 下位4ビットの数
    STA $00
    PLA
    LSR A
    LSR A
    LSR A
    LSR A
    TAX
    LDA BitCount16,X ; 上位4ビットの数
    CLC
    ADC $00
    RTS

BitCount16:
    db 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4

BitCount256の表は、asarの for で値を計算しながら作っています。

それぞれの命令サイクルの数(JSR命令・RTS命令を除く)と、表に使うメモリは次のとおりです。

方法命令サイクル表の大きさ
1ビットずつ調べる87～1190バイト
16個の表を2回引く3716バイト
256個の表を引く6256バイト

1ビットずつ調べる方法は、1になっているビットが多いほど時間がかかります(1ビットあたり、0なら10サイクル、1なら14サイクル)。表を使う方法は、値によらず一定です。

256バイトの表を使えば、時間はおよそ15分の1～20分の1になります。表の大きさを16バイトに抑えても、1ビットずつ調べる方法の2分の1～3分の1ほどの時間で済みます。
このように、表引きには「表を大きくするほど速くなる」という段階があり、その中から使える場所に合ったものを選びます。

表の位置にも注意が必要です。LDA abs,X は、インデクスを足したときにページ境界(アドレスの下位8ビットが$FFから$00になるところ)を越えると1サイクル増えます(LDA命令)。
256個の表をページの先頭に置けば、どの値でも越えません。asarの skip align 256 は、次の$xx00の位置まで進めます。

表を作る場所

場所使うメモリ向いているもの
ROM(アセンブル時に作る)ROM値が最初から決まっているもの(ビットの数、三角関数、2進数とBCDの変換など)
WRAM(起動時やステージの開始時に作る)WRAMステージやゲームの状態によって変わるもの、ROMに置くと大きすぎるが計算で作れるもの

WRAMに作る場合は、表を作る時間もかかります。強制ブランク中や読み込みの途中など、時間に余裕のあるときにまとめて作ります。

表の値に規則性があれば、表を小さくできます。たとえば、1周を256段階に分けた正弦(sin)の表は、16ビットの値なら512バイトです。
正弦の値は0～90度の部分を折り返したり符号を変えたりすると残りの部分が得られるので、0～90度の65個分だけを持てば、130バイトで済みます。その代わりに、角度がどの範囲にあるかを調べて、引く位置と符号を変える処理が増えます。

メモリを使って時間を減らすほかの方法

  • 大きさを2のべき乗に揃える: オブジェクトの管理の構造体の大きさ(16バイト)や、地形との当たり判定のマップの幅(64ブロック)は、2のべき乗にしてあります。
    こうすると、位置の計算が掛け算ではなくシフトで済みます。その代わり、実際に必要な大きさより大きく取る分、使わない領域が生まれます。
  • 結果を取っておく: 1フレームの中で何度も使う値(画面上の座標など)は、一度計算したらメモリに置いて使い回します。
  • 変わったものだけを処理する: タイルマップの写しのうち書き換えた部分だけを転送する、変わったかどうかの印をメモリに持つ、などの方法で、毎回すべてを処理するのを避けます。
    VRAM転送のキューもその1つです。
  • 空間を区切る: オブジェクトを画面の区画ごとに分けて記録しておくと、当たり判定は同じ区画や隣の区画のオブジェクトとだけ行えばよくなります。区画ごとの一覧を持つためのメモリと、一覧を作り直す時間が必要になります。

時間を使ってメモリを減らす方法

  • 圧縮する: データの圧縮と展開。ROMを節約する代わりに、展開する時間がかかります。
  • 詰め込む: 1バイトに複数の値を詰め込むと、WRAMを節約できます。その代わりに、読み書きのたびにビットを取り出したり組み立てたりする処理がかかります(ビットフィールド)。
  • その場で計算する: 表を持たずに、必要になるたびに計算します。

どちらを選ぶか

  • 何回実行されるか: 毎フレーム、オブジェクトやスプライトの数だけ実行される処理は、少しの改善が大きく効きます。ステージの開始時に1回だけ実行される処理は、多少遅くても困りません。
  • どのメモリが足りないか: ROMの空きに比べて、WRAM、特にバンク0の8KBやダイレクトページの256バイトは貴重です。ROMに置ける表と、WRAMに作る必要がある表では、同じ大きさでも重みが違います。
  • まず測る: どの処理が時間を使っているかは、思っているのと違うことがよくあります。最適化する前に、実際にかかっている時間を測ってください。

処理時間を測る

処理の前後で、PPUの垂直カウンタ(今描いているラインの番号)を読むと、その処理にかかった時間をライン単位で測れます。1ラインは1364マスターサイクルです。

; 今のラインの番号(0～261)をAに返す
; 戻るときはAが16ビットになる
GetLine:
    SEP #$20
    LDA $213F       ; STAT78: OPVCTの読み出し順をリセット
    LDA $2137       ; SLHV: カウンタの値をラッチ
    LDA $213D       ; OPVCT: 下位8ビット
    XBA
    LDA $213D       ; OPVCT: 最上位ビット
    AND.b #$01
    XBA
    REP #$20
    RTS

測りたい処理の前と後でGetLineを呼び、差を取ります。処理の途中でフレームが変わると差が負になるので、メインループの最初(Vブランクの直後)から測るのが簡単です。
ラッチはWRIOのビット7が1のときだけ働きます(通常はWRIOを$FFのままにしておきます)(SLHV、OPHCT・OPVCT)。

コードから構造を読み取る

既存のプログラムでは、次のようなところから表引きや前計算を見つけられます。

  • 値を計算してインデクスにしたあと、LDA 表,X で読んだ値をそのまま結果として使っている。表のアドレスが$xx00から始まっていたり、大きさが16や256など2のべき乗だったりすることが多いです。
  • 表の中身が、0から最大値まで滑らかに増えて減る並びなら三角関数、急に減ってから緩やかになる並びなら逆数などの表です。
  • 起動時やステージの開始時に、WRAMの領域を順に埋めていくループがあれば、前計算した表を作っている可能性があります。そのあと、毎フレームの処理でその領域を ,X や ,Y で読んでいれば確かです。
  • 構造体の大きさやマップの幅が2のべき乗になっていて、位置の計算がASL命令やLSR命令の繰り返しになっていれば、計算を速くするために大きさを揃えています。

参照

メモリマップ
テーブルの参照
定数倍とシフトによる乗除算
ビットフィールド
データの圧縮と展開
当たり判定