We use dictionaries in various places in the existing code, where we map tags to objects that each contain that tag. This was never a problem before, as these dictionaries "only" managed several thousand objects. However, we are now at a point with the software where we are more likely to be dealing with tens to hundreds of thousands of objects. The use of the said tag as a key leads to the fact that we consume a lot of unnecessary memory, because these tags are stored twice and can reach lengths of more than 150 characters.
So the idea was obvious to replace the long tags with a hash that has a fixed size. For this we decided to use the FNV hash algorithm, which calculates an unsigned 64-bit integer from the string. To avoid having to make too many changes to the existing code, we enclosed the dictionary in an object that converts the passed string keys and works on an internal dictionary. This saves us masses of changes in the methods that use the previous implementation. You could call it a decorator in the broadest sense. The following is a brief outline of what we came up with.
[Serializable]
public class SimpleTestObject {
public string Tag { get; set; }
public SimpleTestObject(string tag) {
this.Tag = tag;
}
}
[Serializable]
public class FnvDictionary<T> : IDictionary<string, T> where T : SimpleTestObject {
private ConcurrentDictionary<UInt64, T> _InternalDictionary = new ConcurrentDictionary<UInt64, T>();
public T this[string key] {
get {
return this._InternalDictionary[this.CalculateHash(key)];
}
set {
if (key != value.Tag)
throw new ArgumentException();
_InternalDictionary[this.CalculateHash(key)] = value;
}
}
public ICollection<string> Keys {
get { return this._InternalDictionary.Values.Select(item => item.Tag).ToList(); }
}
public ICollection<T> Values {
get { return this._InternalDictionary.Values; }
}
public int Count {
get { return this._InternalDictionary.Count; }
}
public bool IsReadOnly {
get { return false; }
}
public void Add(string key, T value) {
this._InternalDictionary[this.CalculateHash(key)] = value;
}
public void Add(KeyValuePair<string, T> item) {
this.Add(item.Key, item.Value);
}
public void Clear() {
this._InternalDictionary.Clear();
}
public bool Contains(KeyValuePair<string, T> item) {
if (item.Key != item.Value.Tag)
throw new ArgumentException();
return this.ContainsKey(item.Value.Tag);
}
public bool ContainsKey(string key) {
return this._InternalDictionary.ContainsKey(CalculateHash(key));
}
public void CopyTo(KeyValuePair<string, T>[] array, int arrayIndex) {
KeyValuePair<string, T>[] source = this._InternalDictionary
.Select(data => new KeyValuePair<string, T>(data.Value.Tag, data.Value))
.ToArray();
Array.Copy(source, 0, array, arrayIndex, source.Length);
}
public IEnumerator<KeyValuePair<string, T>> GetEnumerator() {
return new FnvDictionaryEnumerator<T>(this._InternalDictionary);
}
public bool Remove(string key) {
return this._InternalDictionary.TryRemove(this.CalculateHash(key), out _);
}
public bool Remove(KeyValuePair<string, T> item) {
return this.Remove(item.Value.Tag);
}
public bool TryGetValue(string key, out T value) {
return this._InternalDictionary.TryGetValue(this.CalculateHash(key), out value);
}
private UInt64 CalculateHash(string input) {
const UInt64 MAGIC_PRIME = 1099511628211;
UInt64 hash = 14695981039346656037;
for (int i = 0; i < input.Length; i++)
hash = (hash ^ (byte)input[i]) * MAGIC_PRIME;
return hash;
}
IEnumerator IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
}
public class FnvDictionaryEnumerator<T> : IEnumerator<KeyValuePair<string, T>> where T : SimpleTestObject {
private ConcurrentDictionary<UInt64, T> _InternalDictionary;
private readonly int _KeysCount;
private int _KeyPos;
public FnvDictionaryEnumerator(ConcurrentDictionary<UInt64, T> data) {
_InternalDictionary = data;
_KeysCount = data.Keys.Count;
_KeyPos = -1;
}
public KeyValuePair<string, T> Current {
get {
T currentItem = _InternalDictionary.ElementAt(_KeyPos).Value;
return new KeyValuePair<string, T>(currentItem.Tag, currentItem);
}
}
object System.Collections.IEnumerator.Current => this.Current;
public bool MoveNext() => ++_KeyPos < _KeysCount;
public void Reset() => _KeyPos = -1;
public void Dispose() {
_InternalDictionary = null;
}
}
Now to the problem: The object described above was examined by us with a small test program and compared directly with the ConcurrentDictionary used so far. For this we have built a small function that outputs the size of the respective dictionaries:
public static long GetObjectSize(object source) {
BinaryFormatter formatter = new BinaryFormatter();
using (MemoryStream stream = new MemoryStream()) {
formatter.Serialize(stream, source);
return stream.Length;
}
}
After we had created 250000 data sets on a test basis and packed them into the dictionaries, we were disillusioned. Although our own creation works exclusively with hashes that are each 8 bytes long, the memory consumption is higher than in the ConcurrentDictionary.
const string TAG_BASE = "XXXXX|XXXXXX|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|XXXXXXXXXXX-";
const int TEST_OBJECTS_COUNT = 250000;
SimpleTestObject[] testObjects = new SimpleTestObject[TEST_OBJECTS_COUNT];
for (int index = 0; index < testObjects.Length; index++)
testObjects[index] = new SimpleTestObject($"{TAG_BASE}{index}");
ConcurrentDictionary<string, SimpleTestObject> concurrentDict = new ConcurrentDictionary<string, SimpleTestObject>();
foreach (SimpleTestObject testObject in testObjects)
concurrentDict[testObject.Tag] = testObject;
Console.WriteLine("Size of the ConcurrentDictionary = {0} bytes.", GetObjectSize(concurrentDict));
FnvDictionary<SimpleTestObject> customDict = new FnvDictionary<SimpleTestObject>();
foreach (SimpleTestObject testObject in testObjects)
customDict.Add(testObject.Tag, testObject);
Console.WriteLine("Size of the FnvDictionary = {0} bytes.", GetObjectSize(customDict));
// Output:
// Size of the ConcurrentDictionary = 36140494 bytes.
// Size of the custom dictionary = 36890908 bytes.
The question that now arises is how it can be that a dictionary that supposedly holds less data can have a larger memory consumption. The assumption is obvious that the ConcurrentDictionary also works only on the basis of hashes, but this is contradicted by the fact that the collection of keys can be retrieved continuously. Is there a design problem in the test scenario described above or even in the GetObjectSize function? And more important: How can the memory consumption of the dictionary be reduced as much as possible?