.NET中数组的隐秘特性
背景知识
Array类是所有数组类型的基类，上一篇文章《.NET中String类的隐秘特性》中提到：数组的长度不是固定不变的，是可变的。
首先了解一些相关的概念：
数组元素：数组包含的值；
数组长度：数组可以包含的元素的个数；
维度数：数组的维度总数；
下限：数组指定的维度的起始索引。多维数组每个维可以有不同的下限。
运行时有两种不同的数组实现--SZ数组和普通数组。SZ数组是以0为下限的一维数组；普通数组指多维的或者下限不为0的数组。有时候我们称呼多维数组为MD数组。由于SZ数组较常用，微软对它的性能进行了极大的优化。下面的表详细列出了SZ数组与MD数组的区别。
SZ数组
MD数组
定义
一维的，以0为下限的数组
多维的，或者下限不为0的数组
C#语法
Object[]
Object[][] (交错数组)
Object[,] ---二维数组
是否兼容CLS
兼容（交错数组除外）
不兼容
IL优化
使用专用的IL指令来操作这些数组，比如：ldlen，stelem等等
在1.0版本，没有专用的IL指令，对数组的所有操作都是通过方法调用来实现
方法优化
基元类型数组有专用的方法，这些方法在操作一些值类型数组时不用反复的装箱，所以具有较高的性能
在1.0版本，引用类型和值类型数组使用同样的方法。值类型在方法调用时被反复地装箱和拆箱，造成了极大的性能冲击
基本长度（不包括8字节的方法表指针和对象头）
值类型数组 — 4字节
引用类型数组 — 8字节
值类型数组 — 4+8*rank(维度数)
引用类型数组 — 8+8*rank(维度数)
JIT优化
JIT编译器消除了范围检查
JIT编译器没有对它进行优化。CLR将会执行额外的代码对每一维进行范围检查
表中的一些内容在文章后面进行了比较详细的讲述。从表中我们可以清楚地看到，SZ数组性能要远远优于MD数组，交错数组可以看作数组元素是SZ数组的SZ数组，当然在性能上它要优于MD数组。不过要记住一点，交错数组不兼容CLS，因此它不能在不同的语言编写的代码之间传递。
数组的IL优化
using System;
namespace abc
{
class Class1
{
[STAThread]
static void Main(string[] args)
{
int[] A=new int[5];
int[,] C=new int[5,5];
A[0]=1;
C[0,0]=1;
}
}
}
上面代码的IL代码如下：
.method private hidebysig static void Main(string[] args) cil managed
{
.entrypoint
.custom instance void [mscorlib]System.STAThreadAttribute::.ctor() = ( 01 00 00 00 )
// Code size 29 (0x1d)
.maxstack 4
.locals ([0] int32[] A,
[1] int32[0...,0...] C)
IL_0000: ldc.i4.5
IL_0001: newarr [mscorlib]System.Int32
IL_0006: stloc.0
IL_0007: ldc.i4.5
IL_0008: ldc.i4.5
IL_0009: newobj instance void int32[0...,0...]::.ctor(int32,
int32)
IL_000e: stloc.1
IL_000f: ldloc.0
IL_0010: ldc.i4.0
IL_0011: ldc.i4.1
IL_0012: stelem.i4
IL_0013: ldloc.1
IL_0014: ldc.i4.0
IL_0015: ldc.i4.0
IL_0016: ldc.i4.1
IL_0017: call instance void int32[0...,0...]::Set(int32,
int32,
int32)
IL_001c: ret
} // end of method Class1::Main
对比一下给SZ数组和MD数组付值的IL代码：给数组A付值使用stelem.i4 指令，而给多维数组付值则必须调用Set方法。
数组内部字段
SZ数组和MD数组都包含有下面2个内部字段。
变量
类型
描述
Array Length
int
数组中实际的元素个数
Element Type
Type
从源代码看，这一字段只在数组包含“指针”的情况下才被使用。这里，“指针”指的是对象的引用，不是非托管代码中的指针
除了上面两个字段外，MD数组还包含下面两个字段。
变量
类型
描述
Bounds[rank]
int[]
数组某一维的元素个数
LowerBound[rank]
int[]
数组某一维的下限。合法的索引应该满足条件：lowerBounds[i] <= index[i] < lowerBounds[i] + bounds[i]
通过下面的例子和图示，你可以更好的了解这些内部字段。下面的非托管代码的主要目的是确定上述的内部字段在内存中的分布。
using System;
namespace ABC
{
class Class1
{
[STAThread]
static void Main(string[] args)
{
int[] A=new int[5];
byte[] a=GetBytes(A,4);
//输出数组A的长度（Array Length）
Console.WriteLine(BitConverter.ToInt32(a,0));
int[,,] B=new int[2,3,4];
// 4+8*rank(维度数): 4+3*8=28
byte[] b=GetBytes(B,28);
//分别输出数组B的长度，第1，2，3维的长度和第1，2，3维的下限
for (int i=0;i<28;i=i+4)
Console.WriteLine(BitConverter.ToInt32(b,i));
Console.ReadLine();
}
static byte[] GetBytes(int[] array,int count)
{
unsafe
{
byte[] b=new byte[count];
byte *pb;
fixed (int *p=&array[0])
pb=(byte *)p;
pb=pb-count;
for (int i=0;i<count;i++)
{
b[i]=*pb++;
}
return b;
}
}
static byte[] GetBytes(int[,,] array,int count)
{
unsafe
{
byte[] b=new byte[count];
byte *pb;
fixed (int *p=&array[0,0,0])
pb=(byte *)p;
pb=pb-count;
for (int i=0;i<count;i++)
{
b[i]=*pb++;
}
return b;
}
}
}
}
根据上面代码的运行结果，我们可以确定数组的内部字段在内存中的分布，如图1所示（我在许多条件下测试了数组各内部字段在内存中的分布，发现它们的排列顺序总是如图）。
图1
对普通数组的访问必须检查几个内部成员，这会对性能造成一定的影响。一般地，我们有两种办法来优化普通数组的性能：一种是使用交错数组；另一种是使用非安全代码访问。
数组类型与分类
如果两个数组有着相同的维度数和相同的元素类型，我们认为这两个数组具有相同的类型，与C/C++不同，这里每一维的上限和下限不予考虑，下面的代码说明了这点。一些方法（比如Array.Copy）在操作多维数组时，它们在内部将多维数组看作一个一维数组（数组长度是各维长度的总和）。
Array A=Array.CreateInstance(typeof(int),new int[2]{2,2},new int[2]{-1,-1});
Array B=Array.CreateInstance(typeof(int),new int[2]{3,3},new int[2]{-10,-2});
if (A.GetType().Equals(B.GetType()))
Console.WriteLine("数组A与B属于同一类型");
具有不同维度数的交错数组属于不同的类型，比如：
int[][] A=new int[2][];
int[][][] B=new int[2][][];
A与B是不同的类型。道理比较显然，我们可以认为交错数组的元素是数组，A与B的元素类型是不一样的，所以A与B属于不同的类型。比较有意思的是，基类Array类型调用Type.IsArray()方法返回值是false，调用Type.GetElementType()方法返回值是null。
除了基本长度外，数组还包含了一些数据，如图1所示。值类型数组包含的是未装箱的结构（连续排列），引用类型数组则包含了指向引用对象的指针（连续排列）。另外，引用类型数组在指针数据块之前还有一个元素类型字段（ElementType）。读者也许会认为：通过数组的方法表可以获得有关元素类型的信息，这个字段显得有点多余了。其实不然，通过这个字段，可以迅速地获得类型信息，另外，这对于数组的其他特性，比如数组变异(Array Covariance)，是非常重要的（后面会详细讲述这点）。
如果数据是值类型，那么元素的长度与相应的值类型一样，引用类型则占用IntPtr.Size个字节。IntPtr.Size在Win32系统中是4个字节，在64位系统中是8个字节。依据微软的文档记录，IntPtr.Size与Void *指针的本地字节数相同，但是在非Win32的Rotor包（比如Mac和Unix），不管CPU是什么，IntPtr.Size总是8个字节。
类型
元素的字节长度
bool
1
byte
1
short
2
int
4
long
8
float
4
double
8
decimal
16
string
IntPtr.Size
object
IntPtr.Size
interface
IntPtr.Size
你不能通过反射来访问数组的内部字段，那是不是需要使用非安全代码来访问内部字段？在这里，没有这个必要，因为Array的内部字段都通过公共方法和属性公开了。比如：GetLength()方法返回数组中指定维度的元素个数。相关的更详细的内容可以参考MSND。
上面提到了两种数组的分类：SZ数组和MD数组；值类型数组和引用类型数组。在代码中我们该如何判断它们？
下面的代码用来判断数组是否SZ数组：
if (array.Rank==1 && array.GetLowerBound(0)==0){}
下面的代码用来判断数组是否值类型数组：
if ((elementType = array.GetType().GetElementType()) && elementType.IsSubclassOf(typeof(ValueType)) && elementType != typeof(Enum) && elementType != typeof(ValueType)){}
有意思的是，Enum[]或者ValueType[]都不是值类型数组，它们包含的元素是指向装箱值类型的引用。
动态的ArrayList类
ArrayList类是处理动态数组的一个很有用的类，除此之外，它还可以用来封装集合类。
ArrayList类允许创建一个内部数组对象并对数组进行直接的修改。没有显式设置ArrayList容量的情况下，使用默认容量（16），ArrayList创建的数组的长度是16。下面表中列出的是ArrayList类的四个内部成员。
变量
类型
描述
_items
Object[]
内部数组
_size
int
ArrayList实例实际包含的元素数
_version
int
在每次对ArrayList进行修改后，_version都会递增。
_defaultCapacity
int
常量字段，表示默认容量
一个ArrayList实例共占用20字节的内存（8字节的对象开销内存+12字节的实例信息），这不包括内部数组（_items）占用的空间。
给ArrayList添加新元素时（比如调用AddRange方法），需要超出ArrayList的初始容量，ArrayList将会自动扩大容量。ArrayList的容量或者加倍或者增加到新的 Count，取二者之中较大者，内部数组（_items）也被重新分配以容纳新元素，并且现有的元素被复制到新数组中。出于优化性能的考虑，如果预先知道长度，应该为ArrayList分配足够的内存一避免不必要的复制。如果所有的数组元素都已经添加进去，并且不再对数组（_items）进行扩充，你应该调用ToArray方法将它装换成类型安全的数组，这样，无论在内存使用还是性能上都得到极大的优化。
我们可以调用TrimToSize方法来截去ArrayList的未使用部分，这个方法实际上是执行一次元素复制。在调用TrimToSize后，要真正的释放数组占用的内存，还要调用Clear方法。要注意的是，在空ArrayList上执行TrimToSize方法是将ArrayList的容量设置为默认容量，而不是零。需要注意的是，创建ArrayList如果将容量设为0，CLR将使用默认值16来创建。
ArrayList类不是Array类的一个完全的替代，我觉得ArrayList比多维数组的性能要好得多，我将在另外一篇文章详细分析二者的区别，特别在性能方面。
Array
ArrayList
内存占用
值类型数组中的数据没有装箱，每个元素的长度等于相应的值类型的长度。
引用类型数组的每个元素的长度等于IntPtr.Size
内部数组是引用类型数组。值类型数组会带来每元素12字节的开销（4字节用于对象引用，8字节是元素装箱时引入的对象头）
性能
有专用的IL指令；消除了范围检查
长度固定
长度可变
访问
对某一索引的元素的访问的前提是该索引之前的所有元素都已经添加。比如下面的代码会发出异常：
ArrayList al=new ArrayList();
al[0]=1;
Array与ArrayList之间的相互转换是很方便的。ArrayList.Adapter方法用来将Array转换成ArrayList，ToArray方法用来将ArrayList转换成Array。
你可以使用下面的办法来访问ArrayList维护的内部数组：(object[]) sb.GetType().GetField("_items", BindingFlags.NonPublic|BindingFlags.Instance).GetValue(arrayList)，这是ToArray的一个替代方法。与ToArray相比，这一方法减少了内存和时间上的开销。但需要注意的是，这种方法得到的数组的长度是ArrayList的容量，而不是实际元素的个数。
不借助ArrayList类对Array进行操作
改变数组的大小
我个人认为，数组应该提供一个方法用来改变数组的大小。下面我写的这个方法模仿ArrayList的行为，你可以使用它来改变数组的大小。
public static Array Resize(Array array, int newSize)
{
Type type = array.Type;
Array newArray = Array.CreateInstance(type.GetElementType(), newSize);
Array.Copy(array, 0, newArray, 0, Math.Min(newArray.Length, newSize))l
return newArray;
}
移动数组
Array类提供了一个Copy方法用来在一个数组与另外一个数组之间复制数据，其实，Copy方法也可以在一个数组内移动数据。这时的复制行为等效于标准 C/C++ 函数 memmove，而不是 memcpy。
下面的InsertHelper方法从index处开始，将后面的内容往右移count位，右移后超出数组长度的元素被舍弃。同样的，RemoveHelper方法从index+count处开始，将后面的所有元素移动index处，array.Length-count后的元素被舍弃。
public static Array InsertHelper(Array array, int index, int count)
{
Array.Copy(array, index, array, index+count, array.Length-(index+count));
array.Clear(index, count);
}
public static Array RemoveHelper(Array array, int index, int count)
{
int copy = ;
Array.Copy(array, index+count, array, index, array.Length - (index+count));
array.Clear(array.Length - count, count);
}
对于不包含任何内部对象引用的值类型数组，Buffer类提供了几个有用的方法（BlockCopy,ByteLength,GetByte,SetByte）来对它们进行操作。在使用这些方法时，元素的类型被忽略，因为Buffer类只是将数组看作一系列的字节，不同类型的数组之间可以相互复制。比如我们可以将浮点类型数组复制到整数类型数组，反过来也一样。
在多维数组复制数据时，数组被看成为一个一维数组（长度等于多维数组所有维的长度的总和）。举个例子，如果有一个三维数组，每维有4个元素（Array[3,4]），从数组开始复制6个元素，其结果是前4个元素是第一维的所有元素，后2个元素是第二维的前面2个元素。
另外，值得我们留意的一个类是BitArray，有点Pascal的风格。BitArray类是管理位值的压缩数组，该值表示为布尔值，其中 true表示位是打开的(1)，false表示位是关闭的(0)。另一个与BitArray相似的是BitVector32结构，该结构以 32 位内存存储布尔值和小整数。对于内部使用的布尔值和小整数，BitVector32 比 BitArray 更有效。BitArray 可以按需要无限地扩大，但它有内存和性能方面的系统开销。相比之下，BitVector32 只使用 32 位。
ArrayList视图
ArrayList可以为Array和IList建立视图。
Adapter
使用ArrayList.Adapter方法可以为任何实现IList接口的类建立一个视图，使它可以被作为ArrayList类来进行操作。换句话说，IList可以利用ArrayList类提供的方法（BinarySearch,Sort,Reverse,GetRange，还有转换功能）。对于Array数组，这就不显得那么有用了，因为它本身也提供了这些方法（除了提取子集外）。
语法
将Ilist转换成Array
ArrayList.Adapter(iList).ToArray()
反转Ilist
ArrayList.Adapter(iList).Reverse()
取得子集
ArrayList.Adapter(iList).GetRange(start, count)
使用对分检索算法查找
ArrayList.Adapter(iList).BinarySearch()
排序
ArrayList.Adapter(iList).Sort()
数组子集
下面的代码可以用来提取Array数组的子集。
public static Array GetRange(Array range, int start, int count)
{
Type type = array.Type;
Array newArray = Array.CreateInstance(type.GetElementType(), count);
Array.Copy(array, start, newArray, 0, count);
return newArray;
}
这种方法实际上是生成一个数组的子集拷贝，会占用很多的内存。ArrayList提供了一个方法GetRange来获取子集，如果数组子集的长度很大，建议使用GetRange，因为它内部没有对数组子集进行复制，节约了大量的内存。GetRange方法返回一个ArrayList的子类，相当于数组视图。你可以对视图进行各种操作（添加，修改或者删除元素）。需要注意的是，我们只能通过GetRange返回的视图对原数组进行操作。如下面代码所示，对al进行修改会导致视图alview失效，你再次使用视图alview时将会抛出InvalidOperationException异常。
int[] A=new int[5];
ArrayList al=new ArrayList(A);
ArrayList alview=al.GetRange(0,2);
al[0]=1;
int a=(int)alview[0];
封装支持
ArrayList提供了三个方法：FixedSize,ReadOnly和Synchronized，每个方法有两个重载版本，这三个方法接受IList或者ArrayList为参数。FixedSize方法返回具有固定大小的列表包装，其中的元素允许修改，但不允许添加或移除。ReadOnly方法返回只读的列表包装。Synchronized方法返回同步（线程安全）的列表包装。
这些方法可以混合使用，比如：ArrayList.Synchronized(ArrayList.ReadOnly(list))返回一个只读的同步的数组。
ReadOnly方法在禁止修改数组方面很有用。你需要注意两种情况：一是数组总是通过引用的方式传递的；另外一种情况是，在Marshal过程中，数组元素个数如果超过10，CLR不是Copy数组，而是“锁住”原数组（防止它被垃圾回收器重定位）。这两种情况下你很可能会不经意的修改数组，从而使程序的结果不可预期。
数组转换
数组变异（Array Covariance）
在C++中可以将一种类型的指针数组转换成另一种指针类型。.NET中，CLR允许将引用类型数组的元素类型隐式或显式转换成另一种类型，这种性质被称为数组变异（Array Coveriance）。CLR不允许将值类型数组转换为其它类型数组。你可以使用其他办法来实现值类型数组的转换，比如，使用Array.Copy方法来创建一个目标数组并将原数组元素转换到目标数组。
int[] A=new int[5];
A[0]=1;
double[] B=new double[5];
Array.Copy(A,0,B,0,1);
不管是显式或者隐式的转换，在编译的时候，原数组类型被转换成为目标类型，转换的前提是两个数组必须有同样的维度数。在转换过程中，数组只是被重新解释，在内存占用上没有任何变化。
如果转换是隐式的，在转换前，数组的元素类型被转换为它支持的接口或者它的一种基类型，这是不需要显示地Cast，也不执行任何运行时检查。如果转换是显式的（转换是从一种接口转换为另一种接口，或者从基类转换为子类，或者从一种类型转换为一种它不直接支持的接口），这时需要显示地Cast，并执行运行时检查。
前面已经提到，引用类型数组有一个元素类型内部字段（ElementType）。这个字段在转换前后都是保持不变的。执行运行时检查主要是检查新类型与元素类型（ElementType）之间的兼容性。
下面的例子可以使你更好的了解数组转换。
public class Animal {}
object [] data = new Animal[2]; // Animal[]被隐式地转换为object[]
Animal [] animals1 = data; // Error: 从object[]到Animal[]需要显式转换
Animal [] animals2 = (Animal[]) data; // object[] 被显式转换成 Animal []
string [] strings1 = (string[]) animals2; // 编译失败，因为string[]与Animal[]之间不能相互转换
string [] strings2 = (string[]) data; // 编译成功，但是运行时会发生异常，因为Animal[]不是从string[]继承而来
object [] data2 = new object[1];
data2[0] = new Animal();
Animal [] animals3 = (Animal[]) data2; // 编译成功，但是运行时会发生异常。运行时检查将会验证元素类型（ElementType）与目标类型Animal的兼容性。
Animal[] animal4=new Animal[1];
object[] data3=(object[])animal4;
Animal[] animal5=(Animal[])data3;//编译成功，运行时也不会发生异常。运行时检查将检测到data3的元素类型（ElementType）与目标类型Animal的兼容。
能够将一种类型的数组重新解释为其它类型，这种方式无论在内存使用还是时间上都大大提高了程序的效率。如果从一种类型数组转换为另一种类型数组需要重新构造一个数组的话，显然，程序的性能会受到极大的冲击。
public void Test()
{
string[] data = new string [] { "a", "b", "c", "d", "e" };
SetRange(data, 1, 3, "x" );
}
public void SetRange(object [] array, int start, int count, object value)
{
for (int i=0; i < count; i++)
array[i+start] = value;
}
上面的例子，新的字符串数组是{ "a", "x", "x", "x", "e" }，如果将一个整数作为参数value，将会引起运行时异常，因为引用类型数组在分配数组元素时执行类型检查，所以在array[i+start]=value这一句会发生异常。
下面的例子显示了值类型数组和引用类型数组的一些区别。
Write( new int [] { 1, 2, 3 } ); // 显示 "System.Int32 []"
Write( new string[] {"a", "b", "c" } ); // 显示 "a", "b", "c"
void Write(params object [] args)
{
for (int i=0; i<args.Length; i++)
Console.WriteLine(args[i]);
}
数组变异（array covariance）的不良影响是每次给数组元素分配对象都必须执行类型检查。
你可以使用object[]或者Array来创建一个"通用"数组。多数情况，object[]在性能上要优于Array,因为object[]属于SZ数组，有专门的IL指令来设置或读取数组元素。但是，object[]不适用于值类型数组和多维数组，而Array则可以。
数组元素转换（Array.Copy）
Array.Copy方法可以在复制时转换数组元素。方法可以执行以下转换：
1 将值类型元素装箱到引用类型，比如：将int[]复制到object[]
2 将引用类型元素取消装箱，比如：将上面得到的object[]转换为int[]
3 拓宽转换，比如，可以将int[]复制到double[]，但不能将double[]复制到int[]。
复制引用类型数组时，先进行类型检查，然后执行浅表复制，如果类型不兼容，抛出ArrayTypeMismatchException异常。
public Array Convert(Array array, Type type)
{
Array newArray = Array.CreateInstance(type, array.Length);
Array.Copy(array,0, newArray,0, array.Length);
return newArray;
}
通过反射机制访问内部成员
你可以通过反射机制来访问、调用或者修改ArrayList类的内部成员，不管它们被声明为private、protected或者internal。
下面代码取得ArrayList的内部成员_items：
object[] abc=new Object[5];
ArrayList al=new ArrayList(5);
al.Add("abc");
abc=(object[])al.GetType().GetField("_items",BindingFlags.NonPublic|BindingFlags.Instance).GetValue(al);
Console.WriteLine(abc[0]);
你可以阅读微软公布的Rotor包来了解类的内部成员，也可以使用IL反编译器，比如Reflector或者Anakrino。
数组性能
对数组进行索引一般都要进行范围检查。根据微软的说法，编译器进行了一些特殊的优化来改善遍历数组或者字符串的性能。我们先来比较一个下面三种遍历数组的方案，看看那一种更快。
a是一维int类型数组
1)
int hash = 0;
for (int i=0; i< a.Length; i++)
{
hash += a[i];
}
2)
int hash = 0;
int length = a.length;
for (int i=0; i< length; i++)
{
hash += a[i];
}
3)
foreach (int i in a)
{
hash += i;
}
令人惊讶的是，在目前这个的JIT编译器下，第一个例子是最快的，第三个例子是最慢的。在下一版本JIT编译器，第三个例子将会跟第一个例子具有相同的速度。
为什么第一个例子比第二个例子快呢？这是因为编译器认识 for (int i=0; i<s.length; i++) 这种模式（仅限于字符串和数组）。编译器将会存储数组的长度，这样在每一次遍历时不用调用任何方法（因为JIT编译器可以自动嵌入只包含简单的流程控制的非虚拟方法和不超过32个字节的IL指令，在这里，编译器将数组长度的引用嵌入）。
另外，编译器还消除了每一次循环对s[i]的范围检查，因为i在for条件中已经被限制在0和数组长度之间。在第二个例子中，由于使用一个整数代替了数组长度，编译器就不会认为它是 for (int i=0; i<a.length; i++) 模式（不会假设i在0和数组长度之间），所以每一次循环都会执行一次范围检查。这就是为什么第二个例子要比第一个例子慢。
一些使用数组应该注意的问题
大数组问题
大数组对性能有很大的影响。超出85K的对象被称为大对象，它们被分配在大对象堆。几乎所有的大对象都是数组，有一些是字符串。显然，很少的类包含有那么多的成员使得占用内存超过85K。大对象不能被压缩，同时，它只能在全垃圾回收（包含第2代的垃圾回收）中才能被回收。如果大对象包含了析构函数，那么至少要两次全垃圾回收才能回收它们。全垃圾回收发生的次数一般的是0代垃圾回收的1/100，显然，回收大垃圾对象占用的内存需要经过一段较长的时间。从内存分配角度看，在程序中频繁的分配临时使用的大对象是一个很糟糕的设计，甚至是最差的设计。
构造ArrayList或其他集合类时，为它们指定足够的容量，避免扩大容量时数组复制造成的性能损失
与多维数组相比较，交错数组具有更好的性能，尽量使用交错数组
尽量使用强类型数组，因为强类型数组可以避免装箱，转换，方法调用等带来的性能损失。
