这是另一个版本,供那些被微软抛弃的框架用户使用。它比 Array.Clear
快4倍,比Panos Theof's solution、Eric J's 以及Petar Petrov's parallel one更快 - 对于大型数组,速度可高达两倍。
首先,我想给大家介绍一下这个函数的先驱,因为这样更容易理解代码。从性能上看,这与 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);
}
正如您所见,这是基于已初始化部分的重复加倍。这种方法简单高效,但违反了现代内存架构的规则。因此产生了一种版本,它仅使用加倍来创建一个缓存友好的种子块,然后在目标区域上进行迭代地传送。
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),这个约束条件可能会在将来可用,也可能不可用。错误的估计并不是什么大问题,但如果该值准确,性能最佳,原因如下:
以下是基准测试,将我的代码与Array.Clear
和先前提到的其他三种解决方案进行比较。计时是针对给定大小的整数数组 (Int32[]
) 填充的。为了减少由于缓存奇异性等造成的变化,每个测试都会连续执行两次,并在第二次执行时记录时间。
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
,就可以保证专业的性能水平。换句话说,按照权利,库函数
Array.Clear
应该让我们手动编写的版本望尘莫及。事实上相反,这表明了事情的严重不协调。同样适用于首先必须自己编写
Fill<>
的情况,因为它仍然只存在于 Core 和 Standard 中,而不是 Framework 中。.NET 已经存在了将近二十年,我们仍然不得不不断地进行 P/Invoke 来处理最基本的问题或自己动手...