.NET框架未公开的特性 ---------String类

.NET框架未公开的特性 ---------String类

转自：http://www.codeproject.com/csharp/strings.asp

作者原文许多地方只是简要地讲述一下观点，不容易理解，译者为这些观点增加了一些论证，所有的论证都以Rotor包为依据，文中注明了它们在Rotor包中的位置，如果有不妥之处，欢迎指正。

这篇文章对.NET Framework的String类进行深入的分析研究，它提供了String类实现的详细信息，同时对使用String的各种不同使用方式的效率进行了描述。
这里提供的许多信息在MSDN或者其他书籍无法找到，因为微软没有公开它们。
背景知识：
String 是.NET的一种基元类型。CLR和JIT为一些特殊的类作了特殊的处理和优化，String就是其中的一种。其他的包括：其他基元类型，StringBuilder，Array，Type，Enum，Delegate和一些Reflection类，比如MethodInfo。
在.NET 1.0中，所有分配到堆的对象都包含了两个东东：一个对象头（4字节）和一个指向方法表的指针（4字节）。对象头提供有5个位标志，其中一个位标志是为GC保留的，它标识对象是否是“可到达对象“（“可到达对象“是垃圾回收算法里的一个名词，简单的说就是指正在被应用程序使用的对象）。剩余的27个位作为一个索引，被称作syncindex，它指向一个表。这个索引有多种用途：首先，在使用"lock" 关键字时，它用于线程同步；另外，在调用Object.GetHashCode()方法时，它被用作缺省的哈希代码（继承类没有重写Object.GetHashCode()时）。尽管这个索引不能为哈希代码提供最好的分布特性，但是，对于哈希代码的另外一个要求---具有相同值的对象返回相同的哈希代码，它是可以满足的。在对象的整个生存周期，syncindex保持不变。
所有的对象都可以根据对象头计算得到它实际的内存占用，计算的公式如下（摘自Rotor包sscli20020326\sscli\clr\src\vm\object.h）：
MT->GetBaseSize() + ((OBJECTTYPEREF->GetSizeField() * MT->GetComponentSize())
对于大多数对象，它们的大小是固定不变的。String类和Array类（包括Array的继承类）是仅有的两个可变长对象，也就是说它们创建后，对象的长度可以发生变化。
String有点类似OLE BSTRs---以长度数据开头，空字符结尾的Unicode字符数组。下面列出的是String在内部维护的三个字段：
[NonSerialized]private int m_arrayLength;
[NonSerialized]private int m_stringLength;
[NonSerialized]private char m_firstChar;
它们的具体含义如下表所示：

m_arrayLength	这是分配给字符串的实际长度（以字符为单位）。通常创建一个字符串时，m_arrayLength与字符串的逻辑长度(m_stringLength)是相同的。但是，如果使用StringBuilder返回一个字符串，实际长度可能比逻辑长度大。
m_stringLength	这是字符串的逻辑长度，你可以通过String.Length属性获得。出于优化性能的需要，m_stringLength的一些高位被用作标识符，所以String的最大长度要比UInt32.Max小得多（32位操作系统）。这些标识符的其中一些用来指示String是否是简单字符（比如plain ASCII），这样在排序和比较的时候，就不采用复杂的UNICODE算法。
m_firstChar	这是字符串的第一个字符。如果是空字符串的话，这是空字符。

String总是以一个空字符结尾，这一点加强了它与非托管代码和传统的Win32API的互操作性。
String总共占用的内存为：16字节+2字节*字符数+2字节（最后的空字符）。表1中已经讲述，如果使用StringBuilder来创建字符串，那么实际分配的内存将可能比String.Length大。
非常有效率的StringBuilder
与String密切关联的是StringBuilder。虽然StringBuilder被放在System.Text命名空间，但它不是一个平常的类。运行时和JIT编译器对StringBuilder进行了特殊的处理，你想写一个跟它一样有效率的类是不容易的。
StringBuilder在内部维护一个字符串变量---m_StringValue，并且允许直接对它进行修改。默认情况下，m_StringValue的m_arrayLength字段为16。下面是StringBuilder维护的2个内部字段：
internal int m_MaxCapacity = 0;
internal String m_StringValue = null;
它们的具体含义如表2所示：

m_MaxCapacity	StringBuilder的最大容量，它规定了最多可以放置到m_StringValue的字符个数，默认值为Int32.MaxValue。你可以自己规定一个小一点的容量，m_MaxCapacity一旦被指定就不能再更改。
m_StringValue	StringBuilder维护的一个字符串（Jeffrey Richter在《Applied Microsoft .NET Framework Programming》中讲述StringBuilder维护的是一个字符数组，译者认为作为字符数组比较容易理解，但从Rotor包的源代码看，实际维护的应该是一个字符串

让我们先看一下StringBuilder的一个Append方法的相关代码（摘自Rotor包sscli20020326\sscli\clr\src\bcl\system\text\stringbuilder.cs）：
public StringBuilder Append(String value) {
//If the value being added is null, eat the null and return.
if (value==null) {
return this;
}
int tid;
// hand inlining of GetThreadSafeString
String currentString = m_StringValue;
tid = InternalGetCurrentThread();
if (m_currentThread != tid)
currentString = String.GetStringForStringBuilder(currentString, currentString.Capacity);

int currentLength = currentString.Length;
int requiredLength = currentLength + value.Length;
if (NeedsAllocation(currentString,requiredLength)) {
String newString = GetNewString(currentString,requiredLength);
newString.AppendInPlace(value,currentLength);
ReplaceString(tid,newString);
} else {
currentString.AppendInPlace(value,currentLength);
ReplaceString(tid,currentString);
}
return this;
}
private bool NeedsAllocation(String currentString,int requiredLength) {
//<= accounts for the terminating 0 which we require on strings.
return (currentString.ArrayLength<=requiredLength);
}
private String GetNewString(String currentString, int requiredLength) {
int newCapacity;
requiredLength++; //Include the terminating null.
if (requiredLength > m_MaxCapacity) {
throw new ArgumentOutOfRangeException(Environment.GetResourceString("ArgumentOutOfRange_NegativeCapacity"),
"requiredLength");
}
newCapacity = ( currentString.Capacity)*2; // To force a predicatable growth of 160,320 etc. for testing purposes
if (newCapacity<requiredLength) {
newCapacity = requiredLength;
}
if (newCapacity> m_MaxCapacity) {
newCapacity = m_MaxCapacity;
}
if (newCapacity<=0) {
throw new ArgumentOutOfRangeException(Environment.GetResourceString("ArgumentOutOfRange_NegativeCapacity"));
}
return String.GetStringForStringBuilder( currentString, newCapacity);
}
我们从上面代码可以知道，添加新字符时，如果构造的字符串长度超出m_StringValue的容量（m_arrayLength），那么将会新创建一个字符串。新字符串容量一般是原来的两倍（如果不超出m_MaxCapacity 的话）。

让我们再看一下StringBuilder.ToString()的源代码（摘自Rotor包sscli20020326\sscli\clr\src\bcl\system\text\stringbuilder.cs）：
public override String ToString() {
String currentString = m_StringValue;
int currentThread = m_currentThread;
if (currentThread != 0 && currentThread != InternalGetCurrentThread()) {
return String.InternalCopy(currentString);
}

if ((2 * currentString.Length) < currentString.ArrayLength) {
return String.InternalCopy(currentString);
}

currentString.ClearPostNullChar();
m_currentThread = 0;
return currentString;
}
// Used by StringBuilder to avoid data corruption
internal static String InternalCopy (String str) {
int length = str.Length;
String result = FastAllocateString(length);
FillStringEx(result, 0, str, length); // The underlying's String can changed length is StringBuilder
return result;
}
使用StringBuilder.ToString()返回一个字符串时，实际的字符串被返回（也就是说该方法返回的是StringBuilder内部维护的字符串字段 （m_StringValue）的引用，而不是创建新字符串）。如果StringBuilder的容量（ArrayLength）超过实际字符数的两倍以上，StringBuilder.ToString()将返回一个字符串的简洁版本。在调用了StringBuilder. ToString()方法之后，再次修改StringBuilder将会产生一个复制动作，它将创建一个新的字符串；这时被修改的是新的字符串，如此，原来已经返回的字符串才不会发生改变。
除了字符串使用的内存外，StringBuilder额外开销了16个字节，但是，同样的StringBuilder对象可以被使用多次来生成多个字符串，这样StringBuilder仅仅带来一次额外开销。
我们可以看到，使用StringBuilder是非常有效率的。
其他的性能技巧：
1> 当使用"+"连接字符串，比如：“a”+"b"+"c"，编译器将会调用Concat(a,b,c)方法，这样可以消除额外的大量的字符串拷贝（这里有一个具体的讨论）。
2> 使用StringBuilder比字符串连接要更快
尽量减少垃圾回收
垃圾回收器
使用StringBuilder来创建字符串能显著的减少内存分配。需要注意的是，许多的测试都表明：一次全垃圾回收也不过只需要几分之一秒---几乎无法察觉的时间。所以，在未对程序进行剖析就一味地考虑避免垃圾回收是不可取的，可另一方面，频繁的垃圾回收有可能对性能造成损害。运行.NET程序有时会遇到一些不可解释的的停滞，很难判定这究竟是JIT编译器、垃圾回收器还是其他因素造成的。以前的一些程序（比如Windows shell，Word还有IE）也有类似的停滞。
.NET使用3个代来回收内存，这种做法基于一种假设：越是新分配的内存，回收越频繁；相反，回收越不频繁。0代是最年轻的代，结束一次0代的垃圾回收后，幸存者将被移入1代；同样的，结束1代的垃圾回收后，幸存者将被移入2代。通常垃圾回收只发生在0代。
根据微软的说法，执行一次0代垃圾回收所需的时间相当于一个页面错误---0-10毫秒；1代垃圾回收需要10-30毫秒，2代的垃圾回收需要看工作环境。另外，我自己的分析表明：0代的垃圾回收次数要比1、2代多出10-100倍。
Jeffrey Richter写的《Applied Microsoft .NET Framework Programming》里提到：CLR初始化时，会为3个代选择不同的阀值，分别是0代256Kb，1代2Mb，2代10Mb。可是，我自己对Rotor包CLI部分的研究却是另外一个结果（下面的代码来自Rotor包sscli20020326\sscli\clr\src\vm\gcsmp.cpp）：0代800Kb，1代1Mb。当然，这些是未公开的，如果更改了是不会做出书面说明的。这些初始值会根据实际程序的内存分配自动调整，如果0代的内存很少被回收（很多被移到1代），那么0代的阀值将会增大。
void gc_heap::init_dynamic_data ()
{
dynamic_data* dd = dynamic_data_of (0);
dd->current_size = 0;
dd->promoted_size = 0;
dd->collection_count = 0;
dd->desired_allocation = 800*1024;
dd->new_allocation = dd->desired_allocation;

dd = dynamic_data_of (1);
dd->current_size = 0;
dd->promoted_size = 0;
dd->collection_count = 0;
dd->desired_allocation = 1024*1024;
dd->new_allocation = dd->desired_allocation;

//dynamic data for large objects
dd = dynamic_data_of (max_generation+1);
dd->current_size = 0;
dd->promoted_size = 0;
dd->collection_count = 0;
dd->desired_allocation = 1024*1024;
dd->new_allocation = dd->desired_allocation;
}
差强人意的String类方法
String类提供的许多方法经常产生不必要的内存分配，这些增加了垃圾回收的频率。
举个例子，ToUpper()方法或者ToLower方法将产生一个新的字符串，不管字符串是否发生了改变。一个更有效率的方法应该是对原来的字符串进行修改并返回原来的字符串。同样的，Substring()方法也是返回一个新字符串，尽管返回的是整个字符串或是空字符串。
.NET类库有数量众多的隐藏的内存分配，要避免这些是很困难的。例如，数值类型（比如int,float）格式化为字符串时（通过String.Format或者Console.WriteLine），一个新的隐藏的字符串被创建。这种情况，我们可以写一段自己的代码进行格式化，你可以控制自己的代码不让它产生新的字符串。显然，写这样一段代码是可能的，但同时更是困难的。
.NET类库的其他部分也暴露了类似的低效率。在Widows Forms类库，Control的Text属性几乎总是返回一个新字符串。这也许是可以理解的，因为属性不能被储藏，所以它必须调用Windows API函数GetWindowText()来取得控件的值。
GDI+是垃圾回收器最糟糕的滥用者，因为每调用一次MeasureText或者DrawText就会创建一个新字符串。
一个比较好的String类方法是GetHashCode()，它考虑了字符串的每一个字符来产生一个整数值，产生的值非常好地平均分布在int的存储范围。
String类的替代方案
为了减少垃圾回收器的压力，你可以采用下面的方案来代替String类：
1) 基于栈的字符数组
char *array = stackalloc char[arraysize ];
2) 固定大小的字符串结构
[StructLayout(LayoutKind.Explicit, Size=514)]
public unsafe struct Str255
{
[FieldOffset(0)] char start;
[FieldOffset(512)] byte length;

#region Properties
public int Length
{
get { return length; }
set
{
length = Convert.ToByte(value);
fixed(char *p=&start) p[length] = '\0';
}
}

public char this[int index]
{
get
{
if (index<0 || index>=length)
throw(new IndexOutOfRangeException());
fixed(char *p=&start)
return p[index];
}
set
{
if (index<0 || index>=length)
throw(new IndexOutOfRangeException());
fixed(char *p=&start)p[index] = value;
}
}
#endregion
}
Str255是一个栈分配的值类型，它对字符串进行操作不会对GC造成压力。它可以处理255个字符，包括一个长度字节。
指向这一结构的引用可以直接传递给一个Windows API调用，因为结构的开始是C-string的第一个字符。当然，可以写一些另外的方法来编辑字符串，不过写的时候需要注意：必须保证字符串是空字符结尾（为了与Windows兼容）。
为了让其他CLR方法可以使用它，需要写一个转换程序将这个结构转化为一个.NET字符串（好像StringBuilder.ToString()方法一样）。如果使用它来创建一个.NET字符串，它比StringBuilder优越之处在于：Str255需要更少的内存分配。
3) “原地”修改字符串
public static unsafe void ToUpper(string str)
{
fixed (char *pfixed = str)
for (char *p=pfixed; *p != 0; p++)
*p = char.ToUpper(*p);
}
上面的例子讲述了如何通过使用unsafe指针来修改一个不可变的字符串。这个方法有着很高的效率，一个例子就是与str.ToUpper()的比较，str.ToUpper()返回一个新的字符串，不管字符串内容是否实际发生了改变，都会创建一个新的字符串。而上面的代码，只是对原来字符串进行修改。
fixed关键字将字符串固定在堆上，这样避免在垃圾回收时移动它，同时也允许字符串的地址可以被转化为一个指针，指针指向字符串的开始位置。
既然字符串实际上能被更改，为什么要强调.NET字符串是"固定不变"的呢？有两个原因，第一，操作"固定不变"的字符串不会存在线程同步的问题；其次，"固定不变"的字符串允许多个引用指向同一个字符串对象，这可以减少系统中字符串的数目，降低内存开销。
通过修改字符串对象的内部字段m_arrayLength，字符串的长度也可以改变。可是，这样做是非常危险的，CLR将来的实现方式或者非Windows系统的实现方式可能会改变字符串隐含的实现方式。
使用这种方法修改字符串有一点需要注意，m_stringLength的高字位包含一些标志，它们是不能变动的。其中一些标志与字符串的内容有关，比如标示字符串是否只包含7位ASCII字符。
消除范围检查
对数组或者字符串进行索引一般都要进行范围检查。根据微软的说法，编译器进行了一些特殊的优化来改善遍历数组或者字符串的性能。我们先来比较一个下面三种遍历字符串的方案，看看那一种更快。
1)
int hash = 0;
for (int i=0; i< s.Length; i++)
{
hash += s[i];
}
2)
int hash = 0;
int length = s.length;
for (int i=0; i< length; i++)
{
hash += s[i];
}
3)
foreach (char ch in s)
{
hash += s[i];
}
令人惊讶的是，在目前这个的JIT编译器下，第一个例子是最快的，第三个例子是最慢的。在下一版本JIT编译器，第三个例子将会跟第一个例子具有相同的速度。
为什么第一个例子比第二个例子快呢？这是因为编译器认识 for (int i=0; i<s.length; i++) 这种模式（仅限于字符串和数组）。字符串是固定不变的（它的长度是固定的），编译器将会存储它的长度，这样在每一次遍历时不用调用任何方法（因为JIT编译器可以自动嵌入只包含简单的流程控制的非虚拟方法和不超过32个字节的IL指令，在这里，编译器将字符串长度的引用嵌入）。
另外，编译器还消除了每一次循环对s[i]的范围检查，因为i在for条件中已经被限制在0和字符串长度之间。在第二个例子中，由于使用一个整数代替了字符串长度，编译器就不会认为它是 for (int i=0; i<s.length; i++) 模式（不会假设i在0和字符串长度之间），所以每一次循环都会执行一次范围检查。这就是为什么第二个例子要比第一个例子慢。
下面的方法比第一个例子还要快（我没有证实它）。
fixed (char *pfixed = s)
{
for (char *p = pfixed; *p; p++)
hash += *p++;
}
高效率的字符串switch语句
c#支持对字符串的switch语句，它采用了一种非常有效的机制。
先看一下下面的代码：
using System;
public class abc
{
static void Main(string[] args)
{
if (args.Length>0)
{
switch (args[0])
{
case "a":
Console.WriteLine("a");
break;
default:
break;
}
}
}
}
这是代码的IL
.method private hidebysig static void Main(string[] args) cil managed
{
.entrypoint
// Code size 52 (0x34)
.maxstack 2
.locals init (string V_0)
IL_0000: ldarg.0
IL_0001: ldlen
IL_0002: conv.i4
IL_0003: ldc.i4.0
IL_0004: ble.s IL_0033
IL_0006: ldstr "a"
IL_000b: leave.s IL_000d
IL_000d: ldarg.0
IL_000e: ldc.i4.0
IL_000f: ldelem.ref
IL_0010: dup
IL_0011: stloc.0
IL_0012: brfalse.s IL_0031
IL_0014: ldloc.0
IL_0015: call string [mscorlib]System.String::IsInterned(string)
IL_001a: stloc.0
IL_001b: ldloc.0
IL_001c: ldstr "a"
IL_0021: beq.s IL_0025
IL_0023: br.s IL_0031
IL_0025: ldstr "a"
IL_002a: call void [mscorlib]System.Console::WriteLine(string)
IL_002f: br.s IL_0033
IL_0031: br.s IL_0033
IL_0033: ret
} // end of method abc::Main

CLR自动维护一个名为“拘留池”(intern pool) 的哈希表，它包含在程序中声明的每个唯一字符串常量的单个实例，以及以编程方式添加的 String 的任何唯一实例。现在来看上面的IL代码，首先IL调用了IsInterned方法，传递在switch语句中指定的字符串args[0]。如果IsInterned返回null，表明args[0]不与case的字符串的任何一个匹配，转而执行default代码。如果IsInterned在“拘留池”中找到了args[0]，它将返回哈希表中的字符串对象的引用，然后将该引用与每个case语句指定的字符串的地址进行比较。比较地址要比比较字符串中的所有字符快得多，代码很快就可以判断出应该执行哪个case语句。
上面所说的仅指有少量的case的情形，如果case数量很大，那么编译器将生成一个哈希表，这个哈希表的加载因子是0.5，初始容量是case数量的两倍（实际上，哈希表的比率在1/3左右，因为哈希表会将元素与存储桶的比率维持在0.72。0.72是速度和内存得最优平衡，这是由微软的性能测试得到的数字）。case语句的字符串将会被添加到这个哈希表中，其他的比较步骤没有什么区别。