Improve ConcurrentDictionary performance, in particular for strings (#81557)
authorStephen Toub <stoub@microsoft.com>
Thu, 9 Feb 2023 16:10:34 +0000 (11:10 -0500)
committerGitHub <noreply@github.com>
Thu, 9 Feb 2023 16:10:34 +0000 (11:10 -0500)
commitfe1607679b977b453d43c4de276968dd9ae6d5ec
treedd29a96285b0c4588a292268891ba0bed63b07c9
parent6bd31e566ee5dcd5f83e0cab75bea73c72738918
Improve ConcurrentDictionary performance, in particular for strings (#81557)

* Improve ConcurrentDictionary performance, in particular for strings

- By default, string hash codes are randomized.  This is an important defense-in-depth security measure, but it also adds some overhead when strings are used as keys in dictionaries.  `Dictionary<>` addresses that overhead by starting out with using non-randomized comparers, and then upgrades to randomized comparers only once enough collisions have been detected. This PR updates `ConcurrentDictionary<>` with similar tricks.  The comparer is moved from being stored on the dictionary itself to instead be stored on the Tables object that's atomically swapped when the table grows; that way, the comparer always remains in sync with the hashcodes stored in the nodes in that table.  When we enumerate a bucket looking for an existing key as part of an add, we count how many items we traverse, and if that resulting number is larger than the allowed threshold and we're currently using a non-randomized comparer, we force a rehash; that rehash will replace the non-randomized comparer with the equivalent randomized one.
- The `ConcurrentDictionary<>` ctor is improved to presize based on the size of a collection being passed in; otherwise, it might resize multiple times as it's populating the dictionary.  The sizing logic is also changed to use the same prime bucket selection size as does `Dictionary<>`.
- The method we were using to compute the bucket for a key wasn't being inlined for reference type keys due to the generic context; that method has been moved to the outer type as a static to avoid the non-inlined call and extra generic dictionary lookup.
- For all key types, we were also paying for a non-inlined ldelema helper call when reading the head node of a bucket; that's been addressed via a struct wrapper with a volatile node field, rather than using Volatile.Read to access the array element.
- We were inconsistent in whether checked math was used in computing the size of the table.  In some situations it would be possible to overflow without it being detected, or for it to be detected and manifest in various ways.  This simplifies to just always use checked for computing the counts.
- Remove unnecessary try/finally blocks that are leftover from CERs and thread abort protection.
- Deduped some code with calls to helper functions.

* Address PR feedback

* Address PR feedback

* Address PR feedback
src/libraries/System.Collections.Concurrent/src/System/Collections/Concurrent/ConcurrentDictionary.cs
src/libraries/System.Collections.Concurrent/tests/ConcurrentDictionary/ConcurrentDictionary.Generic.Tests.cs