8

約 2^26 回実行されるループ内にいくつかの重要な分岐コードがあります。mはランダムであるため、分岐予測は最適ではありません。おそらくビットごとの演算子を使用して、分岐をどのように削除しますか?

bool m;
unsigned int a;
const unsigned int k = ...; // k >= 7
if(a == 0)
    a = (m ? (a+1) : (k));
else if(a == k)
    a = (m ?     0 : (a-1));
else
    a = (m ? (a+1) : (a-1));

によって生成された関連アセンブリは次のgcc -O3とおりです。

.cfi_startproc
movl    4(%esp), %edx
movb    8(%esp), %cl
movl    (%edx), %eax
testl   %eax, %eax
jne L15
cmpb    $1, %cl
sbbl    %eax, %eax
andl    $638, %eax
incl    %eax
movl    %eax, (%edx)
ret
L15:
cmpl    $639, %eax
je  L23
testb   %cl, %cl
jne L24
decl    %eax
movl    %eax, (%edx)
ret
L23:
cmpb    $1, %cl
sbbl    %eax, %eax
andl    $638, %eax
movl    %eax, (%edx)
ret
L24:
incl    %eax
movl    %eax, (%edx)
ret
.cfi_endproc
4

6 に答える 6

4

私が見つけた最速は、テーブルの実装です

私が得たタイミング（新しい測定コードの更新）

HVD の最新: 9.2 秒

テーブル バージョン: 7.4 秒 (k=693 の場合)

テーブル作成コード:

    unsigned int table[2*k];
    table_ptr = table;
    for(int i = 0; i < k; i++){
      unsigned int a = i;
      f(0, a);
      table[i<<1] = a;

      a = i;
      f(1, a);
      table[i<<1 + 1] = a;
    }

テーブル実行時ループ:

void f(bool m, unsigned int &a){
  a = table_ptr[a<<1 | m];
}

HVD の測定コードでは、rand() のコストが実行時間を支配していることがわかったので、ブランチレス バージョンの実行時間は、これらのソリューションとほぼ同じ範囲でした。測定コードをこれに変更しました（ランダムな分岐順序を維持するために更新され、rand（）などがキャッシュを破棄するのを防ぐためにランダムな値を事前に計算します）

int main(){
  unsigned int a = k / 2;
  int m[100000];
  for(int i = 0; i < 100000; i++){
    m[i] = rand() & 1;
  }

  for (int i = 0; i != 10000; i++
  {
    for(int j = 0; j != 100000; j++){
      f(m[j], a);  
    }
  }
}
于 2012-08-19T21:32:33.143 に答える
4

分岐のない除算のないモジュロは便利だったかもしれませんが、実際にはそうではないことがテストで示されています。

const unsigned int k = 639;
void f(bool m, unsigned int &a)
{
    a += m * 2 - 1;
    if (a == -1u)
        a = k;
    else if (a == k + 1)
        a = 0;
}

テストケース：

unsigned a = 0;
f(false, a);
assert(a == 639);
f(false, a);
assert(a == 638);
f(true, a);
assert(a == 639);
f(true, a);
assert(a == 0);
f(true, a);
assert(a == 1);
f(false, a);
assert(a == 0);

テストプログラムを使用して、実際にこれを計ります：

int main()
{
    for (int i = 0; i != 10000; i++)
    {
        unsigned int a = k / 2;
        while (a != 0) f(rand() & 1, a);
    }
}

(注: がないsrandため、結果は決定論的です。)

私の最初の答え：5.3秒

問題のコード: 4.8s

ルックアップ テーブル: 4.5 秒 ( static unsigned lookup[2][k+1];)

ルックアップ テーブル: 4.3 秒 ( static unsigned lookup[k+1][2];)

エリックの答え: 4.2 秒

このバージョン: 4.0s

于 2012-08-19T21:45:48.563 に答える
1

これには枝がありません。K は定数であるため、コンパイラはその値に応じてモジュロを最適化できる場合があります。K が「小さい」場合、完全なルックアップ テーブル ソリューションはおそらくさらに高速になります。

bool m;
unsigned int a;
const unsigned int k = ...; // k >= 7
const int inc[2] = {1, k};

a = a + inc[m] % (k+1);
于 2012-08-19T22:15:34.863 に答える
1

枝を完全に取り除くことはできないと思いますが、最初に m で枝分かれすることで数を減らすことができます。

if (m){
    if (a==k) {a = 0;} else {++a;}
}
else {
    if (a==0) {a = k;} else {--a;}
}
于 2012-08-19T21:11:37.843 に答える
1

Antimony の書き換えに追加:

if (a==k) {a = 0;} else {++a;}

ラップアラウンドで増加するように見えます。これを次のように書くことができます

a=(a+1)%k;

もちろん、これは、分割が分岐よりも実際に高速である場合にのみ意味があります。

もう一方についてはわかりません。(~0)%k がどうなるかを考えるのが面倒です。

于 2012-08-19T21:19:00.123 に答える
1

k がオーバーフローを引き起こすほど大きくない場合は、次のようにすることができます。

int a; // Note: not unsigned int
int plusMinus = 2 * m - 1;
a += plusMinus;
if(a == -1) 
    a = k; 
else if (a == k+1) 
    a = 0;

依然として分岐しますが、エッジ条件は m 関連の条件よりもまれであるため、分岐予測はより良くなるはずです。

于 2012-08-19T22:19:39.433 に答える