Skip to content

Instantly share code, notes, and snippets.

@jamescrowley
Last active August 18, 2019 20:32
Show Gist options
  • Save jamescrowley/636b5f44fc2fa9fd2a04fca08ecadd3a to your computer and use it in GitHub Desktop.
Save jamescrowley/636b5f44fc2fa9fd2a04fca08ecadd3a to your computer and use it in GitHub Desktop.
SharedKeyDictionary.cs
using System;
using System.Collections;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
namespace MemoryOptimisations
{
public sealed class SharedKeyDictionary<TKey, TValue> : IReadOnlyDictionary<TKey, TValue> where TValue : class
{
private readonly ISharedKeyDictionaryIndexLookup<TKey> _indexLookups;
private TValue[] _values;
private readonly TValue _defaultValue;
public SharedKeyDictionary(ISharedKeyDictionaryIndexLookup<TKey> indexLookups) : this(indexLookups, CreateDefaultValue())
{
}
private static TValue CreateDefaultValue()
{
if (typeof(TValue).IsInterface)
throw new ArgumentException("Must provide a default value when using a value type which is an interface");
return Activator.CreateInstance<TValue>();
}
public SharedKeyDictionary(ISharedKeyDictionaryIndexLookup<TKey> indexLookups, TValue defaultValue)
{
Enforce.IsNotNull(defaultValue, "defaultValue");
_indexLookups = indexLookups;
_defaultValue = defaultValue;
_values = new TValue[indexLookups.Count];
for (int i = 0; i < _values.Length; i++)
{
_values[i] = _defaultValue;
}
}
private SharedKeyDictionary(SharedKeyDictionary<TKey, TValue> copyFrom)
{
_indexLookups = copyFrom._indexLookups;
_values = new TValue[copyFrom._values.Length];
copyFrom._values.CopyTo(_values, 0);
}
public void Add(TKey key, TValue value)
{
this[key] = value;
}
public bool Remove(TKey key)
{
if (!TryGetIndexWithinBounds(key, out int index))
return false;
_values[index] = _defaultValue;
return true;
}
public bool ContainsKey(TKey key)
{
return TryGetValue(key, out TValue value);
}
public bool TryGetValue(TKey key, out TValue value)
{
value = null;
if (!TryGetIndexWithinBounds(key, out var index))
return false;
var storedValue = _values[index];
if (ReferenceEquals(storedValue, _defaultValue))
return false;
value = storedValue;
return true;
}
public TValue this[TKey key]
{
get
{
if (!TryGetValue(key, out TValue value))
throw new KeyNotFoundException(message: $"Could not find the key {key}");
return value;
}
set
{
if (!_indexLookups.TryGetOrAddIndexForKey(key, out int index))
throw new SharedKeyNotDefinedException(message: $"Could not set the {key}");
if (!IsWithinBounds(index))
{
ResizeBoundsForIndex(index);
}
_values[index] = value;
}
}
private void ResizeBoundsForIndex(int index)
{
var initialUpperBound = _values.Length;
var newUpperBound = index + 1;
// this could be optimised in future
//
// However, the usage pattern expected for this dictionary is sequentially
// adding keys to each dictionary (as opposed to adding values to random
// dictionaries sharing the underlying index lookup).
// therefore, we only take the hit resizing the first time we find a new key
// on the first row - subsequent SharedKeyDictionaries will then already
// allocate space for this
Array.Resize(ref _values, newUpperBound);
for (int i = initialUpperBound; i < newUpperBound; i++)
{
_values[i] = _defaultValue;
}
}
private bool TryGetIndexWithinBounds(TKey key, out int index)
{
if (!_indexLookups.TryGetIndexForKey(key, out index))
return false;
if (!IsWithinBounds(index))
return false;
return true;
}
private bool IsWithinBounds(int index)
{
return index < _values.Length;
}
public IEnumerable<TKey> Keys => _indexLookups.Keys.Where(ContainsKey);
public IEnumerable<TValue> Values => _values.Where(x => !ReferenceEquals(x, _defaultValue));
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
return new SharedKeyDictionaryEnumerator<TKey, TValue>(this);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public int Count => _values.Count(x => !ReferenceEquals(x, _defaultValue));
public bool IsReadOnly => false;
}
public class SharedKeyNotDefinedException : Exception
{
public SharedKeyNotDefinedException(string message) : base(message) {}
}
public class ReadOnlySharedKeyDictionaryIndexLookup<TKey> : ISharedKeyDictionaryIndexLookup<TKey>
{
private readonly IReadOnlyDictionary<TKey, int> _keyToIndexLookup;
public ReadOnlySharedKeyDictionaryIndexLookup(IEnumerable<TKey> keys, IEqualityComparer<TKey> comparer)
{
var lookup = new Dictionary<TKey, int>(comparer);
foreach (var key in keys)
{
lookup.Add(key, lookup.Count);
}
_keyToIndexLookup = lookup;
}
public IEnumerable<TKey> Keys => _keyToIndexLookup.Keys;
public int Count => _keyToIndexLookup.Count;
public bool TryGetIndexForKey(TKey key, out int value)
{
return _keyToIndexLookup.TryGetValue(key, out value);
}
public bool TryGetOrAddIndexForKey(TKey key, out int value)
{
if (TryGetIndexForKey(key, out value))
return true;
return false;
}
}
public class NonThreadSafeSharedKeyDictionaryIndexLookup<TKey> : ISharedKeyDictionaryIndexLookup<TKey>
{
private readonly ConcurrentDictionary<TKey, int> _keyToIndexLookup;
public NonThreadSafeSharedKeyDictionaryIndexLookup(IEqualityComparer<TKey> comparer)
{
_keyToIndexLookup = new ConcurrentDictionary<TKey, int>(comparer);
}
protected int AllocateIndexForKey(TKey key)
{
lock(_keyToIndexLookup) {
var index = _keyToIndexLookup.Count;
return _keyToIndexLookup.GetOrAdd(key, index);
}
}
public IEnumerable<TKey> Keys => _keyToIndexLookup.Keys;
public int Count => _keyToIndexLookup.Count;
public bool TryGetIndexForKey(TKey key, out int value)
{
return _keyToIndexLookup.TryGetValue(key, out value);
}
public bool TryGetOrAddIndexForKey(TKey key, out int value)
{
if (TryGetIndexForKey(key, out value))
return true;
value = AllocateIndexForKey(key);
return true;
}
}
public interface ISharedKeyDictionaryIndexLookup<TKey>
{
IEnumerable<TKey> Keys { get; }
int Count { get; }
bool TryGetIndexForKey(TKey key, out int value);
bool TryGetOrAddIndexForKey(TKey key, out int value);
}
class SharedKeyDictionaryEnumerator<TKey, TValue> : IEnumerator<KeyValuePair<TKey, TValue>> where TValue : class
{
private readonly SharedKeyDictionary<TKey, TValue> _sharedKeyDictionary;
private readonly IEnumerator<TKey> _keysEnumerator;
public SharedKeyDictionaryEnumerator(SharedKeyDictionary<TKey, TValue> sharedKeyDictionary)
{
_sharedKeyDictionary = sharedKeyDictionary;
_keysEnumerator = sharedKeyDictionary.Keys.GetEnumerator();
}
public void Dispose()
{
}
public bool MoveNext()
{
return _keysEnumerator.MoveNext();
}
public void Reset()
{
throw new NotImplementedException(); //From documentation https://msdn.microsoft.com/en-us/library/system.collections.ienumerator.reset(v=vs.110).aspx: The Reset method is provided for COM interoperability. It does not necessarily need to be implemented; instead, the implementer can simply throw a NotSupportedException.
}
public KeyValuePair<TKey, TValue> Current
{
get
{
var currentKey = _keysEnumerator.Current;
var currentValue = _sharedKeyDictionary[currentKey];
return new KeyValuePair<TKey, TValue>(currentKey, currentValue);
}
}
object IEnumerator.Current
{
get { return Current; }
}
}
}
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using NUnit.Framework;
namespace MemoryOptimisations.UnitTests
{
[TestFixture]
class SharedKeyDictionaryTests
{
private SharedKeyDictionary<string, object> _sharedKeyDictionaryA;
private SharedKeyDictionary<string, object> _sharedKeyDictionaryB;
private ReadOnlySharedKeyDictionaryIndexLookup<string> _indexLookupWithTwoInitialKeys;
private string _key1 = "Key1";
private string _key2 = "Key2";
private string _extraKey1 = "ExtraKey1";
[SetUp]
public void Setup()
{
_indexLookupWithTwoInitialKeys = new ReadOnlySharedKeyDictionaryIndexLookup<string>(new []{ _key1, _key2 }, StringComparer.OrdinalIgnoreCase);
_sharedKeyDictionaryA = new SharedKeyDictionary<string, object>(_indexLookupWithTwoInitialKeys);
_sharedKeyDictionaryB = new SharedKeyDictionary<string, object>(_indexLookupWithTwoInitialKeys);
}
[Test]
public void When_adding_item_then_can_retrieve()
{
var object1 = 222;
_sharedKeyDictionaryA[_key1] = object1;
Assert.AreEqual(object1, _sharedKeyDictionaryA[_key1]);
}
[Test]
public void Adding_new_key_throws_exception()
{
var initialSize = _indexLookupWithTwoInitialKeys.Count;
Assert.Throws(typeof(SharedKeyNotDefinedException), () =>
{
_sharedKeyDictionaryA["bubbles"] = 696969;
});
Assert.AreEqual(initialSize, _indexLookupWithTwoInitialKeys.Count);
Assert.AreEqual(0, _sharedKeyDictionaryA.Count);
}
[Test]
public void When_getting_item_that_hasnt_been_explicitly_set_then_will_return_false()
{
object storedObject;
var result = _sharedKeyDictionaryA.TryGetValue(_key1, out storedObject);
Assert.IsFalse(result);
Assert.IsNull(storedObject);
}
[Test]
public void When_getting_item_by_key_that_hasnt_been_explicitly_set_then_will_throw_KeyNotFoundException()
{
Assert.Throws(typeof(KeyNotFoundException), () => { var blah = _sharedKeyDictionaryA["bubbles"]; });
}
[Test]
public void Contains_key_returns_true_only_if_a_key_is_present_and_a_value_set()
{
Assert.IsFalse(_sharedKeyDictionaryA.ContainsKey(_key1));
_sharedKeyDictionaryA[_key1] = 696969;
Assert.IsTrue(_sharedKeyDictionaryA.ContainsKey(_key1));
}
[Test]
public void Keys_only_returns_keys_with_values_set()
{
_sharedKeyDictionaryA[_key1] = 11111;
var keys = _sharedKeyDictionaryA.Keys;
CollectionAssert.Contains(keys, _key1);
CollectionAssert.DoesNotContain(keys, _key2);
}
[Test]
public void Values_only_returns_values_that_have_been_set()
{
int value = 11111;
_sharedKeyDictionaryA[_key1] = value;
var values = _sharedKeyDictionaryA.Values;
Assert.AreEqual(1, values.Count());
CollectionAssert.Contains(values, value);
}
[Test]
public void Count_only_returns_count_of_non_default_values()
{
Assert.AreEqual(0, _sharedKeyDictionaryA.Count);
_sharedKeyDictionaryA[_key1] = 1111;
Assert.AreEqual(1, _sharedKeyDictionaryA.Count);
}
[Test]
public void Enumerator_only_enumerates_over_values_that_have_been_explicitly_set()
{
_sharedKeyDictionaryA[_key1] = 1111;
foreach (var keyValuePair in _sharedKeyDictionaryA)
{
Assert.AreEqual(_key1, keyValuePair.Key);
}
}
[Test]
public void Remove_should_set_value_back_to_default_and_no_longer_be_visible()
{
_sharedKeyDictionaryA[_key1] = 1111;
Assert.AreEqual(1, _sharedKeyDictionaryA.Count);
_sharedKeyDictionaryA.Remove(_key1);
Assert.AreEqual(0, _sharedKeyDictionaryA.Count);
}
[Test]
public void Calling_remove_with_a_key_that_doesnt_exist_should_do_nothing()
{
var initialSize = _indexLookupWithTwoInitialKeys.Count;
Assert.DoesNotThrow(() => _sharedKeyDictionaryA.Remove("bubbles"));
Assert.AreEqual(initialSize, _indexLookupWithTwoInitialKeys.Count);
}
[Test]
public void Cannot_specify_null_as_a_default_value()
{
Assert.Throws(typeof(ArgumentNullException),() => new SharedKeyDictionary<string, object>(new ReadOnlySharedKeyDictionaryIndexLookup<string>(new string[] {}, StringComparer.Ordinal), null));
}
[Test]
public void If_value_type_is_interface_and_no_default_value_specified_then_throws_exception()
{
Assert.Throws(typeof(ArgumentException), () => new SharedKeyDictionary<string, ICollection>(new ReadOnlySharedKeyDictionaryIndexLookup<string>(new string[] {}, StringComparer.Ordinal)));
}
[Test]
public void Adding_new_keys_to_second_dictionary_is_not_supported()
{
Assert.Throws(typeof(SharedKeyNotDefinedException), () =>
{
_sharedKeyDictionaryB[_extraKey1] = 333;
});
Assert.AreEqual(2, _indexLookupWithTwoInitialKeys.Count);
Assert.AreEqual(0, _sharedKeyDictionaryB.Count);
Assert.Throws(typeof(KeyNotFoundException), () =>
{
var x = _sharedKeyDictionaryB[_extraKey1];
});
}
[Test]
public void Contains_key_returns_false_if_doesnt_exist()
{
Assert.IsFalse(_sharedKeyDictionaryA.ContainsKey(_extraKey1));
}
[Test]
public void Adding_and_removing_items()
{
_sharedKeyDictionaryA.AddIfNotDefined(_key1, "ABC");
_sharedKeyDictionaryA.AddIfNotDefined(_key1, "ABC");
Assert.AreEqual(1, _sharedKeyDictionaryA.Count);
_sharedKeyDictionaryA.Remove(_key1);
Assert.AreEqual(0, _sharedKeyDictionaryA.Count);
_sharedKeyDictionaryA.AddIfNotDefined(_key1, "ABC");
Assert.AreEqual(2, _indexLookupWithTwoInitialKeys.Count);
Assert.AreEqual(1, _sharedKeyDictionaryA.Count);
}
}
}
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using NUnit.Framework;
namespace MemoryOptimisations
{
[TestFixture]
class SharedKeyDictionaryWithMutableLookupTests
{
private SharedKeyDictionary<string, object> _sharedKeyDictionaryA;
private SharedKeyDictionary<string, object> _sharedKeyDictionaryB;
private NonThreadSafeSharedKeyDictionaryIndexLookup<string> _indexLookup;
private string _key1 = "Key1";
private string _key2 = "Key2";
private string _extraKey1 = "Key3";
private string _extraKey2 = "Key4";
private string _extraKey3 = "Key5";
[SetUp]
public void Setup()
{
_indexLookup = new NonThreadSafeSharedKeyDictionaryIndexLookup<string>(StringComparer.OrdinalIgnoreCase);
_sharedKeyDictionaryA = new SharedKeyDictionary<string, object>(_indexLookup);
_sharedKeyDictionaryB = new SharedKeyDictionary<string, object>(_indexLookup);
}
[Test]
public void When_adding_item_then_can_retrieve()
{
var object1 = 222;
_sharedKeyDictionaryA[_key1] = object1;
Assert.AreEqual(object1, _sharedKeyDictionaryA[_key1]);
}
[Test]
public void When_adding_new_key_then_shared_index_lookup_is_extended()
{
var initialSize = _indexLookup.Count;
_sharedKeyDictionaryA["bubbles"] = 696969;
Assert.AreEqual(initialSize + 1, _indexLookup.Count);
Assert.AreEqual(1, _sharedKeyDictionaryA.Count);
Assert.AreEqual(696969, _sharedKeyDictionaryA["bubbles"]);
}
[Test]
public void When_getting_item_that_hasnt_been_explicitly_set_then_will_return_false()
{
object storedObject;
var result = _sharedKeyDictionaryA.TryGetValue(_key1, out storedObject);
Assert.IsFalse(result);
Assert.IsNull(storedObject);
}
[Test]
public void When_getting_item_by_key_that_hasnt_been_explicitly_set_then_will_throw_KeyNotFoundException()
{
Assert.Throws(typeof(KeyNotFoundException), () => { var blah = _sharedKeyDictionaryA["bubbles"]; });
}
[Test]
public void Contains_key_returns_true_only_if_a_key_is_present_and_a_value_set()
{
Assert.IsFalse(_sharedKeyDictionaryA.ContainsKey(_key1));
_sharedKeyDictionaryA[_key1] = 696969;
Assert.IsTrue(_sharedKeyDictionaryA.ContainsKey(_key1));
}
[Test]
public void Keys_only_returns_keys_with_values_set()
{
_sharedKeyDictionaryA[_key1] = 11111;
var keys = _sharedKeyDictionaryA.Keys;
CollectionAssert.Contains(keys, _key1);
CollectionAssert.DoesNotContain(keys, _key2);
}
[Test]
public void Values_only_returns_values_that_have_been_set()
{
int value = 11111;
_sharedKeyDictionaryA[_key1] = value;
var values = _sharedKeyDictionaryA.Values;
Assert.AreEqual(1, values.Count());
CollectionAssert.Contains(values, value);
}
[Test]
public void Count_only_returns_count_of_non_default_values()
{
Assert.AreEqual(0, _sharedKeyDictionaryA.Count);
_sharedKeyDictionaryA[_key1] = 1111;
Assert.AreEqual(1, _sharedKeyDictionaryA.Count);
}
[Test]
public void Enumerator_only_enumerates_over_values_that_have_been_explicitly_set()
{
_sharedKeyDictionaryA[_key1] = 1111;
foreach (var keyValuePair in _sharedKeyDictionaryA)
{
Assert.AreEqual(_key1, keyValuePair.Key);
}
}
[Test]
public void Remove_should_set_value_back_to_default_and_no_longer_be_visible()
{
_sharedKeyDictionaryA[_key1] = 1111;
Assert.AreEqual(1, _sharedKeyDictionaryA.Count);
_sharedKeyDictionaryA.Remove(_key1);
Assert.AreEqual(0, _sharedKeyDictionaryA.Count);
}
[Test]
public void Calling_remove_with_a_key_that_doesnt_exist_should_do_nothing()
{
var initialSize = _indexLookup.Count;
Assert.DoesNotThrow(() => _sharedKeyDictionaryA.Remove("bubbles"));
Assert.AreEqual(initialSize, _indexLookup.Count);
}
[Test]
public void Cannot_specify_null_as_a_default_value()
{
Assert.Throws(typeof(ArgumentNullException),() => new SharedKeyDictionary<string, object>(new NonThreadSafeSharedKeyDictionaryIndexLookup<string>(StringComparer.Ordinal), null));
}
[Test]
public void If_value_type_is_interface_and_no_default_value_specified_then_throws_exception()
{
Assert.Throws(typeof(ArgumentException), () => new SharedKeyDictionary<string, ICollection>(new NonThreadSafeSharedKeyDictionaryIndexLookup<string>(StringComparer.Ordinal)));
}
[Test]
public void Adding_new_keys_to_second_dictionary_extends_shared_index_lookup()
{
_sharedKeyDictionaryA[_key1] = 333;
_sharedKeyDictionaryA[_key2] = 444;
_sharedKeyDictionaryB[_extraKey1] = 333;
_sharedKeyDictionaryB[_extraKey2] = 444;
Assert.AreEqual(4, _indexLookup.Count);
Assert.AreEqual(2, _sharedKeyDictionaryB.Count);
Assert.AreEqual(333, _sharedKeyDictionaryB[_extraKey1]);
Assert.AreEqual(444, _sharedKeyDictionaryB[_extraKey2]);
}
[Test]
public void Adding_new_keys_to_second_dictionary_does_not_affect_other_dictionary()
{
_sharedKeyDictionaryA[_key1] = "ABC";
_sharedKeyDictionaryB[_key2] = "XYZ";
_sharedKeyDictionaryB[_extraKey1] = "ABC2";
_sharedKeyDictionaryB[_extraKey2] = "XYZ2";
Assert.AreEqual(4, _indexLookup.Count);
Assert.AreEqual(3, _sharedKeyDictionaryB.Count);
Assert.AreEqual(1, _sharedKeyDictionaryA.Count);
}
[Test]
public void If_index_lookup_has_been_extended_then_cannot_access_those_new_values()
{
_sharedKeyDictionaryB[_extraKey1] = 2;
_sharedKeyDictionaryB[_extraKey2] = 3;
Assert.Throws(typeof(KeyNotFoundException), () => { var blah = _sharedKeyDictionaryA[_extraKey1]; });
Assert.IsFalse(_sharedKeyDictionaryA.TryGetValue(_extraKey1, out object storedObject));
}
[Test]
public void Contains_key_returns_false_if_added_to_index_after_creation()
{
_sharedKeyDictionaryB[_extraKey1] = 2;
_sharedKeyDictionaryB[_extraKey2] = 3;
Assert.IsFalse(_sharedKeyDictionaryA.ContainsKey(_extraKey1));
}
[Test]
public void Keys_doesnt_return_keys_added_to_index_after_creation()
{
_sharedKeyDictionaryB[_extraKey1] = 2;
_sharedKeyDictionaryB[_extraKey2] = 3;
var keys = _sharedKeyDictionaryA.Keys;
CollectionAssert.DoesNotContain(keys, _extraKey1);
}
[Test]
public void Count_doesnt_return_anything_from_indexes_added_after_creation()
{
_sharedKeyDictionaryB[_extraKey1] = 2;
_sharedKeyDictionaryB[_extraKey2] = 3;
Assert.AreEqual(0, _sharedKeyDictionaryA.Count);
}
[Test]
public void Calling_remove_with_a_key_that_is_added_to_index_after_creation_should_do_nothing()
{
_sharedKeyDictionaryB[_extraKey1] = 2;
_sharedKeyDictionaryB[_extraKey2] = 3;
Assert.DoesNotThrow(() => _sharedKeyDictionaryA.Remove(_extraKey1));
}
[Test]
public void Adding_items_out_of_order_so_we_increase_allocation_by_more_than_one_should_keep_accurate_count()
{
_sharedKeyDictionaryA[_key1] = "ABC";
_sharedKeyDictionaryB[_key2] = "XYZ";
_sharedKeyDictionaryB[_extraKey1] = "ABC2";
_sharedKeyDictionaryB[_extraKey2] = "XYZ2";
_sharedKeyDictionaryA[_extraKey3] = "XYZ2";
Assert.AreEqual(5, _indexLookup.Count);
Assert.AreEqual(2, _sharedKeyDictionaryA.Count);
Assert.AreEqual(3, _sharedKeyDictionaryB.Count);
}
[Test]
public void Adding_and_removing_items()
{
_sharedKeyDictionaryA.AddIfNotDefined(_key1, "ABC");
_sharedKeyDictionaryA.AddIfNotDefined(_key1, "ABC");
Assert.AreEqual(1, _sharedKeyDictionaryA.Count);
_sharedKeyDictionaryA.Remove(_key1);
Assert.AreEqual(0, _sharedKeyDictionaryA.Count);
_sharedKeyDictionaryA.AddIfNotDefined(_key1, "ABC");
Assert.AreEqual(1, _indexLookup.Count);
Assert.AreEqual(1, _sharedKeyDictionaryA.Count);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment