4

これは非常に頻繁に呼び出されるコードの小さな断片であり、最適化しようとしている畳み込みアルゴリズムの一部です (技術的には、これは私の最初のパスの最適化であり、速度は既に 2 倍向上していますが、今は立ち往生しています) :

inline int corner_rank( int max_ranks, int *shape, int pos ) {
  int i;
  int corners = 0;
  for ( i = 0; i < max_ranks; i++ ) {
    if ( pos % shape[i] ) break;
    pos /= shape[i];
    corners++;
  }
  return corners;
}

このコードはpos、N 次元配列内の位置のプロパティを計算するために使用されています (ポインターと演算にフラット化されています)。max_ranksは次元数でshape、各次元のサイズの配列です。

3 次元配列の例にはmax_ranks = 3、 、および が含まれる場合がありshape = { 3, 4, 5 }ます。最初のいくつかの要素の概略レイアウトは次のようになります。

 0       1       2       3       4       5       6       7       8
 [0,0,0] [1,0,0] [2,0,0] [0,1,0] [1,1,0] [2,1,0] [0,2,0] [1,2,0] [2,2,0]

 Returned by function:
 3       0       0       1       0       0       1       0       0

最初の行 0..8 は によって与えられるインデックス オフセットを示し、pos以下の数字は多次元インデックスを示します。編集: その下に、関数によって返される値を配置しました (2 の値は 12、24、および 36 の位置に返されます)。

この関数は、多次元インデックスの「先頭の」ゼロの数を効果的に返し、インクリメントごとに配列インデックスに完全に変換する必要がないように設計されています。

この関数を本質的に高速化するためにできることはありますか? を回避する賢い方法%、または「コーナー ランク」を計算する別の方法はありますか - ちなみに、私が知らないより正式な名前が付けられている場合は申し訳ありません。. .

4

1 に答える 1

2

返す必要があるのは、ゼロに等しい場合max_ranksだけです。posこれを確認すると、for ループから条件付きチェックを削除できます。これにより、最悪の場合の完了時間と、max_ranks の値が大きい場合のループ速度の両方が改善されます。

ここに私の追加と、除算演算を回避する別の方法があります。divこれは、2 回目の乗算を行わずに剰余を生成する方法がない限り、@twalberg が示唆していたような手書きと同じくらい速いと思います。

残念ながら、最も一般的な答えは 0 (最初の mod 呼び出しを通過することさえできない) であるため、多くの改善は見られません。私の推測では、平均実行時間はモジュラス関数自体の実行時間に非常に近いと思います。数値が の因数であるかどうかを判断するためのより高速な方法を探してみてくださいpos。実際に剰余を計算する必要はありません。残りがあるかどうかを知る必要があるだけです。

コードを再構築して混乱を招いたら申し訳ありません。コンパイラがこれらの最適化を既に行っていない限り、これはわずかに高速になると思います。

inline int corner_rank( int max_ranks, int *shape, int pos ) {
  // Most calls will not get farther than this.
  if (pos % shape[0] != 0) return 0;

  // One check here, guarantees that while loop below always returns.
  if (pos == 0) return max_ranks;

  int divisor = shape[0] * shape[1];
  int i = 1;
  while (true) {
    if (pos % divisor != 0) return i;
    divisor *= shape[++i];
  }
}

posまた、 anddivisorを可能な限り最小の型として宣言してみてください。255 を超えることがない場合は、unsigned char. 一部のプロセッサは、大きい数値よりも小さい数値で除算を高速に実行できることを知っていますが、変数の型を適切に設定する必要があります。

于 2013-10-18T12:13:26.950 に答える