how much faster is it than Dictionary and why

WITH .NET 8 release C# developers now have a new collection in their arsenal – FrozenDictionary. The peculiarity of this dictionary is that it is immutable, but at the same time provides faster reading compared to the usual Dictionary. It is not without reason that I have divided the results on the cover by type – those used in FrozenDictionary algorithms are highly dependent on the key type, dictionary size, or even, for example, the number of string keys of the same length. In this article, we will examine in detail how FrozenDictionary faster and why.

Dictionary, you come alone. We will come alone too.

Before you begin battle comparison with Dictionaryit is important to note that FrozenDictionary<TKey, TValue> – is an abstract class with many implementations. More precisely, there are 18 of them. Instead of explaining when which implementation is used, it is easier to show it on the diagram, so let's look at Figure 1.

There is no need to be afraid, the implementations can be divided into 5 groups according to the operating principle:

1. IN DefaultFrozenDictionary And ValueTypeDefaultComparerFrozenDictionary structure is used FrozenHashTable.

2. Int32FrozenDictionary also uses FrozenHashTable, but there is no hash code calculation, since the key value is the hash code.

3. LengthBucketsFrozenDictionary uses an algorithm similar to block sort.

4. Implementations OrdinalStringFrozenDictionary also use FrozenHashTable, but they have a special algorithm for calculating the hash code.

5. SmallValueTypeComparableFrozenDictionary, SmallValueTypeDefaultComparerFrozenDictionary And SmallFrozenDictionary use linear search, since the size of the dictionaries does not exceed 10 elements.

The choice of a suitable implementation depends on many parameters and occurs in the method CreateFromDictionary of static class FrozenDictionaryNow let's take a closer look at each group separately, study their algorithms and take measurements.

Disclaimer

The benchmark results in this article are very conditional and are only valid under certain conditions. I admit that the benchmark may show different results on another PC, with another CPU, with another compiler, or in another scenario of using the language functionality in question. Always check your code on your specific hardware and do not rely only on articles from the Internet.

The source code of the benchmarks and the raw results data can be found in in this repository.

Group 1. Default dictionaries

As has been said before, in DefaultFrozenDictionary And ValueTypeDefaultComparerFrozenDictionary structure is used FrozenHashTable. This structure, as you might guess from the name, is an implementation of a hash table. To better understand what the algorithm in FrozenHashTable differs from Dictionarylet's briefly recall how the search works DictionaryIf you remember this, you can skip the explanation.

Let's assume we have the following dictionary:

var dictionary = new Dictionary<Fruit, string>()
{
    [new("apple")] = "APPLE",
    [new("grape")] = "GRAPE",
    [new("lemon")] = "LEMON",
    [new("fig")] = "FIG",
    [new("lime")] = "LIME",
    [new("kiwi")] = "KIWI",
};

public record Fruit(string Value);

When, for example, we look up a value for a key Fruit("fig")V Dictionary the following happens (Figure 2):

1. The hash code of the key is calculated hashCode.

2. Bucket index is calculated bucketIndex.

3. If the key in the bucket is equal to the one we are looking for, then the value is returned. Otherwise, we move on to the next key with the same hash code and repeat step 3.

Search algorithm

Immutability FrozenDictionary allows you to implement work with buckets in a different way FrozenHashTableSince the number of key-value pairs does not change, we can:

1. Pick up the number of buckets so that the number of collisions will be no more than 5% from the number of unique hashes.

2. Place keys and values ​​sequentially in arrays _keys And _valuesinstead of a linked list in Dictionary. This will make the search more efficient due to higher data locality.

When using FrozenDictionary find value for key Fruit("fig") would look like this (Figure 3):

1. The hash code of the key is calculated hashCode.

2. Bucket index is calculated bucketIndex.

3. In the bucket array we get the values start And enddefining the boundaries in the array HashCodes.

4. Iterate through the array HashCodes from start to endsearching for the desired key and returning the value when found.

Benchmark

Benchmark results for DefaultFrozenDictionary And ValueTypeDefaultComparerFrozenDictionary in figures 4 and 5.

High speed search in Dictionary compared to ValueTypeDefaultComparerFrozenDictionary with a dictionary size of up to 1000 elements, it is probably associated with aggressiveness inline methods Dictionary. I couldn’t understand why the limit is exactly 1000 elements, because in source code there is nothing about it. It may be a JIT compiler implementation detail. If you have any ideas on this, please share in the comments.

In other cases, FrozenDictionary 31-32% faster for value types and 17-18% faster for reference types.

Group 2. Dictionary for keys of type Int32

Int32FrozenDictionary also uses FrozenHashTable. The peculiarity of this implementation is that if the key type is an integer, then its hash is equal to its value and collisions in such a dictionary are impossible in principle. For example, you cannot add 2 elements with the key 123 – an exception will be thrown.

var dict = new Dictionary<int, int>();
dict.Add(123, 1);
dict.Add(123, 2); 
// System.ArgumentException: An item with the same key has already been added.

Search algorithm

Such a feature Int32FrozenDictionary allows you to skip the hash calculation when reading and use key value directly. As a result, the search for a value looks like this (Figure 6):

1. Bucket index bucketIndex calculated immediately based on the key value.

2. In the array bucket we get the values start And enddefining the boundaries in the array HashCodes.

3. Iterate through the array HashCodes from start to endsearching for the desired key and returning the value when found.

Benchmark

Thanks to optimizations, reading from Int32FrozenDictionary 34-42% faster (Figure 7).

Group 3. Dictionary with an algorithm for distributing strings by length

When creating “frozen” dictionaries with a string key, FrozenDictionary will try to create a class first LengthBucketsFrozenDictionary. This class is optimized for situations where keys have different lengths. This is achieved distribution of keys across buckets: for each unique key length, a bucket with a capacity of MaxPerLength = 5 elements. In essence, this is the implementation block sortTo make it clearer, let's look at an example:

var dictionary = new Dictionary<string, string>()
{
    ["apple"] = "APPLE",
    ["grape"] = "GRAPE",
    ["lemon"] = "LEMON",
    ["fig"] = "FIG",
    ["lime"] = "LIME",
    ["kiwi"] = "KIWI",
}
var frozenDictionary = dictionary.ToFrozenDictionary();

The dictionary contains keys of length 3, 4 and 5 characters. Therefore, they can be distributed into 3 buckets (Figure 8):

1. Key Bucket Length 3: fig.

2. Key Bucket Length 4: lime And kiwi.

3. Key bucket length 5: apple, grape And lemon.

Since the minimum (3) and maximum (5) key lengths are known, there is no point in creating 3 separate buckets. Everything can be stored in one array. _lengthBucketsIn this case, the index is calculated as follows: (key.Length - minLength) * MaxPerLength.

Search algorithm

The search is carried out in 3 steps (Figure 9):

1. A bucket is defined in an array _lengthBuckets.

2. Linear search in a bucket determines the index of the searched key in _keys.

3. The value is returned.

U LengthBucketsFrozenDictionary There are 2 limitations:

1. The number of keys with the same length should not exceed MaxPerLength (Dirichlet principle). You cannot fit 6 rows of the same length into a bucket with a capacity of 5 elements.

2. The number of empty buckets must be < 20%. Otherwise, the implementation becomes inefficient in terms of memory usage.

If one of these conditions is not met, one of the implementations will be selected. OrdinalStringFrozenDictionary (more about it later).

Benchmark

The benchmark results show that reading from LengthBucketsFrozenDictionary can be up to 99% faster than usual Dictionary. But if the number of keys with the same length in the dictionary reaches 5, then the performance of small dictionaries (up to 100 elements) may be worse (Figure 10).

Group 4. Dictionaries with a key of type string

As we already know, LengthBucketsFrozenDictionary there are restrictions. Therefore, if it is impossible to distribute keys across buckets, one of the 11 implementations of the abstract class is used OrdinalStringFrozenDictionary. They all use FrozenHashTablebut differ in algorithm calculating the hash code of a string.

Selecting the optimal implementation OrdinalStringFrozenDictionary depends on the result of the key analysis KeyAnalyzer class. The result is affected by the length of the keys, the presence of non-ASCII characters, and the specified string comparison rules (StringComparison) and the presence of unique substrings in the keys.

Obviously, the longer the string, the slower the hash code calculation is. Therefore KeyAnalyzer tries to find substrings of the shortest length that allow the key to be uniquely identified. For a better understanding, let's look at the fruit example again: apple, grape, fig, lime, lemon And kiwi.

First KeyAnalyzer analyzes substrings of length 1 character with left-aligned keys (Figure 11).

In our example, with left-aligned text, there are repeated substrings. For example, the 0th character lime And lemon1st character fig And lime and the 2nd character in lime And lemon. That is, it is impossible to uniquely identify a key by one character with such alignment. Therefore, the search for a substring continues with right-side alignment. In this case, substrings will be unique when using the 2nd or 1st character from the end. Knowing the alignment, the start index and the length of the substring, you can uniquely identify the string by calculating the hash code of its substring.

If there are no unique substrings of 1 character length, the search will continue for substrings of 2 characters, 3 characters, up to the maximum substring length. This value is calculated as the minimum between minLength (minimum key length) and MaxSubstringLengthLimit = 8. This limitation is made specifically to avoid analyzing too long substrings, since their use does not provide any performance gain.

If there are no unique substrings at all, then the hash code will be calculated for the entire string.

In addition to having unique substrings for implementation, there are also affected by the specified string comparison parameters (StringComparison) and the presence of non-ASCII characters. Depending on these parameters, a more optimal comparator will be selected.

Search algorithm

Search in dictionaries based on OrdinalStringFrozenDictionaryis happening as follows:

1. Checks whether the key length is within the allowed range. This is necessary to quickly identify keys that are clearly not suitable in length.

2. Next, the same steps are performed that we have previously seen in other dictionaries with FrozenHashTable. The hash code of the substring is calculated and a search is performed in the hash table. In case of a collision, a linear search is performed.

Benchmark

According to the benchmark results, FrozenDictionary up to 75 thousand elements faster than usual DictionaryHowever, with further increase in the dictionary size, the search speed decreases (Figure 12).

High speed FrozenDictionary is due to the fast calculation of the hash code of the keys. The algorithm used in FrozenDictionary75% – 90% faster than the regular algorithm Dictionary (Figure 13).

The performance drop in dictionaries with 75K elements or more is caused by the increasing number of hash collisions as the dictionary size increases (Figure 14).

As can be seen from the graphs, the algorithm used in FrozenDictionaryallows you to speed up the calculation of the string hash code, improving performance by up to 70%. However, this approach has a negative impact on the performance of searching in relatively large dictionaries.

Group 5. Small dictionaries

SmallValueTypeComparableFrozenDictionary, SmallValueTypeDefaultComparerFrozenDictionary are used when the original dictionary has no more than 10 elements, and SmallFrozenDictionary – no more than 4 elements. In this case, SmallValueTypeComparableFrozenDictionary applies if the key type is built-in primitive value type (int, long, double, enum etc.). If the key type is, for example, some custom structure, then the type will be used SmallValueTypeDefaultComparerFrozenDictionary.NET developers explain this division by the fact that built-in types have a 100% implemented interface. IComparable and therefore you can optimize the search a little by pre-sorting the arrays of keys and values:

Search algorithm

Strictly speaking, classes SmallValueTypeComparableFrozenDictionary, SmallValueTypeDefaultComparerFrozenDictionary And SmallFrozenDictionary – these are not hash tables. The search for a value in them is carried out by a simple linear search through for (Figure 15).

IN SmallValueTypeComparableFrozenDictionarysince arrays _keys And _value sorted, you can search as long as the searched key value is greater than the current value _keys[i].

Implementations SmallValueTypeDefaultComparerFrozenDictionary And SmallFrozenDictionary are similar to the previous one, with the only difference being that they do not use sorting. Accordingly, a linear search by an array of keys _keys will always be realized.

Benchmark

Despite all the optimizations in these classes, the benchmark results do not look impressive (Figure 16). Even the small speedup that these classes can provide is only a few tens of nanoseconds.

Resume

In this article I tried to analyze the main points related to FrozenDictionaryWe have made sure that FrozenDictionary in most cases it really is faster Dictionary.

In fact, in FrozenDictionary many more algorithms and optimizations are used. For example, using an array pool ArrayPooloptimized algorithm for calculating the remainder of division, using an array of integers with bit shifts, instead of an array bool etc. It would be impossible to analyze all the details within the framework of one article. But I periodically share such technical subtleties in short posts on on his Telegram channelsince the Habr format is not always suitable for this. If you are interested, I will be glad to see you among the readers.