5

最適化に関する私の (限られた) 知識に関する限り、私は常に、コンパイラーの最適化はそれほど重要ではないと考えていました。つまり、メモリーの代わりにレジスターを使用してループをアンローリングすることで、かなりの数パーセント (非常に大まかな概算としては 0...100% かもしれません) の時間を確かに得ることができますが、コードのパフォーマンスを制約する基本的な要因は実際にはアルゴリズムの選択。

私は最近、小さなインタープリター型スクリプト言語であるペット プロジェクトを開始しました。バイトコードにコンパイルし、仮想マシンを使用して実行します。デバッグ、プロファイリング、およびテストを容易にするために、最初に(および) の-O0 -gフラグを使用してコードを自然にコンパイルし、次に. 次に、VM 上で実行する小さなプログラムを作成しました。これは基本的にこれを行います (疑似コード、プロジェクトが公開されるまで実際の構文は示しません)。gccclang-O2time

i = 1
sum = 0

while (i < 10000000) {
    sum = (sum + i * i) mod 1000000
    i++
}

print sum

これは、大まかに次の疑似アセンブリに変換されます。

load r0, 0   # sum = 0
load r1, 1   # i = 1
load r2, 1000000
load r3, 10000000

loop:
mul  r4, r1, r1 # i * i
add  r0, r0, r4 # sum += i * i
mod  r0, r0, r2 # sum %= 1000000
inc  r1
gt   r5, r1, r3 # if i > 10000000
jz   r5, loop   # then don't goto loop

ret  r0

基本的に、これは 10000000 回の反復を伴うタイトなループです。でコンパイルした場合は 0.47...0.52 秒、 でコンパイルした場合は 1.51...1.74 秒、プロファイリング ( ) が有効な場合は 3.16...3.47 秒timeで実行されることが報告されています。-O2-O0 -g-pg

ご覧のとおり、最速の実行時間と最も遅い実行時間の間には 7 倍の差があります。

これ自体はそれほど驚くべきことではありません。なぜなら、追加のデバッグ情報と小さな最適化の欠如が実際にコードの実行を遅くすることを知っていたからです。実際に何が起こるかをより現実的に理解するために、Lua 5.2 で同じゲームをプレイしました。をいじってみるMakefileと、まったく同じ Lua プログラムであることがわかりました。

local sum = 0

for i = 1, 10000000 do
    sum = (sum + i * i) % 1000000
end

print(sum)

Lua を でコンパイルすると約 0.8...0.87 秒、 onlyを有効-O0 -g -pgにすると 0.39...0.43 秒で実行されます。-O2

そのため、オプティマイザーがトリッキーな修正を実行すると、コードの速度が 7 倍に向上したように見えますが、Lua リファレンス実装では、これらの改善によるメリットははるかに少ないようです。

今私の質問は次のとおりです。

  1. なぜこれが起こるのか分かりますか？その主な理由は、Lua の作成者が私より頭が良く、コンパイラとその VM が何をしているかをよく知っているからだと思います。

  2. また、「これは時期尚早の最適化に違いない。オプティマイザーに渡してみましょう。とにかく仕事をしてくれる」と何度か考えていることに気づきました。これらには、ほぼすべての VM 命令の実装で呼び出される 1 行の静的関数 (必要に応じてインライン化されると思っていました)、さまざまな複雑な式の使用 (予測が容易ではない副作用を伴う場合もあります) が含まれます。ただし、それは単純化できます。私のこの態度も重要ですか？（ちなみに、それは正しい態度ですか？）

  3. とにかく、この現象についてまったく心配する必要がありますか？結局、私のコードは Lua よりも 1.5​​ 倍遅く実行されます。これはかなり良いことです (少なくとも、私にとっては十分です)。デバッグ ビルドのパフォーマンスを改善しようとする必要があるのは、自分のコードに関する詳細な知識が不足していることを示しているからです。それとも、リリース (最適化) ビルドが十分に高速である限り、完全に忘れてもいいですか?

(この質問が Prog.SE または CodeReview に適している場合は、お知らせください。移行します。)

4

1 に答える 1

1

Firstly, your assertion that the algorithm is more important than the optimizations is generally true, but the same algorithm can be coded to make best or worst use of the platform you are executing on, so optimizations should always be considered... just avoid optimising prematurely, instead of avoiding optimising at all.

Next, remember that debug builds add a lot of overhead. Much more than merely disabling optimisation. To see what the optimiser is doing, use a release build with optimizations disabled.

The differences between Lua and your language will be due to the efficiency of your bytecode interpreter. A tiny inefficiency in here will have a massive effect on the speed of execution of such a large loop. you might also be able to add optimizations such as:

  • using "registers" to hold the variables used within the loop (in the byte code, load the variable into slot 1, then use new instructions that multiply and mod the slots using a simple array index rather than a named variable, then write the final value of the slot back to the variable at the end of the loop.
  • detecting that the loop executes a constant number of times, perhaps there is a way you can express this in byecode so that the loop variable and logic is executed by native code rather than by interpreting bytecode. You can obviously add special cases for lots of situations, so the trick here is to work out the most common constructs and optimise those first, to get the biggest bang for your buck.

Lastly, don't worry about the efficiency of your debug code. When you have a working interpreter, then you can profile a release build to look for areas that you can improve. Doing this prematurely will not help, as there is no point optimising partially complete code and then finding out that it needs to be changed to support a new feature. And it's only when you have a working system that you can start writing typical scripts that will exercise your interpreter in a realistic manner - you may find that optimising a loop like the example above yields no benefit in day to day scripts.

于 2013-09-01T10:41:56.113 に答える