字符串未记录

引言

这是一篇深入、幕后了解公共语言运行时 (CLR) 和 .NET Framework 中字符串实现的文章。本研究提供了字符串实现的详细信息，并描述了使用字符串的有效和无效方法。

我计划开发一系列文章，探索 C# 和框架中各种基本功能的底层实现，本文是第一篇。如果 Code Project 社区发现这些信息有用，并能对本文提出任何额外建议。

这里呈现的大部分信息在其他地方都找不到，MSDN、任何书籍或任何文章中都没有。我的目的是理解如何有效地使用 C# 来开发严肃的商业应用程序。我曾是 Microsoft Excel 的开发者，现在已经创办了自己的软件公司，从事开发采用人工智能的应用程序。

背景

.NET 世界中的字符串，如您所知，是一个基本类型。它们是 CLR 和 JIT 编译器密切了解的一小组独占对象之一。其他对象当然包括原始数据类型、StringBuilder、Array、Type、Enum、Delegates 以及其他一些Reflection 类，如 CLR 中的MethodInfo。

.NET 1.0 版本中，每个堆分配的对象都包含一个 4 字节的对象头和指向方法表的 4 字节指针。4 字节对象头提供五个位标志，其中一个标志保留给垃圾收集器，用于标记对象是否可访问且未被释放。剩余位指向一个 27 位索引，称为 syncindex，它可能指向另一个表。此索引有多种用途：顾名思义，它用于同步，当使用 "lock" 关键字时。它也用作Object.GetHashCode()的默认哈希码。它不为哈希码提供最佳的分布属性，但它满足引用相等性哈希码的最低要求。syncindex 在对象生命周期内保持不变。

String类和Array类（包括派生类）是仅有的两个可变长度对象。

内部，字符串类似于 OLE BSTRs——一个 Unicode 字符数组，前面是长度数据，后面是一个终止的 null 字符。字符串会占用额外的空间，因为它按顺序包含以下成员。稍后，我将解释如何访问和更改其中一些内部变量，使用或不使用反射。

变量	类型	描述
m_arrayLength	int	这是为字符串分配的实际字符数。对于正常创建的字符串，这等于逻辑字符串长度 + 1（用于 null 字符），但对于 StringBuilder 返回的字符串，实际长度可能达到字符串长度的两倍。
m_stringLength	int	这是字符串的逻辑长度，即 String.Length 返回的值。 由于使用了许多高位来附加标志以提高性能，因此对于 32 位系统，字符串的最大长度被限制在一个远小于UInt32.Max的限制。其中一些标志表示字符串包含简单的字符，如纯 ASCII，不需要调用复杂的 UNICODE 算法进行排序和比较测试。
m_firstChar	char	这是字符串的第一个字符，或空字符串的 null 字符。

字符串总是以 null 字符结尾，即使字符串包含嵌入的 null 字符也是有效的。这便于与非托管代码和传统的 Win32 API 互操作。

总而言之，字符串占用 16 字节内存 + 2 字节/分配的字符 + 2 字节用于终止的 null 字符。如表中所示，如果用于创建字符串，则分配的字符数最多可以是字符串长度的两倍。

极其高效的 StringBuilder

与String密切相关的是StringBuilder类。虽然StringBuilder位于System.Text命名空间中，但它不是一个普通类，而是由运行时和 JIT 编译器特殊处理的类。因此，可能无法编写一个与它一样高效的等效StringBuilder类。

StringBuilder将构造一个字符串对象（您认为它是不可变的），并直接修改它。默认情况下，StringBuilder 会创建一个 16 个字符的字符串。（然而，使用奇数 15 可能更合适，因为字符串的分配空间包含一个 null 字符，浪费了一个本不会被使用的字符，因为创建的对象在 4 字节边界上对齐。）

变量	类型	描述
m_MaxCapacity	int	字符串的最大容量。
m_currentThread	int	创建字符串的线程 ID。
m_StringValue	字符串	要修改的实际字符串。

如果字符串需要增长超出其容量，将构造一个新字符串，其容量为先前容量的两倍或新的所需大小中的较大者，并受 maxcapacity 约束。这种方法需要 O(3n) 的线性时间。通过固定量而不是百分比增长字符串的替代方法会导致二次方时间性能，O(n^2)。

当StringBuilder.ToString()返回字符串时，将返回实际正在修改的字符串。然而，如果字符串的容量超过字符串长度的两倍，StringBuilder.ToString()将构造一个紧凑的新版本字符串。多次调用ToString()将返回相同的字符串。

在ToString()之后修改StringBuilder会导致写时复制；会使用一个全新的字符串副本，以避免更改先前返回的不可变字符串。

StringBuilder 占用 16 字节，不包括字符串占用的内存。然而，同一个StringBuilder对象可以多次重用以创建多个字符串，方法是将 Length 设置为 0，Capacity 设置为所需大小，因此StringBuilder的成本只产生一次。

如您所见，使用 StringBuilder 创建字符串是一项极其高效的操作。

其他性能技巧

• 使用 + 连接字符串时，例如 " a + b + c "，编译器将调用具有相应参数数量的Concat(a,b,c)版本，从而消除多余的字符串副本。
• 当然，使用StringBuilder比连接字符串更快。
• 如果您事先知道字符串的容量，可以在构造函数中设置它，以避免不必要的复制。如果还有一个上限（MaxCapacity），也可以在构造函数中设置它——但只能在构造函数中设置。

最小化垃圾回收

垃圾收集器

使用StringBuilder构造字符串可以显著减少分配。然而，一些快速测试表明，即使是完整的垃圾回收也可以在不到一秒的时间内完成——这是无法察觉的时间。在分析应用程序之前，避免垃圾回收可能不值得。另一方面，频繁的垃圾回收可能会损害性能。我有时会注意到 .NET 应用程序中短暂的未解释暂停；很难说这是否是由于 JIT 编译器、垃圾收集器或其他任何因素。许多老式应用程序，如 Windows shell、Word 和 Internet Explorer 也有未解释的暂停。

.NET 使用一种三代方法来收集内存，其依据是新分配的内存往往比旧分配的内存更容易被释放，而旧分配的内存往往更永久。Gen 0 是最年轻的一代，在垃圾回收后，任何幸存者都会进入 Gen 1。同样，Gen 1 回收中的任何幸存者都会进入 Gen 2。通常，垃圾回收只发生在 Gen 0，并且仅当达到某个限制后才会发生。

在垃圾回收下分配堆内存的成本低于 C 运行时堆分配器的成本。直到内存耗尽，分配每个新对象的成本就是递增指针——这接近于推进栈指针的性能。根据微软的说法，第 0 代垃圾回收的成本相当于页面错误——从 0 到 10 毫秒。第 1 代回收的成本为 10 到 30 毫秒，而第 2 代回收取决于工作集。我自己的分析表明，第 0 代回收的频率是其他两代的 10-100 倍。

Jeffrey Richter 的一本书建议第 0 代的假设限制为 250Kb，第 1 代为 2Mb，第 2 代为 10Mb。然而，我对 Rotor 共享源 CLI 的调查表明，阈值似乎最初是第 0 代的 800Kb 和第 1 代的 1Mb；当然，这些是未公开的，并且可能发生变化。阈值会根据实际程序分配动态自动调整。如果在第 0 代中很少有内存被释放并幸存到第 1 代，则阈值会扩展。

低效的字符串函数

String 类提供的许多函数经常产生不必要的分配，从而增加了垃圾回收的频率。

例如，ToUpper和ToLower函数会生成一个新的已分配字符串，无论字符串是否实际发生了更改。更高效的实现应该返回原始的不可变字符串。同样，Substring也会返回一个新字符串，即使返回的是整个字符串或空字符串。在后一种情况下，返回String.Empty会更优化。

很难，如果不是不可能，来逃避类库中发生的众多隐藏分配。例如，每当任何数字数据类型（如 int 或 float）被格式化为字符串时（例如，通过String.Format或Console.WriteLine），都会创建一个新的隐藏字符串。在这种情况下，可以编写我们自己的代码来格式化字符串，但这很不方便。

当使用带值类型的Console.WriteLine时，该值类型对象会被装箱然后转换为字符串，从而导致两次分配。例如，Console.WriteLine(format, myint)实际上等同于Console.WriteLine(format, ((object)myint).ToString())。通过显式调用ToString，可以使用Console.WriteLine(format, myint.ToString())来节省一次额外的分配。由于WriteLine包含常见原始类型的重载，所以它更多地是针对自定义值类型或调用带多个参数的WriteLine。

库的其他部分也存在这些低效之处。例如，在 Windows Forms 库中，Control Text 属性始终返回一个新的字符串；这可能可以理解，因为该属性可能未被缓存，因此必须调用 Windows API 函数GetWindowText来检索控件的值。

GDI+ 是垃圾收集器的最大滥用者，因为每次调用MeasureText或DrawText时都必须构造一个新的字符串。

一个好的字符串函数是GetHashCode，它生成一个分布非常好的整数代码，并考虑了代码中的每个字符。

直接修改字符串

1) 字符串的就地修改

public static unsafe void ToUpper(string str)
{
    fixed (char *pfixed = str)
    for (char *p=pfixed; *p != 0; p++)
        *p = char.ToUpper(*p);
}

上面的示例演示了如何通过使用不安全指针来更改不可变字符串。通过这种方法获得的效率的一个好例子是str.ToUpper()，它返回一个新构造的字符串，该字符串是原始字符串的大写版本。无论是否进行了更改，都会创建一个全新的字符串；而使用上面的代码，相同的字符串会被就地修改。

fixed关键字将字符串固定在堆上，使其在垃圾回收期间无法移动，并允许将字符串的地址转换为指针。新地址指向字符串的开头（或者如果包含索引，如&str[index]，则指向由索引引用的位置），该字符串保证以 null 结尾。

下面的函数提供了一套更完整的函数，用于在不使用反射的情况下修改字符串。

public static unsafe int GetCapacity(string s)
{
    fixed(char *p = s)
    {
        int *pcapacity = (int *)p - 2;
        return *pcapacity;
    }    
}

public static unsafe int GetLength(string s)
{
    // This function is redundant, because it accomplishes 
    // the same role as s.Length
    // but it does demonstrate some of the precautions 
    // that must be taken to 
    // recover the length variable
    fixed(char *p = s)
    {
        int *plength = (int *)p - 1;
        int length = *plength & 0x3fffffff;
        Debug.Assert(length == s.Length);
        return length;
    }
}

public static unsafe void SetLength(string s, int length)
{
    fixed(char *p = s)
    {
        int *pi = (int *)p;
        if (length<0 || length > pi[-2])
            throw( new ArgumentOutOfRangeException("length") );
        pi[-1] = length;
        p[length] = '\0';
    }
}

public static unsafe string NewString(int capacity)
{
    return new string('\0', capacity);
}

public static unsafe void SetChar(string s, int index, char ch)
{
    if (index<0 || index >= s.Length)
        throw( new ArgumentOutOfRangeException("length") );
    fixed(char *p = s)
        p[index] = ch;
}

修改值确实会更改字符串。如果字符串可以被更改，那么它们为什么是不可变的呢？字符串不可变的事实使它们可以像普通整数一样轻松地传递。字符串可以初始化为 null，并可以在一个结构到另一个结构之间进行复制，而无需使用复杂的写时复制机制。

容量是指字符串的数组长度，它不能改变。但是，可以通过引用字符串之前的 32 位整数来更改逻辑字符串长度。然而，检查或修改此值需要谨慎。字符串长度必须始终小于字符串的数组长度。高两位包含标志，指示字符串是否完全由 7 位 ASCII 文本组成，如果是，则可以快速排序和比较。这两位的值为零表示状态不确定。读取长度值时，长度必须与 0x3fffffff 进行按位与操作，以避免读取这两个位。修改长度是可以的，只要高两位是清除的，这通常就是这种情况。

未来实现或当前的非 Windows CLR 实现可能会更改字符串的底层实现。幸运的是，您构建时使用的运行时版本将在您的可执行文件启动时被选中。

System.Reflection 还允许程序员访问隐藏的字段、成员和属性——是的，即使是标记为内部和私有的。这种基于反射的方法比上述手动方法慢得多，但不需要不安全代码，并且在运行时版本更改时应该更健壮。该行演示了通过反射更改不可变字符串长度的能力。

typeof(string).GetField("m_stringLength",
BindingFlags.NonPublic|BindingFlags.Instance).SetValue(s, 5);

我编写了一个简短的测试函数来演示上述各种字符串函数的用法。

/// <SUMMARY>

/// The main entry point for the application.
/// </SUMMARY>

[STAThread]
static unsafe void Main(string[] args)
{
    StringBuilder sb = new StringBuilder();
    sb.Append("Good morning");

    string test = "How are you";
    SetLength(test, 5);
    SetChar(test, 1, 'a');

    string [] sarray = new String[] { String.Empty, "hello", "goodbye", 
                                      sb.ToString(), test};
    foreach (string s in sarray)
    Console.WriteLine("'{0}' has capacity {1}, length {2}", s,
        GetCapacity(s),
        GetLength(s));

    Console.ReadLine();
}

上面的测试代码产生了以下输出，证明了字符串实际上可以被轻松更改。

'' has capacity 1, length 0
'hello' has capacity 6, length 5
'goodbye' has capacity 8, length 7
'Good morning' has capacity 17, length 12
'Haw a' has capacity 12, length 5

2) 检索 StringBuilder 中的字符串工作副本

对于胆小的人来说，他们更喜欢不那么亲密、不那么底层的字符串交互。可以恢复StringBuilder正在使用的实际字符串。通过反射，我们可以访问隐藏的内部 m_StringValue 变量。

string test = (string) sb.GetType().GetField("m_StringValue", BindingFlags.NonPublic|BindingFlags.Instance).GetValue(sb);

返回的字符串 "test" 将继续反映 StringBuilder 中的更改，除非修改所需的容量超过了字符串的容量。在这种情况下，StringBuilder 将放弃原始字符串并构造一个全新的、更大的工作字符串。

一个需要注意的地方是，StringBuilder永远不会缩小字符串的容量，除非调用ToString。ToString基本上确保当前字符串长度至少是容量的一半。没有它，当前字符串只会增长，永远不会缩小，始终保持在其峰值大小。

未来的文章 "UNDOCUMENTED 对象" 将演示如何在不使用反射的情况下访问隐藏成员。

字符串替代方案

避免影响垃圾回收器来构造字符串的一种方法是执行以下操作之一：

所有这些替代方案都使用不安全的功能，如果您正在编写独立的应用程序，这些功能没有实际影响。请记住，托管 C++ 是不安全的。我并不真正推荐这些方法，但为了让您了解情况而提及它们。

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 是一个基于堆栈分配的值类型，它允许在不影响垃圾收集器的情况下执行字符串操作。它可以处理最多 255 个字符，并包含一个长度字节。

该结构的引用可以直接传递给 Windows API 调用，因为结构体的开头是 C 字符串的第一个字符。当然，需要通过编辑字符串来编写额外的函数。还需要仔细注意确保字符串以 null 结尾，以便与 Windows 互操作。

此外，还需要一个转换例程将该结构转换为 .NET 字符串，以便其他 CLR 函数可以使用它。如果使用它来创建 .NET 字符串，它在某一方面将优于 StringBuilder：Str255 需要更少的分配。

范围检查消除

索引数组或字符串通常包含范围检查。根据微软的说法，编译器会执行一项特殊的优化，以提高迭代数组或字符串的性能。首先，比较以下三种迭代字符串的方法。哪种最快？

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 迭代

foreach (char ch in s)
{
    hash += s[i];
}

令人惊讶的是，在 NET v1.0 的 JIT 编译器中，第一个示例，即重复调用string.Length，实际上产生了最快的代码，而第三个 "foreach" 示例产生了最慢的代码。在编译器更高版本中，foreach示例将针对字符串进行特殊处理，以提供与示例 1 相同的性能或更好的性能。

为什么示例 1 比示例 2 快？这是因为编译器识别出字符串和数组的模式 for (int i=0; i<s.length; i++)。字符串是不可变的；它们的长度是恒定的。由于字符串和数组的长度都是固定的，编译器会简单地将长度存储起来，这样在每次迭代时就不会调用函数。（JIT 编译器会自动内联由简单控制流组成的非虚方法调用，并且 IL 指令少于 32 字节，实际上可能会内联对字符串长度的引用。）

此外，编译器会消除循环中所有 s[i] 实例的范围检查测试，因为在 for 条件中，i 保证在 0 <= i < length的范围内。通常，对字符串的任何索引都会执行范围检查；这就是为什么试图通过存储长度变量在示例 2 中节省时间实际上比示例 1 产生更慢的代码。

注意：在 1.1 版本中，C# 团队已对foreach进行了特殊处理，使其行为类似于第一个循环，因此应该没有区别。

还有第四种方法应该更快，尽管我没有验证过；但是，它确实需要生成不安全代码。

fixed (char *pfixed = s)
{
     for (char *p = pfixed; *p; p++)
       hash += *p++;
}

高效字符串开关

C# 支持字符串开关。在这样做时，它使用一种高效的机制进行开关。

    
public void Test(string test)
{
    
     switch(test)
     {
    case "a": break;
    case "b": break;
    ...
     }
}

对于少量情况，编译器将生成查看内部字符串哈希表的代码。编译器将首先调用 String.IsIntern 对开关值进行检查。String.IsIntern 实际上返回一个字符串而不是布尔值，失败时返回 null，成功时返回字符串的已驻留值。

case 标签中的每个字符串常量在编译时都是已知的，因此保证是已驻留的。此时，编译器将使用引用相等性将字符串的已驻留值与每个字符串常量进行比较。

    
public void Test(string test)
{
  object interned = IsInterned(test);
  if (interned != null)
  {
    if (interned == "a")
    {
        ; // Handle case a
    }
    else if (interned == "b")
    {
        ; // Handle case b
    }
  }
}

这是此代码的示例 IL。

.method public hidebysig instance void  Test(string test) cil managed
{
  // Code size       34 (0x22)
  .maxstack  2
  .locals ([0] string CS$00000002$00000000)
  IL_0000:  ldstr      "a"
  IL_0005:  leave.s    IL_0007
  IL_0007:  ldarg.1
  IL_0008:  dup
  IL_0009:  stloc.0
  IL_000a:  brfalse.s  IL_001f
  IL_000c:  ldloc.0
  IL_000d:  call       string [mscorlib]System.String::IsInterned(string)
  IL_0012:  stloc.0
  IL_0013:  ldloc.0
  IL_0014:  ldstr      "a"
  IL_0019:  beq.s      IL_001d
  IL_001b:  br.s       IL_001f
  IL_001d:  br.s       IL_0021
  IL_001f:  br.s       IL_0021
  IL_0021:  ret
} 

如果 case 的数量很大（在本例中为 14 个），编译器将生成一个稀疏哈希表，其负载因子为 0.5，容量为两倍。[[ 实际上，负载因子为 0.5 的哈希表生成的容量是原容量的两倍，因为Hashtable会尝试确保表中已用桶与可用桶的比例最多为（负载因子 * 0.72），其中默认负载因子为 1。魔术数字 0.72 代表了微软性能测试确定的平衡速度和内存的最佳比例。]]

哈希表会将每个字符串映射到一个对应的索引，如 C# 说明中编译器生成的示例所示。

    
private static Hashtable CompilerGeneratedHash;

public void Test(string test)
{
    if (CompilerGeneratedVariable==null)
    {
        CompilerGeneratedHash=new Hashtable(28, 0.5);
        CompilerGeneratedHash.Add("a", 0);
        CompilerGeneratedHash.Add("b", 1);
        ...
    }
    object result = CompilerGeneratedHash[test];
    if (result != null)
    {
        switch( (int) result )
        {
            case 0:
            case 1:
            ...
        }
    }
}

实际的 IL 版本如下所示。

.method public hidebysig instance void  Test(string test) cil managed
{
  // Code size       373 (0x175)
  .maxstack  4
  .locals ([0] object CS$00000002$00000000)
  IL_0000:  volatile.
  IL_0002:  ldsfld     class [mscorlib]
    System.Collections.Hashtable '<PRIVATEIMPLEMENTATIONDETAILS>
'
::'$$method0x6000106-1'
  IL_0007:  brtrue     IL_0100
  IL_000c:  ldc.i4.s   28
  IL_000e:  ldc.r4     0.5
  IL_0013:  newobj     instance void [mscorlib]
System.Collections.Hashtable::.ctor(int32, float32)
  IL_0018:  dup
  IL_0019:  ldstr      "a"
  IL_001e:  ldc.i4.0
  IL_001f:  box        [mscorlib]System.Int32
  IL_0024:  call       instance void [mscorlib]
System.Collections.Hashtable::Add(object, object)..... object)
  IL_00f9:  volatile.
  IL_00fb:  stsfld     class [mscorlib]
    System.Collections.Hashtable '<PRIVATEIMPLEMENTATIONDETAILS>
'
::'$$method0x6000106-1'
  IL_0100:  ldarg.1
  IL_0101:  dup
  IL_0102:  stloc.0
  IL_0103:  brfalse.s  IL_0172
  IL_0105:  volatile.
  IL_0107:  ldsfld     class [mscorlib]
    System.Collections.Hashtable '<PRIVATEIMPLEMENTATIONDETAILS>
'
::'$$method0x6000106-1'
  IL_010c:  ldloc.0
  IL_010d:  call       
instance object [mscorlib]System.Collections.Hashtable::get_Item(object)
  IL_0112:  dup
  IL_0113:  stloc.0
  IL_0114:  brfalse.s  IL_0172
  IL_0116:  ldloc.0
  IL_0117:  unbox      [mscorlib]System.Int32
  IL_011c:  ldind.i4
  IL_011d:  switch     ( 
                        IL_0158,
                        IL_015a,
                        IL_015c,
                        IL_015e,
            ....
                        IL_0170)
  IL_0156:  br.s       IL_0172
    ....
  IL_0174:  ret
}

Whidbey

下一版 C# 编译器将引入一系列对字符串的改进。字符串将具有改进的哈希函数，具有更好的分布属性，因此您不想依赖当前行为。

字符串类中的其他新函数包括：静态方法IsNullOrEmpty，用于在不变文化中转换为小写或大写的函数（ToLowerInvariant、ToUpperInvariant），以及其他字符串规范化函数（Normalize、IsNormalized）。Hashtables现在直接在构造函数中支持多种不区分大小写的字符串搜索形式。

这些功能已在 Whidbey 的当前预发布版本中提供，但在 beta 版之前可能还会有更多更改。

结论

我的字符串讨论到此为止。将来，我将继续更新本文，提供新的源代码和实际基准测试。请务必关注此页面的更新版本。

由于本文引起的热情，我将继续开发更多 "UNDOCUMENTED" 文章。我的下一篇文章将讨论数组和集合的实现。希望在完成该系列后发表几十篇文章。

我的来源包括微软出版的各种书籍、共享源 CLI、MSDN、杂志文章、采访、内部消息来源、开发者会议演讲，以及经典的反汇编。所有这些幕后信息都需要一些研究和获取工作，所以，如果您喜欢这篇文章，别忘了投票。

版本历史

版本	描述
2003年12月26日	更新和 Whidbey
2002年12月31日	添加了用于提取和修改字符串隐藏信息的函数，使用和不使用反射。
2002年11月16日	关于字符串的原始文章