Я работаю над многопоточным многозначным словарем. Внутри этого словаря используется параллельный словарь (.net 4.0) с настраиваемым списком ссылок в качестве значения. Такие же ключевые элементы добавляются в список ссылок. Проблема в том, что когда я использую метод AddOrUpdate параллельного словаря (подход 1) для вставки элемента, код работает немного медленнее по сравнению с тем, когда я использую метод TryGetValue для проверки наличия ключа. а затем добавьте или обновите значение вручную внутри блокировки (подход 2). Для вставки 3 миллионов записей с использованием первого подхода требуется около 20 секунд, тогда как при использовании второго подхода на одном компьютере (Intel i3 2-го поколения 2,2 ГГц и 4 Гб оперативной памяти) требуется около 9,5 секунд. Должно быть чего-то не хватает, чего я пока не могу понять.
Я также проверил код для параллельного словаря, но, похоже, он делает то же самое, что и я внутри блокировки:
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. И почему AddOrUpdate занимает вдвое больше времени по сравнению с AddOrGet. Код для всех подходов приведен ниже:
Метод GetOrAdd и AddOrUpdate в ConcurrentDictionary (.net 4) имеет следующий код:
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();
}
