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，我们可以通过使用较小的初始容量来减少对缓存的影响（以及增加字典保留在缓存中的可能性）。

这引发了以下问题：

容量到底是什么意思？
- (A) 字典不需要增长来容纳这么多元素?
- (B) A 的固定百分比，取决于字典的最大值 "fullness"，例如75%？
- (C) A 或 B 的近似值，取决于实际内容的哈希码如何分布？
什么构成和不构成 "a small prime"？显然，31 没有。 11吗？ 17吗？ 23吗？
如果我们恰好想要一个接近小质数的容量，我们可以选择什么容量呢？我们是简单地选择最接近的非素数，还是素数对容量更好，我们真的应该选择更大的素数吗？

Answer 1

在 reference source for ConcurrentDictionary<TKey, TValue> 你可以看到：

Node[] buckets = new Node[capacity];

因此，容量是散列的有效大小table。不考虑 "fullness"。这个数字唯一的预处理是：

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 以内的素数取自预先计算的数组。较大的计算 "the hard way"。有趣的是，最小的素数是 3.

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

如果我理解正确，这两种实现都根据冲突次数而不是根据特定的填充因子 ("fullness") 调整散列 table 的大小。

如果你想

优化速度：取一个初始容量，它是一个比预期的最大字典大小大 30% 左右的素数。这样可以避免调整大小。
优化内存占用：取一个比最小值预期大小大 30% 的素数。
速度和内存占用之间的平衡：从上面的两者之间取一个数字。但无论如何，取一个素数。

ConcurrentDictionary：适当的小初始容量

ConcurrentDictionary: Proper small initial capacity

c#

primes

capacity

concurrentdictionary