Skip to content

Instantly share code, notes, and snippets.

@ayende
Created December 1, 2013 17:53
Show Gist options
  • Save ayende/7738436 to your computer and use it in GitHub Desktop.
Save ayende/7738436 to your computer and use it in GitHub Desktop.
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)
}
};
}
}
}
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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment