コードの最適化について詳しく解説

コンピューター プログラミングにおける最適化とは、一般に関数の実行時間、データとプログラムが占めるスペース、または消費電力を削減することです。

最適化の第一のルールは、プログラムが動作し、機能仕様を満たした場合にのみ最適化を行うべきであるということです。経験によれば、これら 2 つの条件が満たされる前にコードに低レベルの最適化を適用すると、ほとんどの場合時間の無駄が発生し、コードの明瞭さとプログラムの適切な機能に悪影響を及ぼします。

「時期尚早の最適化は諸悪の根源である」とドナルド・クヌースはダイクストラの言葉を引用した。

ただし、この切り詰められた引用は誤解されることがよくあります。完全版は次のとおりです。

「私たちは小さな効率のことは忘れるべきです。97% の確率で、時期尚早な最適化が諸悪の根源です。)」、ドナルド・クヌース

元の引用では、このルールはローカルの低レベルの最適化 (アセンブラでの書き換え、ループの展開など) にのみ適用されるべきであり、プロジェクトのアルゴリズムやアーキテクチャの選択に関する高レベルの最適化には適用されないことが非常に明確に示されています。それどころか、プロジェクトが大規模になるほど、これらの高レベルの最適化を実行することは、不可能ではないにしても、より困難でより高価になります (時間、難易度、予算の点で)。

最新のコンパイラは、手動で実行すると面倒でソース コードが読みにくくなる、一定数の最適化を自動的に実行します。

非常に特殊なケースでは、ローカルの手動による最適化が必要になる場合がありますが、測定によると、多数のレジスタがあり、パイプライン効果の恩恵を受けるために効率を高めるために同一の命令をグループ化する必要がある RISC マシンでは、Cコンパイラのオプティマイザがより多くの機能を提供することがよくあります。経験豊富なプログラマがアセンブリで作成するコードよりも効率的なコードになります (CISC マシンでは決してそうではありませんでした)。さらに、このコードは保守がはるかに簡単です。C の命令は、マシンの特性ではなく、コードのわかりやすさのみに関連付けられた順序のままであるためです。実際、現在のオプティマイザーでは、マシンの順序は、実行効率の理由から、命令は必ずしも連続した位置にある必要はありません。これにより、生成されたアセンブリ コードが特に解読不能になります。

最適化の実践

最初のアプローチ

最適化を始める前に、コードの速度を測定する方法を知っておく必要があります。これを行うには、パラメータ、できれば単純で測定可能なパラメータを選択する必要があります。これは、たとえば、特定のデータセットの処理時間、 1 秒あたりに表示される画像の数、さらには1 分あたりに処理されるリクエストの数などです。

測定パラメータが決定されたら、プログラムの各部分に費やされた時間を測定する必要があります。時間の 80% ～ 90% がコードの 10% (クリティカル ループ) の実行に費やされることも珍しくありません。数字はプロジェクトの規模と複雑さによって異なります。最適化で最大の利益を得るには、コードの 10% をローカライズする必要があります。このローカリゼーション手順は、プロファイラーと呼ばれる特殊なコード計測ツールを使用して実行できます。これらは、各関数の実行数と、実行中の対応するマイクロプロセッササイクルをカウントする責任があります。

次に、最も多くのリソースを消費するセクションを必要なだけ繰り返します。

• コードの一部の最適化
• パフォーマンスの向上の測定

2 番目のアプローチ

プログラムはいくつかのレベルで最適化できます。

• アルゴリズムレベルでは、(数学的な意味で) より複雑性の低いアルゴリズムと適切なデータ構造を選択することで、
• 開発言語レベルでは、可能な限り最適な命令を並べ、利用可能なライブラリを使用することで、
• 低レベル言語(C 言語、または最も重要なニーズの場合はアセンブリ言語) をローカルで使用します。

レベルの可能性を使い果たした場合にのみ、次の最適化レベルに移行します。速度を上げるためにプロジェクト全体で低レベル言語を使用することは、産業プロジェクトが犯す可能性のある最も一般的でコストのかかる間違いの 1 つです。

コードの最適化は、多くのアマチュア開発者にとって、やや魔法のような技術であると考えられており、このため、プログラミングの最もエキサイティングな部分の 1 つであると考えられています。このため、優れたプログラマとはプログラムを最初から最適化する人であると信じ込まされてしまいます。ただし、経験上、初期設計が不十分であることは克服できないことがわかっています。開発者の経験が最も大きく影響するのは設計です。さらに、多くの場合、そしてますます多くの場合、「優れたプログラマ」とは、賢いコードを書く人ではなく（オプティマイザの方がほとんどの場合、彼よりも優れたコードを作成します）、読みやすく使いやすいコードを書く人です。維持する。

データ構造技術やアルゴリズムに関する十分な知識は (アルゴリズムの複雑さに関する高度な理論的考察まで行かなくても) アセンブリ言語の知識よりもはるかに有益です。最適なアルゴリズムが決定したら、次のパスを使用して最も効率的な最適化を行うことができます。

• 高級言語(Scheme や Common Lisp など) で重要なコードを作成する
• リソース消費を削減しながらプログラム仕様を維持する連続的な数学的変換の適用、
• 変換されたコードを低水準言語 (C 言語) に翻訳します。

実際には、現在のマシンのパフォーマンスは、入出力が遅いアプリケーションがこれら 3 つのステップを回避し、Haskell のような言語で直接作成できることを意味します。 Usenet フォーラムで公開された画像を体系的に収集するよく知られたngetアプリケーションは、最初の実装では Haskell で書かれていました。 C バージョンは単なる翻訳であり、このタイプのアプリケーションにとってより効率的であるとは証明されていません。一方、主に CPU とメモリ速度によって制限されるアプリケーションは、C や C++ などの言語で作成すると大きなメリットが得られます。

自動最適化

コンパイラーは多くの場合、ローカルな最適化を行うことができますが、これを一見した開発者は誰も思いつきません。

C 言語の場合、次のことが考慮されます。

• ローカル変数とレジスタ
• アセンブラに関数として実装されていない関数
• 最適なスイッチ。

ただし、可能な場合は const キーワードや replace キーワードを使用して変数を宣言することで、コンパイラを大幅に支援できます。そうしないと、コンパイラはメモリ領域が他の参照からアクセス可能かどうかを知ることができず、最適化が無効になります (メモリ エイリアシングとして知られる現象)。

例

ローカル変数を使用してメモリのエイリアシングを回避する

次の C++ コードは、ループ コードが反復カウンターを変更するかどうか (ポインターまたは参照によって変更される可能性がある) を認識できないことが多いため、一般にコンパイラーによる最適化が不十分になります。

void MyClass::DoSomething() const
{
for(int i=0; i< m_nbrElements ; ++i)
{
void *ptr = GetSomePtr();
....
}
}

このバージョンでは、事前に固定され決して変更されない反復回数を使用することを明確に示し、コンパイラーがより積極的な最適化を実行できるようにします。

void MyClass::DoSomething()
{
const int numElements = m_nbrElements;
for( int i=0; i< nbrElements ; ++i )
{
....
}
}

バイナリの特殊性: シフト

非常に最初の最適化の 1 つは、2 の累乗による除算と乗算でした。

実際、電流計算は2 進数に基づいています。これは、2 つの異なる値しか許容しない基本要素としてトランジスタ (および歴史的には以前はリレー) を使用しているためです。

そこで、左シフト演算と右シフト演算を機械語で論理的に実装しました。

実際、2 進数では、数値を 1 ステップ左にシフトすると、2 倍になります。

したがって、2 (10 ₂ ) を 1ビットシフトすると 4 (100 ₂ ) になります。

5 (101 ₂ ) を 2 ビットシフトすると 20 (10100 ₂ ) になります: 5 * 2 ² = 20 。

これは、ビットを右にシフトすることにより、除算にも機能します。

100 (1100100 ₂ ) を右に 3 ビットシフトすると、100 / 2 ³ = 12.5になります。整数を扱うため、12 (1100 ₂ ) となります。

除算は (この場合と病的な場合を除いて) マシンタイムにコストのかかる命令であり、大多数の RISC タイプのプロセッサではまだ利用できません。

Cのインラインキーワード

次の C コード:

インラインint f(int a, int b) {
a * b を返します。
}
int g (int a) {
スイッチ(a) {
ボックス10:
f(a, a)を返します。
ボックス11:
ボックス12:
f(a - 2, a)を返します。
ボックス1200:
f(a - 2, a)を返します。
デフォルト：
f(a, a)を返します。
}
}

gcc -O4 -S でコンパイルすると次のようになります。

.file "opt.c"
。文章
.p2align 4,,15
.globl g
.type g、@function
g:
プッシュl %ebp
movl %esp、%ebp
movl 8(%ebp)、%edx
cmpl $12、%edx
jg.L14
leal -2(%edx)、%eax
cmpl $11、%edx
じげ.L15
movl $100、%eax
cmpl $10、%edx
.L17:
I .L2
movl %edx、%eax
.L15:
imull %edx、%eax
.L2:
ポップル%ebp
レット
.p2align 4,,7
.L14:
movl $1437600、%eax
cmpl $1200、%edx
jmp .L17
.size g、.-g
.section .note.GNU-stack,"",@progbits
.ident "GCC: (GNU) 3.3.2 (Mandrake Linux 10.0 3.3.2-6mdk)"

これを理解しやすくするために、次の C コードに変換できます。

int g(int a) {
int eax、b;
if (a > 12) /* case a == 1200 */
gotoL14 ;
eax = a - 2;
if (a >= 11) /* a == 11 または a == 12 の場合 */
gotoL15;
eax=100; /* = 10 * 10 */
b=10;
L17:
if (a == b) /* case a == 10 */
gotoL2;
/* 「デフォルト」の場合 */
eax=a;
L15:
eax=eax*a;
L2:
eax を返します。
L14:
eax = 1437600; /* = 1200*(1200-2) */
b = 1200;
gotoL17;
}

たとえば、関数 ‘f’ は生成されませんでしたが、そのコードが関数 ‘g’ に直接組み込まれたことがわかります (キーワード ‘inline’ を使用すると、C でこのタイプの最適化を強制できます)。