LinkedDic.cs

using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace Voron.Util
{
	public class LinkedDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
		where TValue : class, new()
	{
		private readonly TValue _deleteMarker = new TValue();

		private class Node
		{
			public Dictionary<TKey, TValue> Dictionary;
			public KeyValuePair<TKey, TValue>? Value;
			public Node Prev;
			public int Depth;
		}

		private IEqualityComparer<TKey> _comparer = EqualityComparer<TKey>.Default;

		private Node _header;

		private LinkedDictionary()
		{

		}

		public static readonly LinkedDictionary<TKey, TValue> Empty = new LinkedDictionary<TKey, TValue>();

		public static LinkedDictionary<TKey, TValue> From(Dictionary<TKey, TValue> inner)
		{
			return new LinkedDictionary<TKey, TValue>
			{
				_header = new Node
				{
					Dictionary = inner,
					Prev = null,
					Depth = 1,
				}
			};
		}

		public bool TryGetValue(TKey key, out TValue value)
		{
			var current = _header;
			while (current != null)
			{
				if (current.Value != null)
				{
					var kvp = current.Value.Value;
					if (_comparer.Equals(kvp.Key, key))
					{
						if (kvp.Value == _deleteMarker)
						{
							value = null;
							return false;
						}
						value = kvp.Value;
						return true;
					}
				}
				else
				{
					if (current.Dictionary.TryGetValue(key, out value))
					{
						if (value == _deleteMarker)
						{
							value = null;
							return false;
						}
						return true;
					}

				}
				current = current.Prev;
			}
			value = null;
			return false;
		}

		private LinkedDictionary<TKey, TValue> NewNode(Node header)
		{
			header.Prev = _header;
			if (_header == null)
			{
				header.Depth = 1;
			}
			else
			{
				header.Depth = _header.Depth + 1;
			}
			if (header.Depth > 32)
			{
				return MergeItems(header);
			}
			return new LinkedDictionary<TKey, TValue>
			{
				_comparer = _comparer,
				_header = header
			};
		}

		private LinkedDictionary<TKey, TValue> MergeItems(Node header)
		{
			// too deep, let us merge it all and generate a single dictionary;
			var dic = new Dictionary<TKey, TValue>(_comparer);
			var existing = new HashSet<TKey>(_comparer);
			var current = header;
			while (current != null)
			{
				if (current.Value != null)
				{
					var kvp = current.Value.Value;
					if (existing.Add(kvp.Key) && kvp.Value != _deleteMarker)
					{
						dic.Add(kvp.Key, kvp.Value);
					}
				}
				else
				{
					foreach (var kvp in current.Dictionary)
					{
						if (existing.Add(kvp.Key) && kvp.Value != _deleteMarker)
						{
							dic.Add(kvp.Key, kvp.Value);
						}
					}
				}

				current = current.Prev;
			}
			return new LinkedDictionary<TKey, TValue>
			{
				_comparer = _comparer,
				_header = new Node
				{
					Dictionary = dic,
					Depth = 1,
				}
			};
		}

		public LinkedDictionary<TKey, TValue> SetItems(Dictionary<TKey, TValue> items)
		{
			return NewNode(new Node { Dictionary = items });
		}

		public LinkedDictionary<TKey, TValue> Add(TKey key, TValue value)
		{
			return NewNode(new Node
			{
				Value = new KeyValuePair<TKey, TValue>(key, value),
			});
		}

		public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
		{
			var current = _header;
			var existing = new HashSet<TKey>(_comparer);
			while (current != null)
			{
				if (current.Value != null)
				{
					var kvp = current.Value.Value;
					if (existing.Add(kvp.Key) && kvp.Value != _deleteMarker)
					{
						yield return kvp;
					}
				}
				else
				{
					foreach (var kvp in current.Dictionary)
					{
						if (existing.Add(kvp.Key) && kvp.Value != _deleteMarker)
						{
							yield return kvp;
						}
					}
				}

				current = current.Prev;
			}
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}

		public LinkedDictionary<TKey, TValue> RemoveRange(IEnumerable<TKey> range)
		{
			var items = new Dictionary<TKey, TValue>();
			foreach (var key in range)
			{
				items[key] = _deleteMarker;
			}
			return NewNode(new Node
			{
				Dictionary = items
			});
		}

		public bool IsEmpty
		{
			get
			{
				var current = _header;
				while (current != null)
				{
					if (current.Value == null)
					{
						if (current.Dictionary.Values.Any(x => x != _deleteMarker))
							return false;
					}
					else if (current.Value.Value.Value != _deleteMarker)
					{
						return false;
					}
					current = current.Prev;
				}
				return true;
			}
		}

		public LinkedDictionary<TKey, TValue> WithComparers(IEqualityComparer<TKey> equalityComparer)
		{
			return new LinkedDictionary<TKey, TValue>
			{
				_comparer = equalityComparer,
				_header = _header
			};
		}

		public LinkedDictionary<TKey, TValue> Remove(TKey key)
		{
			return new LinkedDictionary<TKey, TValue>
			{
				_comparer = _comparer,
				_header = new Node
				{
					Prev = _header,
					Value = new KeyValuePair<TKey, TValue>(key, _deleteMarker)
				}
			};
		}
	}
}

program.cs

using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Linq;
using System.Text;
using Voron.Util;

namespace ConsoleApplication8
{
	class Program
	{

		static void Main()
		{
			//warmup
			MutableDicAdd(10);
			LinkedDicAdd(10);
			ImmutableDictionaryAdd(10);
			SafeDicAdd(10);

			// actual test
			//var d = MutableDicAdd(50 * 100);
			//var sd = SafeDicAdd(50 * 1000);
			var ld = LinkedDicAdd(50 * 1000);
			//var id = ImmutableDictionaryAdd(50 * 100);

			//ReadItemsMutable(d, 10 * 1000);
			ReadItemsLinked(ld, 10 * 1000);
			//ReadItemsImmutable(id, 10 * 1000);
		}

		private static void ReadItemsMutable(Dictionary<long, object> ld, int iterations)
		{
			var sp = Stopwatch.StartNew();

			for (int i = 0; i < iterations; i++)
			{
				object value;
				ld.TryGetValue(i, out value);
			}

			Console.WriteLine(sp.Elapsed + " Reading values mutable dictionary");
		}

		private static void ReadItemsLinked(LinkedDictionary<long, object> ld, int iterations)
		{
			var sp = Stopwatch.StartNew();

			for (int i = 0; i < iterations; i++)
			{
				object value;
				ld.TryGetValue(i, out value);
			}

			Console.WriteLine(sp.Elapsed + " Reading values linked dictionary");
		}

		private static void ReadItemsImmutable(ImmutableDictionary<long, object> ld, int iterations)
		{
			var sp = Stopwatch.StartNew();

			for (int i = 0; i < iterations; i++)
			{
				object value;
				ld.TryGetValue(i, out value);
			}

			Console.WriteLine(sp.Elapsed + " Reading values immutable dictionary");
		}

		private static LinkedDictionary<long, object> LinkedDicAdd(int iterations)
		{
			var dic = LinkedDictionary<long, object>.Empty;

			var sp = Stopwatch.StartNew();
			var rnd = new Random(32);
			for (int i = 0; i < iterations; i++)
			{
				var tmp = new Dictionary<long, object>();
				foreach (var item in Enumerable.Range(rnd.Next(0, i), Math.Max(i * 2, 16)))
				{
					tmp[item] = null;
				}

				dic = dic.SetItems(tmp);
			}

			Console.WriteLine(sp.Elapsed + " Adding items, linked dictionary");

			return dic;
		}

		private static Dictionary<long, object> MutableDicAdd(int iterations)
		{
			var tmp = new Dictionary<long, object>();

			var sp = Stopwatch.StartNew();
			var rnd = new Random(32);
			for (int i = 0; i < iterations; i++)
			{
				foreach (var item in Enumerable.Range(rnd.Next(0, i), Math.Max(i * 2, 16)))
				{
					tmp[item] = null;
				}

			}

			Console.WriteLine(sp.Elapsed + " Adding items, mutable dictionary");

			return tmp;
		}

		private static Dictionary<long, object> SafeDicAdd(int iterations)
		{
			var dic = new Dictionary<long, object>();

			var sp = Stopwatch.StartNew();
			var rnd = new Random(32);
			for (int i = 0; i < iterations; i++)
			{
				var tmp = new Dictionary<long, object>();
				foreach (var item in Enumerable.Range(rnd.Next(0, i), Math.Max(i * 2, 16)))
				{
					tmp[item] = null;
				}
				dic = new Dictionary<long, object>(dic);
				foreach (var o in tmp)
				{
					dic[o.Key] = o.Value;
				}
			}

			Console.WriteLine(sp.Elapsed + " Adding items, safe dictionary");

			return dic;
		}


		private static ImmutableDictionary<long, object> ImmutableDictionaryAdd(int iterations)
		{
			var dic = ImmutableDictionary<long, object>.Empty;

			var sp = Stopwatch.StartNew();

			var rnd = new Random(32);
			for (int i = 0; i < iterations; i++)
			{
				var tmp = new Dictionary<long, object>();
				foreach (var item in Enumerable.Range(rnd.Next(0, i), Math.Max(i * 2, 16)))
				{
					tmp[item] = null;
				}

				dic = dic.SetItems(tmp);
			}

			Console.WriteLine(sp.Elapsed + " Adding items, immutable dictionary");

			return dic;
		}
	}
}