1

我正在研究线程安全的多值字典。在内部，此字典使用带有自定义链接列表作为值的并发字典 (.net 4.0)。在链接列表中添加了相同的关键项。问题是当我使用并发字典的 AddOrUpdate 方法（方法 1）插入项目时，与使用 TryGetValue 方法检查键是否存在然后添加或更新值相比，代码运行速度有点慢手动锁内（方法 2）。使用第一种方法插入 300 万条记录大约需要 20 秒，而使用第二种方法在同一台机器上大约需要 9.5 秒（Intel i3 第二代 2.2 ghz 和 4 Gb ram）。一定有一些我无法弄清楚的东西丢失了。

我还检查了并发字典的代码，但它似乎和我在锁内做的一样：

public TValue AddOrUpdate(TKey key, Func<TKey, TValue> addValueFactory, Func<TKey, TValue, TValue> updateValueFactory)
    {
        if (key == null) throw new ArgumentNullException("key"); 
        if (addValueFactory == null) throw new ArgumentNullException("addValueFactory");
        if (updateValueFactory == null) throw new ArgumentNullException("updateValueFactory"); 

        TValue newValue, resultingValue;
        while (true) 
        {
            TValue oldValue;
            if (TryGetValue(key, out oldValue))
            //key exists, try to update 
            {
                newValue = updateValueFactory(key, oldValue); 
                if (TryUpdate(key, newValue, oldValue)) 
                {
                    return newValue; 
                }
            }
            else //try add
            { 
                newValue = addValueFactory(key);
                if (TryAddInternal(key, newValue, false, true, out resultingValue)) 
                { 
                    return resultingValue;
                } 
            }
        }
    }

这是线程安全多值字典的代码（方法 2 已注释，取消注释以检查差异）。

更新：下面还有我没有粘贴的删除、添加和其他方法。

class ValueWrapper<U, V>
{
    private U _key;
    private V _value;

    public ValueWrapper(U key, V value)
    {
        this._key = key;
        this._value = value;
    }

    public U Key
    {
        get { return _key; }
    }

    public V Value
    {
        get { return _value; }
        set { _value = value; }
    }
}

class LinkNode<Type>
{
    public LinkNode(Type data)
    {
        Data = data;
    }
    public LinkNode<Type> Next;
    public Type Data;
}

public class SimpleLinkedList<T> 
{
    #region Instance Member Variables
    private LinkNode<T> _startNode = null;
    private LinkNode<T> _endNode = null;
    private int _count = 0;

    #endregion

    public void AddAtLast(T item)
    {
        if (_endNode == null)
            _endNode = _startNode = new LinkNode<T>(item);
        else
        {
            LinkNode<T> node = new LinkNode<T>(item);
            _endNode.Next = node;
            _endNode = node;
        }

        _count++;
    }

    public T First
    {
        get { return _startNode == null ? default(T) : _startNode.Data; }
    }

    public int Count
    {
        get { return _count; }
    }

}

class MultiValThreadSafeDictionary<U, T>
{
    private ConcurrentDictionary<U, SimpleLinkedList<ValueWrapper<U, T>>> _internalDictionary;

    private ReaderWriterLockSlim _slimLock = new ReaderWriterLockSlim();


    public MultiValThreadSafeDictionary()
    {
        _internalDictionary = new ConcurrentDictionary<U, SimpleLinkedList<ValueWrapper<U, T>>>(2, 100);
    }

    public T this[U key]
    {
        get
        {
            throw new NotImplementedException();
        }
        set
        {
            /* ****Approach 1 using AddOrUpdate**** */


            _internalDictionary.AddOrUpdate(key, (x) =>
            {
                SimpleLinkedList<ValueWrapper<U, T>> list = new SimpleLinkedList<ValueWrapper<U, T>>();
                ValueWrapper<U, T> vw = new ValueWrapper<U, T>(key, value);
                list.AddAtLast(vw);
                //_internalDictionary[key] = list;

                return list;
            },

            (k, existingList) =>
            {
                try
                {
                    _slimLock.EnterWriteLock();

                    if (existingList.Count == 0)
                    {
                        ValueWrapper<U, T> vw = new ValueWrapper<U, T>(key, value);
                        existingList.AddAtLast(vw);
                    }
                    else
                        existingList.First.Value = value;

                    return existingList;
                }
                finally
                {
                    _slimLock.ExitWriteLock();
                }
            });


            /* ****Approach 2 not using AddOrUpdate**** */

            /*
            try
            {
                _slimLock.EnterWriteLock();

                SimpleLinkedList<ValueWrapper<U, T>> list;
                if (!_internalDictionary.TryGetValue(key, out list))
                {
                    list = new SimpleLinkedList<ValueWrapper<U, T>>();
                    ValueWrapper<U, T> vw = new ValueWrapper<U, T>(key, value);

                    list.AddAtLast(vw);

                    _internalDictionary[key] = list;
                    //_iterator.AddAtLast(vw);
                    return;
                }

                if (list.Count == 0)
                {
                    ValueWrapper<U, T> vw = new ValueWrapper<U, T>(key, value);
                    list.AddAtLast(vw);
                    //_iterator.AddAtLast(vw);
                }
                else
                    list.First.Value = value;
            }
            finally
            {
                _slimLock.ExitWriteLock();
            }
            */

        }
    }
}

测试代码仅插入项目，所有项目都具有唯一键。如下。

MultiValThreadSafeDictionary<string, int> testData = new MultiValThreadSafeDictionary<string, int>();

    Task t1 = new Task(() =>
        {
            for (int i = 0; i < 1000000; i++)
            {
                testData[i.ToString()] = i;
            }
        }
    );

    Task t2 = new Task(() =>
    {
        for (int i = 1000000; i < 2000000; i++)
        {
            testData[i.ToString()] = i;
        }
    }
    );

    Task t3 = new Task(() =>
    {
        for (int i = 2000000; i < 3000000; i++)
        {
            testData[i.ToString()] = i;
        }
    }
    );

    Stopwatch watch = new Stopwatch();
    watch.Start();

    t1.Start();
    t2.Start();
    t3.Start();

    t1.Wait();
    t2.Wait();
    t3.Wait();

    watch.Stop();

    Console.WriteLine("time taken:" + watch.ElapsedMilliseconds);

更新1：

根据“280Z28”的回答，我重新表述了这个问题。为什么 GetOrAdd 和“我的”方法花费几乎相同的时间，而在我的方法中，我需要一个额外的锁并且还调用 TryAndGet 方法。以及与 AddOrGet 相比，为什么 AddOrUpdate 需要双倍的时间。所有方法的代码如下：

ConcurrentDictionary (.net 4) 中的 GetOrAdd 和 AddOrUpdate 方法具有以下代码：

public TValue GetOrAdd(TKey key, TValue value)
{
    if (key == null) throw new ArgumentNullException("key");
    TValue resultingValue;
    TryAddInternal(key, value, false, true, out resultingValue); 
    return resultingValue; 
}

public TValue AddOrUpdate(TKey key, Func<TKey, TValue> addValueFactory, Func<TKey, TValue, TValue> updateValueFactory)
{
    if (key == null) throw new ArgumentNullException("key"); 
    if (addValueFactory == null) throw new ArgumentNullException("addValueFactory");
    if (updateValueFactory == null) throw new ArgumentNullException("updateValueFactory"); 

    TValue newValue, resultingValue;
    while (true) 
    {
        TValue oldValue;
        if (TryGetValue(key, out oldValue))
        //key exists, try to update 
        {
            newValue = updateValueFactory(key, oldValue); 
            if (TryUpdate(key, newValue, oldValue)) 
            {
                return newValue; 
            }
        }
        else //try add
        { 
            newValue = addValueFactory(key);
            if (TryAddInternal(key, newValue, false, true, out resultingValue)) 
            { 
                return resultingValue;
            } 
        }
    }
}

GetOrAdd 在我的代码中使用如下（需要 9 秒）：

SimpleLinkedList<ValueWrapper<U, T>> existingList = new SimpleLinkedList<ValueWrapper<U, T>>();
existingList = _internalDictionary.GetOrAdd(key, existingList);
try
{
    _slimLock.EnterWriteLock();

    if (existingList.Count == 0)
    {
        ValueWrapper<U, T> vw = new ValueWrapper<U, T>(key, value);
        existingList.AddAtLast(vw);
    }
    else
        existingList.First.Value = value;
}
finally
{
    _slimLock.ExitWriteLock();
}

AddOrUpdate 的使用如下（所有添加需要 20 秒，没有更新）。如答案之一所述，这种方法不适合更新。

_internalDictionary.AddOrUpdate(key, (x) =>
{
    SimpleLinkedList<ValueWrapper<U, T>> list = new SimpleLinkedList<ValueWrapper<U, T>>();
    ValueWrapper<U, T> vw = new ValueWrapper<U, T>(key, value);
    list.AddAtLast(vw);
    return list;
},

(k, existingList ) =>
{
    try
    {
        _slimLock.EnterWriteLock();

        if (existingList.Count == 0)
        {
            ValueWrapper<U, T> vw = new ValueWrapper<U, T>(key, value);
            existingList.AddAtLast(vw);
        }
        else
            existingList.First.Value = value;

        return existingList;
    }
    finally
    {
        _slimLock.ExitWriteLock();
    }
});

没有 AddOrGet 和 AddOrUpdate 的代码如下（耗时 9.5 秒）：

try
{
    _slimLock.EnterWriteLock();

    VerySimpleLinkedList<ValueWrapper<U, T>> list;
    if (!_internalDictionary.TryGetValue(key, out list))
    {
        list = new VerySimpleLinkedList<ValueWrapper<U, T>>();
        ValueWrapper<U, T> vw = new ValueWrapper<U, T>(key, value);

        list.AddAtLast(vw);

        _internalDictionary[key] = list;
        return;
    }

    if (list.Count == 0)
    {
        ValueWrapper<U, T> vw = new ValueWrapper<U, T>(key, value);
        list.AddAtLast(vw);
    }
    else
        list.First.Value = value;
}
finally
{
    _slimLock.ExitWriteLock();
}
4

2 回答 2

1

您不应该使用AddOrUpdate此代码。这一点非常清楚，因为您的更新方法从未真正更新存储在其中的值ConcurrentDictionary——它总是返回existingList不变的参数。相反，您应该执行以下操作。

SimpleLinkedList<ValueWrapper<U, T>> list = _internalDictionary.GetOrAdd(key, CreateEmptyList);
// operate on list here

...

private static SimpleLinkedList<ValueWrapper<U, T>> CreateEmptyList()
{
    return new SimpleLinkedList<ValueWrapper<U, T>>();
}
于 2013-04-30T13:22:20.493 回答
0

对字典的读取操作以无锁方式执行。如http://msdn.microsoft.com/en-us/library/dd287191.aspx中所述

AddOrUpdate 的实现是使用细粒度锁来检查项目是否已经存在，但是当您第一次自己阅读时，无锁阅读会更快，并且这样做可以减少现有项目所需的锁。

于 2013-04-30T08:13:33.710 回答