C＃マイクロ最適化クエリ：IEnumerable Replacement

Question

注：私は過去の経験とプロファイラソフトウェアのアドバイスのために最適化しています。代替の最適化は、GetNeighborsをあまり頻繁に呼び出さないことに気付きましたが、現時点では二次的な問題です。

私は以下に説明する非常に単純な機能を持っています。一般に、私はforeachループの中でそれを呼び出します。私はその機能をたくさん（毎秒約10万回）呼びます。しばらく前に、私はJavaでこのプログラムのバリエーションをコーディングしていましたが、速度をあまりにもうんざりさせ、いくつかのforループを4つのif文で置き換えました。ループアンローリングは醜いと思われますが、アプリケーションの速度に顕著な差がありました。だから、私はいくつかの潜在的な最適化を思い付くと、私は自分のメリットにと提案について意見を求めるだろうと思ってきました：

• 十字完全文とはDRY原則を無視した場合。私はこれが過去の経験に基づいてパフォーマンスを改善すると確信していますが、それは私を悲しくします。明確にするために、4つのif文をgetNeighbors（）をあまりにも頻繁に呼び出す場所にペーストし、foreachブロックの内側をペーストします。
• いくつかの不思議な方法で結果をメモしてください。
• すべての四角に「近隣」プロパティを追加します。初期化時にその内容を生成します。

• コード生成ユーティリティを使用して、GetNeighborsの呼び出しをコンパイルの一部としてif文に変換します。

  public static IEnumerable<Square> GetNeighbors(Model m, Square s) 
  { 
      int x = s.X; 
      int y = s.Y;   
      if (x > 0) yield return m[x - 1, y]; 
      if (y > 0) yield return m[x, y - 1]; 
      if (x < m.Width - 1) yield return m[x + 1, y]; 
      if (y < m.Height - 1) yield return m[x, y + 1]; 
      yield break; 
  } 
  
  //The property of Model used to get elements. 
  private Square[,] grid; 
  //... 
  public Square this[int x, int y] 
  { 
      get 
      { 
       return grid[x, y]; 
      } 
  } 
  

注：GetNeighbors関数で費やされた時間の20％はm.get_Itemへの呼び出しに費やされ、他の80％は方法自体に費やされています。

Answer 1

ブライアン、

私は自分のコードで同様のことを実行しました。私はほとんど私を助けたのC＃で見つけた

二つのこと：

まず、必ずしも配分を恐れてはいけません。 C＃のメモリ割り当ては非常に高速であるため、配列をオンザフライで割り当てることは、しばしば列挙子を作成するよりも高速です。ただし、これが役立つかどうかは、結果をどのように使用しているかによって大きく異なります。私が見る唯一の落とし穴は、固定サイズの配列（4）を返すと、結果を使用しているルーチンのエッジケースをチェックする必要があるということです。

モデルの正方形の行列の大きさにもよりますが、正面にあるかどうかチェックするのが一番良いかもしれません。そうでない場合は、完全な配列を事前に計算して返してください。エッジにいる場合は、特殊ケースを別々に扱うことができます（必要に応じて1つまたは2つの要素配列を作成します）。これはそこに大きな文を1つ入れますが、それは私の経験ではしばしばより速いです。モデルが大きければ、私はすべての隣人を事前に計算することを避けるでしょう。四角形のオーバーヘッドが利益を上回る可能性があります。私の経験で

は、同様に、事前割り当て及び歩留りを使用して対戻すことの速度に大きな違いを作ることができ、あなたの関数をインライン化するJIT可能性が高くなります。 IEnumerableの結果を利用することができ、返されたすべての要素を常に使用しているとは限りませんが、そうでなければ事前計算が高速になる可能性があります。

あなたのケースでは、どの情報がSquareに保存されているのか分かりませんが、オブジェクトが比較的小さく、大きなマトリックスで使用され、何度も何度も反復された場合は、それは構造体です。私はこれに似たルーチン（ループで数十万回または何百万回と呼ばれる）を行い、クラスを構造体に変更すると、私の場合、ルーチンが40％以上高速化しました。これは、あなたが.net 3.5sp1を使用していることを前提としていますが、JITは最新リリースの構造体でさらに多くの最適化を行います。そこ

もちろん、クラス対構造体への切り替えに他の潜在的な落とし穴がありますが、それは巨大なパフォーマンスへの影響を持つことができます。

Answer 2

私は四角形（容量4）の配列を作り、それを代わりに返すことをお勧めします。パフォーマンスに敏感な状況でイテレータを使用することについては、私は非常に疑念があります。例：

// could return IEnumerable<Square> still instead if you preferred. 
public static Square[] GetNeighbors(Model m, Square s) 
{ 
    int x = s.X, y = s.Y, i = 0; 
    var result = new Square[4]; 

    if (x > 0) result[i++] = m[x - 1, y]; 
    if (y > 0) result[i++] = m[x, y - 1]; 
    if (x < m.Width - 1) result[i++] = m[x + 1, y]; 
    if (y < m.Height - 1) result[i++] = m[x, y + 1]; 

    return result; 
} 

これははるかに高速であれば驚かないでしょう。

Answer 3

私は滑りやすい斜面にいるので、免責事項をここに挿入してください。

私はオプション3を使うつもりです。隣人の参考文献をゆっくりと記入してください。あなたはある種のメモを持っています。

他の種類のメモは、怠惰なIEnumerableの代わりに配列を返すことになり、GetNeighborsはmemoizeするのは簡単な純粋な関数になります。しかし、これはおおよそオプション3になります。

いずれにしても、あなたはこれを知っていますが、すべての手順をプロファイルして再評価してください。私は、例えば、怠惰なIEnumerableと結果の配列を直接返すこととの間のトレードオフについては確信しています。 （あなたはいくつかの回帰を避けるが、割り当てが必要である）。

Answer 4

なぜそれの隣人を返すの広場クラスが責任を負うことはありませ？その後、メモ生成の余分なオーバーヘッドなしに怠惰な初期化を行うのに最適な場所があります。

public class Square { 

    private Model _model; 
    private int _x; 
    private int _y; 
    private Square[] _neightbours; 

    public Square(Model model, int x, int y) { 
     _model = model; 
     _x = x; 
     _y = y; 
     _neightbours = null; 
    } 

    public Square[] Neighbours { 
     get { 
      if (_neightbours == null) { 
       _neighbours = GetNeighbours(); 
      } 
      return _neighbours; 
     } 
    } 

    private Square[] GetNeightbours() { 
     int len = 4; 
     if (_x == 0) len--; 
     if (_x == _model.Width - 1) len--; 
     if (_y == 0) len--; 
     if (-y == _model.Height -1) len--; 
     Square [] result = new Square(len); 
     int i = 0; 
     if (_x > 0) { 
      result[i++] = _model[_x - 1,_y]; 
     } 
     if (_x < _model.Width - 1) { 
      result[i++] = _model[_x + 1,_y]; 
     } 
     if (_y > 0) { 
      result[i++] = _model[_x,_y - 1]; 
     } 
     if (_y < _model.Height - 1) { 
      result[i++] = _model[_x,_y + 1]; 
     } 
     return result; 
    } 

} 

Answer 5

はGetNeighborsの用途に応じて、多分コントロールのいくつかの反転は助けることができる：

public static void DoOnNeighbors(Model m, Square s, Action<s> action) { 
    int x = s.X; 
    int y = s.Y;   
    if (x > 0) action(m[x - 1, y]); 
    if (y > 0) action(m[x, y - 1]); 
    if (x < m.Width - 1) action(m[x + 1, y]); 
    if (y < m.Height - 1) action(m[x, y + 1]); 
} 

しかし、これは良いパフォーマンスを持っている場合、私は、よく分かりません。