Last active
February 1, 2016 19:30
-
-
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //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; | |
| } | |
| } | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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); | |
| } | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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); | |
| } | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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