为什么是ConcurrentDictionary.AddOrUpdate方法缓慢
本文关键字：方法 缓慢 AddOrUpdate ConcurrentDictionary 为什么 | 更新日期: 2023-09-27 18:11:33
我正在研究一个线程安全的多值字典。在内部这个字典使用一个并发字典(.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);
根据'280Z28'的回答，我正在改写这个问题。为什么是GetOrAdd和'我的'方法采取几乎相同的时间，在我的方法中，我采取额外的锁，也调用TryAndGet方法也。为什么AddOrUpdate花费的时间是AddOrGet的两倍。所有方法的代码如下:
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();
}
您不应该在此代码中使用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>>();
}
对字典的读操作以无锁方式执行。如http://msdn.microsoft.com/en-us/library/dd287191.aspx
所述
AddOrUpdate的实现是使用细粒度锁来检查项目是否已经存在，但是当你第一次自己读的时候，使用无锁读取会更快，这样你就减少了现有项目所需的锁。