秋梦无痕

from: flier's Sky@blogcn

自从有编程语言以来，如何处理字符串就一直是一个争论不休的问题。从C/C++用字符数组表示字符串，让用户完全控制其生命周期；到Delphi/VB通过编译器内建支持，使用引用计数自动维护字符串生命周期；再到Java/C#通过不可变字符串以及垃圾回收管理生命周期。不同的策略有着不同的倾向性，也有各自的缺点和优点。这儿我不想评论多种策略之间的优劣，只是想针对C#的实现做一点点较为深入的探讨。

CLR中选择了和Java类似的不可变字符串策略，以简化生命期维护以及多线程同步问题的处理，但同时也付出了一定的效率和空间上的代价，故而不得不通过编译器一级定制来优化。
Chris Brumme和Yun Jin在其BLog上讨论了需要保障字符串不变性(immutability)的原因，并指出通过PInvoke以及unsafe代码直接修改字符串内容可能带来的危害。
Interning Strings & immutability
Dangerous PInvokes - string modification

为了提高效率和节约空间，CLR内部实际上维护了一个不可变字符串表。在堆中分配的字符串可以通过String.Intern函数确保其被加入此表；通过String.IsInterned函数判断自己是否在表中。如果在表中，则可以通过引用来直接对字符串进行比较，大大提高字符串比较效率。MSDN上的例子如下

// Sample for String.Intern(String)
using System;
using System.Text;

class Sample {
public static void Main() {
String s1 = "MyTest";
String s2 = new StringBuilder().Append("My").Append("Test").ToString();
String s3 = String.Intern(s2);
Console.WriteLine("s1 == '{0}'", s1);
Console.WriteLine("s2 == '{0}'", s2);
Console.WriteLine("s3 == '{0}'", s3);
Console.WriteLine("Is s2 the same reference as s1?: {0}", (Object)s2==(Object)s1);
Console.WriteLine("Is s3 the same reference as s1?: {0}", (Object)s3==(Object)s1);
}
}
/*
This example produces the following results:
s1 == 'MyTest'
s2 == 'MyTest'
s3 == 'MyTest'
Is s2 the same reference as s1?: False
Is s3 the same reference as s1?: True
*/

如果熟悉CLR的Metadata文件结构的朋友可能立刻会想到，在Metadata表中实际上本来就有#String流和#US流，分别保存程序中固化的字符串和用户字符串。例如上面的"MyTest"字符串就会被放入流中直接载入，而CLR动态维护的字符串表就是在此基础上扩展的。
动态创建的字符串，如前面例子中通过StringBuilder构造的字符串，则缺省放在堆中，只有用户显式调用了String.Intern函数，才会被加入到静态字符串表中。查看Rotor的代码，会发现String.Intern实际上是调用当前线程所在AppDomain的GetOrInternString函数；而进一步调用此AppDomain的字符串映射表的GetInternedString函数。

String.Intern(String str) (bcl\system\string.cs:1194)
Thread.GetDomain().GetOrInternString(str)

AppDomain.GetOrInternString(String str) (bcl\system\appdomain.cs:1558)
InternalCall

BaseDomain::GetOrInternString(STRINGREF *pString) (vm\appdomain.cpp:856)
m_pStringLiteralMap->GetInternedString(pString, ...)

AppDomainStringLiteralMap::GetInternedString(...) (vm\stringliteralmap.cpp:196)

在GetOrInternString函数中：首先会根据字符串的内容计算出其HashCode；然后使用此HashCode在当前AppDomain的字符串映射表(m_StringToEntryHashTable)中搜索；如果没有找到则进一步在CLR的全局字符串映射表(SystemDomain::GetGlobalStringLiteralMap())中搜索；如果还是没有找到，则根据参数决定是否将此字符串以HashCode为索引加入全局字符串映射表(GetInternedString函数中根据参数bAddIfNotFound判断是否添加)；如果当前AppDomain可能被卸载，则还会将此字符串以HashCode为索引加入到当前AppDomain的局部字符串映射表中。伪代码如下：

STRINGREF *AppDomainStringLiteralMap::GetInternedString(STRINGREF *pString, BOOL bAddIfNotFound, BOOL bAppDomainWontUnload)
{
StringLiteralEntry *Data;
DWORD dwHash = m_StringToEntryHashTable->GetHash(字符串数据);

if (m_StringToEntryHashTable->GetValue(&StringData, &Data, dwHash))
{
return Data->GetStringObject();
}
else
{
StringLiteralEntry *pEntry = SystemDomain::GetGlobalStringLiteralMap()->GetInternedString(pString, dwHash, bAddIfNotFound);

if(pEntry)
{
if (!bAppDomainWontUnload)
{
m_StringToEntryHashTable->InsertValue(&StringData, (LPVOID)pEntry, FALSE);
}
}
else
{
return pEntry->GetStringObject();
}
}
}

另外一个函数String.IsInterned实际上调用路径完全一样，只是在GetInternedString没有在字符串映射表搜索到字符串时不自动加入(bAddIfNotFound = false)。

由此我们可以得出一些结论：
1.Intern String的作用域是整个CLR，虽然每个AppDomain有独立的优先缓存机制。这样既可以保障查询效率，又可以保障在不同级别（如CLR/AppDomain)载入的共享的Assembly中字符串的一致性。
2.Intern String中的内容直接决定其HashCode，进而决定其在字符串表中的存储和索引，直接内容修改可能导致未知问题。直接修改内容后再使用String.IsInterned，就会返回一个和以前完全不同的索引项。
3.Intern String可以通过其引用直接比较。因为在隐式（固化在Metadata的#String或#US流中）或显示（调用String.Intern）将字符串Intern的时候，内容相同的字符串都会被定位到字符串索引表的同一入口，返回相同的对象引用。