ConcurrentDictionary.TryGetValue faster than Dictionary.TryGetValue

[gurustron]

Not sure if this is actually an issue but in some cases ConcurrentDictionary.TryGetValue seems to be faster than it's non-concurrent counterpart (maybe due to different collisions handling).

From this SO question.

Description

public class SearchBenchmark2 {
    [Params(1, 20, 50, 777)] // Number of elements in the structure
    // ReSharper disable once UnassignedField.Global
    public int NumberOfElements;

#pragma warning disable CS8618 // value init in the Setup function
    private Dictionary<int, int> _itemDictionary;
    private ConcurrentDictionary<int, int> _itemConcurrentDictionary;
    private int[] _toSearch;
#pragma warning restore CS8618
    [GlobalSetup]
    public void Setup()
    {
	    var s = Guid.NewGuid().ToString();
	    _toSearch = Enumerable.Range(1, NumberOfElements).Select(i => i + 121).ToArray();
        _itemDictionary = _toSearch.ToDictionary(i => i);
        _itemDictionary = new Dictionary<int, int>(_itemDictionary);
        _itemConcurrentDictionary = new ConcurrentDictionary<int, int>(_itemDictionary);
    }

    [Benchmark]
    public int DictionarySearch() {
	    int result = default;
        for (int i = 0; i < 1_000; i++)
	        foreach (var id in _toSearch)
	        {
		        _itemDictionary.TryGetValue(id, out result);
	        }
        return result;
    }
    [Benchmark]
    public int ConcurrentDictionarySearch()
    {
	    int result = default;
	    for (int i = 0; i < 1_000; i++)
		    foreach (var id in _toSearch)
		    {
			    _itemConcurrentDictionary.TryGetValue(id, out result);
		    }
	    return result;
    }
}

public class SearchBenchmark2 {
    [Params(1, 20, 50, 777)] // Number of elements in the structure
    // ReSharper disable once UnassignedField.Global
    public int NumberOfElements;

#pragma warning disable CS8618 // value init in the Setup function
    private Dictionary<string, string> _itemDictionary;
    private ConcurrentDictionary<string, string> _itemConcurrentDictionary;
    private string[] _toSearch;
#pragma warning restore CS8618
    [GlobalSetup]
    public void Setup()
    {
	    var s = Guid.NewGuid().ToString();
	    _toSearch = Enumerable.Range(1, NumberOfElements).Select(i => s + (i + 121)).ToArray();
        _itemDictionary = _toSearch.ToDictionary(i => i);
        _itemDictionary = new Dictionary<string, string>(_itemDictionary);
        _itemConcurrentDictionary = new ConcurrentDictionary<string, string>(_itemDictionary);
    }

    [Benchmark]
    public string DictionarySearch() {
	    string result = "";
        for (int i = 0; i < 1_000; i++)
	        foreach (var id in _toSearch)
	        {
		        _itemDictionary.TryGetValue(id, out result);
	        }
        return result;
    }
    [Benchmark]
    public string ConcurrentDictionarySearch() {
	    string result = "";
	    for (int i = 0; i < 1_000; i++)
		    foreach (var id in _toSearch)
		    {
			    _itemConcurrentDictionary.TryGetValue(id, out result);
		    }
	    return result;
    }
}

Configuration

BenchmarkDotNet v0.13.11, Windows 11 (10.0.22621.2861/22H2/2022Update/SunValley2)
Intel Core i7-9750H CPU 2.60GHz, 1 CPU, 12 logical and 6 physical cores
.NET SDK 8.0.100
[Host] : .NET 8.0.0 (8.0.23.53103), X64 RyuJIT AVX2
DefaultJob : .NET 8.0.0 (8.0.23.53103), X64 RyuJIT AVX2

Regression?

N/A

Data

With ints:

Method	NumberOfElements	Mean	Error	StdDev
DictionarySearch	1	5.146 us	0.0936 us	0.0875 us
ConcurrentDictionarySearch	1	2.531 us	0.0277 us	0.0231 us
DictionarySearch	20	96.793 us	1.3276 us	1.2419 us
ConcurrentDictionarySearch	20	52.107 us	0.9807 us	0.9173 us
DictionarySearch	50	254.157 us	2.9856 us	2.4931 us
ConcurrentDictionarySearch	50	124.251 us	1.9200 us	1.7020 us
DictionarySearch	777	3,845.440 us	76.3898 us	71.4550 us
ConcurrentDictionarySearch	777	1,747.044 us	31.0962 us	29.0874 us

With strings (have not checked for collisions generated):

Method	NumberOfElements	Mean	Error	StdDev
DictionarySearch	1	16.63 us	0.154 us	0.129 us
ConcurrentDictionarySearch	1	14.25 us	0.083 us	0.074 us
DictionarySearch	20	417.35 us	2.538 us	2.374 us
ConcurrentDictionarySearch	20	311.96 us	1.956 us	1.734 us
DictionarySearch	50	1,001.90 us	7.227 us	6.407 us
ConcurrentDictionarySearch	50	740.98 us	7.614 us	7.122 us
DictionarySearch	777	16,658.93 us	60.573 us	53.696 us
ConcurrentDictionarySearch	777	15,127.73 us	118.530 us	105.074 us

Analysis

[eiriktsarpalis]

It's interesting that the difference manifests consistently, even in dictionaries with just one entry. This makes me think that it's an inherent property of the lookup implementation and not something related to collisions occurring.

Looking at the implementation I would guess it has something to do with the added concurrent operation tracking logic, which isn't necessary in the case of ConcurrentDictionary. Of course this is pure speculation unless somebody actually profiles the methods.

I think this has been pointed out already in the SO discussion, but this is no reason for recommending users to switch to CD -- assuming updates are needed these are substantially more expensive compared to a regular dictionary and assuming they are not users would be even better off using a FrozenDictionary instead.

[gurustron]

@eiriktsarpalis non-key types? I have run several tests with custom Item type (with overloaded equality members to simulate/control collisions) results were pretty much the same.

[eiriktsarpalis]

non-key types?

That should have been non-integer key types 😑

[gurustron]

@eiriktsarpalis rerun the tests with non-integer key types. For custom type FrozenDictionary fluctuates around ConcurrentDictionary and for string gave me better performance.

[eiriktsarpalis]

That should be expected, the cost of computing the hash code is typically a substantial component of the lookup operation. Given that for integer keys in particular getting a hash code is trivial, any discrepancies in the lookup implementation itself should show up more prominently in benchmarks.

[danmoseley]

@gurustron you could extract Dictionary and paste it into your benchmark and remove the check for concurrent access from your copy, and see whether that makes any difference.