AMi*_*ico 5 .net initialization multidimensional-array
如何尽可能快地初始化基本类型的多维数组？
我坚持使用多维数组.我的问题是表现.以下例程初始化大约100x100阵列.500蜱.删除int.MaxValue初始化导致大约.180个滴答仅用于循环.大约100个刻度来创建数组而不循环并且没有初始化为int.MaxValue.
我对如何优化数组的非默认初始化的建议持开放态度.我的一个想法是在可用时使用较小的原始类型.例如,使用byte而不是int,可以节省100个滴答.我会对此感到满意,但我希望我不必更改原始数据类型.
public int[,] CreateArray(Size size) {
int[,] array = new int[size.Width, size.Height];
for (int x = 0; x < size.Width; x++) {
for (int y = 0; y < size.Height; y++) {
array[x, y] = int.MaxValue;
}
}
return array;
}
使用以下内容减少到450个滴答:
public int[,] CreateArray1(Size size) {
int iX = size.Width;
int iY = size.Height;
int[,] array = new int[iX, iY];
for (int x = 0; x < iX; x++) {
for (int y = 0; y < iY; y++) {
array[x, y] = int.MaxValue;
}
}
return array;
}
在一次性初始化2800个滴答后,降至约165个滴答.(请参阅下面的答案.)如果我可以stackalloc使用多维数组,我应该能够获得相同的性能而无需初始化private static数组.
private static bool _arrayInitialized5;
private static int[,] _array5;
public static int[,] CreateArray5(Size size) {
if (!_arrayInitialized5) {
int iX = size.Width;
int iY = size.Height;
_array5 = new int[iX, iY];
for (int x = 0; x < iX; x++) {
for (int y = 0; y < iY; y++) {
_array5[x, y] = int.MaxValue;
}
}
_arrayInitialized5 = true;
}
return (int[,])_array5.Clone();
}
在不使用上述"克隆技术"的情况下降至约165个滴答.(请参阅下面的答案.)我确信如果我可以找出返回值,我可以降低价格CreateArray9.
public unsafe static int[,] CreateArray8(Size size) {
int iX = size.Width;
int iY = size.Height;
int[,] array = new int[iX, iY];
fixed (int* pfixed = array) {
int count = array.Length;
for (int* p = pfixed; count-- > 0; p++)
*p = int.MaxValue;
}
return array;
}
我提供有关此问题的所有代码和注释作为答案.希望它能在未来节省一些人的时间.
在大对象堆(LOH)上分配的数组不是本讨论的一部分.所听到的性能改进仅适用于堆上分配的阵列.
我使用stackalloc消除初始化数组到默认值的想法没有用,因为分配的堆栈内存必须从方法中复制出来.意思是,我必须创建另一个数组来保存结果.该阵列将被初始化,从而破坏了使用的整个目的stackalloc.
只有unsafe在完全受信任的程序集中,CLR才会执行代码.
需要变量来确定数组是否已初始化并存储初始化的数组.初始化后,性能与不安全/固定方法相同.请参阅Dan Tao的可能解决方案的答案.
我吮吸百分比,但300%是我想象的(500到165刻度).
对于这个应用程序,我决定使用"克隆"方法.以下是应用程序中使用性能样本的"精简"通用实现.
初始化:
Grid<int>; 通用克隆类初始化:4348,4336,4339,4654Grid<bool>; 通用克隆类初始化:2692,2684,3916,2680Grid<Color>; 通用克隆类initalize:3747,4630,2702,2708使用:
Grid<int>; 通用克隆类:185,159,152,290Grid<bool>; 通用克隆类:39,36,44,46Grid<Color>; 通用克隆类:2229,2431,2460,2496
public class Grid<T> {
private T[,] _array;
private T _value;
private bool _initialized;
private int _x;
private int _y;
public Grid(Size size, T value, bool initialize) {
_x = size.Width;
_y = size.Height;
_value = value;
if (initialize) {
InitializeArray();
}
}
private void InitializeArray() {
int iX = _x;
int iY = _y;
_array = new T[iX, iY];
for (int y = 0; y < iY; y++) {
for (int x = 0; x < iX; x++) {
_array[x, y] = _value;
}
}
_initialized = true;
}
public T[,] CreateArray() {
if (!_initialized) {
InitializeArray();
}
return (T[,])_array.Clone();
}
}
关于您的方法的注释Clone：我怀疑您在性能方面能否击败它。但是，考虑到在第一次初始化后，它会忽略Size参数并在每次调用时仅返回相同大小的数组，这可能是一个重大更改。根据这在您的场景中是否真正重要，您可以：
Dictionary<Size, int[,]>（我相信 Size它可以作为键正常工作——尚未测试）来在每次Size请求唯一值时预初始化一个数组。我不确定这个的开销。Clone想法。如果你最终不得不选择上面的 3 个，这里有一些近乎荒谬的建议：
1. 在本地缓存您的Width和Height属性，而不是Size在每次迭代时从结构体访问它们。
static int[,] CreateArray(Size size) {
int w = size.Width;
int h = size.Height;
int[,] array = new int[w, h];
for (int x = 0; x < w; x++) {
for (int y = 0; y < h; y++) {
array[x, y] = int.MaxValue;
}
}
return array;
}
要在我的计算机上创建 1000x1000 数组，这会导致平均执行时间约为 120000 个时钟周期，而不是大约 140000 个时钟周期。
2. 如果有多个核心，请利用它们并并行初始化阵列。
static int[,] CreateArray(Size size) {
int w = size.Width;
int h = size.Height;
int[,] array = new int[w, h];
Action<int[,], int, int> fillFirstHalf = FillArray;
Action<int[,], int, int> fillSecondHalf = FillArray;
var firstResult = fillFirstHalf.BeginInvoke(array, 0, h / 2, null, null);
var secondResult = fillSecondHalf.BeginInvoke(array, h / 2, h, null, null);
fillFirstHalf.EndInvoke(firstResult);
fillSecondHalf.EndInvoke(secondResult);
return array;
}
static void FillArray(int[,] array, int ystart, int yend) {
int w = array.GetLength(0);
for (int x = 0; x < w; ++x) {
for (int y = ystart; y < yend; ++y) {
array[x, y] = int.MaxValue;
}
}
}
在您的场景中，这可能不是一个非常现实的建议，因为您似乎只创建 100x100 数组，在这种情况下，并行化的开销超过了性能增益。然而，对于创建 1000x1000 数组，我发现这种方法将我的执行时间减少到平均约 70k 滴答（与我建议的第一次优化中获得的约 120k 滴答相比）。
另外，如果您以这种方式创建许多数组，我强烈建议您并行化（即，如果您需要创建一千个数组，请从两个线程中每个数组创建 500 个），假设您有多个处理器来为您完成这项工作。没有多个处理器，就算了；添加线程只会损害你的性能。
3. 通过使用unsafe指针获得增强的性能。
现在有一个有趣的发现：.NET 中的二维数组似乎是以可预测的方式分配的*：基本上作为一维内存块，其中每个“行”从起始点偏移等量的量到所有先前行的长度。换句话说，10x2数组可以像20x1数组一样使用指针访问；10x10 数组可以像 100x1 数组一样访问，等等。
我不知道这是否有记录的行为。它可能是您不想依赖的未指定的实现细节。无论哪种方式，都值得研究。
*大多数其他 .NET 开发人员可能已经知道这一点，而我只是陈述显而易见的事实，在这种情况下，我会撤销我关于这一点“有趣”的评论。
无论如何，了解这一点可以让您fixed在unsafe上下文中利用关键字来显着提高性能：
static int[,] CreateArray(Size size) {
int w = size.Width;
int h = size.Height;
int[,] array = new int[w, h];
unsafe {
fixed (int* ptr = array) {
for (int i = 0; i < w * h; ++i)
ptr[i] = int.MaxValue;
}
}
return array;
}
对于初始化大尺寸数组，我什至建议将上述方法（并行化）与此方法相结合——因此，请与建议#2 保持相同CreateArray，然后重写FillArray为：
static void FillArray(int[,] array, int ystart, int yend) {
int w = array.GetLength(0);
unsafe {
fixed (int* p = array) {
for (int i = w * ystart; i < w * yend; ++i)
p[i] = int.MaxValue;
}
}
}
实际上，在我发布此内容之前，您似乎已经弄清楚了最后一部分，但我认为无论如何我都会将其包含在内，主要是为了与unsafe并行化相结合。
注释stackalloc：我认为您可能正在用这个追逐彩虹尽头的妖精。根据以下文档stackalloc：
大小足以容纳该
expr类型元素的内存块type是在堆栈上分配的，而不是在堆上；块的地址存储在指针中ptr。该内存不受垃圾回收的影响，因此不必固定（通过fixed）。内存块的生命周期仅限于定义它的方法的生命周期。（强调我的）
这使我相信您不能 返回其数据存储在stackalloc函数分配的内存中的对象，因为该内存仅在函数的生命周期内分配。