c - Cプログラムを最適化するためにどのようなコーディング手法を使用していますか？

Question

数年前、私は比較的上級の組み込みCプログラマーのポジションの候補者にインタビューしているパネルにいました。

私が尋ねた標準的な質問の1つは、最適化手法についてでした。候補者の中には答えがなかったので、とても驚きました。

では、後世のためのリストをまとめるために、Cプログラムを最適化するときに通常使用する手法と構成は何ですか？

速度とサイズの両方の最適化に対する回答が受け入れられました。

score 40 · Accepted Answer

まず最初に-あまりにも早く最適化しないでください。コードのチャンクを注意深く最適化することに時間を費やして、それが予定されていると思っていたボトルネックではないことを見つけることは珍しくありません。または、別の言い方をすれば、「速くする前に、機能させる」ということです。

コードを最適化する前に、アルゴリズムを最適化するためのオプションがあるかどうかを調べてください。コードを最適化するよりも、貧弱なアルゴリズムを最適化することでパフォーマンスの向上を見つける方が簡単です。その後、アルゴリズムを変更したときにコードを破棄するだけです。

そして、そもそもなぜ最適化する必要があるのかを理解してください。何を達成しようとしていますか？たとえば、あるイベントへの応答時間を改善しようとしている場合、タイムクリティカルな領域を最小限に抑えるために実行の順序を変更する機会があるかどうかを確認します。たとえば、外部割り込みへの応答を改善しようとする場合、イベント間のデッドタイムに準備をすることができますか？

コードを最適化する必要があると判断したら、どのビットを最適化しますか？プロファイラーを使用します。最も頻繁に使用される領域に（最初に）注意を向けます。

では、それらの領域について何ができるでしょうか。

状態チェックを最小限に抑えます。条件のチェック（ループの終了条件など）は、実際の処理に費やされていない時間です。ループ展開などの手法を使用すると、条件チェックを最小限に抑えることができます。
状況によっては、関数ポインタを使用して条件チェックを排除することもできます。たとえば、ステートマシンを実装している場合、個々の状態のハンドラーを小さな関数として（均一なプロトタイプで）実装し、次のハンドラーの関数ポインターを格納することで「次の状態」を格納する方が、個々のcaseステートメントに実装されたハンドラーコードを含む大きなswitchステートメント。YMMV。
関数呼び出しを最小限に抑えます。関数呼び出しは通常、コンテキスト保存の負担を伴います（たとえば、レジスターに含まれるローカル変数をスタックに書き込む、スタックポインターを保存する）。したがって、呼び出しを行う必要がない場合、これは時間の節約になります。1つのオプション（スペースではなく速度を最適化する場合）は、インライン関数を使用することです。
関数呼び出しが避けられない場合は、関数に渡されるデータを最小限に抑えてください。たとえば、ポインタを渡す方が構造体を渡すよりも効率的である可能性があります。
速度を最適化するときは、プラットフォームのネイティブサイズであるデータ型を選択してください。たとえば、32ビットプロセッサでは、8ビットまたは16ビットの値よりも32ビットの値を操作する方が効率的である可能性があります。（補足-コンパイラがあなたが思っていることを実行していることを確認する価値があります。私のコンパイラがすべてのtoおよびfrom変換で8ビット値に対して16ビット演算を実行することを主張していることに気付いた状況がありました。彼らと一緒に行く）
事前に計算できるデータを見つけて、初期化中に計算するか、（さらに良いことに）コンパイル時に計算します。たとえば、CRCを実装する場合、CRC値をその場で（多項式を直接使用して）計算することができます。これはサイズに最適です（ただし、パフォーマンスには恐ろしいです）。または、すべての中間値のテーブルを生成できます。これは、サイズを犠牲にして、はるかに高速な実装。
データをローカライズします。データのブロブを操作している場合、プロセッサはすべてをキャッシュに保存することで処理速度を上げることができる場合があります。また、コンパイラは、よりローカライズされたデータに適した短い命令を使用できる場合があります（たとえば、32ビットではなく8ビットオフセットを使用する命令）。
同じように、機能をローカライズします。同じ理由で。
実行している操作について行うことができる仮定を理解し、それらを活用する方法を見つけます。たとえば、8ビットプラットフォームで、32ビット値で実行している唯一の操作が増分である場合、この目的のために特別にインライン化（またはマクロを作成）することで、コンパイラよりも優れた処理を実行できることがわかります。通常の算術演算を使用するのではなく。
高価な指示は避けてください-除算はその代表的な例です。
「register」キーワードはあなたの友達になることができます（ただし、コンパイラーがレジスターの使用法についてかなり良い考えを持っていることを願っています）。「登録」を使用する場合は、最初に「登録」するローカル変数を宣言する必要がある可能性があります。
データ型と一致している。データ型の混合（たとえば、shortsとints、doublesとfloats）で算術演算を実行している場合、コンパイラーは不一致ごとに暗黙の型変換を追加しています。これは、不要なCPUサイクルの無駄です。

上記のオプションのほとんどは、悪影響を与えることなく通常の練習の一部として使用できます。ただし、実際に最高のパフォーマンスを発揮しようとしている場合は、次のようにします。-エラーチェックを（安全に）無効にできる場所を調査します。推奨されていませんが、スペースとサイクルを節約できます。-コードの一部をアセンブラーで手作りします。もちろん、これはコードの移植性がなくなったことを意味しますが、それが問題にならない場合は、ここで節約できる可能性があります。ただし、自由に使用できるレジスタへのデータの移動やレジスタからのデータの移動には時間がかかる可能性があることに注意してください（つまり、コンパイラのレジスタ使用量を満たすため）。また、コンパイラはそれ自体でかなり良い仕事をしているはずだということにも注意してください。（もちろん例外もあります）

score 27 · Accepted Answer

他の誰もが言ったように:プロファイル、プロファイルプロファイル。

実際のテクニックについては、まだ言及されていないと思います：

ホットデータとコールドデータの分離: CPU のキャッシュ内にとどまることは非常に重要です。これを行う 1 つの方法は、データ構造を頻繁にアクセスされる (「ホット」) セクションとめったにアクセスされない (「コールド」) セクションに分割することです。

例: 次のような顧客の構造があるとします。

struct Customer
{
    int ID;
    int AccountNumber;
    char Name[128];
    char Address[256];
};

Customer customers[1000];

ここで、ID と AccountNumber には頻繁にアクセスしたいが、名前と住所にはあまりアクセスしたくないと仮定しましょう。あなたがすることは、それを2つに分割することです：

struct CustomerAccount
{
    int ID;
    int AccountNumber;
    CustomerData *pData;
};

struct CustomerData
{
    char Name[128];
    char Address[256];
};

CustomerAccount customers[1000];

このように、「customers」配列をループしている場合、各エントリはわずか 12 バイトであるため、より多くのエントリをキャッシュに収めることができます。レンダリングエンジンの内部ループのような状況に適用できれば、これは大きなメリットとなります。

score 20 · Accepted Answer

私のお気に入りのテクニックは、優れたプロファイラーを使用することです。ボトルネックがどこにあるかを示す良いプロファイルがなければ、トリックやテクニックは役に立ちません。

score 15 · Accepted Answer

私が遭遇した最も一般的なテクニックは次のとおりです。

ループ展開
キャッシュプリフェッチを改善するためのループ最適化（つまり、NxMの特異な操作ではなくMサイクルでNの操作を実行する）
データの調整
インライン関数
手作りのasmスニペット

一般的な推奨事項に関しては、それらのほとんどはすでに鳴らされています：

より良いアルゴを選ぶ
プロファイラーを使用する
20〜30％のパフォーマンス向上が得られない場合は、最適化しないでください

score 8 · Accepted Answer

低レベルの最適化の場合：

ffmpegのSTART_TIMER/STOP_TIMERマクロ（任意のコードを測定するためのクロックレベルの精度）。
もちろん、プロファイリング用のOprofile。
膨大な量の手作業でコーディングされたアセンブリ（x264の/ common /x86ディレクトリでwc-lを実行するだけで、ほとんどのコードがテンプレート化されていることを覚えておいてください）。
一般的に注意深いコーディング。通常は短いコードの方が適しています。
私が書いた64ビットビットストリームライターのようなスマートな低レベルアルゴリズムは、単一のifのみを使用し、elseは使用しません。
明示的なwrite-combining。
Intelのキャッシュライン分割の問題など、プロセッサの重要な奇妙な側面を考慮に入れます。
ロスレスまたはほぼロスレスで早期終了できるケースを見つける。早期終了チェックのコストは、それから得られる速度よりもはるかに低くなります。
中央値の計算など、x86 SIMDユニットにはるかに適したタスクの実際のインラインアセンブリ（MMXサポートのコンパイル時チェックが必要）。

score 5 · Accepted Answer

何よりもまず、より優れた/より高速なアルゴリズムを使用してください。設計上遅いコードを最適化する意味はありません。
速度を最適化するときは、メモリを速度と交換します。事前に計算された値のルックアップテーブル、バイナリツリー、システムコールのより高速なカスタム実装を記述します。
速度をメモリと交換する場合：メモリ内圧縮を使用します

score 4 · Accepted Answer

ヒープの使用は避けてください。同じサイズのオブジェクトには、obstacksまたはpool-allocatorを使用します。寿命の短い小さなものをスタックに置きます。allocaはまだ存在しています。

score 4 · Accepted Answer

4

時期尚早の最適化はすべての悪の根源です！;）

于 2008-09-21T10:21:29.883 に答える

score 4 · Accepted Answer

私のアプリケーションは通常、設計上あまり CPU 時間を必要としないため、ディスク上とメモリ内のバイナリのサイズに注目しています。私が主に行っていることは、静的にサイズ設定された配列を探し、それらを動的に割り当てられたメモリに置き換えることです。後でメモリを解放するという追加の努力に値します。バイナリのサイズを削減するために、コンパイル時に初期化される大きな配列を探し、初期化を実行時に行います。

char buf[1024] = { 0, };
/* becomes: */
char buf[1024];
memset(buf, 0, sizeof(buf));

これにより、バイナリの .DATA セクションから 1024 のゼロバイトが削除され、代わりに実行時にスタック上にバッファーが作成され、ゼロで埋められます。

編集:そうそう、私は物事をキャッシュするのが好きです。これは C 固有のものではありませんが、キャッシュする内容によっては、パフォーマンスが大幅に向上する可能性があります。

PS: リストが完成したらお知らせください。非常に興味があります。;)

score 4 · Accepted Answer

0 との比較は別のより高速なアセンブラコマンドで実装されることが多いため、特にループでは、可能であれば、任意の数値ではなく 0 と比較してください。

たとえば、可能であれば、次のように記述します。

for (i=n; i!=0; --i) { ... }

それ以外の

for (i=0; i!=n; ++i) { ... }

score 3 · Accepted Answer

まとめにくい…

データ構造:
- 用途に応じてデータ構造を分割することは非常に重要です。フロー制御に基づいてアクセスされるデータを保持する構造体をよく見かけます。この状況では、キャッシュの使用率が大幅に低下する可能性があります。
- キャッシュラインサイズとプリフェッチルールを考慮します。
- 構造体のメンバーを並べ替えて、コードからメンバーへの順次アクセスを取得するには
アルゴリズム:
- 時間をかけて問題について考え、正しいアルゴリズムを見つけてください。
- 選択したアルゴリズムの制限を理解してください (10 個の要素をソートするための基数ソート/クイックソートは、最良の選択ではない可能性があります)。
低レベル:
- 最新のプロセッサに関しては、本体が小さいループを展開することはお勧めしません。プロセッサはこれに対して独自の検出メカニズムを提供し、パイプラインのセクション全体を短絡します。
- HW プリフェッチャーを信頼してください。もちろん、データ構造が適切に設計されている場合;)
- L2 キャッシュラインミスに注意してください。
- プロセッサがコアあたりのキャッシュを小さくする傾向にあるため、アプリケーションのローカルワーキングセットを可能な限り減らすようにしてください (C2D はコアあたり最大 3MB を享受しましたが、iCore7 はコアあたり最大 256KB + 8MB をすべてのコアで共有します)。クアッドコアダイ)。

最も重要なこと: 早期に測定する、頻繁に測定し、決して仮定をしない、プロファイラーによって取得されたデータに基づいて思考と最適化を行う ( PTUを使用してください)。

別のヒントとして、パフォーマンスはアプリケーションの成功の鍵であり、設計時に考慮する必要があり、明確なパフォーマンス目標を設定する必要があります。

これは網羅的なものではありませんが、興味深いベースを提供するはずです。

score 3 · Accepted Answer

言及されていない別のこと：

要件を理解する: 発生する可能性が低い、またはまったく発生しない状況に合わせて最適化するのではなく、費用対効果が最も高いことに集中する

score 3 · Accepted Answer

基本/一般:

問題がなければ最適化しないでください。
プラットフォーム/CPU を知る...
…とことん知る
あなたのABIを知る
コンパイラーに最適化を任せて、仕事を手伝ってください。

実際に役立ったいくつかのこと：

サイズ/メモリの選択:

ブール値の格納にビットフィールドを使用する
ユニオンでオーバーレイすることにより、大きなグローバル配列を再利用します（注意してください）

速度を選択します (注意してください):

可能な場合は事前計算されたテーブルを使用する
重要な機能/データを高速メモリに配置
頻繁に使用されるグローバルには専用レジスタを使用する
ゼロまでカウント、ゼロフラグは無料

score 3 · Accepted Answer

最近では、最適化で最も重要なことは次のとおりです。

キャッシュを尊重する - 単純なパターンでメモリにアクセスするようにし、楽しみのためにループを展開しないでください。ポインター追跡が多いデータ構造の代わりに配列を使用すると、少量のデータの場合はおそらく高速になります。そして、大きすぎるものを作らないでください。
待ち時間の回避 - 他の計算がすぐに依存する場合に遅い除算やものを避けるようにしてください。他のメモリアクセスに依存するメモリアクセス (つまり、a[b[c]]) は不適切です。
予測不可能性を回避する - 予測不可能な条件を伴う多数の if/else、またはより多くのレイテンシーを導入する条件は、本当にあなたを混乱させます。ここで役立つ分岐のない数学のトリックはたくさんありますが、レイテンシが増加するため、本当に必要な場合にのみ役立ちます。それ以外の場合は、単純なコードを書くだけで、クレイジーなループ条件はありません。

コードのコピーアンドペースト (ループのアンローリングなど) を含む最適化や、手作業によるループの並べ替えを気にしないでください。通常、コンパイラはこれを実行するよりも優れた仕事をしますが、ほとんどのコンパイラはそれを元に戻すほど賢くありません。

score 2 · Accepted Answer

コード実行のプロファイルを収集すると、そこまでの道のりの50％が得られます。他の50％は、これらのレポートの分析を扱っています。

さらに、GCCまたはVisualC ++を使用する場合は、「プロファイルガイド付き最適化」を使用できます。この場合、コンパイラーは以前の実行から情報を取得し、命令を再スケジュールしてCPUをより高速にします。

score 2 · Accepted Answer

インライン関数！ここでプロファイリングファンに触発されて、私は私のアプリケーションをプロファイリングし、MP3フレームでビットシフトを行う小さな関数を見つけました。これは、私のアプリケーションのすべての関数呼び出しの約90％を実行するので、インラインで作成しました。プログラムは、以前のCPU時間の半分を使用するようになりました。

score 2 · Accepted Answer

私が作業したほとんどの組み込みシステムにはプロファイリングツールがなかったので、プロファイラーを使用すると言うのは良いことですが、あまり実用的ではありません。

速度最適化の最初のルールは- クリティカルパスを見つけることです。
通常、このパスはそれほど長くなく、それほど複雑ではないことがわかります。これを最適化する方法を一般的な方法で言うのは難しいですが、それはあなたが何をしているか、そして何をする力があるかに依存します。たとえば、通常はクリティカルパスでmemcpyを避けたいので、DMAを使用したり最適化したりする必要がありますが、hwにDMAがない場合はどうでしょうか。memcpyの実装が、書き直さない場合に最適かどうかを確認してください。
組み込みでは動的割り当てをまったく使用しないでください。ただし、何らかの理由で使用する場合は、クリティカルパスで使用しないでください。
スレッドの優先順位を正しく整理します。正しいのは本当の問題であり、明らかにシステム固有です。
非常にシンプルなツールを使用して、タイムスタンプとインデックスを格納するボトルネックのシンプルなマクロを分析します。ケースの90％で実行される数は、あなたが時間を費やす場所を見つけることはほとんどありません。
そして最後は、非常に重要なコードレビューです。ほとんどの場合、コードレビュー中のパフォーマンスの問題を非常に効果的な方法で回避します:)

score 2 · Accepted Answer

パフォーマンスを測定します。
現実的で自明でないベンチマークを使用します。「小さな N ではすべてが高速」であることを忘れないでください。
プロファイラーを使用してホットスポットを見つけます。
動的メモリ割り当て、ディスクアクセス、データベースアクセス、ネットワークアクセス、およびユーザー/カーネル遷移の数を減らします。これらはしばしばホットスポットになる傾向があるためです。
パフォーマンスを測定します。

さらに、パフォーマンスを測定する必要があります。

score 2 · Accepted Answer

場合によっては、より多くのスペースと速度のどちらを求めているかを決定する必要があり、ほとんど逆の最適化につながります。たとえば、スペースを最大限に活用するには、#pragma pack(1) などの構造体をパックし、構造体でビットフィールドを使用します。速度を上げるには、プロセッサの設定に合わせてパックし、ビットフィールドを避けます。

もう 1 つのトリックは、realloc を介して配列を拡大するための適切なサイズ変更アルゴリズムを選択することです。または、特定のアプリケーションに基づいて独自のヒープマネージャーを作成することをお勧めします。コンパイラに付属しているものがすべてのアプリケーションにとって最善の解決策であると思い込まないでください。

score 2 · Accepted Answer

If someone doesn't have an answer to that question, it could be they don't know much.

It could also be that they know a lot. I know a lot (IMHO :-), and if I were asked that question, I would be asking you back: Why do you think that's important?

The problem is, any a-priori notions about performance, if they are not informed by a specific situation, are guesses by definition.

I think it is important to know coding techniques for performance, but I think it is even more important to know not to use them, until diagnosis reveals that there is a problem and what it is.

Now I'm going to contradict myself and say, if you do that, you learn how to recognize the design approaches that lead to trouble so you can avoid them, and to a novice, that sounds like premature optimization.

To give you a concrete example, this is a C application that was optimized.

score 1 · Accepted Answer

素晴らしいリスト。上記のリストに記載されていないヒントを 1 つだけ追加します。場合によっては、最小限のコストで大幅な最適化を実現できます。

バイパスリンカー

main.c と lib.c などの 2 つのファイルに分割されたアプリケーションがある場合、多くの場合、\#include "lib.c"main.c に a を追加するだけでリンカを完全にバイパスし、コンパイラの最適化をより効率的に行うことができます。

ファイル間の依存関係を最適化しても同じ効果が得られますが、変更のコストは通常高くなります。

score 0 · Accepted Answer

より効率的なアルゴリズムを使用して最適化することをお勧めします。後付けで行うのではなく、最初からそのようにコーディングすることをお勧めします。コンパイラは、ターゲットプロセッサについてユーザーよりも多くのことを知っているため、小さなことの詳細はコンパイラに任せます。

1 つには、ループを使用して検索することはめったになく、アイテムをハッシュテーブルに追加してから、ハッシュテーブルを使用して結果を検索します。

たとえば、検索する文字列があり、50 個の可能な値があるとします。したがって、50 個の strcmps を実行する代わりに、50 個の文字列すべてをハッシュテーブルに追加し、それぞれに一意の番号を付けます (これを行う必要があるのは 1 回だけです)。次に、ハッシュテーブルでターゲット文字列を検索し、50 個すべてのケース (または関数ポインターを持つ) を持つ 1 つの大きなスイッチを取得します。

一般的な入力セット (css rules など) を使用して検索する場合、高速コードを使用して可能な唯一のソリューションを追跡し、それらを反復して一致を見つけます。一致が得られたら、結果を (キャッシュとして) ハッシュテーブルに保存し、後で同じ入力セットを取得した場合にキャッシュ結果を使用します。

コードを高速化するための主なツールは次のとおりです。

hashtable - 迅速な検索と結果のキャッシュ用

qsort - 私が使用する唯一のソートです

bsp - エリアに基づいて物事を検索するため (地図のレンダリングなど)

c - Cプログラムを最適化するためにどのようなコーディング手法を使用していますか？

23 に答える 23

Related

Reference