Hello World
Spiga

谈表达式树的缓存(6):五种缓存方式的性能比较

2009-05-26 21:06 by 老赵, 22805 visits

开始还债,因为还有至少两个可写的重要话题依赖在这个系列上,不解决就难以前进。

目前我们已经涉及了五种不同的缓存实现,它们分别是:

  1. SimpleKeyCache:构造字符串作为Key,使用字典作为存储。
  2. PrefixTreeCache:使用前缀树进行存储。
  3. SortedListCache:使用排序列表或二叉搜索树进行存储。
  4. HashedListCache:先对表达式树取散列值,再从字典中取出二叉搜索树。
  5. 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

结果和您想象的是否一样?在老赵的机器上,这个结果还是相当稳定的,每次测试只差十几毫秒,而垃圾收集次数则完全一样。从这个数据中您看出什么来了吗?或者说,您能否回答以下几个问题呢?

  1. SimpleKeyCache的垃圾收集次数为什么明显较多?PrefixTreeCache为什么也有不少垃圾收集?
  2. SimpleKeyCache和PrefixTreeCache的时间复杂度都是理论最优值O(m),但是为什么它们却比不过SortedListCache这个理论上时间复杂度是O(m * log(n))的容器呢?
  3. 您能否设定一种用例,让SortedListCache的耗时超过PrefixTreeCache或SimpleKeyCache呢?
  4. HashedListCache为什么会超过SortedListCache,DictionaryCache的性能为什么也那么好呢(与HashedListCache不分伯仲,多次测试互有“胜负”)?
  5. DictionaryCache有一次1代的垃圾收集,这说明DictionaryCache消耗内存超过前些容器吗?
  6. SimpleKeyCache从时间和空间上看全面落后,那么他有什么好处吗?
  7. 您能为每种容器提出改进意见吗?

您是否还能提出更多问题?您能够在老赵发布下一篇文章讨论这些问题之前,在这里留言给出您对这些问题的看法呢?

 

完整代码下载:http://code.msdn.microsoft.com/ExpressionCache

相关文章:

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

15 条回复

  1. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2009-05-26 21:15:00

    沙发,新模板什么时候搞定啊?

  2. Brett
    *.*.*.*
    链接

    Brett 2009-05-26 21:16:00

    板凳

  3. 未注册[未注册用户]
    *.*.*.*
    链接

    未注册[未注册用户] 2009-05-26 21:17:00

    地板。

  4. 老赵
    admin
    链接

    老赵 2009-05-26 21:19:00

    --引用--------------------------------------------------
    麒麟.NET: 沙发,新模板什么时候搞定啊?
    --------------------------------------------------------
    已经提交给dudu了,他比较忙,大家耐心多等几天,其实我最迫不及待呢。:)

  5. 温景良(Jason)
    *.*.*.*
    链接

    温景良(Jason) 2009-05-26 22:55:00

    我发现老赵你写得东西我是越来越看不懂了,

  6. 老赵
    admin
    链接

    老赵 2009-05-26 23:13:00

    --引用--------------------------------------------------
    温景良(Jason): 我发现老赵你写得东西我是越来越看不懂了,
    --------------------------------------------------------
    我应该讲清楚了吧,慢慢看,会看懂的。

  7. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-05-26 23:32:00

    这个系列的终结篇终于出来了。
    先去睡觉,明天慢慢看。明天还要赶到学校呢。

  8. 老赵
    admin
    链接

    老赵 2009-05-26 23:55:00

    @Kevin Dai
    你没看文章嘛,明显说了还有一篇分析……

  9. lewi's-blog
    *.*.*.*
    链接

    lewi's-blog 2009-05-27 09:03:00

    ~~~~(>_<)~~~~ 好难喔。

  10. fdsafdsaf[未注册用户]
    *.*.*.*
    链接

    fdsafdsaf[未注册用户] 2009-05-27 09:20:00

    老赵也要写点浅显的文章,比如园子很多时候别人发的基础文章其实都是误导新人的。

  11. airwolf2026
    *.*.*.*
    链接

    airwolf2026 2009-05-27 10:01:00

    chinese only 是不是对老外要求有点高哈哈

  12. 老赵
    admin
    链接

    老赵 2009-05-27 10:13:00

    @airwolf2026
    其实我真想写英文,但是实在写不好,写太慢。

  13. 老赵
    admin
    链接

    老赵 2009-05-27 10:13:00

    --引用--------------------------------------------------
    fdsafdsaf: 老赵也要写点浅显的文章,比如园子很多时候别人发的基础文章其实都是误导新人的。
    --------------------------------------------------------
    但是园子里也有很多人的基础文章写得很好啊。

  14. AlexLiu
    *.*.*.*
    链接

    AlexLiu 2009-05-27 12:06:00

    这篇文章等了好长时间了:)

  15. Joyaspx
    *.*.*.*
    链接

    Joyaspx 2009-06-01 08:30:00

    看了老赵的文章,觉得自己确实还有很多基础知识需要补补!

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我