Cで配列を分割する最速（ポータブル）の方法＃

Question

完全に管理されたMercurialライブラリ（完全に管理されたMercurial Server for Windowsで使用される予定です）と、私が見ている最も重大なパフォーマンス上の問題の1つ不思議なことに、配列を分割することです。

考え方は次のとおりです。サイズが数百バイトから1メガバイトまでのバイト配列があります。私が必要とするのは、私の特定のケースでは、区切りで分割することです。\n文字。

は今、何ドットトレースが私を示しては私"optimized" versionのSplitドットトレース自体によって導入された明白なパフォーマンスヒットがあります（2300回のコールのために11秒を要しますが、すべての（コードは私が始まった正しい、here's the naiveバージョンである）ということです最大規模まで）。ここで

は数字です：

• unsafeバージョン：だからここ2 312通話

ため20 001 MSが行く：何を2 312通話

ため11 297ミリ秒（ "ナイーブ"）のバージョンを管理しますC＃で配列を分割する方法が最も速くなります（移植性があり、x86とx64の両方をサポートすることが好ましい）。

Answer 1

スプリットの場合、32ビットマシンでのulongの処理は実際には遅いため、確かにuintに減らしてください。本当にulongが必要な場合は、32ビット用と64ビット用の2つのバージョンを実装します。

また、一度に処理バイトが高速かどうかを測定する必要があります。

メモリ割り当てのコストをプロファイルする必要があります。十分な大きさであれば、複数の呼び出しでメモリを再利用してみてください。

その他：

ToStringメソッド：それは "（" + + Offset.ToString（）+ "" + Length.ToString（） "）" を使用するように高速です。

GetHashCodeメソッド：複数回使用した場合、

---

このバージョンは本当に高速である必要があります（= &バッファ[オフセット]バイト* b）は固定してみてください。 重要な点：内部配列が適切なサイズに拡張された後、新しいメモリ割り当てが行われず、最小のデータコピー。

class ArraySplitter 
{ 
    private byte[] m_data; 
    private int m_count; 
    private int[] m_stops; 

    private void AddRange(int start, int stop) 
    { 
     // Skip empty range 
     if (start > stop) 
     { 
      return; 
     } 

     // Grow array if needed 
     if ((m_stops == null) || (m_stops.Length < (m_count + 2))) 
     { 
      int[] old = m_stops; 

      m_stops = new int[m_count * 3/2 + 4]; 

      if (old != null) 
      { 
       old.CopyTo(m_stops, 0); 
      } 
     } 

     m_stops[m_count++] = start; 
     m_stops[m_count++] = stop; 
    } 

    public int Split(byte[] data, byte sep) 
    { 
     m_data = data; 
     m_count = 0;  // reuse m_stops 

     int last = 0; 

     for (int i = 0; i < data.Length; i ++) 
     { 
      if (data[i] == sep) 
      { 
       AddRange(last, i - 1); 
       last = i + 1; 
      } 
     } 

     AddRange(last, data.Length - 1); 

     return m_count/2; 
    } 

    public ArraySegment<byte> this[int index] 
    { 
     get 
     { 
      index *= 2; 
      int start = m_stops[index]; 

      return new ArraySegment<byte>(m_data, start, m_stops[index + 1] - start + 1); 
     } 
    } 
} 

---

テストプログラム：

static void Main(string[] args) 
    { 
     int count = 1000 * 1000; 

     byte[] data = new byte[count]; 

     for (int i = 0; i < count; i++) 
     { 
      data[i] = (byte) i; 
     } 

     Stopwatch watch = new Stopwatch(); 

     for (int r = 0; r < 10; r++) 
     { 
      watch.Reset(); 
      watch.Start(); 

      int len = 0; 

      foreach (var seg in data.MySplit(13)) 
      { 
       len += seg.Count; 
      } 

      watch.Stop(); 

      Console.WriteLine("MySplit  : {0} {1,8:N3} ms", len, watch.Elapsed.TotalMilliseconds); 

      watch.Reset(); 
      watch.Start(); 

      ArraySplitter splitter = new ArraySplitter(); 

      int parts = splitter.Split(data, 13); 

      len = 0; 

      for (int i = 0; i < parts; i++) 
      { 
       len += splitter[i].Count; 
      } 

      watch.Stop(); 
      Console.WriteLine("ArraySplitter: {0} {1,8:N3} ms", len, watch.Elapsed.TotalMilliseconds); 
     } 
    } 

結果：

MySplit  : 996093 9.514 ms 
ArraySplitter: 996093 4.754 ms 
MySplit  : 996093 7.760 ms 
ArraySplitter: 996093 2.710 ms 
MySplit  : 996093 8.391 ms 
ArraySplitter: 996093 3.510 ms 
MySplit  : 996093 9.677 ms 
ArraySplitter: 996093 3.468 ms 
MySplit  : 996093 9.685 ms 
ArraySplitter: 996093 3.370 ms 
MySplit  : 996093 9.700 ms 
ArraySplitter: 996093 3.425 ms 
MySplit  : 996093 9.669 ms 
ArraySplitter: 996093 3.519 ms 
MySplit  : 996093 9.844 ms 
ArraySplitter: 996093 3.416 ms 
MySplit  : 996093 9.721 ms 
ArraySplitter: 996093 3.685 ms 
MySplit  : 996093 9.703 ms 
ArraySplitter: 996093 3.470 ms 

Answer 2

私はこの問題は、あなたがループ内で複雑な操作をたくさんやっていること、であると考えています。このコードは、ループ内での単一の加算と比較を除くすべての演算を削除します。他の複雑なものは、分割が検出された場合、または配列の最後に発生した場合にのみ発生します。

また、テストを実行するデータの種類を特定するのは難しいので、これは推測に過ぎません。

public static unsafe Segment[] Split2(byte[] _src, byte value) 
{ 
    var _ln = _src.Length; 

    if (_ln == 0) return new Segment[] { }; 

    fixed (byte* src = _src) 
    { 
     var segments = new LinkedList<Segment>(); // Segment[c]; 

     byte* last = src; 
     byte* end = src + _ln - 1; 
     byte lastValue = *end; 
     *end = value; // value-termination 

     var cur = src; 
     while (true) 
     { 
      if (*cur == value) 
      { 
       int begin = (int) (last - src); 
       int length = (int) (cur - last + 1); 
       segments.AddLast(new Segment(_src, begin, length)); 

       last = cur + 1; 

       if (cur == end) 
       { 
        if (lastValue != value) 
        { 
         *end = lastValue; 
        } 
        break; 
       } 
      } 
      cur++; 
     } 

     return segments.ToArray(); 
    } 
} 

編集：コードを修正するので、それが正しい結果を返します。

Answer 3

アントン、

あなたはまだこれを最適化することに興味がある場合は、このスレッドはかなり古いですので、私はしかし、私はあなたのコードは、オンラインリポジトリにほとんど同じだったので、私は私が思ったことを見た、知りません試してみます。あなたのHgLabアプリケーションを評価しながら、bitbucket.orgのHgSharpコードを調べました。私はそれを大幅に単純化したネイティブな構造を使って関数を書き直しました。私のテストでは、元のルーチンよりも半分以上の時間がかかりました。数メガバイトのソースファイルをロードしてテストし、元のルーチンを使用して同じ操作のパフォーマンスとタイミングを比較しました。

基本ロジックを書き換えることに加えて、ネイティブArraySegment<>をカスタム実装の代わりにフレームワークに組み込むことにしました。大きな違いはArraySegment<>がLengthプロパティの代わりにCountプロパティを公開していることです。私はポインタを使用していないので、以下のコードはunsafeキーワードを必要としませんが、そうするように変更された場合、わずかなパフォーマンスの改善が見られます。

---

public static ArraySegment<byte>[] SplitEx(this byte[] source, byte value) { 
     var _previousIndex = -1; 
     var _segments = new List<ArraySegment<byte>>(); 
     var _length = source.Length; 

     if (_length > 0) { 
      int _index; 

      for (_index = 0; _index < _length; _index++) { 
       var _value = source[_index]; 
       if (_value == value) { 
        _segments.Add(new ArraySegment<byte>(source, _previousIndex + 1, _index - _previousIndex)); 
        _previousIndex = _index; 
       } 
      } 

      if (--_index != _previousIndex) { 
       _segments.Add(new ArraySegment<byte>(source, _previousIndex + 1, _index - _previousIndex)); 
      } 
     } 

     return _segments.ToArray(); 
    }