不可变词典与词典Vs C5对F# - 表现
sra*_*raj 13 .net performance f# dictionary immutability
我们的应用程序使用了大量字典,这些字典具有不经常更改的多级查找.我们正在研究转换使用字典进行大量查找的一些关键代码,以使用替代结构 - 更快的查找,点亮内存/ gc.这让我们比较了各种可用的词典/库 -
Dictionary(System.Collections.Generics.Dictionary-SCGD) ,ImmutableDictionary,.C5.HashDictionaryFSharpMap
运行包含各种项目的以下程序 - 100,1000,10000,100000 - 表示词典在大多数范围内仍然是赢家.第一行表示集合中的项目.MS/Ticks将随机执行x查找所花费的时间(代码如下).
项目 - 100
SCGD - 0 MS - 50 Ticks
C5 - 1 MS - 1767 Ticks
Imm - 4 MS - 5951 Ticks
FS - 0 MS - 240 Ticks
项目 - 1000
SCGD - 0 MS - 230 Ticks
C5 - 0 MS - 496 Ticks
Imm - 0 MS - 1046 Ticks
FS - 1 MS - 1870 Ticks
项目 - 10000
SCGD - 3 MS - 4722 Ticks
C5 - 4 MS - 6370 Ticks
Imm - 9 MS - 13119 Ticks
FS - 15 MS - 22050 Ticks
项目 - 100000
SCGD - 62 MS - 89276 Ticks
C5 - 72 MS - 103658 Ticks
Imm - 172 MS - 246247 Ticks
FS - 249 MS - 356176 Ticks
这是否意味着,我们已经使用最快且不必改变？我曾假设不可变结构应位于表格的顶部,但事实并非如此.我们做错了比较还是我错过了什么？坚持这个问题,但觉得,问题更好.任何链接或注释或任何引用光线的参考都会很棒.
完整的测试代码 -
namespace CollectionsTest
{
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Runtime;
using Microsoft.FSharp.Collections;
/// <summary>
///
/// </summary>
class Program
{
static Program()
{
ProfileOptimization.SetProfileRoot(@".\Jit");
ProfileOptimization.StartProfile("Startup.Profile");
}
/// <summary>
/// Mains the specified args.
/// </summary>
/// <param name="args">The args.</param>
static void Main(string[] args)
{
// INIT TEST DATA ------------------------------------------------------------------------------------------------
foreach (int MAXITEMS in new int[] { 100, 1000, 10000, 100000 })
{
Console.WriteLine("\n# - {0}", MAXITEMS);
List<string> accessIndex = new List<string>(MAXITEMS);
List<KeyValuePair<string, object>> listofkvps = new List<KeyValuePair<string, object>>();
List<Tuple<string, object>> listoftuples = new List<Tuple<string, object>>();
for (int i = 0; i < MAXITEMS; i++)
{
listoftuples.Add(new Tuple<string, object>(i.ToString(), i));
listofkvps.Add(new KeyValuePair<string, object>(i.ToString(), i));
accessIndex.Add(i.ToString());
}
// Randomize for lookups
Random r = new Random(Environment.TickCount);
List<string> randomIndexesList = new List<string>(MAXITEMS);
while (accessIndex.Count > 0)
{
int index = r.Next(accessIndex.Count);
string value = accessIndex[index];
accessIndex.RemoveAt(index);
randomIndexesList.Add(value);
}
// Convert to array for best perf
string[] randomIndexes = randomIndexesList.ToArray();
// LOAD ------------------------------------------------------------------------------------------------
// IMMU
ImmutableDictionary<string, object> idictionary = ImmutableDictionary.Create<string, object>(listofkvps);
//Console.WriteLine(idictionary.Count);
// SCGD
Dictionary<string, object> dictionary = new Dictionary<string, object>();
for (int i = 0; i < MAXITEMS; i++)
{
dictionary.Add(i.ToString(), i);
}
//Console.WriteLine(dictionary.Count);
// C5
C5.HashDictionary<string, object> c5dictionary = new C5.HashDictionary<string, object>();
for (int i = 0; i < MAXITEMS; i++)
{
c5dictionary.Add(i.ToString(), i);
}
//Console.WriteLine(c5dictionary.Count);
// how to change to readonly?
// F#
FSharpMap<string, object> fdictionary = new FSharpMap<string, object>(listoftuples);
//Console.WriteLine(fdictionary.Count);
// TEST ------------------------------------------------------------------------------------------------
Stopwatch sw = Stopwatch.StartNew();
for (int index = 0, indexMax = randomIndexes.Length; index < indexMax; index++)
{
string i = randomIndexes[index];
object value;
dictionary.TryGetValue(i, out value);
}
sw.Stop();
Console.WriteLine("SCGD - {0,10} MS - {1,10} Ticks", sw.ElapsedMilliseconds, sw.ElapsedTicks);
Stopwatch c5sw = Stopwatch.StartNew();
for (int index = 0, indexMax = randomIndexes.Length; index < indexMax; index++)
{
string key = randomIndexes[index];
object value;
c5dictionary.Find(ref key, out value);
}
c5sw.Stop();
Console.WriteLine("C5 - {0,10} MS - {1,10} Ticks", c5sw.ElapsedMilliseconds, c5sw.ElapsedTicks);
Stopwatch isw = Stopwatch.StartNew();
for (int index = 0, indexMax = randomIndexes.Length; index < indexMax; index++)
{
string i = randomIndexes[index];
object value;
idictionary.TryGetValue(i, out value);
}
isw.Stop();
Console.WriteLine("Imm - {0,10} MS - {1,10} Ticks", isw.ElapsedMilliseconds, isw.ElapsedTicks);
Stopwatch fsw = Stopwatch.StartNew();
for (int index = 0, indexMax = randomIndexes.Length; index < indexMax; index++)
{
string i = randomIndexes[index];
fdictionary.TryFind(i);
}
fsw.Stop();
Console.WriteLine("FS - {0,10} MS - {1,10} Ticks", fsw.ElapsedMilliseconds, fsw.ElapsedTicks);
}
}
}
}
Jul*_*anR 10
标准词典已经很好地优化了.当你进行查找时它真正做的就是计算提供的密钥的哈希值(其速度取决于密钥的类型及其实现方式GetHashCode),对哈希值进行模运算以找到正确的桶然后它迭代桶的内容,直到它找到正确的值(其速度取决于GetHashCode函数的质量,因此如果桶很平衡并且不包含太多项,并且Equals方法的速度为类型).
总而言之,它对查找没有那么多,所以我认为你不会找到一个明显更快的通用数据结构.但是,根据您计划使用词典的方式,您可以构建更专业的解决方案.例如,我需要一个非常快速的查找,其中键是一个类型.dictionary[typeof(T)]我没有使用字典和做,而是像这样制作了一个泛型类:
class ValueStore<T>
{
public static T Value;
}
所以我可以做ValueStore<T>.Value几乎零查询开销.
你是否可以做类似的事情(以及它是否值得)真的取决于你的用例; 结构将容纳多少项,读取和写入的频率,是否需要线程安全,写入速度有多重要等等.例如,如果写入速度完全没有关系,但是如果需要线程安全性,您需要进行写时复制,其中数据结构永远不会被写入而是被复制,从而确保线程安全和无锁(因此:快速)读取,代价是写入速度.专门研究可以对写入结构进行重新排序以优化它,因此散列桶不包含多于N个项目.
PS:如果你真的非常渴望速度但无法构建更专业的数据结构,那么你可能从复制Dictionary<TKey,TValue>和删除各种健全性检查(空检查等)和虚拟/接口方法调用中获得小额收益.但是,如果有的话,我怀疑这会给你带来超过20%的收益.
- @sraj - 如果您需要线程安全并且只有很少的写入和很少的键，我肯定会考虑写时复制而不是锁。基本上，无论何时修改字典，都不要将其添加到原始字典中，而是创建一个副本并将其添加到副本中，然后以原子方式交换副本和原始字典。示例：http://stackoverflow.com/questions/10675400/threadsafe-collection-without-lock (2认同)
你不可变词典允许更快查找的假设是错误的,因为几乎所有不可变集合避免在"修改"上复制整个结构的方式是将数据存储在树中,只复制"修改"中的一些节点,共享所有其他节点.
我知道你对读取性能(冻结字典)很感兴趣,但是不可变集合的树特征在写入性能中表现得与记录的相似:
Items Dict Conc Immu
===========================
100 1.90 1.00 361.81
1000 1.07 1.00 4.33
10000 1.24 1.00 1.74
100000 1.00 1.33 2.71
---------------------------
100 1.06 1.00 2.56
1000 1.03 1.00 4.34
10000 1.00 1.06 3.54
100000 1.00 1.17 2.76
---------------------------
100 1.06 1.00 2.50
1000 1.66 1.00 4.16
10000 1.00 1.02 3.67
100000 1.00 1.26 3.13
顺便说一下,如果按原样运行示例代码,至少不可变字典的值在正常(运行时间较长)的应用程序中将非常不典型,因为由于某种原因,不可变字典显然需要时间来预热.性能差异巨大.只需看看前3次运行的输出:
???????????????????????????????????????????????????????????????????????
Mutable (amortized) Mutable (worst) Immutable
???????????????????????????????????????????????????????????????????????
Stack.Push O(1) O(n) O(1)
Queue.Enqueue O(1) O(n) O(1)
List.Add O(1) O(n) O(log n)
HashSet.Add O(1) O(n) O(log n)
SortedSet.Add O(log n) O(n) O(log n)
Dictionary.Add O(1) O(n) O(log n)
SortedDictionary.Add O(log n) O(n log n) O(log n)
???????????????????????????????????????????????????????????????????????
FWIW,我比较了单线程读取性能的Dictionary<,>,ConcurrentDictionary<,>以及ImmutableDictionary<,>根据您的代码.
预热后30次运行的平均结果:
为了感受写入性能,我还运行了一个测试,为字典添加了50多个条目.再次,热身后30次运行的平均结果:
经过测试
- .net 4.5.1
- Microsoft Bcl Immutable 1.0.34.0
注意:应该注意的是,在许多现实生活中的多线程应用程序中,不可变字典的速度要快得多,并且/或者允许更高级别的并发性,否则将不得不诉诸缓慢或容易出错的技术,如防御性复制,锁定等等,以应对面对线程的可变性.如果您需要快照,例如乐观并发,MVCC,则尤其如此.
| 归档时间： |
|
| 查看次数： |
5805 次 |
| 最近记录： |