これは、Microsoft によって放棄されたフレームワーク ユーザー向けの別のバージョンです。これは、 Panos Theof のソリューション、Eric JとPetar Petrov の並列Array.Clear
ソリューションよりも 4 倍速く、大規模な配列では最大 2 倍高速です。
最初に、関数の祖先を示したいと思います。これにより、コードが理解しやすくなります。パフォーマンスに関しては、これは Panos Theof のコードとほぼ同等であり、すでに十分である可能性があるものもあります。
public static void Fill<T> (T[] array, int count, T value, int threshold = 32)
{
if (threshold <= 0)
throw new ArgumentException("threshold");
int current_size = 0, keep_looping_up_to = Math.Min(count, threshold);
while (current_size < keep_looping_up_to)
array[current_size++] = value;
for (int at_least_half = (count + 1) >> 1; current_size < at_least_half; current_size <<= 1)
Array.Copy(array, 0, array, current_size, current_size);
Array.Copy(array, 0, array, current_size, count - current_size);
}
ご覧のとおり、これは既に初期化された部分の繰り返しの 2 倍化に基づいています。これは単純で効率的ですが、最新のメモリ アーキテクチャに反します。したがって、キャッシュに適したシード ブロックを作成するためだけに倍増を使用するバージョンが生まれました。このシード ブロックは、ターゲット エリアで繰り返しブラストされます。
const int ARRAY_COPY_THRESHOLD = 32; // 16 ... 64 work equally well for all tested constellations
const int L1_CACHE_SIZE = 1 << 15;
public static void Fill<T> (T[] array, int count, T value, int element_size)
{
int current_size = 0, keep_looping_up_to = Math.Min(count, ARRAY_COPY_THRESHOLD);
while (current_size < keep_looping_up_to)
array[current_size++] = value;
int block_size = L1_CACHE_SIZE / element_size / 2;
int keep_doubling_up_to = Math.Min(block_size, count >> 1);
for ( ; current_size < keep_doubling_up_to; current_size <<= 1)
Array.Copy(array, 0, array, current_size, current_size);
for (int enough = count - block_size; current_size < enough; current_size += block_size)
Array.Copy(array, 0, array, current_size, block_size);
Array.Copy(array, 0, array, current_size, count - current_size);
}
注: 以前のコードは(count + 1) >> 1
、最後のコピー操作で残っているすべてをカバーするのに十分な飼料があることを確認するために、倍増ループの制限として必要でした。count >> 1
代わりに使用される場合、これは奇数カウントには当てはまりません。現在のバージョンでは、線形コピー ループがスラックを拾うため、これは重要ではありません。
配列セルのサイズはパラメーターとして渡す必要があります。なぜなら、将来利用可能になるかどうかわからないsizeof
制約 ( ) を使用しない限り、ジェネリックは使用できないからです。unmanaged
間違った見積もりは大した問題ではありませんが、次の理由により、値が正確であればパフォーマンスは最高になります。
要素サイズを過小評価すると、ブロック サイズが L1 キャッシュの半分を超える可能性があるため、コピー ソース データが L1 から追い出され、低速のキャッシュ レベルから再フェッチする必要が生じる可能性が高くなります。
要素サイズを過大評価すると、CPU の L1 キャッシュが十分に活用されなくなります。つまり、線形ブロック コピー ループが最適な使用率で実行されるよりも頻繁に実行されます。したがって、厳密に必要な以上の固定ループ/呼び出しオーバーヘッドが発生します。
これは、私のコードとArray.Clear
前述の他の 3 つのソリューションを比較するベンチマークです。Int32[]
タイミングは、指定されたサイズの整数配列 ( ) を埋めるためのものです。キャッシュの変動などによる変動を減らすために、各テストを連続して 2 回実行し、タイミングは 2 回目の実行に合わせました。
array size Array.Clear Eric J. Panos Theof Petar Petrov Darth Gizka
-------------------------------------------------------------------------------
1000: 0,7 µs 0,2 µs 0,2 µs 6,8 µs 0,2 µs
10000: 8,0 µs 1,4 µs 1,2 µs 7,8 µs 0,9 µs
100000: 72,4 µs 12,4 µs 8,2 µs 33,6 µs 7,5 µs
1000000: 652,9 µs 135,8 µs 101,6 µs 197,7 µs 71,6 µs
10000000: 7182,6 µs 4174,9 µs 5193,3 µs 3691,5 µs 1658,1 µs
100000000: 67142,3 µs 44853,3 µs 51372,5 µs 35195,5 µs 16585,1 µs
このコードのパフォーマンスが十分でない場合、有望な方法は、線形コピー ループ (すべてのスレッドが同じソース ブロックを使用する) を並列化するか、古き良き友である P/Invoke です。
注: 通常、ブロックのクリアとフィルは、MMX/SSE 命令などを使用して高度に特殊化されたコードに分岐するランタイム ルーチンによって行われるため、適切な環境では、それぞれの道徳的に同等のものを呼び出すだけstd::memset
で、プロのパフォーマンス レベルが保証されます。IOW、ライブラリ関数Array.Clear
は、すべての手動バージョンをほこりの中に残す必要があります。それが逆であるという事実は、物事が実際にどれほどうまくいかないかを示しています. Fill<>
フレームワークではなく、コアとスタンダードのみにあるため、最初に自分でロールバックする必要がある場合も同様です。.NET が誕生してから 20 年近くが経ちますが、最も基本的なものを左右に P/Invoke するか、独自のものを作成する必要があります...