谈表达式树的缓存（6）：五种缓存方式的性能比较
2009-05-26 21:06 by 老赵, 24127 visits开始还债，因为还有至少两个可写的重要话题依赖在这个系列上，不解决就难以前进。
目前我们已经涉及了五种不同的缓存实现，它们分别是：
- SimpleKeyCache：构造字符串作为Key，使用字典作为存储。
- PrefixTreeCache：使用前缀树进行存储。
- SortedListCache：使用排序列表或二叉搜索树进行存储。
- HashedListCache：先对表达式树取散列值，再从字典中取出二叉搜索树。
- DictionaryCache：实现了散列值和表达式树的比较方法，直接使用字典进行存储。
如果要从一个已经包含n个表达式树的存储中，查找一个有m个节点的表达式树，根据几篇文章的分析，从理论上说除了HashedListCache的时间复杂度是O(m * log(n))之外，其它几种实现的时间复杂度都是O(m)。不过，理论上的结果和实际使用中的效果完全符合吗？如果完全符合的话，那么我们在构建第一个SimpleKeyCache，获得了一种既简单直观又“高效”（达到了理论上最好的时间复杂度O(m)）的实现之后为什么还要继续设计剩下的方案呢？如果您看完了文章还没有想到，这说明您的.NET编程“常识”还需要加强。
那么我们就写一个程序，让数据说话。
这是一个控制台应用程序，接受用户参数，并由此生成试验数据，或进行性能比较。
生成试验数据
需要进行测试，自然要准备试验数据，而这里所需要的试验数据自然是大量的表达式树。
表达式树的种类非常纷繁，如果要构造各种类型的树，其代价也是非常昂贵的。因此在这里，我们只构建所谓的“整数的四则运算”表达式进行试验。对于这样的表达式，每个运算符占用一个节点，每个数字又会占用另一个节点，因此表达式数的节点个数m便是操作符的个数p，与数字的个数q之和。而由于每个元算符都是二元运算符，因此p等于q - 1。于是我们就可以得出m与p之间的关系：
m = 2p + 1
知道了这个关系，我们便可以获得一定规模的试验数据。于是我们写一个简单的小程序来随机输出一个表达式：
private static void WriteSingleExpression( TextWriter writer, Random random, int opCount) { string ops = "+-*/"; writer.Write(random.Next(100)); while (opCount-- > 0) { writer.Write(" "); writer.Write(ops[random.Next(4)]); writer.Write(" "); writer.Write(random.Next(100)); } writer.WriteLine(); }
这个方法的目的是向TextWriter中随机输出一个拥有opCount个运算符的表达式（可以得知，这个表达式树有m = 2 * opCount + 1个节点）。例如，当opCount等于11的时候，它可能就会生成这样一个表达式：
82 / 6 - 76 * 75 - 33 / 32 * 56 + 47 + 3 + 22 * 5 + 63
然后我们获取用户参数输入，并输出一系列随机的表达式：
private static void GenerateExpressions(NameValueCollection args) { string output = args["out"] ?? "expressions.txt"; int min = Int32.Parse(args["min"] ?? "11"); int max = Int32.Parse(args["max"] ?? (min + 9).ToString()); int repeat = Int32.Parse(args["repeat"] ?? "100");
以上代码的目的是获取用户参数，用户输入的参数将被解析为NameValueCollection，参数含义如下：
- output：输出文件
- min：最短表达式中的运算符数量
- max：最长表达式中的运算符数量
- repeat：每种长度的表达式重复次数
向文件输出所有的随机表达式便不是难事了：
Random random = new Random(DateTime.Now.Millisecond); using (var stream = File.Open(output, FileMode.Create)) { StreamWriter writer = new StreamWriter(stream); for (int opCount = min; opCount <= max; opCount++) { for (int i = 0; i < repeat; i++) { WriteSingleExpression(writer, random, opCount); } } } }
代码简单，就不多作分析了。
试验代码
首先，自然是获取用户输入参数，方法同上：
static void PerfTest(NameValueCollection args) { string intput = args["in"] ?? "expressions.txt"; int repeat = Int32.Parse(args["repeat"] ?? "100");
现在便要读入表达式了。解析表达式不是一件容易的事情，我们这里使用ScottGu所提过的Dynamic Query Library，解析一个表达式就再容易不过了：
List<Expression> expressions = File.ReadAllLines(intput).Select( s => DynamicExpression.Parse(null, s)).ToList();
接着，准备5种缓存容器：
var caches = new SortedDictionary<string, IExpressionCache<object>>() { { "1. SimpleKeyCache", new SimpleKeyCache<object>() }, { "2. PrefixTreeCache", new PrefixTreeCache<object>() }, { "3. SortedListCache", new SortedListCache<object>() }, { "4. HashedListCache", new HashedListCache<object>() }, { "5. DictionaryCache", new DictionaryCache<object>() }, };
初始化CodeTimer：
CodeTimer.Initialize();
遍历字典中的每个缓存对象，将其放入缓存容器中。这段代码还有一个作用便是“热身”——请注意，对.NET中任意代码作性能测试时，都需要让它预运行一下。由于JIT的存在，一个方法第一次运行时所花时间总是较长的，这不应该统计在内：
var value = new object(); foreach (var pair in caches) { var cache = pair.Value; expressions.ForEach(exp => cache.Get(exp, (_) => value));
最后，则是使用CodeTimer对当前缓存容器进行性能测试：
CodeTimer.Time(pair.Key, repeat, () => expressions.ForEach(exp => cache.Get(exp, null))); } }
PerfTest编写完毕，我们最后还需要指定一个函数的入口，如下：
static void Main(string[] args) { var arguments = ParseArguments(args); if (arguments["task"] == "test") { PerfTest(arguments); } else { GenerateExpressions(arguments); } }
如果直接执行程序，便会创建一个expression.txt文件，其中包括操作符数量在11到20之间，每种表达式各100个。如果加上了task参数，并指定test字符串，便会进行性能比较。
比较结果
输入命令，便会使用expression.txt中的每个表达式各调用100次：
Benchmark.exe /task:test
对于运算符数量为11到20的表达式各100个（即总共1000个表达式），各调用100次的结果如下（不过，请不要直接看结果，再想想，再想想）：
1. SimpleKeyCache
Time Elapsed: 2,807ms
CPU Cycles: 7,090,489,283
Gen 0: 412
Gen 1: 0
Gen 2: 0
2. PrefixTreeCache
Time Elapsed: 2,391ms
CPU Cycles: 6,039,211,085
Gen 0: 142
Gen 1: 0
Gen 2: 0
3. SortedListCache
Time Elapsed: 1,939ms
CPU Cycles: 4,903,538,425
Gen 0: 0
Gen 1: 0
Gen 2: 0
4. HashedListCache
Time Elapsed: 1,237ms
CPU Cycles: 3,129,685,287
Gen 0: 0
Gen 1: 0
Gen 2: 0
5. DictionaryCache
Time Elapsed: 1,219ms
CPU Cycles: 3,076,107,042
Gen 0: 3
Gen 1: 1
Gen 2: 0
结果和您想象的是否一样？在老赵的机器上，这个结果还是相当稳定的，每次测试只差十几毫秒，而垃圾收集次数则完全一样。从这个数据中您看出什么来了吗？或者说，您能否回答以下几个问题呢？
- SimpleKeyCache的垃圾收集次数为什么明显较多？PrefixTreeCache为什么也有不少垃圾收集？
- SimpleKeyCache和PrefixTreeCache的时间复杂度都是理论最优值O(m)，但是为什么它们却比不过SortedListCache这个理论上时间复杂度是O(m * log(n))的容器呢？
- 您能否设定一种用例，让SortedListCache的耗时超过PrefixTreeCache或SimpleKeyCache呢？
- HashedListCache为什么会超过SortedListCache，DictionaryCache的性能为什么也那么好呢（与HashedListCache不分伯仲，多次测试互有“胜负”）？
- DictionaryCache有一次1代的垃圾收集，这说明DictionaryCache消耗内存超过前些容器吗？
- SimpleKeyCache从时间和空间上看全面落后，那么他有什么好处吗？
- 您能为每种容器提出改进意见吗？
您是否还能提出更多问题？您能够在老赵发布下一篇文章讨论这些问题之前，在这里留言给出您对这些问题的看法呢？
完整代码下载：http://code.msdn.microsoft.com/ExpressionCache
相关文章：
沙发，新模板什么时候搞定啊？