Skip to content

Instantly share code, notes, and snippets.

@ctigeek
Last active February 1, 2016 19:30
Show Gist options
  • Select an option

  • Save ctigeek/9c93c7557d5c3f1f40ec to your computer and use it in GitHub Desktop.

Select an option

Save ctigeek/9c93c7557d5c3f1f40ec to your computer and use it in GitHub Desktop.
An add-only concurrent dictionary that's lightweight, doesn't require locks on reads. Although it implements IReadOnlyDictionary, you can change values in the dictionary.
//License:
// This code was authored by Steven Swenson (github.com/ctigeek, twitter.com/ctigeek)
// and is released under the MIT license.
// https://opensource.org/licenses/MIT
//
// Use cases for this code:
// You need to have an in-memory dictionary that's only added to, and is typically built when the process spins up.
// You can add items to the dictionary at any time, but it's expensive (i.e. it rebuilds the entire underlying dict) but reads are extrememly fast.
// You can easily augment this code to implement a remove function, but if you're doing lots of adds and removes you're probably better off using a regular ConcurrentDictionary.
// It *does* allow you to modify values. This is slightly misleading since it implements IReadOnlyDictionary.
using System;
using System.Collections;
using System.Collections.Generic;
namespace ConcurrentImmutableDictionary
{
public class ConcurrentImmutableDictionary<TKey, TValue> : IReadOnlyDictionary<TKey, TValue>
{
private static readonly object lockObject = new object();
private Dictionary<TKey, TValue> dictionary;
public ConcurrentImmutableDictionary() : this(null)
{
}
public ConcurrentImmutableDictionary(IDictionary<TKey, TValue> dictionary)
{
var dictCopy = dictionary == null
? new Dictionary<TKey, TValue>()
: new Dictionary<TKey, TValue>(dictionary);
this.dictionary = new Dictionary<TKey, TValue>(dictCopy);
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
return dictionary.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return dictionary.GetEnumerator();
}
public int Count
{
get { return dictionary.Count; }
}
public bool ContainsKey(TKey key)
{
return dictionary.ContainsKey(key);
}
public bool TryGetValue(TKey key, out TValue value)
{
return dictionary.TryGetValue(key, out value);
}
public TValue this[TKey key]
{
get { return dictionary[key]; }
set { dictionary[key] = value; }
}
public IEnumerable<TKey> Keys
{
get { return dictionary.Keys; }
}
public IEnumerable<TValue> Values
{
get { return dictionary.Values; }
}
public void Add(TKey key, TValue value)
{
if (key == null) throw new ArgumentNullException(nameof(key));
lock (lockObject)
{
var newDict = new Dictionary<TKey, TValue>(dictionary);
newDict.Add(key, value);
//The following line is atomic. It does not require a lock by itself, however the Add method could be called simultaneously resulting in data loss without a lock.
dictionary = newDict;
}
}
}
}
using System;
using System.Text;
using System.Threading;
using NUnit.Framework;
// This is designed to test concurrency. It will not fail despite using it concurrently.
namespace ConcurrentImmutableDictionary
{
[TestFixture]
public class ConcurrentImmutableTests
{
private ConcurrentImmutableDictionary<string, string> concurrentImmutableDict;
[Test]
public void Test()
{
concurrentImmutableDict = new ConcurrentImmutableDictionary<string,string>();
for (int i = 0; i < 10000; i++)
{
ThreadPool.QueueUserWorkItem(AddToDict, i.ToString());
var sb = new StringBuilder();
foreach (string s in concurrentImmutableDict.Keys)
{
sb.AppendFormat("int={0}, key={1}, value={2} ", i, s, concurrentImmutableDict[s]);
}
}
}
private void AddToDict(object o)
{
var s = o as string;
concurrentImmutableDict.Add(s, s);
}
}
}
using System.Collections.Generic;
using System.Text;
using System.Threading;
using NUnit.Framework;
//This test is identical to the other test file, but this one uses a regular dictionary and will fail every time due to no support for concurrency.
namespace ConcurrentImmutableDictionary
{
[TestFixture]
public class RegularDictTests
{
private Dictionary<string, string> regularDict;
[Test]
public void Test()
{
regularDict = new Dictionary<string, string>();
for (int i = 0; i < 10000; i++)
{
ThreadPool.QueueUserWorkItem(AddToDict, i.ToString());
var sb = new StringBuilder();
foreach (string s in regularDict.Keys)
{
sb.AppendFormat("int={0}, key={1}, value={2} ", i, s, regularDict[s]);
}
}
}
private void AddToDict(object o)
{
var s = o as string;
regularDict.Add(s, s);
}
}
}
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using NUnit.Framework;
namespace ConcurrentImmutableDictionary
{
[TestFixture]
public class StopwatchTests
{
private Dictionary<string, string> regularDict;
private ConcurrentDictionary<string, string> concurrentDictionary;
private ConcurrentImmutableDictionary<string, string> concurrentImmutableDictionary;
[Test]
public void ConcurrentDictTest()
{
//typically about 3.1 seconds
concurrentDictionary = new ConcurrentDictionary<string, string>();
AddItemsToDict(concurrentDictionary);
var timespan = ReadDict(concurrentDictionary);
Console.WriteLine(timespan.TotalMilliseconds);
}
[Test]
public void ConcurrentImmutableDictionaryTest()
{
//typically about 2.5 seconds
concurrentImmutableDictionary = new ConcurrentImmutableDictionary<string, string>();
for (int i = 0; i < 10000; i++)
{
concurrentImmutableDictionary.Add(i.ToString(), i.ToString());
}
var sw = Stopwatch.StartNew();
var sb = new StringBuilder();
foreach (var key in concurrentImmutableDictionary.Keys)
{
sb.AppendFormat("key={0}, value={1}", key, concurrentImmutableDictionary[key]);
}
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);
}
[Test]
public void RegularDictTest()
{
// typically about 2 seconds. Why is this longer than concurrent??
regularDict = new Dictionary<string, string>();
AddItemsToDict(regularDict);
var timespan = ReadDict(regularDict);
Console.WriteLine(timespan.TotalMilliseconds);
}
private void AddItemsToDict(IDictionary<string, string> dict)
{
for (int i = 0; i < 10000; i++)
{
dict.Add(i.ToString(),i.ToString());
}
}
private TimeSpan ReadDict(IDictionary<string, string> dict)
{
var sw = Stopwatch.StartNew();
var sb = new StringBuilder();
foreach (var key in dict.Keys)
{
sb.AppendFormat("key={0}, value={1}", key, dict[key]);
}
sw.Stop();
return sw.Elapsed;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment