c# - ConcurrentDictionary:初始容量适当小

Question

我一直缺乏为 ConcurrentDictionary<TKey, TValue> 选择适当初始容量的指导。 .

我的一般用例是您确实想要执行以下操作但无法执行的情况:

public static class StaticCache<T>
{
    public static readonly Action CompiledExpression = ...;
}

这种基于泛型的方法避免了字典查找，但只有在我们始终在编译时知道所需类型的情况下才能使用。如果我们只有 Type在运行时已知，我们不能再使用这种方法。下一个竞争者是 ConcurrentDictionary<TKey, TValue> .

documentation状态:

The default capacity (DEFAULT_CAPACITY), which represents the initial number of buckets, is a trade-off between the size of a very small dictionary and the number of resizes when constructing a large dictionary. Also, the capacity should not be divisible by a small prime number. The default capacity is 31.

我预期的元素数量往往相对较少。有时小至 3 或 5，有时可能 15。因此:

• 应用程序生命周期内的插入次数将极少，保证[写入]并发级别为1，从而优化紧凑性和读取操作。
• 最好具有尽可能小的内存占用量，以优化缓存行为。

由于默认初始容量为 31，因此我们可以通过使用较小的初始容量来减少对缓存的影响(并增加字典保留在缓存中的可能性)。

这提出了以下问题:

1. 容量的实际含义是什么？

   • (A) 字典不需要增长来容纳这么多元素？
   • (B) A 的固定百分比，取决于字典的最大“完整性”，例如75%？
   • (C)​​ A 或 B 的近似值，具体取决于实际内容的哈希码如何分配它们？

2. 什么构成“小素数”，什么不构成“小素数”？显然，31 没有。 11 吗？ 17 吗？ 23岁吗？

3. 如果我们碰巧想要一个接近小质数的容量，我们可以选择什么容量？我们是简单地选择最接近的非素数，还是素数的容量更好，我们真的应该选择更大的素数吗？

Answer 1

在 reference source对于 ConcurrentDictionary<TKey, TValue>你可以看到:

Node[] buckets = new Node[capacity];

所以，容量就是哈希表的有效大小。不考虑“完整性”。这个数字唯一的预处理是:

if (capacity < concurrencyLevel)
{
    capacity = concurrencyLevel;
}

哪里concurrencyLevel是由您通过构造函数参数定义的，或者是定义为 PlatformHelper.ProcessorCount 的默认并发级别。 .

Dictionary<TKey,TValue> 中对容量的处理方式不同。这里它被初始化为

private void Initialize(int capacity) {
    int size = HashHelpers.GetPrime(capacity);
    buckets = new int[size];
    ...
}

和HashHelpers.GetPrime获取大于或等于指定容量的最小素数。素数高达 7199369取自预先计算的数组。较大的则以“困难的方式”计算。有趣的是，最小的素数是 3 .

不幸的是，HashHelpers是一个内部类。

如果我理解正确的话，这两种实现都会根据冲突数量而不是根据特定的填充因子(“填充度”)来调整哈希表的大小。

如果你愿意

• 优化速度:初始容量比预期最大字典大小大30%左右。这可以避免调整大小。
• 优化内存占用:采用比最小预期大小大 30% 左右的质数。
• 速度和内存占用之间的平衡:在上面的两者之间取一个数字。但无论如何，请先做好准备。