Hello World
Spiga

并发环境下的缓存容器性能优化(上):不可变的哈希表

2009-11-12 00:03 by 老赵, 19991 visits

我们在项目中经常会遇到这样的场景:一些信息读取开销较大,但只需要生成一次便可反复使用,因此我们会将其永久地缓存起来。例如在ASP.NET MVC中,系统会根据Controller的名称来缓存对应的元数据。这些缓存容器都有一些共同的特点,便是存储的对象数量有限(少则几十,多不过数千),但都需要在并发环境下被大量地读取,因此必须是线程安全的。那么,我们该如何设计这样的容器呢?

一个非常常见的做法是使用字典(System.Collections.Generic.Dictionary<TKey, TValue>)进行存储。字典使用了“哈希表”这个数据结构,其读取和写入的时间复杂度几乎都是O(1),性能可谓非常之高。只不过,字典不是线程安全的,例如它在添加元素的时候可能会对内部的bucket数组进行动态调整,这显然不是一个原子操作。因此,它无法直接用户并行环境的读写,我们对它的操作必须加锁。

说起加锁,最简单的方式便是在读和写方法中使用同一个互斥体(mutex)进行lock:

object mutex = new object();
Dictionary<int, int> dict = new Dictionary<int, int>();

// read with lock
lock (mutex)
{
    var value = dict[1];
}

// write with lock
lock(mutex)
{
    dict[1] = 1;
}

这么做可以保证在任意时刻只有单个线程在访问字典,无论读写,这自然做到了线程安全。但是,这么做的话对于并发环境并不友好。因为一个字典是完全可以同时被多个线程“读”的,也就是说,如果我们简单使用lock便会大大降低“读”操作的可并发性,从而对性能产生负面影响。

那么我们能否对“写”操作进行lock,而让“读”操作完全自由呢?例如:

object mutex = new object();
Dictionary<int, int> dict = new Dictionary<int, int>();

// read directly
var value = dict[1];

// write with lock
lock(mutex)
{
    dict[1] = 1;
}

这也是不允许的。因为这样做无法避免在某个线程读取字典的同时,另一个线程正在修改字典。一旦出现读写操作同时进行的情况,字典就很可能被破坏了。因此,其实我们的要求有两点:

  • 只能由单个线程写,但可以由多个线程同时读。
  • 在进行读操作时,不可同时进行写操作。反之亦然。

这便是“读写锁”使用场景。只要使用“写”锁来保护修改操作,而使用“读”锁来保护读取操作,便可以让字典正确并高效地工作在并发环境下。“读写锁”在.NET框架中有着两个实现:ReaderWriterLock和ReaderWriterLockSlim。前者出现在.NET 1.x中,而后者随.NET 2.0发布。两者的区别在于前者性能低,后者性能高,因此在目前,基本上需要读写锁的场景都会建议使用ReaderWriterLockSlim(除了稍后会提到的情况)。

但是,ReaderWriterLockSlim并非不会带来开销,我们接下来的试验便要来验证这一点。首先,我们准备1000个数字,它们便是我们使用的测试数据源:

var source = Enumerable.Range(1, 1000).ToArray();
var dict = source.ToDictionary(i => i);

然后,我们使用CodeTimer测试它在三种情况下的性能:

int iteration = 10000;
CodeTimer.Initialize();

CodeTimer.Time("Read Free", iteration, () =>
{
    foreach (var i in source)
    {
        var ignore = dict[i];
    }
});

var rwLockSlim = new ReaderWriterLockSlim();
CodeTimer.Time("ReaderWriterLockSlim", iteration, () =>
{
    foreach (var i in source)
    {
        rwLockSlim.EnterReadLock();
        var ignore = dict[i];
        rwLockSlim.ExitReadLock();
    }
});

var rwLock = new ReaderWriterLock();
CodeTimer.Time("ReaderWriterLock", iteration, () =>
{
    foreach (var i in source)
    {
        rwLock.AcquireReaderLock(0);
        var ignore = dict[i];
        rwLock.ReleaseReaderLock();
    }
});

最后一种方式使用了性能较差的ReaderWriterLock,我的目的除了表现出它与ReaderWriterLockSlim的性能差距之外,还有一个原因在于.NET 3.5的ReaderWriterLockSlim类会在某些时候读取Environment.ProcesserCount,这在Medium Trust的环境下会引发SecurityException。因此您会发现,在目前的ASP.NET MVC框架中,所有需要读写锁的地方都使用了ReaderWriterLock而不是Slim组件。

试验结果如下:

Read Free
        Time Elapsed:   228ms
        CPU Cycles:     538,190,052
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

ReaderWriterLockSlim
        Time Elapsed:   1,161ms
        CPU Cycles:     2,783,025,072
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

ReaderWriterLock
        Time Elapsed:   2,792ms
        CPU Cycles:     6,682,368,396
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

可见,尽管ReaderWriterLockSlim的性能比ReaderWriterLock要高出许多,但相对于无锁的读取还是有明显差距。这让我感到很不合算,因为这是由缓存容器的使用性质决定的。在一般情况下,这种容器都是“有限次地修改”,而几近“无限次地读取”,尤其到了程序运行后期,所以该使用的对象都已经缓存下来,字典内容更不会产生任何改变——但是,每一次读取还要继续承受ReaderWriterLockSlim的开销,这笔帐相信人人会算。那么,我们又如何能够做到“无锁”地读取呢?既然我们“锁”的目的是因为需要“修改”,那么我们使用“不可变(Immutable)”的容器是否就能有所帮助呢?为此,我向F#借来了Immutable Map。

F#中的Map类定义在Microsoft.FSharp.Core.dll中,这需要安装F# SDK for Visual Studio 2008,当然如果您直接安装了VS 2010自然也就有了相应的程序集——不过一些辅助类库(如Microsoft.FSharp.PowerPack),以及源文件(F#是个开源的语言)还是需要去之前的链接里下载一个压缩包。在项目中引用了程序集后,便可以使用Microsoft.FSharp.Collections命名空间下的FSharpMap类型了。我们也为它准备了同样的试验代码:

var map = source.Aggregate(FSharpMap<int, int>.Empty, (m, i) => m.Add(i, i));
CodeTimer.Time("Immutable Map", iteration, () =>
{
    foreach (var i in source)
    {
        var ignore = map[i];
    }
});

把它和ReaderWriterLockSlim相比,结果如下:

ReaderWriterLockSlim
        Time Elapsed:   1,232ms
        CPU Cycles:     2,963,830,380
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

Immutable Map
        Time Elapsed:   2,055ms
        CPU Cycles:     4,956,894,996
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

嗯?为什么使用Immutable Map之后,即便没有锁,性能还是不如ReaderWriterLockSlim的版本呢?阅读代码(fsharp\FSharp.Core\map.fs)之后发现,其原因在于数据结构的选取上。FSharpMap的数据结构是“AVL树”,即自平衡(self-balancing)的二叉搜索树,它的Get操作时间复杂度是O(logN),N为节点个数——这自然比不过字典的O(1)时间复杂度了。那么,我们能否得到一个Get操作时间复杂度为O(1)的Immutable Map呢?

我在推特上提出这个问题之后不多久,许式伟大牛谈了他的看法:

我的理解中,FP中线性数据结构如数组,Hash等都会失效,所以没有O(1)的Immutable Map。

我同意这个看法。字典的高性能,在于求得key的Hash之后,可以通过数组下标“瞬间”定位到元素所在的bucket,但是在FP中无法做到这一点。不过幸好,我们用的C#并非是FP,我们有自己的“保底”方案:添加元素时将现有的元素完整复制到新的字典中,最后返回的是新的字典。例如:

public static class DictionaryExtensions
{
    public static Dictionary<TKey, TValue> AddImmutably<TKey, TValue>(
        this Dictionary<TKey, TValue> source, TKey key, TValue value)
    {
        var result = source.ToDictionary(p => p.Key, p => p.Value);
        result.Add(key, value);
        return result;
    }
}

这不就是一个“不可变的哈希表”吗?当然,对于真正可应用的缓存容器来说,还需要考虑更多一些东西。我在这里准备了两个缓存容器的基类,可用于此类容器的实现。其中ReadWriteCache类基于ReaderWriterLockSlim,而ReadFreeCache类则基于不可变的字典。那么,这两种做法的性能究竟如何,又分别适合什么样的场景,我们还有没有其他的做法呢?

关于这些问题,就留到下次再讨论吧。

相关文章

Creative Commons License

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

Add your comment

57 条回复

  1. 不若相忘于江湖
    *.*.*.*
    链接

    不若相忘于江湖 2009-11-12 00:05:00


    哈哈. 沙发.

    老赵. 你的产量怎么这么高啊. 一篇文章下来少则上千.

    多则几千. 佩服.

  2. 老赵
    admin
    链接

    老赵 2009-11-12 00:09:00

    @不若相忘于江湖
    不就是码字嘛,很快的,半小时就可以1.5K字。
    以前见过专业的速记员,1000字也就2、3分钟的事情。
    基本上都是随读随录的。

  3. 木野狐(Neil Chen)
    *.*.*.*
    链接

    木野狐(Neil Chen) 2009-11-12 01:48:00

    AddImmutably 每执行一遍就要重新创建一个字典,并复制现有字典里的所有元素,然后返回新字典。

    对这个我有点疑问,假设对一个现有元素比较多的字典,比如连续增加50个元素,那么字典不是要被重新创建50次么?

    如果加一个类似 AddRangeImmutably 的方法会不会好点。

  4. toEverybody
    *.*.*.*
    链接

    toEverybody 2009-11-12 02:11:00

    适用于Winform程序吗???

  5. 老赵
    admin
    链接

    老赵 2009-11-12 09:02:00

    @toEverybody
    这是.NET基础,和具体啥表现技术有啥关系……

  6. 老赵
    admin
    链接

    老赵 2009-11-12 09:02:00

    @木野狐(Neil Chen)
    当然,如果是真实环境需要的话,一个AddRangeImmutably也是必要的。
    同样必要的还有为字典提供初始化元素,而不是准备一个空的然后一点点加。
    还有就是,这个只是个说明问题的示例了,呵呵,你看我的ReadFreeCache也没有直接这么搞。

  7. 可可NET
    *.*.*.*
    链接

    可可NET 2009-11-12 09:03:00

    怎么没有原来的跳转了?

  8. 老赵
    admin
    链接

    老赵 2009-11-12 09:05:00

    @可可NET
    什么跳转?

  9. 刘领福
    *.*.*.*
    链接

    刘领福 2009-11-12 09:09:00

    经常观注老赵的文章,很Humor!

  10. Zhenway
    *.*.*.*
    链接

    Zhenway 2009-11-12 09:26:00

    Jeffrey Zhao:
    “读写锁”在.NET框架中有着两个实现:ReaderWriterLock和ReaderWriterLockSlim。前者出现在.NET 1.x中,而后者随.NET 2.0发布。


    挑个毛病,ReaderWriterLockSlim是随着.net 3.5发布的
    另外,老赵不妨写一个Lock-Free的哈希表吧

  11. GUO Xingwang
    *.*.*.*
    链接

    GUO Xingwang 2009-11-12 09:31:00

    老赵很让人佩服

  12. 老赵
    admin
    链接

    老赵 2009-11-12 09:36:00

    @Zhenway
    哦,谢谢指出,我确认一下。Lock-Free的哈希表已经有了,4.0的ConcurrentDictionary。
    不过在现在这个场景中,Lock-Free并不优,因为花了很多开销在于同步,性能比Read Free要差很多,我猜甚至比不上RwLockSlim。
    ConcurrentDictionary的适用场景在于不停地需要读写,而不是现在这种少量写,大量读。
    下次我会谈谈这个问题,呵呵。

  13. overred
    *.*.*.*
    链接

    overred 2009-11-12 10:05:00

    高并发且元素多的情况下,对字典读写操作可以使用主副模式(以空间换时间):

             Dictionary<int, Test> main = new Dictionary<int, Test>();
             Test t1 = new Test("t1");
             main.Add(0, t1);
             //........
    
             Dictionary<int, Test> sub = null;
             lock (_syncRoot)
             {
                sub = new Dictionary<int, Test>(main);
             }
    

    以后就可no-lock对sub进行读操作,
    对main进行low-lock读写操作。

    而不用在main的foreach里进行任何锁(在循环里执行锁操作,不管是否slim,都是低效的吧)。

  14. 老赵
    admin
    链接

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

    @overred
    这个就是我最后给的ReadFreeCache里的做法,其实这个就是不可变得哈希表,呵呵。

  15. 老赵
    admin
    链接

    老赵 2009-11-12 10:14:00

    @overred
    好像也有些不一样,没咋听懂,foreach是什么意思?你能不能完整实现这个接口呢?

    public interface IConcurrentCache<TKey, TValue>
    {
        TValue Get(TKey key);
        void Set(TKey key, TValue value);
    }
    可以不关心Get操作给的key不存在,或是用相同的key重复Set的情况。

  16. overred
    *.*.*.*
    链接

    overred 2009-11-12 10:24:00


    Jeffrey Zhao:
    @overred
    好像也有些不一样,没咋听懂,foreach是什么意思?你能不能完整实现这个接口呢?

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

    可以不关心Get操作给的key不存在,或是用相同的key重复Set的情况。


    这个可以关心。。。。

             foreach (KeyValuePair<int, Test> kvp in sub)
             {
                if (main.ContainsKey(kvp.Key))
                {
                   lock (_syncRoot1) main.Remove(kvp.Key);
                }
             }
    


    不知道咱俩的内心世界是否想着同一个美女?

  17. 老赵
    admin
    链接

    老赵 2009-11-12 10:26:00

    @overred
    很可能不是同一个美女……
    我说的不用关心,是指可以简化开发,呵呵……foreach操作不在我的考虑范围内,因为平时没人对缓存容器做foreach啊。
    话说你还是实现一个IConcurrentCache吧,就两个方法,我现在还是不懂你的意思,呵呵。

  18. Steven Chen
    *.*.*.*
    链接

    Steven Chen 2009-11-12 10:39:00

    非常好非常好非常好的文章,在还没有看你写的那两个实现之前先回帖。


    非常让我郁闷的是,场景中的Cache不仅仅要高速读取,而且写入的也是比较频繁,读:写小于2:1吧,同时Cache非常非常的大,痛苦啊ing......

    我记得我在很早之前做的测试,读:写=2:1 500万元素 (实际上我的场景中所谓的写入仅仅是TValue里面的一个Int属性++,真正的添加元素没有这么多), 使用ReaderWriterLockSlim好像是还没有直接全部lock快????(我非常怀疑是我的测试代码写错了)

    大牛您能不能打您上面那组测试加入Lock的一组结果。

  19. 老赵
    admin
    链接

    老赵 2009-11-12 10:43:00

    @Steven Chen
    我的场景是要求读写比很高的,10000 : 1甚至更高的数量级,而且往往到了一定阶段就不增加了,呵呵。
    你的场景,ReaderWriterLockSlim就行,但是ConcurrentDictionary可能更好,这需要你试验一下了。
    如果比单线程的话,ReaderWriterLockSlim的确不如lock,但是RwLock的优势就在于,它不是所有操作完全互斥,它的read操作时可以并行的,因此并发环境下比lock有优势。

  20. 老赵
    admin
    链接

    老赵 2009-11-12 10:46:00

    @Steven Chen
    我这里比较性能都是相对的,使用RWLock的确比Read Free要慢,但其实还是非常快的,所以是否要在这方面追求很多,需要根据实际情况考虑一下,呵呵。

  21. Zhenway
    *.*.*.*
    链接

    Zhenway 2009-11-12 11:07:00

    @Jeffrey Zhao
    ConcurrentDictionary内部还是用lock的。。。只不过lock的对象好像和桶有关,降低了,没仔细研究它的代码

    @Steven Chen
    当然只读Dictionary肯定是最快的(无锁,效率谁与争锋?),
    读写锁因为读可以并发,适合读写比很高的情况,
    排他锁(lock)的方式因为Monitor实现的效率很高而适合读写比接近1的情况,所以2:1的情况肯定是用排他锁效率最好

    至于前面说的lock-free dictionary的话,纯粹是因为想挑战一下,如果能写出来的话,效率应该比lock的方式好一些,不过肯定也存在某些限制

  22. 老赵
    admin
    链接

    老赵 2009-11-12 11:09:00

    @Zhenway
    要写出高效的lock-free容器不容易啊,例如很可能先用lock-free尝试,再结合SpinWait,再某些时候再上lock的做法……

  23. 宗哥
    *.*.*.*
    链接

    宗哥 2009-11-12 11:45:00

    学习了不少。

  24. 简单生活
    *.*.*.*
    链接

    简单生活 2009-11-12 12:40:00

    简化一下,这样实现如何?

          private Dictionary<K, V> dictionary = new Dictionary<K, V>();
    
          /// <summary>
          /// 
          /// </summary>
          /// <param name="key"></param>
          /// <returns></returns>
          public V this[ K key ]
          {
             get { return dictionary[key]; }
             set { Set( key, value ); }
          }
    
          /// <summary>
          /// 
          /// </summary>
          /// <param name="key"></param>
          /// <param name="value"></param>
          public void Add( K key, V value )
          {
             Dictionary<K, V> old;
             Dictionary<K, V> _new;
             do
             {
                old = dictionary;
                _new = new Dictionary<K, V>( old );
                _new.Add( key, value );
             } while ( Interlocked.CompareExchange( ref dictionary, _new, old ) != old );
          }
    
    

  25. 老赵
    admin
    链接

    老赵 2009-11-12 12:53:00

    @简单生活
    并发环境下会出现许多无用的字典,所以我在ReadFreeCache中选择直接使用Lock。

  26. cache[未注册用户]
    *.*.*.*
    链接

    cache[未注册用户] 2009-11-12 13:03:00

    都自己造一个全局容器?
    不用内部的cache?
    效率原因??

  27. 老赵
    admin
    链接

    老赵 2009-11-12 13:06:00

    @cache
    你没有搞清楚现在在解决什么问题……

  28. LoveC#[未注册用户]
    *.*.*.*
    链接

    LoveC#[未注册用户] 2009-11-12 14:11:00

    .Net类库中没有现成的线程安全的容器吗?
    类库中哪个命名空间相当于java.util.concurrent包?

  29. 老赵
    admin
    链接

    老赵 2009-11-12 14:18:00

    @LoveC#
    .NET里有System.Threading命名空间,就是多线程的组件。
    .NET 4.0里有一些线程安全容器,但是并发容器的性能肯定不比现在的做法好。

  30. LoveC#[未注册用户]
    *.*.*.*
    链接

    LoveC#[未注册用户] 2009-11-12 15:22:00

    Jeffrey Zhao:
    @LoveC#
    .NET里有System.Threading命名空间,就是多线程的组件。
    .NET 4.0里有一些线程安全容器,但是并发容器的性能肯定不比现在的做法好。



    能不能对读写次数做记录,根据读写次数之比对同步算法做不同的调整,这样容器在一开始可能性能不是太好,用的多了之后会越来越好,这样的容器能不能实现?

  31. 老赵
    admin
    链接

    老赵 2009-11-12 15:26:00

    @LoveC#
    要做肯定是可以做的,不过大部分应用不需要这样的方式,因为一般都是可以预测出来的。

  32. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-11-12 16:31:00

    Jeffrey Zhao:
    @LoveC#
    要做肯定是可以做的,不过大部分应用不需要这样的方式,因为一般都是可以预测出来的。




    实际上这种容器在大多数应用中是没有实用价值的,因为在它进入最佳状态前,电脑已经重启了。。。。。

  33. Funeral
    *.*.*.*
    链接

    Funeral 2009-11-12 16:43:00

    赵老师,如果这样设计的话,是不是也可行?

    首先定义一个全局Boolean型变量:

    private bool IsWritting;
    


    然后用一个全局变量来存储需要读取的信息的原始值:
    private string oldName = string.Empty;
    


    然后设计可能会有多个线程读/写的属性:
    private string _name ;
    
            public string Name
            {
                set 
                { 
                    IsWritting = true; 
                    oldName = _name;
                    _name = value;
                    IsWritting = false;
                }
                get
                {
                    if (!IsWritting) return _name;
                    else if (string.IsNullOrEmpty(oldName))
                        return _name;
                    else
                        return oldName;
                }
            }
    

  34. 老赵
    admin
    链接

    老赵 2009-11-12 20:04:00

    Ivony...:
    实际上这种容器在大多数应用中是没有实用价值的,因为在它进入最佳状态前,电脑已经重启了。。。。。


    话说好像ReadWriteLockSlim会自我调整的,刚试了一下,呵呵。

  35. 老赵
    admin
    链接

    老赵 2009-11-12 20:06:00

    @Funeral
    你这边没有任何线程控制逻辑,当然不行……

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

    韦恩卑鄙 alias:v-zhewg 2009-11-13 01:01:00

    public static class DictionaryExtensions
    {
        public static Dictionary<TKey, TValue> AddImmutably<TKey, TValue>(
            this Dictionary<TKey, TValue> source, TKey key, TValue value)
        {
            var result = source.ToDictionary(p => p.Key, p => p.Value);
            result.Add(key, value);
            return result;
        }
    }
    


    这个不喜欢 有多少个元素还要凭空算多少次hash

    我个人建议 从dictionary 派生一个cloneable的版本

    把克隆的引用放在一个不可写的外壳里面

    比如

     class DicClonable<Tkey,Tvalue>
      {
        ......
       DicClonable<Tkey,Tvalue> Clone()
       {
           return this.memberwiseclone() as DicClonable<Tkey,Tvalue> ;
        }
      }
    


    class DicReadonly<Tkey,TValue>:IDictionary<Tkey,TValue>:
    {
       IDictionary<Tkey,TValue> _core
       DicReadonly(IDictionary<Tkey,TValue>: core)
        {
           this._core =core;
        }
       void Add()
       {
          throw new notimplemtsexception();
       }
      TValue this[Tkey key]
      {
          get{return core[key]}
          set {throw new notimplemtsexception();}
      }
    }
    
    
    

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

    韦恩卑鄙 alias:v-zhewg 2009-11-13 01:11:00

    又重新想了下
    我这个想法是因为你德扩展来自 Dictionary 把一个已经尽力好的hashtable作为参数 所以第一次建立dictionary的整个hash计算是无用功
    换个角度看的话 如果一开始你输入的就是一个准KeyValuePair<TKey,TValue> 的话 这个损耗就可以避免

    比如

       int[] ints;
       var  ints.ToDictionary(){i=>i,i=>i.ToString()};
    

    直接这么搞 应该也是不错的,相比之下强行扩展到Dictionary反倒有点多余了

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

    韦恩卑鄙 alias:v-zhewg 2009-11-13 01:27:00

    话说我是很相信 rwslim的 而且他很适合我常用的场景 从基本原理的理解上 感觉不会有在我常用场景比这个更高效的应用了
    于是我做了如下实现

     public   class SyncDictionary<TKey, TValue> : Dictionary<TKey, TValue> ,ICloneable
        {
    
          public SyncDictionary():base(){}
    
          public SyncDictionary(int capacity) : base(capacity) { }
    
          public SyncDictionary(IEqualityComparer <TKey > comparer) : base( comparer ) { }
          public SyncDictionary(int capacity, IEqualityComparer<TKey> comparer) : base(capacity,comparer) { }
    
    
          public SyncDictionary(IDictionary<TKey, TValue> dictionary) : base(dictionary) { }
    
          public SyncDictionary(System.Runtime.Serialization.SerializationInfo info, System.Runtime.Serialization.StreamingContext context) : base(info,context ) { }
    
         
    
          public SyncDictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer) : base(dictionary, comparer) { }
    
    
            private ReaderWriterLockSlim _lock = new ReaderWriterLockSlim();
    
            public new void Add(TKey key, TValue value)
            {
                _lock.EnterWriteLock();
                base.Add(key, value);
                _lock.ExitWriteLock();
    
            }
    
            public new void Clear()
            {
                _lock.EnterWriteLock();
                base.Clear();
                _lock.ExitWriteLock();
    
            }
            public new bool ContainsKey(TKey key)
            {
                _lock.EnterReadLock();
                var rv = base.ContainsKey(key);
                _lock.ExitReadLock();
                return rv;
            }
    
    
    
            public new bool ContainsValue(TValue value)
            {
                _lock.EnterReadLock();
                var rv = base.ContainsValue(value);
                _lock.ExitReadLock();
                return rv;
            }
    
    
            public new Dictionary<TKey, TValue>.Enumerator GetEnumerator()
            {
                _lock.EnterReadLock();
                var rv = new Dictionary<TKey, TValue>(this).GetEnumerator();
                _lock.ExitReadLock();
                return rv;
            }
            public new bool Remove(TKey key)
            {
                _lock.EnterWriteLock();
                var rv = base.Remove(key);
                _lock.ExitWriteLock();
                return rv;
    
            }
            public new bool TryGetValue(TKey key, out TValue value)
            {
                _lock.EnterReadLock();
                var rv = base.TryGetValue(key, out value);
                _lock.ExitReadLock();
                return rv;
    
            }
    
    
            public new int Count
            {
                get
                {
                    _lock.EnterReadLock();
                    var rv = base.Count;
                    _lock.ExitReadLock();
                    return rv;
                }
    
            }
    
    
            public new TValue this[TKey key]
            {
                get
                {
                    _lock.EnterReadLock();
                    var rv = base[key];
                    _lock.ExitReadLock();
                    return rv;
                }
                set
                {
                    _lock.EnterWriteLock();
                    base[key] = value;
                    _lock.ExitWriteLock();
           
                }
            }
    
    
            public  new Generic.Dictionary <TKey, TValue>.KeyCollection Keys
            {
                get
                {
    
                    _lock.EnterReadLock();
                    var rv = new KeyCollection( this);
                    _lock.ExitReadLock();
                    return rv;
                }
    
            }
    
            public new Generic.Dictionary<TKey, TValue>.ValueCollection Values
            {
                get
                {
                    _lock.EnterReadLock();
                    var rv = new ValueCollection (this);
                    _lock.ExitReadLock();
                    return rv;
                }
    
    
       
            }
     
     public  SyncDictionary<TKey, TValue> GetDeepCopy  ()
      {
          return (SyncDictionary<TKey, TValue>)Clone();
      }
    
    
    
    
        
    #region ICloneable Members
    
    public object  Clone()
    {
     	return MemberwiseClone ();
    }
    
    #endregion
    }
    


    目前看 可能对于values 和keys 的属性还有优化余地
    这两个属性在读取的过程 没做到深复制 但是作为一个不常用的功能 我妥协了 >_<

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

    韦恩卑鄙 alias:v-zhewg 2009-11-13 01:31:00

    再贴一个 给线程不安全的字典带上的线程安全套
    建议老赵采用的只读安全套 也大抵从这里开始。

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.ComponentModel;
    using System.ComponentModel.Design;
    using System.Runtime.InteropServices;
    using System.Diagnostics;
    using System.Threading;
    using System.Security.Permissions;
    namespace System.Collections.Generic.Sync
    {
     public class SyncDictionaryProxty<TKey, TValue> : IDictionary<TKey, TValue>
     {
      private ReaderWriterLockSlim _lock = new ReaderWriterLockSlim();
      IDictionary<TKey, TValue> BaseDictionary { get; set; }
      private ICollection<KeyValuePair<TKey, TValue>> BaseCollection
      {
       get
       { return (ICollection<KeyValuePair<TKey, TValue>>)BaseDictionary; }
       
      }
      public SyncDictionaryProxty(IDictionary<TKey, TValue> dictionary)
      {
       BaseDictionary = dictionary;
      }
      #region IDictionary<TKey,TValue> Members
    
      public void Add(TKey key, TValue value)
      {
       _lock.EnterWriteLock();
       BaseDictionary.Add(key, value);
       _lock.ExitWriteLock();
      }
    
      public bool ContainsKey(TKey key)
      {
        
       _lock.EnterReadLock();
       var rv = BaseDictionary .ContainsKey(key);
       _lock.ExitReadLock();
       return rv;
      }
    
      public ICollection<TKey> Keys
      {
       get
       {
        _lock.EnterReadLock();
        var rv = BaseDictionary.Keys.ToList();
        _lock.ExitReadLock();
        return rv;
       }
      }
    
      public bool Remove(TKey key)
      {
       _lock.EnterWriteLock();
       var rv = BaseDictionary.Remove(key);
       _lock.ExitWriteLock();
       return rv;
      }
    
      public bool TryGetValue(TKey key, out TValue value)
      {
       _lock.EnterReadLock();
       var rv = BaseDictionary.TryGetValue(key, out value);
       _lock.ExitReadLock();
       return rv;
      }
    
      public ICollection<TValue> Values
      {
       get
       {
        _lock.EnterReadLock();
        var rv = BaseDictionary.Values.ToList ();
        _lock.ExitReadLock();
        return rv;
       }
      }
    
      public TValue this[TKey key]
      {
       get
       {
        _lock.EnterReadLock();
        var rv = BaseDictionary[key];
        _lock.ExitReadLock();
        return rv;
       }
       set
       {
        _lock.EnterWriteLock();
        BaseDictionary[key] = value;
        _lock.ExitWriteLock();
    
       }
      }
    
      #endregion
    
      #region ICollection<KeyValuePair<TKey,TValue>> Members
    
      public void Add(KeyValuePair<TKey, TValue> item)
      {
       _lock.EnterWriteLock();
       BaseCollection.Add(item);
       _lock.ExitWriteLock ();
       
      }
    
      public void Clear()
      {
       _lock.EnterWriteLock();
       BaseCollection.Clear ();
       _lock.ExitWriteLock();
      }
    
      public bool Contains(KeyValuePair<TKey, TValue> item)
      {
       _lock.EnterReadLock ();
       var rv = BaseCollection.Contains(item);
       _lock.ExitReadLock ();
       return rv;
    
      }
    
      public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
      {
       _lock.EnterReadLock();
       BaseCollection.CopyTo(array, arrayIndex);
       _lock.ExitReadLock();
      }
    
      public int Count
      {
       get {
        _lock.EnterReadLock();
        var rv = BaseCollection.Count;
        _lock.ExitReadLock();
        return rv;
       }
      }
    
      public bool IsReadOnly
      {
       get
       {
    
        return BaseCollection.IsReadOnly;
    
       }
      }
    
      public bool Remove(KeyValuePair<TKey, TValue> item)
      {
       _lock.EnterWriteLock ();
       var rv = BaseCollection.Remove(item);
       _lock.ExitWriteLock();
       return rv;
      }
    
      #endregion
    
      #region IEnumerable<KeyValuePair<TKey,TValue>> Members
    
      public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
      {
       return BaseDictionary.GetEnumerator();
      }
    
      #endregion
    
      #region IEnumerable Members
    
      IEnumerator IEnumerable.GetEnumerator()
      {
       return BaseDictionary.GetEnumerator();
      }
    
      #endregion
     }
    }
    

  40. 老赵
    admin
    链接

    老赵 2009-11-13 01:37:00

    @韦恩卑鄙 alias:v-zhewg
    你越搞越复杂了……不同场景就有不同应对方式么,不可变的哈希表最适合读取了。
    只要你用了RWLock,就算Slim的,也肯定比不上不用任何锁的读呀,嘿嘿。
    这种缓存场景,就一个Get,最多再来个Set,有谁会遍历缓存内所有元素啊,同理Count啊CopyTo我都不考虑了。
    要说并发的字典,.NET 4中有ConcurrentDictionary,其实性能很高,比用RWLockSlim要好,而且它可以并发写,锁的粒度很小。
    这些都不容易啊。

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

    韦恩卑鄙 alias:v-zhewg 2009-11-13 01:38:00

    上面贴的两个 是为了能够更方便的和老赵你下一章的成品做一个直观的比较

    一旦你提出来的方案更快 我马上抄去 :D

  42. 老赵
    admin
    链接

    老赵 2009-11-13 01:39:00

    韦恩卑鄙 alias:v-zhewg:
    再贴一个 给线程不安全的字典带上的线程安全套
    建议老赵采用的只读安全套 也大抵从这里开始。


    总之,只要带套,再Slim也比不上我在这里无套内射来的彻底啊,姆嘿嘿嘿嘿……

  43. 老赵
    admin
    链接

    老赵 2009-11-13 01:41:00

    韦恩卑鄙 alias:v-zhewg:
    上面贴的两个 是为了能够更方便的和老赵你下一章的成品做一个直观的比较

    一旦你提出来的方案更快 我马上抄去 :D


    我不考虑完整的字典啊,我只考虑我文章最后贴出来的代码所用的场景……
    你用了ReaderWriterLock,就和我文章里的例子一样了……但这就是我想突破的……

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

    韦恩卑鄙 alias:v-zhewg 2009-11-13 01:42:00

    Jeffrey Zhao:
    @韦恩卑鄙 alias:v-zhewg

    这种缓存场景,就一个Get,最多再来个Set,有谁会遍历缓存内所有元素啊,同理Count啊CopyTo我都不考虑了。
    要说并发的字典,.NET 4中有ConcurrentDictionary,其实性能很高,比用RWLockSlim要好,而且它可以并发写,锁的粒度很小。
    这些都不容易啊。


    话说我做游戏大厅的用户列表就是经常要遍历的。 咱们场景确实差很多

    我最初的版本是用hashtable 的clone 没加锁。当然用户多的时候就会卡:(

  45. 老赵
    admin
    链接

    老赵 2009-11-13 01:42:00

    俺去睡了,不睡明天干不动了……

  46. 老赵
    admin
    链接

    老赵 2009-11-13 01:47:00

    韦恩卑鄙 alias:v-zhewg:
    话说我做游戏大厅的用户列表就是经常要遍历的。 咱们场景确实差很多
    我最初的版本是用hashtable 的clone 没加锁。当然用户多的时候就会卡:(


    用.NET 4的ConcurrentDictionary吧,写一个高效的并发字典很困难的。

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

    韦恩卑鄙 alias:v-zhewg 2009-11-13 01:50:00

    属于高科技阿 我们那个项目1.1开始的 哪里用到4.0了聂5555
    今天还是第一次听说这玩意,不信你去bing一下
    ConcurrentDictionary+性能 就你这一帖
    哈哈

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

    韦恩卑鄙 alias:v-zhewg 2009-11-13 01:52:00

    等你弄好 加上ConcurrentDictionary一起作个测试报告吧 填补中文资料空白!

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

    韦恩卑鄙 alias:v-zhewg 2009-11-13 02:20:00

    参考了这个地址的测试资料
    http://www.lovethedot.net/2009/04/bit-about-performance-of-concurrent.html
    我感觉似乎还是很不错啊

  50. 老赵
    admin
    链接

    老赵 2009-11-13 09:04:00

    韦恩卑鄙 alias:v-zhewg:等你弄好 加上ConcurrentDictionary一起作个测试报告吧 填补中文资料空白!


    不过我测试的应该只是我的场景,和你的差别还是蛮大的……

  51. airwolf2026
    *.*.*.*
    链接

    airwolf2026 2009-11-13 18:23:00

    @Jeffrey Zhao

    老赵你的推特不用爬墙呀?莫非你不是在中国?

  52. 老赵
    admin
    链接

    老赵 2009-11-13 18:42:00

    @airwolf2026
    我们一起欢迎邪恶美帝的奥巴马总统入贡吧。

  53. 骑着夕阳看着猪
    *.*.*.*
    链接

    骑着夕阳看着猪 2009-11-16 10:04:00

    老赵的文章越写越好啊,复杂东东东,却写的浅显易懂,特意登录来回复~~~老赵,牛牛~~~

  54. xxxxxxxx[未注册用户]
    *.*.*.*
    链接

    xxxxxxxx[未注册用户] 2009-11-17 21:44:00

    头像, 后面怎么还有一个面目狰狞的...

  55. xxxxxxxx[未注册用户]
    *.*.*.*
    链接

    xxxxxxxx[未注册用户] 2009-11-17 21:47:00

    xxxxxxxx:头像, 后面怎么还有一个面目狰狞的...


    好吧, 貌似还有一个美女.

  56. .net爱好者-sanji[未注册用户]
    *.*.*.*
    链接

    .net爱好者-sanji[未注册用户] 2009-11-18 20:33:00

    我觉得没必要考虑得如此复杂,读的时候可以不加锁,除非一些特定的领域才有必要在读的时候加锁,你认为了?

  57. 老赵
    admin
    链接

    老赵 2009-11-18 21:08:00

    @.net爱好者-sanji
    那是,当然只需要在特定环境下才需要加锁——这个特定环境不就是我文章里写的并发环境吗?

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我