1

次のドキュメントの 4 ～ 5 ページ:

http://www.open-std.org/jtc1/sc22/wg21/docs/ESC_Boston_01_304_paper.pdf

typedef int (* jumpfnct)(void * param); 
static int CaseError(void * param) 
{ 
  return -1; 
} 
static jumpfnct const jumptable[] = 
{ 
  CaseError, CaseError, ... 
  . 
  . 
  . 
  Case44,    CaseError, ... 
  . 
  . 
  . 
  CaseError, Case255 
}; 
  result = index <= 0xFF ? jumptable[index](param) : -1;

IF-ELSE と SWITCH を比較してから、この「ジャンプ テーブル」を紹介します。どうやらこれは 3 つの中で最速の実装です。正確には何ですか？どのように機能するのかわかりませんか??

4

5 に答える 5

3

jumptable は、入力整数をアクションにマッピングする方法です。これは、入力整数を配列のインデックスとして使用できることに起因します。

このコードは、関数へのポインターの配列を設定します。次に、入力整数を使用して、これらの関数ポインターを選択します。一般的には、関数へのポインタになるようCaseErrorです。ただし、時々指摘されるのは別の機能になります。

そのように設計されています

  jumptable[62] = Case62;
  jumptable[95] = Case95;
  jumptable[35] = Case35;
  jumptable[34] = CaseError; /* For example... and so it goes on */

したがって、呼び出す正しい関数を選択するのは一定の時間です... if-else と select を使用すると、正しい関数を選択するのにかかる時間は入力整数に依存します...コンパイラが選択を最適化しないと仮定するとjumptable 自体... 埋め込みコード用の場合、この種の最適化が無効になっている可能性があります...確認する必要があります。

正しい関数ポインターが見つかったら、最後の行でそれを呼び出します。

result = index <= 0xFF ? jumptable[index](param) : -1;

になる

result = index <= 0xFF  /* Check that the index is within
                           the range of the jump table */

         ? jumptable[index](param) /* jumptable[index] selects a function
                                      then it gets called with (param) */

         : -1; /* If the index is out of range, set result to be -1
                  Personally, I think a better choice would be to call
                  CaseError(param) here */
于 2012-12-21T23:46:57.603 に答える
2

Jumpfnct は関数へのポインタです。Jumptable は、多数の jumpfnct で構成される配列です。関数は、配列内の位置を参照するだけで呼び出すことができます。

たとえば、jumptable0 は最初の関数を実行し、param を渡します。jumptable1 は 2 番目の関数を実行します。

関数ポインターについて知らない場合は、このトリックを使用しないでください。狭い領域では非常に便利です。

多数の同様の関数呼び出しを切り替えている場合、非常に高速でスペース効率が高くなります。switch ステートメントが必ずしも持つとは限らない関数呼び出しのオーバーヘッドを追加しているため、すべての状況で適切であるとは限りません。コードが次のような場合:

switch(x) {
  case 1:
    function1();
    break;
  case 2:
    function2();
    break;
...
}

ジャンプ台は良い代替品かもしれません。ただし、スイッチが次のような場合:

switch(x) {
  case 1:
    y++;
    break;
  case 1023:
    y--;
    break;
...
}

おそらくやる価値はないでしょう。

私はおもちゃの FORTH 言語インタープリターでそれらを使用しましたが、非常に価値がありましたが、ほとんどの場合、使用する価値のある速度の利点は見られません。最適化のためではなく、プログラムのロジックをより明確にする場合に使用してください。

于 2012-12-21T23:58:26.510 に答える
1

ジャンプ テーブルは明らかですが、めったに使用されない最適化であり、何らかの理由で支持されなくなったようです。

簡単に言えば、値をテストして switch/case または if-else ブロックを終了して関数またはコード パスに分岐する代わりに、プログラムが分岐できる関数のアドレスで埋められた配列を作成します。

完了すると、この配置により、if-else および switch/case ブロックを使用した執拗な if テスト アテンダントが排除されます。このコードは、そうでなければ if でテストされる変数を関数ポインター配列の添字として使用し、適切なコード (sans ANY if testing) に直接進みます。完全に効率的なブランチ。アセンブリ コードは文字通りジャンプである必要があります。

コードをプロファイリングし、プログラムが時間の大部分を費やしているホットスポットを見つけた場合は、パフォーマンスを改善するためにこの種の最適化を検討してください。これがコードのホットスポットの一部である場合、このほんの少しが大いに役立ちます。

リンクをありがとう。いい発見！

于 2012-12-22T00:00:25.187 に答える
1

この jumptable は、そのインデックスによって関数へのポインターを返します。無効なインデックスが無効なコード (例の -1 など) を返す関数を指し、有効なインデックスが呼び出す必要のある関数を指すように、このテーブルを定義します。

工事

jumptable[index]

関数へのポインタを返し、この関数が呼び出されます

jumptable[index](param)

paramカスタムパラメータはどこにありますか。

于 2012-12-21T23:45:33.950 に答える
0

上記のコメントで述べたように、このソリューションがたとえば switch ステートメントよりも効率的かどうかは、各ケースで実行する必要がある作業量によって異なります。

処理したい値に対して通常の switch ステートメントを記述すると、コードが何をするかを確認するためのより明確な方法になります。したがって、スペースまたは速度の要件によってより洗練されたソリューションが必要とされない限り、これは「より良い」ソリューションではないことをお勧めします。

ただし、関数ポインターのテーブルは、特定の問題を解決するための効率的で優れた方法です。私はテーブルで関数ポインターをかなり定期的に使用して、「問題に対するベンチマーク 11 の異なるソリューション」のようなことを行います。ここでは、関数の名前と関数、およびおそらくいくつかのパラメーターを含む構造体があります。次に、時間を計ってコードを数百万回ループする関数が 1 つあります (または、意味をなすのに十分な長さの測定値を取得するのに必要なものは何でも)。

于 2012-12-21T23:55:50.727 に答える