7

簡単な質問があります。たとえば、次のコードがあり、同じように10回繰り返されたとします。

if blah then
    number = number + 2^n
end if

評価する方が速いでしょうか：

number = number + blah*2^n?

これも問題を引き起こしますが、ブール値に整数を掛けることができますか（2 ^ nから返される型はわかりませんが、整数か符号なしなど）？（私はエイダで働いていますが、これを一般化してみましょう。）

編集：申し訳ありませんが、私は2のn乗を見ていることを明確にする必要があります。cでこの問題に遭遇した場合、将来自分の学習に興味があったので、そこにcを入れました。これらのボードにいるプログラマー、次にAda（私は推測していて、それが何を意味するのか知っています）、しかし私の現在の問題はAda言語にありますが、質問はかなり言語に依存しないはずです（私は願っています）。

4

10 に答える 10

10

このような質問に対する一般的な答えはありません。これはコンパイラとCPUに大きく依存します。最新のCPUには条件付き移動命令があるため、すべてが可能です。

ここで知る唯一の方法は、（通常-Sはコンパイラオプションとして）生成されたアセンブラを検査して測定することです。

于 2010-10-26T13:45:53.103 に答える
7

C について話していて、どうしようもない場合は、次のようにします。

if(何とか) 数 += (1<<n);

Cには実際にはブール値はなく、そうである必要もありません。falseはゼロで、trueはゼロではないため、ソリューションに必要なゼロではない1であると仮定することはできません。また、特定の何とかビットが設定されています。たとえば、次のようになります。

number += (何とか&1)<<n;

0x2 または 0x4、またはビット 0 をクリアしたゼロ以外のものは true と見なされるため、必ずしも機能するとは限りません。通常、0xFFF...FFFF (マイナス 1、またはすべて 1) が true として使用されますが、標準に依存することはできません。

さて、あなたが何とかの値を完全に制御していて、それを厳密に false の場合は 0 に、true の場合は 1 に保つ場合、あなたが求めていたことを行うことができます:

number += 何とか <<n;

また、分岐、余分なキャッシュ ライン フィルなどの可能性を回避します。

ただし、一般的なケースに戻り、次の一般的なソリューションを採用します。

unsigned int fun ( int blah, unsigned int n, unsigned int number )
{
    if(何とか) 数 += (1<<n);
    戻り値 (数値);
}

そして、最も一般的/使用されている 2 つのプラットフォーム用にコンパイルします。

    testl %edi, %edi
    movl %edx, %eax
    ジェ.L2
    移動 $1、%edx
    movl %esi, %ecx
    %cl、%edx を販売
    addl %edx, %eax
.L2:

上記は条件分岐を使用しています。

以下は条件付き実行を使用し、分岐もパイプライン フラッシュも決定論的ではありません。

  cmp r0,#0
  ムーヴネr3,#1
  addne r2、r2、r3、asl r1
  移動r0、r2
  bx lr

関数呼び出しで引数を再配置することで mov r0,r2 命令を保存できたかもしれませんが、それは学術的なことであり、通常はこれで関数呼び出しを焼き付けることはありません。

編集：

提案どおり：

unsigned int fun ( int blah, unsigned int n, unsigned int number )
{
    数値 += ((何とか!=0)&1)<<n;
    戻り値 (数値);
}

  サブ r0、r0、#0
  移動 r0、#1
  r0、r2、r0、asl r1 を追加
  bx lr

確かに安価で、コードは見栄えがしますが、blah!=0 の結果 (ゼロまたはコンパイラーが true と定義したもの) には常に lsbit が設定されているとは思いません。コンパイラが動作するコードを生成するためにそのビットを設定する必要はありません。おそらく、標準が true の特定の値を指示しているのでしょう。関数パラメーターを再配置することにより、 if(blah) number +=... も3つの単一クロック命令になり、仮定はありません。

EDIT2：

C99標準であると私が理解しているものを見ると：

== (等しい) および != (等しくない) 演算子は、優先順位が低いことを除いて関係演算子に似ています。各演算子は、指定されたリレーションが true の場合は 1 を返し、false の場合は 0 を返します。

これは、上記の編集が機能する理由と、他の乱数ではなく movne r0,#1 を取得する理由を説明しています。

投稿者は C に関して質問をしていましたが、ADA が現在の言語であることにも言及しました。言語に依存しない観点から、上記の C 機能のような「機能」を想定して、if(blah) 数値 = 数値 + (1 <<n)。しかし、これはCタグで尋ねられたので、一般的に（プロセッサに依存しない）Cの最速の結果は、 number += (blah!=0)<<n; だと思います。したがって、Steven Wright のコメントは正しかったので、彼の功績は認められるべきです。

ポスターの仮定も基本的に正しいです。何とか0または1の形式にできる場合は、分岐がないという意味で数学でそれを使用する方が高速です。ブランチよりもコストがかからずにその形にするのがコツです。

于 2010-10-27T14:18:51.197 に答える
5

エイダで…

元の処方：

if Blah then
  Number := Number + (2 ** N);
end if;

Blah が Boolean 型で Number と N が適切な型であると仮定すると、代替の一般的な定式化が行われます。

Number := Number + (Boolean'pos(Blah) * (2 ** N));

（ユーザー定義の整数型または浮動小数点型についてはN、Number適切な定義と型変換が必要になる場合があります。ここでの重要なポイントはBoolean'pos()、定義済みのブール型に対して Ada が保証する構造です。）

これが速いかどうかについては、@Cthutu に同意します。

私はそれを条件付きで保持します。この時点では、低レベルの最適化の詳細について心配する必要はありません。アルゴリズムを最もよく表すコードを記述し、コンパイラを信頼してください。

于 2010-10-26T14:18:46.867 に答える
4

私はそれを条件付きで保持します。この時点では、低レベルの最適化の詳細について心配する必要はありません。アルゴリズムを最もよく表すコードを記述し、コンパイラを信頼してください。一部の CPU では、乗算が遅くなります (たとえば、各命令に条件がある ARM プロセッサ)。一部のコンパイラでより適切に最適化される ?: 式を使用することもできます。例えば：

number += (blah ? 2^n : 0);

なんらかの理由で、プロファイリング後にこの小さな計算がアプリケーションのボトルネックになっている場合は、低レベルの最適化について心配してください。

于 2010-10-26T13:47:54.057 に答える
4

C では、blah*2^n について: blah が値 0 と 1 を取ると信じる理由はありますか? この言語は、0 <-> FALSE および (その他すべて) <-> TRUE を約束するだけです。C では、一時的な「ブール値」に別の数値を掛けることができますが、result=0 <=> ブール値が false であるか数値がゼロである場合を除いて、結果は定義されません。

Ada では、blah*2^n に関して: 言語はブール型の乗算演算子を定義していません。したがって、blah を bool にして乗算することはできません。

于 2010-10-26T13:50:01.090 に答える
1

あなたの言語がブール値と数値の間の乗算を許可している場合、そうです、それは条件付きよりも高速です。条件文には分岐が必要であり、CPUのパイプラインが無効になる可能性があります。また、ブランチが十分に大きい場合、それは命令でキャッシュミスを引き起こす可能性さえありますが、それはあなたの小さな例ではありそうにありません。

于 2010-10-26T13:41:24.243 に答える
1

一般的に、特に Ada を使用する場合は、このようなマイクロ最適化の問題について心配する必要はありません。読み手にわかりやすいようにコードを書き、パフォーマンスに問題がある場合にのみパフォーマンスについて心配し、コードのその部分まで追跡します。

CPU が異なればニーズも異なり、非常に複雑になる可能性があります。たとえば、この場合、どちらが速いかは、CPU のパイプライン設定、その時点でキャッシュにあるもの、およびその分岐予測ユニットがどのように機能するかに大きく依存します。コンパイラの仕事の一部は、これらの専門家になることであり、最高のアセンブリ プログラマ以外のすべてのプログラマよりも優れた仕事をします。あなた（または私）よりも確実に優れています。

したがって、良いコードを書くことだけを考えて、そこから効率的なマシン コードを作成することをコンパイラに任せればよいのです。

于 2010-10-26T14:38:58.103 に答える
0

どちらの場合でも、(内部的に) 分岐を回避することはできないため、試みないでください。

の

number = number + blah*2^n

コンパイラが blah が 0 のときに停止するほどスマートでない限り、完全な式を常に評価する必要があります。そうであれば、blah が 0 の場合に分岐が発生します。そうでない場合は、常に高価な乗算が行われます。何とかfalseの場合、不要な追加と割り当ても取得します。

「if then」ステートメントでは、blah が true の場合にのみステートメントが追加と代入を行います。

つまり、この場合の質問に対する答えは「はい」です。

于 2010-10-26T13:55:33.223 に答える