使用值类型LazyString分析字符串
2009-12-07 10:09 by 老赵, 6178 visits.NET里提供了值类型与引用类型可谓是一个非常关键的特性，例如开发人员使用值类型时，可以充分控制内存的布局方式，这对于Interop等操作非常重要。不过，其实值类型最重要，最基本的特性还是内存分配上。现在基本上是个.NET开发人员就会叨念说“值类型”分配在栈上，“引用类型”分配在堆上。但是什么是栈什么堆？分配在栈上和堆上的区别是什么？如果说这两个问题太“理论”，那么来个实际的：您在平时什么情况下会使用，或者说，定义一个值类型呢？其实这才是重要的，否则背再多概念也没有用。只可惜从我面试的经验上来看，基本没有多少兄弟能把这些.NET基础完整说清楚。
其实值类型与性能的关系很大，因为它是直接分配在线程的调用栈上，随着方法的退出分配的内存就完全释放了，因此不会对GC产生压力——对一个托管程序来说，可以说是性能最为关键的因素之一。不过，值类型在作为参数传递或者变量赋值时，拷贝的不是一个字长，而是整个对象，因此我们一般不会创建拥有很多字段的值类型。如果一个类型的目的是保存数据，字段不多，但是会创建许多个，便可以考虑将其构造为值类型。例如，我昨天总结的PDC 09中的PLINQ内容中，第一条建议便是在合适的时候使用值类型，否则Concurrent GC可能成为性能瓶颈。
不过这让我想起了我常用的一个值类型，它不是为了保存数据用的，而是一个工具类：LazyString。它的目的是减少字符串解析过程中所生成的字符串的数量，这样便可以节省一定时间和空间上的开销。例如有这么一个需求，从一个使用“-”分割的字符串中，拆分出所有的整数（保证输入没有错误），那么最简单的做法可能便是使用Split：
public static List<int> ParseBySplit(string input) { return input.Split('-').Select(s => Int32.Parse(s)).ToList(); }
不过假设这个问题比较复杂，没有办法使用Split，需要我们手动进行分析，那么最简单的方法可能就是这样的：
public static List<int> ParseByString(string input) { var result = new List<int>(); var s = input; while (true) { int index = s.IndexOf('-'); if (index < 0) { result.Add(Int32.Parse(s)); break; } result.Add(Int32.Parse(s.Substring(0, index))); s = s.Substring(index + 1); } return result; }
在这段代码中，我们在一个循环中不断查找第一个“-”，然后将该字符前段作为整数放入结果集中，再将该字符的后段进行后续处理。在分析过程中，我们会将字符串不断地缩短、缩短……只可惜每次Substring都会生成一个新的字符串，这给GC带来的一定压力，大量的复制也会带来一些时间上的开销。当然，在这个例子中我们可以使用变量保存下标，不断地向后移动，慢慢的分割出一个一个地整数，这样可以避免出现更多字符串，但是这种做法从“思路”上来说，似乎没有直接修改字符串来的直接。为了在保持程序清晰度的同时减少开销，我构建了一个叫做LazyString的值类型组件：
public struct LazyString { public LazyString(string s) : this(s, 0, s.Length) { } private string m_str; private int m_index; private int m_length; private LazyString(string s, int index, int length) { this.m_str = s; this.m_index = index; this.m_length = length; } public int Length { get { return this.m_length; } } public override string ToString() { return this.m_str.Substring(this.m_index, this.m_length); } }
在这个值类型中，我们保存了三个字段：源字符串的引用，当前起始下标，以及长度。通过这三个字段，我们便可以得到这个LazyString对象所“表示”的字符串：如ToString所示，它可以由字符串的Substring方法来获得。不过，这个Substring操作也只有在ToString方法调用时才会执行，因此在平时的操作过程中是不会产生新字符串的。那么LazyString有哪些操作呢？其实它们都是些和字符串本身对应的操作，例如：
public struct LazyString { ... public LazyString Substring(int index, int length) { if (index >= this.m_length) { throw new ArgumentOutOfRangeException(); } if (index + length > this.m_length) { length = this.m_length - index; } return new LazyString(this.m_str, this.m_index + index, length); } public LazyString Substring(int index) { if (index >= this.m_length) { throw new ArgumentOutOfRangeException(); } return new LazyString(this.m_str, this.m_index + index, this.m_length - index); } public int IndexOf(char c) { var index = this.m_str.IndexOf(c, this.m_index); return index < 0 ? index : index - this.m_index; } }
Substring和IndexOf的语义和String类型中定义的方法完全一致，不过如Substring已经不是返回一个新字符串对象了，而是一个新的LazyString对象。这是个值类型对象，不会在堆上分配数据，因此不会给GC带来压力，而构造这么一个对象，也只是进行了一些简单的整数运算，这样它表示的字符串是改变了，但是性能非常高。而且，由于对应方法的语义相同，使用起来也和String没有太大区别：
public static List<int> ParseByLazy(string input) { var result = new List<int>(); var s = new LazyString(input); while (true) { int index = s.IndexOf('-'); if (index < 0) { result.Add(Int32.Parse(s.ToString())); break; } result.Add(Int32.Parse(s.Substring(0, index).ToString())); s = s.Substring(index + 1); } return result; }
可见，除了构造方式及一些必要的ToString方法，其它部分的逻辑与直接使用String对象没有任何区别。但是这么做的性能便可以有较大提高，测试一下：
var ints = Enumerable.Range(0, 1000); var input = String.Join("-", ints.Select(i => i.ToString()).ToArray()); CodeTimer.Initialize(); int iteration = 1000; CodeTimer.Time("Split", iteration, () => ParseBySplit(input)); CodeTimer.Time("String", iteration, () => ParseByString(input)); CodeTimer.Time("LazyString", iteration, () => ParseByLazy(input));
结果是：
Split
Time Elapsed: 348ms
CPU Cycles: 838,419,828
Gen 0: 49
Gen 1: 1
Gen 2: 0
String
Time Elapsed: 1,684ms
CPU Cycles: 4,054,499,880
Gen 0: 3837
Gen 1: 0
Gen 2: 0
LazyString
Time Elapsed: 241ms
CPU Cycles: 584,045,208
Gen 0: 30
Gen 1: 15
Gen 2: 0
可见，LazyString是性能最高的做法，而String产生的GC数量也是最为可观的。不过也必须注意到，LazyString带来了15次Gen 1的GC操作，这虽然不会带来性能问题，但也给了我们一些“警示”：LazyString虽然不会生成新字符串，但是会把旧的字符串持有更长的时间。因为，LazyString即便是表示一小段字符串，也是需要引用一整个字符串。这意味着LazyString只能是一个“工具类型”而不能用它来完全代替String来表示字符串。当然，LazyString在进行Substring操作时，也可以进行一些判断，例如可以在m_length小于m_str.Length一半的情况下生成新的字符串，这样便可以在时间和空间两方面做出一个权衡。
不过我在使用LazyString时并没有那么复杂，因为我的场景保证了操作总是一瞬间就可以完成的，不会把一个较长的字符串捏住不放。
介个。。。。。Indexof和Substring都有两个参数的版本么。