Skip to content

Instantly share code, notes, and snippets.

@StephenCleary

StephenCleary/LinkedDic.cs

Forked from ayende/LinkedDic.cs
Last active December 31, 2015 04:09
Show Gist options
  • Save StephenCleary/7932242 to your computer and use it in GitHub Desktop.
Save StephenCleary/7932242 to your computer and use it in GitHub Desktop.
Download ZIP
Added tests with Builder, SortedImmutableDictionary, and LinkedDictionaryUnoptimized.
Raw
LinkedDic.cs
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace Voron.Util
{
public class LinkedDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>, IReadOnlyDictionary<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)
}
};
}
public bool ContainsKey(TKey key)
{
throw new System.NotImplementedException();
}
public IEnumerable<TKey> Keys
{
get { throw new System.NotImplementedException(); }
}
public IEnumerable<TValue> Values
{
get { throw new System.NotImplementedException(); }
}
public TValue this[TKey key]
{
get { throw new System.NotImplementedException(); }
}
public int Count
{
get { throw new System.NotImplementedException(); }
}
}
}
Raw
LinkedDicUnoptimized.cs
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace Voron.Util
{
public class LinkedDictionaryUnoptimized<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>, IReadOnlyDictionary<TKey, TValue>
where TValue : class, new()
{
private const int DepthLimit = 1;
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 LinkedDictionaryUnoptimized()
{
}
public static readonly LinkedDictionaryUnoptimized<TKey, TValue> Empty = new LinkedDictionaryUnoptimized<TKey, TValue>();
public static LinkedDictionaryUnoptimized<TKey, TValue> From(Dictionary<TKey, TValue> inner)
{
return new LinkedDictionaryUnoptimized<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 LinkedDictionaryUnoptimized<TKey, TValue> NewNode(Node header)
{
header.Prev = _header;
if (_header == null)
{
header.Depth = 1;
}
else
{
header.Depth = _header.Depth + 1;
}
if (header.Depth > DepthLimit)
{
return MergeItems(header);
}
return new LinkedDictionaryUnoptimized<TKey, TValue>
{
_comparer = _comparer,
_header = header
};
}
private LinkedDictionaryUnoptimized<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 LinkedDictionaryUnoptimized<TKey, TValue>
{
_comparer = _comparer,
_header = new Node
{
Dictionary = dic,
Depth = 1,
}
};
}
public LinkedDictionaryUnoptimized<TKey, TValue> SetItems(Dictionary<TKey, TValue> items)
{
return NewNode(new Node { Dictionary = items });
}
public LinkedDictionaryUnoptimized<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 LinkedDictionaryUnoptimized<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 LinkedDictionaryUnoptimized<TKey, TValue> WithComparers(IEqualityComparer<TKey> equalityComparer)
{
return new LinkedDictionaryUnoptimized<TKey, TValue>
{
_comparer = equalityComparer,
_header = _header
};
}
public LinkedDictionaryUnoptimized<TKey, TValue> Remove(TKey key)
{
return new LinkedDictionaryUnoptimized<TKey, TValue>
{
_comparer = _comparer,
_header = new Node
{
Prev = _header,
Value = new KeyValuePair<TKey, TValue>(key, _deleteMarker)
}
};
}
public bool ContainsKey(TKey key)
{
throw new System.NotImplementedException();
}
public IEnumerable<TKey> Keys
{
get { throw new System.NotImplementedException(); }
}
public IEnumerable<TValue> Values
{
get { throw new System.NotImplementedException(); }
}
public TValue this[TKey key]
{
get { throw new System.NotImplementedException(); }
}
public int Count
{
get { throw new System.NotImplementedException(); }
}
}
}
Raw
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
{
private const int AddIterations = 50 * 100;
private const int ReadIterations = 50 * 100;
static void Main()
{
//warmup
ReadItems(SafeDicAdd(10), "warmup", 10);
ReadItems(LinkedDicAdd(10), "warmup", 10);
ReadItems(LinkedDicUnoptimizedAdd(10), "warmup", 10);
ReadItems(ImmutableDictionaryAdd(10), "warmup", 10);
ReadItems(ImmutableDictionaryBuilderAdd(10), "warmup", 10);
ReadItems(ImmutableSortedDictionaryBuilderAdd(10), "warmup", 10);
Console.WriteLine("Warmup complete.");
// actual test
var sd = SafeDicAdd(AddIterations); // 2.77
var ld = LinkedDicAdd(AddIterations); // 1.85
var ldu = LinkedDicUnoptimizedAdd(AddIterations); // 5.14
var id = ImmutableDictionaryAdd(AddIterations); // 11.0
var idb = ImmutableDictionaryBuilderAdd(AddIterations); // 10.6
var isdb = ImmutableSortedDictionaryBuilderAdd(AddIterations); // 3.87
ReadItems(sd, "safe dictionary", ReadIterations); // 0.096
ReadItems(ld, "linked dictionary", ReadIterations); // 0.16
ReadItems(ldu, "linked dictionary unoptimized", ReadIterations); // 0.11
ReadItems(id, "immutable dictionary", ReadIterations); // 0.81
ReadItems(idb, "immutable dictionary builder", ReadIterations); // 0.80
ReadItems(isdb, "immutable sorted dictionary builder", ReadIterations); // 0.63
Console.ReadKey();
}
private static void ReadItems(IReadOnlyDictionary<long, object> ld, string name, int iterations)
{
var sp = Stopwatch.StartNew();
for (int j = 0; j != 1000; ++j)
{
for (int i = 0; i < iterations; i++)
{
object value;
ld.TryGetValue(i, out value);
}
}
Console.WriteLine(sp.Elapsed + " Reading values " + name);
}
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 LinkedDictionaryUnoptimized<long, object> LinkedDicUnoptimizedAdd(int iterations)
{
var dic = LinkedDictionaryUnoptimized<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 unoptimized");
return dic;
}
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;
}
private static ImmutableDictionary<long, object> ImmutableDictionaryBuilderAdd(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 mutableDic = dic.ToBuilder();
foreach (var item in Enumerable.Range(rnd.Next(0, i), Math.Max(i * 2, 16)))
{
mutableDic[item] = null;
}
dic = mutableDic.ToImmutable();
}
Console.WriteLine(sp.Elapsed + " Adding items, immutable dictionary builder");
return dic;
}
private static ImmutableSortedDictionary<long, object> ImmutableSortedDictionaryBuilderAdd(int iterations)
{
var dic = ImmutableSortedDictionary<long, object>.Empty;
var sp = Stopwatch.StartNew();
var rnd = new Random(32);
for (int i = 0; i < iterations; i++)
{
var mutableDic = dic.ToBuilder();
foreach (var item in Enumerable.Range(rnd.Next(0, i), Math.Max(i * 2, 16)))
{
mutableDic[item] = null;
}
dic = mutableDic.ToImmutable();
}
Console.WriteLine(sp.Elapsed + " Adding items, immutable sorted dictionary builder");
return dic;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment