序文
Luaはそのパフォーマンスで知られるスクリプト言語で、特にゲームでは広く使われています。World of Warcraftのようなプラグイン、Grand Master、Divine Comedy、Lost Landsのようなモバイルゲームなどは、すべてLuaでロジックが書かれています。
クヌースの有名な言葉に「早すぎる最適化は諸悪の根源」というものがあります。これは、時期尚早の最適化は不必要であり、多くの時間を浪費し、コードの混乱を招くという考え方です。
どの部分を最適化するかを決めるのに、推測や当て推量に頼ることはできません。アナライザーを使ってパフォーマンスのボトルネックを測定し、最適化を開始する必要があります。最適化後も、アナライザの助けを借りて、行った最適化が本当に効果的かどうかを測定する必要があります。
くだらないコードを大量に書いてから最適化について考えるのではなく、****が書かれたときに****プラクティスに従って高性能なコードを書くのが****の方法だと思います。仕事が終わってから最適化することの面倒くささは、みんなよく分かっているはずです。
高性能なLuaコードを書くと決めたら、次のセクションでは、Luaで最適化できるコード、低速になるコード、そしてそれらを最適化する方法について説明します。
ローカル
コードを実行する前に、Luaはソースコードをプリコンパイルし、Javaの仮想マシンに似た中間コードに変換します。このフォーマットは、Cインタープリタによって解釈され、全体のプロセスは多くのswitch.......case文で、caseは解析される命令に対応します。
Lua 5.0以降、Luaはレジスタに似た仮想マシンモデルを採用しています。Luaはレジスタを格納するためにスタックを使用します。スタックの長さは8ビットで表されるため、各関数のスタックには最大250個のレジスタを格納することができます。
これだけ多くのレジスタがあれば、Luaのプリコンパイラがすべてのローカル変数をレジスタに格納することができます。そのため、Luaはローカル変数のフェッチを非常に効率的に行うことができます。
例：a と b をローカル変数とすると、a = a + b のプリコンパイルは次の命令を生成します：
;a是寄存器0 b是寄存器1
ADD 0 0 1
しかし、aもbもローカル変数として宣言されていない場合、プリコンパイルは次のような指令を出します：
GETGLOBAL 0 0 ;get a
GETGLOBAL 1 1 ;get b
ADD 0 0 1 ;do add
SETGLOBAL 0 0 ;set a
Luaのコードを書くときは、ローカル変数を使うようにしましょう。
a = os.clock()
for i = 1,10000000 do
local x = math.sin(i)
end
b = os.clock()
print(b-a) -- 1.113454
ローカル変数に代入します：
a = os.clock()
local sin = math.sin
for i = 1,10000000 do
local x = sin(i)
end
b = os.clock()
print(b-a) --0.75951
math.sinを直接使うと1.11秒かかり、ローカル変数sinを使ってmath.sinを節約すると0.76秒かかります。30%の効率向上が得られます！
表について
テーブルはLuaのコンテナのほとんどを置き換えるため、Luaでは非常に頻繁に使用されます。そのため、Luaがテーブルをどのように実装しているかを簡単に見ておくと、Luaのコードを書く際に役立ちます。
Luaのテーブルは配列部分とハッシュ部分に分かれています。配列部分には1からnまでのすべての整数キーが格納され、それ以外のキーはハッシュ部分に格納されます。
ハッシュ部分は、実際にはハッシュテーブルであり、ハッシュテーブルは本質的に配列であり、それは、添え字の配列にキーを変換するためにハッシュアルゴリズムを使用し、添え字が競合している場合、それはチェーンテーブルを作成するために添え字に競合し、このチェーンテーブル上のキーの文字列とは異なります、競合解決のこのメソッドは、次のように呼ばれます：チェーンアドレス法。
テーブルに新しいキー値を代入する際、配列とハッシュテーブルが一杯になると再ハッシュが発生します。再ハッシュにはコストがかかります。まずメモリ上に新しい長さの配列を確保し、それからすべてのレコードをハッシュし直し、元のレコードを新しい配列に移します。新しいハッシュテーブルの長さは、全要素数に最も近い2の乗数となります。
空のテーブルが作成されると、配列とハッシュ・セクションの長さは共に0に初期化されます。次のコードを実行すると、Luaではどうなるかを見てみましょう：
local a = {}
for i=1,3 do
a[i] = true
end
1回の繰り返しで、a[1] = trueがリハッシュのトリガーとなり、ルアは配列部分の長さを2^0、つまり1に設定し、ハッシュ部分は空のままです。2回目の繰り返しでは、a[2] = trueで再びリハッシュが実行され、配列部分の長さが2^1、つまり2に設定されました。 *** 1回の繰り返しで再びリハッシュが実行され、配列部分の長さが2^2、つまり4に設定されました。
以下のコード：
a = {}
a.x = 1; a.y = 2; a.z = 3
テーブルのハッシュ部分を3回リハッシュすることを除けば、前のコードと似ています。
3つの要素しかないテーブルは3回のリハッシュを行います。しかし、100万個の要素を持つテーブルは、2^20 = 1048576 > 1000000であるため、20回のリハッシュしか行いません。
例えば、{true,true,true}の場合、Luaはこのテーブルが3つの要素を持つことを知っているので、Luaは直接3つの要素の長さの配列を作成します。同様に、{x=1, y=2, z=3}の場合、Luaは長さ4の配列をハッシュセクションに作成します。
次のコードは1.53秒で実行されました：
a = os.clock()
for i = 1,2000000 do
local a = {}
a[1] = 1; a[2] = 2; a[3] = 3
end
b = os.clock()
print(b-a) --1.528293
テーブルを作成するときにそのサイズを入力すれば、わずか0.75秒で、効率は2倍になります！
a = os.clock()
for i = 1,2000000 do
local a = {1,1,1}
a[1] = 1; a[2] = 2; a[3] = 3
end
b = os.clock()
print(b-a) --0.746453
そのため、小さなサイズのテーブルを大量に作成する必要がある場合は、テーブルのサイズを事前に入力しておく必要があります。
文字列について
他の主流のスクリプト言語とは異なり、Luaは文字列型の実装に2つの違いがあります。
*** すべての文字列は、Luaの中に1つのコピーしか保存されません。新しい文字列が現れると、Luaはその文字列と同じコピーがあるかどうかをチェックし、なければ作成し、なければそのコピーを指すようにします。文字列の比較は参照が一致するかどうかをチェックするだけなので、文字列の比較やテーブルのインデックス作成が非常に速くなります。
第二に、すべての文字列変数は文字列参照のみを保存し、そのバッファは保存しません。例えば、Perlでは$x = $yとすると、$yのバッファ全体が$xのバッファにコピーされます。一方Luaでは、同じ代入でも参照だけをコピーするのが非常に効率的です。
しかし、参照だけを保存すると、文字列を連結するときに遅くなります。Perlでは、$s = $s . x' と $s .= 'x' は驚くほど効率が違います。前者は $s 全体のコピーを取り、その末尾に 'x' を追加しますが、後者は $x バッファの末尾に直接 'x' を挿入します。
後者はコピーする必要がないので、その効率は$sの長さに依存しません。
Luaでは2番目の高速な処理はサポートされていません。次のコードは6.65秒かかります：
a = os.clock()
local s = ''
for i = 1,300000 do
s = s .. 'a'
end
b = os.clock()
print(b-a) --6.649481
バッファはテーブルでシミュレートすることができ、以下のコードにかかる時間はわずか0.72秒で、9倍以上効率が向上しています：
a = os.clock()
local s = ''
local t = {}
for i = 1,300000 do
t[#t + 1] = 'a'
end
s = table.concat( t, '')
b = os.clock()
print(b-a) --0.07178
ですから、大きな文字列の連結は避けるべきです。バッファをシミュレートするためにテーブルを適用し、最終的な文字列を得るために連結します。
#p#
Rプリンシプル
3R原則とは、リデュース（削減）、リユース（再使用）、リサイクル（再資源化）の3原則の頭文字をとったものです。
3Rは循環経済と環境保護の原則ですが、Luaにも当てはまります。
Reducing
新しいオブジェクトを作らず、メモリを節約する方法はたくさんあります。例えば、プログラムがあまりにも多くのテーブルを使用する場合、それらを別のデータ構造で表現することを検討するかもしれません。
栗の実を取りましょう。 プログラムの型に多角形があり、多角形の頂点を格納するためにテーブルを使うとします：
polyline = {
{ x = 1.1, y = 2.9 },
{ x = 1.1, y = 3.7 },
{ x = 4.6, y = 5.2 },
...
}
上記のデータ構造は非常に自然で理解しやすい。しかし、各頂点はハッシュセクションに格納する必要があります。配列セクションに配置すれば、メモリフットプリントは小さくなります。
polyline = {
{ 1.1, 2.9 },
{ 1.1, 3.7 },
{ 4.6, 5.2 },
...
}
100万頂点では、メモリは153.3MBから107.6MBに削減されますが、その代償として可読性の低いコードになります。
可能な限り病的な方法で：
polyline = {
x = {1.1, 1.1, 4.6, ...},
y = {2.9, 3.7, 5.2, ...}
}
100万頂点の場合、メモリは元の1/5の32MBしか消費しません。パフォーマンスとコードの可読性のトレードオフを行う必要があります。
for i=1,n do
local t = {1,2,3,'hi'}
--ロジックを実行しても変わらない
...
end
ループの中で不変のものは、ループの外に置いて作るべきです：
local t = {1,2,3,'hi'}
for i=1,n do
--ロジックを実行しても変わらない
...
end
Reusing
新しいオブジェクトの作成を避けられない場合は、古いオブジェクトの再利用を検討する必要があります。
次のコードを考えてみましょう：
local t = {}
for i = 1970, 2000 do
t[i] = os.time({year = i, month = 6, day = 14})
end
ループの各反復では、新しいテーブルが作成されますが、それは変数である場合に限られます。
次のコードでは、このテーブルを再利用しています：
local t = {}
local aux = {year = nil, month = 6, day = 14}
for i = 1970, 2000 do
aux.year = i;
t[i] = os.time(aux)
end
再利用のもう一つの方法は、計算をキャッシュして、その後の計算の繰り返しを避けることです。同じ状況に遭遇した場合は、直接テーブルをチェックして取り出すことができます。このアプローチは、実はダイナミックプランニング法の高効率の理由であり、その本質は空間を時間に利用することです。
Recycling
Luaには独自のゴミコレクターが搭載されているので、通常、ゴミ収集について考える必要はありません。
Luaのゴミコレクションを理解することで、プログラミングの自由度が高まります。
Luaのゴミコレクターは、インクリメンタルに動作するメカニズムです。つまり、リサイクルは多くの小さなステップに分割されます。
頻繁なゴミ収集は、プログラムの運営効率を低下させる可能性があります。
ゴミ収集機はLuaの関数で制御できます。
関数には、ゴミ収集の停止、ゴミ収集の再開、リサイクルサイクルの強制、ゴミ収集の1ステップの強制、Luaが占有するメモリの取得、ゴミ収集の頻度とステップサイズに影響する2つのパラメータがあります。
Luaのバッチプログラムでは、ゴミ箱回収を停止することで、バッチプログラムのメモリが全て解放されるため、効率が上がります。
ゴミ収集のペースについて一般化するのは難しいです。ゴミ収集の大きさを速くすると、CPUの消費量は増えますが、メモリはより多く解放され、CPUのページング時間も短縮されます。どちらがよいかは、注意深く実験してみなければわかりません。
まとめ
高水準のコードを書くべきで、後から最適化するのは避けるべきです。
実際にパフォーマンスに問題がある場合、ツールを使って効率を定量化し、ボトルネックを見つけて、それに対して最適化する必要があります。もちろん最適化した後は、最適化が成功したかどうかを確認するために再度測定する必要があります。
最適化では、コードの可読性と動作効率、CPUとメモリ、メモリとCPUなど、さまざまな選択を迫られます。最終的なバランスポイントを見つけるには、実際の状況に応じて実験を続ける必要があります。
*** 武器を2つ持って：
使用することで、コードを修正することなく、平均約5倍のスピードアップが可能です。ご確認ください。
次に、ボトルネックとなる部分をC/C++で記述します。LuaとCは自然に近いため、LuaとCを混ぜてプログラミングすることが可能になります。しかし、CとLuaの間のコミュニケーションは、Cがもたらす利点のいくつかを打ち消してしまいます。
LuaのコードをC言語で書き換えれば書き換えるほど、LuaJITによる最適化は減少します。
免責事項
ロベルトさん、Luaでの努力と献身に感謝します！
