发信人: flier (小海 [寻找风车中]), 信区: DotNET
标  题: CLR中字符串不变性的优化
发信站: BBS 水木清华站 (Thu Feb 26 17:16:47 2004), 转信

http://www.blogcn.com/user8/flier_lu/main.asp?id=1269085

CLR中字符串不变性的优化

    自从有编程语言以来，如何处理字符串就一直是一个争论不休的问题。从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的时候，内容相同的字符串都会被定位到字符串索引表的同一入口，返回相同的对象引用。
--
.    生命的意义在于   /\   ____\ /\_ \   /\_\    http://flier_lu.blogone.net.                            .  
.        希望         \ \  \___/_\/\ \   \/_/__     __    _ _★              .  
.        工作          \ \   ____\\ \ \    /\  \  /'__`\ /\`'_\              .  
.      爱你的人         \ \  \___/ \ \ \___\ \  \/\ __// \ \ \/              .  
.     和你爱的人         \ \___\    \ \_____\ \__\ \____\ \ \_\              .  
.        ……             \/___/     \/_____/\/__/\/____/  \/_/ @nsfocus.com.  


※ 来源:·BBS 水木清华站 smth.org·[FROM: 211.167.254.*]
上一篇
返回上一页
回到目录
回到页首
下一篇