Hello World
Spiga

并发环境下的缓存容器性能优化(下):性能测试

2009-11-16 00:29 by 老赵, 18822 visits

上一篇文章里,我谈到对于某些场景中的缓存容器,其写操作非常少,到了程序后期甚至为零,而对它的读操作却几乎是密集连续且无穷无尽的。对于这样的容器,如果使用ReaderWriterLockSlim去进行保护每个“读”操作,这开销是在有些多余。因此我提出了“不可变”的哈希表,目的是在保持读操作的时间复杂度为O(1)的情况下,尽可能避免多余的开销。现在我们便将它和其他几种时间进行一个性能的对比。

需要强调一点的是,我们这里讨论的仅仅是符合我提出的特定场景的缓存容器,而不是一个“线程安全的字典”。或者说,其实我这里更强调的是“并发环境下”的“读”性能,而不涉及IDictionary<TKey, TValue>的其他操作(如Count),更不会关心如CopyTo、Remove这类功能的性能。

上一篇文章结束时,我给出了两个缓存容器的基类,可用于此类容器的实现。其中ReadWriteCache类基于ReaderWriterLockSlim,而ReadFreeCache类则基于不可变的字典。不过这两种做法不太适合进行性能测试,因此我这里的实验使用了这样的接口:

public interface IConcurrentCache<TKey, TValue>
{
    TValue Get(TKey key);
    void Set(TKey key, TValue value);
}

我为这个接口提供了几种最基本实现,无论是“读”还是“写”,都是最直接的,并不对任何特殊的情况(如key缺失,key重复)进行处理。例如ImmutableMapCache:

public class ImmutableMapCache<TKey, TValue> : IConcurrentCache<TKey, TValue>
{
    private object m_writeLock = new object();
    private FSharpMap<TKey, TValue> m_map = FSharpMap<TKey, TValue>.Empty;

    public TValue Get(TKey key)
    {
        return this.m_map[key];
    }

    public void Set(TKey key, TValue value)
    {
        lock (this.m_writeLock)
        {
            this.m_map = this.m_map.Add(key, value);
        }
    }
}

ImmutableMapCache是基于F#中的Map而实现的读写操作。由于是Immutable的集合,因此对它的读操作不需要任何并发方面的保护——而写操作理论上也是线程安全的,但是我这里还是使用了lock。这是因为如果没有lock的话,在实际并发的场景中容易出现“摇摆”的情况出现。试想,同时有2个线程正在添加元素,它们同时读取了集合的当前状态,但是在写回的时候只后一个线程的操作生效,先写回的线程的修改丢失了。当并发程度高的情况下,“摇摆”会更加严重。因此,无论是ImmutableMapCache,还是基于Immutable Dictionary的实现,在Set操作中都使用lock进行保护。

测试代码如下:

static void CacheBenchmark<TCache>()
    where TCache : IConcurrentCache<int, int>, new()
{
    var typeName = typeof(TCache).Name;
    var index = typeName.IndexOf('`');
    var cacheName = typeName.Substring(0, index);

    // warm up
    TCache cache = new TCache();
    cache.Set(1, 1);
    cache.Get(1);

    for (int n = 100; n <= 1000; n += 100)
    {
        cache = new TCache();

        CodeTimer.Time(cacheName + " (Set " + n + " elements)", 100, () =>
        {
            for (var i = 0; i < n; i++)
            {
                cache.Set(i, i);
            }
        });

        CodeTimer.Time(cacheName + " (Get from " + n + " elements)", 1, () =>
        {
            var key = 0;
            for (int i = 0; i < 1000 * 1000 * 5; i++)
            {
                cache.Get(key);
                key = (key + 1) % n;
            }
        });
    }
}

请注意,这里的测试都是在单线程环境下的。严格来说,这并不表示每种容器在多线程环境下的表现。事实上,即便是多线程环境下,不同实现随并发程度的高低也会有所变化。因此,除了进行实验和观察结果之外,也必须结合实际情况进行思考,而不能简单的“采纳”这次实验的结果。在这里我们总共测试5种不同的实现:

CacheBenchmark<RwLockSlimDictionaryCache<int, int>>();
CacheBenchmark<RwLockDictionaryCache<int, int>>();
CacheBenchmark<ImmutableMapCache<int, int>>();
CacheBenchmark<ImmutableDictionaryCache<int, int>>();
CacheBenchmark<ConcurrentDictionaryCache<int, int>>();

它们分别是:

  1. RwLockSlimDictionary:基于Dictionary,使用ReaderWriterLockSlim进行保护的缓存容器。
  2. RwLockDictionary:基于Dictionary,使用ReaderWriterLock进行保护的缓存容器。
  3. Immutable Map:基于F#中Map实现的缓存容器。
  4. Immutable Dictionary:基于不可变的哈希表实现的缓存容器。
  5. Concurrent Dictionary:基于.NET 4.0中提供的Concurrent Dictionary实现的缓存容器。

运行环境是.NET 4.0 Beta 2,实验进行三次。我们首先关注“写”操作的结果,如下:

取平均值作为最后结果,并绘制成图表:

在这结果里我并没有包含基于Immutable Dictionary的实现,因为它的结果实在太惨,如果一并放入的话,其他实现方式就几乎看不出来了。我们在来看一下我们的测试代码,它是统计向一个空容器内添加n个元素所花的时间(n等于100、200、...、1000)。对于基于字典的实现来说,添加1个元素的时间复杂度是O(1),因此添加n个元素的时间复杂度是O(n)。而基于Immutable Map的实现,其添加1个元素的时间复杂度是O(log(n)),于是添加n个元素的时间复杂度是O(n * log(n))。这两种时间复杂度都可以从图表中表现出来——当然,这个表现形式是“趋势”也就是“形状”,同样的时间复杂度的常数还是不一样的。

那么Immutable Dictionary又是什么样的呢?我们为其单独进行一番实验,减小实验粒度,希望可以得到更清晰的结果:

for (int n = 100; n <= 10000; n += 100)
{
    CodeTimer.Time(String.Format("add {0} elements", n), 1, () =>
    {
        var cache = new ImmutableDictionaryCache<int, int>();
        for (int i = 0; i < n; i++)
        {
            cache.Set(i, i);
        }
    });
}

将其结果绘制成图表:

向Immutable Dictionary中添加1个元素的时间复杂度是O(n),于是添加n个元素的时间复杂度则是O(n2),从图表上看,这趋势也是相当明显的。而且,与基于Dictionary的实现方式不同,由于Immutable Dictionary每次都要重新复制元素,它对于GC的压力也是非常可观的,如下:

从图中可以看到一个有趣的结果,那就是GC的频率在n为8000到9000的某一个时刻的收集频率突然开始加快了,莫非这就是传说中GC的自我调节能力吗?不过这并非是本次实验的关键,我们只需要发现说,Immutable Dictionary与Dictionary相比,前者对GC的消耗较大,而后者则几乎没有GC方面的压力。

在写方面,Immutable Dictionary的表现可谓残不忍睹,但如果是“读”的话,一切就都不一样了:

将结果绘制成图表:

与“写”操作的测试方式不同,“读”操作测试的是“从包含n个元素的容器中读取元素”所需要的时间。除了Immutable Map是O(logN)的时间复杂度外,其余4种容器都是基于Get操作时间复杂度为O(1)的哈希表。换句话说,基于Immutable Map的容器会随着元素数量而耗时增加,而其他4种容器,它们“读”操作的耗时和其中有多少元素并没有关系。

从结果上我们可以得出一些有趣的结论。首先,ReaderWriterLockSlim似乎会进行“自我调节”,一开始它的Write Lock开销较大,但是随着实验的进行,它的开销变小了很多。其次,基于Immutable Dictionary的实现自然因为其“Read Free”而表现最好,但是.NET中Concurrent Dictionary的表现也相当出色,可谓遥遥领先于基于ReaderWriterLockSlim的实现。而在“写”操作测试时,它的表现也可圈可点,仅次于RwLockSlimDictionary。我并不清楚Concurrent Dictionary的实现方式,有人说是Lock Free,也有人说是小粒度的锁。这点可以通过阅读代码来得知,在这里就不多作展开了。

相关文章

Creative Commons License

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

Add your comment

41 条回复

  1. ruson
    *.*.*.*
    链接

    ruson 2009-11-16 00:44:00

    这么晚了居然来抢个沙发, 先休息了,明天看。呵呵

  2. 老赵
    admin
    链接

    老赵 2009-11-16 09:08:00

    不是吧,这篇文章怎么看的人这么少,呵呵。

  3. 程序设计的艺术
    *.*.*.*
    链接

    程序设计的艺术 2009-11-16 09:28:00

    老赵,你的图表是用什么工具绘出的?

  4. 老赵
    admin
    链接

    老赵 2009-11-16 09:32:00

    @程序设计的艺术
    google doc生成的,有点丑,尤其是以前用Excel画的,差距有点大。
    不过优点就是方便。

  5. 老赵
    admin
    链接

    老赵 2009-11-16 09:33:00

    @Leon Weng
    究竟哪里看不懂呢?

  6. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2009-11-16 09:44:00

    Jeffrey Zhao:
    @Leon Weng
    究竟哪里看不懂呢?


    事实上3.0的语法不太熟悉导致,怪自己。F#更是没接触过。

  7. 假正经哥哥
    *.*.*.*
    链接

    假正经哥哥 2009-11-16 09:46:00

    cnblogs是初学者乐园,你这个太深奥别个看不懂,哈哈!!

  8. 老赵
    admin
    链接

    老赵 2009-11-16 09:49:00

    Leon Weng:

    static void CacheBenchmark<TCache>()
        where TCache : IConcurrentCache<int, int>, new()
    
    不太了解。


    你这不是3.0的语法不懂,是2.0了……这些随便找本2.0的书就能看明白了。

  9. 老赵
    admin
    链接

    老赵 2009-11-16 09:50:00

    假正经哥哥:cnblogs是初学者乐园,你这个太深奥别个看不懂,哈哈!!


    还有吵架乐园,嗯嗯。

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

    hong2[未注册用户] 2009-11-16 10:00:00

    @Jeffrey Zhao
    老赵

    lock (this.m_writeLock)
    {
    if (this.m_storage.TryGetValue(key, out value))
    {
    return value;
    }

    value = this.Create(key);
    var newStorage = this.m_storage.ToDictionary(
    p => p.Key,
    p => p.Value,
    this.m_storage.Comparer);

    newStorage.Add(key, value);
    this.m_storage = newStorage;
    }

    这里为什么要new一个dictionary再往里添加,直接往m_storage不行吗?

  11. 老赵
    admin
    链接

    老赵 2009-11-16 10:03:00

    @hong2
    看一下前篇文章吧。

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

    温景良(Jason) 2009-11-16 10:16:00

    老赵的文章现在都是只能大概看一下,然后收藏.

  13. Duron800[未注册用户]
    *.*.*.*
    链接

    Duron800[未注册用户] 2009-11-16 10:40:00

    warm up 有什么好处吗?

  14. 老赵
    admin
    链接

    老赵 2009-11-16 11:06:00

    @Duron800
    不是好处,是让测试更准确一些。

  15. Duron800[未注册用户]
    *.*.*.*
    链接

    Duron800[未注册用户] 2009-11-16 14:12:00

    Jeffrey Zhao:
    @Duron800
    不是好处,是让测试更准确一些。


    为什么会更准确呢?

  16. 老赵
    admin
    链接

    老赵 2009-11-16 14:14:00

    @Duron800
    了解一下JIT的工作方式吧。

  17. Duron800[未注册用户]
    *.*.*.*
    链接

    Duron800[未注册用户] 2009-11-16 15:09:00

    @Jeffrey Zhao

    Jeffrey Zhao:
    @Duron800
    了解一下JIT的工作方式吧。


    哦,是关于加载相关Type和缓存吗?

  18. 老赵
    admin
    链接

    老赵 2009-11-16 15:14:00

    @Duron800
    不是,别猜,看书吧,比如CLR via C#。

  19. Duron800[未注册用户]
    *.*.*.*
    链接

    Duron800[未注册用户] 2009-11-16 15:34:00

    Jeffrey Zhao:
    @Duron800
    不是,别猜,看书吧,比如CLR via C#。


    好的,在看,还没看完,才看到delegate.

  20. 老赵
    admin
    链接

    老赵 2009-11-16 15:52:00

    @Duron800
    估计你已经看过了,JIT是在书的比较前面的部分。

  21. Duron800[未注册用户]
    *.*.*.*
    链接

    Duron800[未注册用户] 2009-11-16 15:59:00

    Jeffrey Zhao:
    @Duron800
    估计你已经看过了,JIT是在书的比较前面的部分。


    是呀,我也感觉是这样的,百看了。
    我以为是关于按需加载,然后缓存,以便之后再次调用。
    我认为跟性能有关,不明白你说的“让测试更准确一些”指的是什么。

  22. 迭戈_Forever
    *.*.*.*
    链接

    迭戈_Forever 2009-11-16 16:07:00

    并发?记得当时看资料的时候那个并发环境下的lock都实践过,到现在都忘了。
    对于多线程,最熟悉的就是微软已经封装好的那个backgroundwork类了。
    等这几天晚上有时间好好看看老赵的这篇文章。

  23. 老赵
    admin
    链接

    老赵 2009-11-16 16:57:00

    @Duron800
    一个方法第一次调用时会进行JIT,JIT后IL变成Native Code。
    JIT是需要时间的,Warm up就是把这段时间排除,这样提高准确性。

  24. 韦恩卑鄙 alias:v-zhewg
    *.*.*.*
    链接

    韦恩卑鄙 alias:v-zhewg 2009-11-16 17:09:00

    阿 终于中文资料的空白 被填补了!

  25. Duron800[未注册用户]
    *.*.*.*
    链接

    Duron800[未注册用户] 2009-11-16 17:12:00

    Jeffrey Zhao:
    @Duron800
    一个方法第一次调用时会进行JIT,JIT后IL变成Native Code。
    JIT是需要时间的,Warm up就是把这段时间排除,这样提高准确性。


    嗯,知道了。

  26. dark
    *.*.*.*
    链接

    dark 2009-11-16 19:33:00

    收藏页面了(PS:我发现老赵的页面基本上要去揣摩的.哎 还是要先学设计模式 - -| 我感觉这个最重要)....
    以后用到的话 在慢慢研究...

  27. 老赵
    admin
    链接

    老赵 2009-11-16 19:36:00

    @dark
    这个和设计模式的确没有什么关系的……

  28. dark
    *.*.*.*
    链接

    dark 2009-11-16 19:41:00

    ...俺晓得没关系额 不过我现在在看设计模式.这个以后回家慢慢琢磨...文章链接中的代码俺略看了一下 蛮Happy的
    (PS:我发现我现在看到高手写的代码就兴奋.....)

  29. 韦恩卑鄙 alias:v-zhewg
    *.*.*.*
    链接

    韦恩卑鄙 alias:v-zhewg 2009-11-16 21:03:00

    dark:
    收藏页面了(PS:我发现老赵的页面基本上要去揣摩的.哎 还是要先学设计模式 - -| 我感觉这个最重要)....
    以后用到的话 在慢慢研究...



    设计模式是要有一定经验基础才能学明白的 这个强求不得
    反倒是这个初学者学比较容易

  30. 老赵
    admin
    链接

    老赵 2009-11-16 22:12:00

    韦恩卑鄙 alias:v-zhewg:
    设计模式是要有一定经验基础才能学明白的 这个强求不得
    反倒是这个初学者学比较容易


    这个说法有一定道理的……

  31. dark
    *.*.*.*
    链接

    dark 2009-11-17 04:48:00

    @韦恩卑鄙 alias:v-zhewg

    韦恩卑鄙 alias:v-zhewg:

    dark:
    收藏页面了(PS:我发现老赵的页面基本上要去揣摩的.哎 还是要先学设计模式 - -| 我感觉这个最重要)....
    以后用到的话 在慢慢研究...



    设计模式是要有一定经验基础才能学明白的 这个强求不得
    反倒是这个初学者学比较容易



    我现在的感觉是业务需求没有一个好的架构,写起来有时候蛮郁闷的.不断的重构,重构.我在做这些事的时候不明白的是为什么要这样构建起来.优点有些什么 只晓得便于开发,减少工作量. 所以才看设计模式,我看的是Juditb Bisbop写的C# 3.0设计模式.感觉很棒.不过运用起来好像还要有丰富的经验才行啊- -|
    设计模式是学起来简单,用起来难.
    老赵的是学起来简单,用起来...(这个都不晓得偶撒时候才能用到额..) 所以我看到有好的文章都保存页面,知道能这么做,以后有需要了 就研究 - -|....我这样做 感觉 老赵...我是不是辱没了你的文章啊?

  32. 迭戈_Forever
    *.*.*.*
    链接

    迭戈_Forever 2009-11-17 10:28:00

    @dark
    同感,我对于老赵的一些文章也是收藏,然后慢慢体会。我想这就是一年的菜鸟程序员和老赵这样架构师的差距了。

  33. hong2[未注册用户]
    *.*.*.*
    链接

    hong2[未注册用户] 2009-11-17 17:08:00

    这里为什么要new一个dictionary再往里添加,直接往m_storage不行吗?

    看了上篇文章.还是没看太明白.能不能说的通俗些?

  34. 老赵
    admin
    链接

    老赵 2009-11-17 17:10:00

    @hong2
    已经说得很清楚了……再看几遍吧,仔细看看,如果还不懂,那么可以说说哪几句话没懂……

  35. tianxd
    *.*.*.*
    链接

    tianxd 2010-01-06 17:47:00

    综合来看ConcurrentDictionary是首选啊,呵呵
    vs2010赶快发布吧

  36. TUPUNCO
    *.*.*.*
    链接

    TUPUNCO 2010-03-18 23:19:00

    .net 2.0 内没有ReaderWriterLockSlim,反编译出了一个, 结果发现效果真差, 直接用monitor的锁效率就很不错.
    ConcurrentDictionary 前几天反编译得到结果看是 空间分带哈希集(Striped Hash Set) 的方法实现的.

  37. 老赵
    admin
    链接

    老赵 2010-03-19 22:23:00

    @TUPUNCO
    Monitor和ReadWriteLockSlim的功能是不一样的,怎么用来比较?

  38. pq
    115.236.66.*
    链接

    pq 2011-12-01 17:49:58

    请教你一下,你提到这些缓存容器的应用场景是读多写少,比如RwLockSlimDictionaryCache.cs,在读的时候不需要判断Dictionary中是否存在该Key吗?这样不就抛出异常了吗?

  39. 老赵
    admin
    链接

    老赵 2011-12-01 21:02:57

    @pg

    看下我的代码啊。

  40. 古道
    124.126.123.*
    链接

    古道 2011-12-23 16:54:03

    老赵,这个呢?Hashtable.Synchronized

  41. 老赵
    admin
    链接

    老赵 2011-12-23 21:23:23

    @古道

    你可以试一下,这个从原理上就是很慢的。

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我