我想知道我是否应该使用列表或字典,因为我知道我的结构只有很少的项目。所以我做了一个简单的基准测试📊来测试 1、3、10、20 和 50 找到该元素最快的数据结构。
令我惊讶的是😲,
ConcurrentDictionary
比正常的Dictionary
更快。我感觉由于允许多线程访问的锁,它会变慢。
➡️ 我的基准测试有问题吗? ➡️有逻辑上的理由吗? ➡️我应该一直使用
ConcurrentDictionary
BenchmarkDotNet=v0.13.5, OS=Windows 10 (10.0.19045.3803/22H2/2022Update)
AMD Ryzen 9 5900X, 1 CPU, 24 logical and 12 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
| Method | N | Mean | Error | StdDev | Allocated |
|--------------------------- |--- |-----------:|----------:|----------:|----------:|
| ListLoopSearch | 1 | 1.416 ns | 0.0153 ns | 0.0143 ns | - |
| DictionarySearch | 1 | 4.253 ns | 0.1054 ns | 0.1128 ns | - |
| ConcurrentDictionarySearch | 1 | 2.891 ns | 0.0144 ns | 0.0127 ns | - |
| ListLoopSearch | 3 | 6.237 ns | 0.0281 ns | 0.0234 ns | - |
| DictionarySearch | 3 | 10.849 ns | 0.1968 ns | 0.1745 ns | - |
| ConcurrentDictionarySearch | 3 | 6.225 ns | 0.0760 ns | 0.0711 ns | - |
| ListLoopSearch | 10 | 36.174 ns | 0.5519 ns | 0.5162 ns | - |
| DictionarySearch | 10 | 33.303 ns | 0.6607 ns | 0.7608 ns | - |
| ConcurrentDictionarySearch | 10 | 18.787 ns | 0.1348 ns | 0.1261 ns | - |
| ListLoopSearch | 20 | 118.554 ns | 1.5678 ns | 1.4665 ns | - |
| DictionarySearch | 20 | 67.028 ns | 0.4722 ns | 0.3943 ns | - |
| ConcurrentDictionarySearch | 20 | 36.108 ns | 0.6998 ns | 0.6546 ns | - |
| ListLoopSearch | 50 | 979.931 ns | 6.9250 ns | 5.4066 ns | - |
| DictionarySearch | 50 | 161.658 ns | 0.5295 ns | 0.4953 ns | - |
| ConcurrentDictionarySearch | 50 | 87.737 ns | 1.2800 ns | 1.0689 ns | - |
这是基准测试的完整代码。
#nullable enable
using BenchmarkDotNet.Attributes;
using System.Collections.Concurrent;
namespace Benchmarks;
public class Item {
public int Id { get; set; }
public int Value { get; set; }
}
public class SearchBenchmark {
[Params(1, 3, 10, 20, 50)] // 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 List<Item> _itemList;
private Dictionary<int, Item> _itemDictionary;
private ConcurrentDictionary<int, Item> _itemConcurrentDictionary;
private List<int> _searchIds; // List of IDs to search
#pragma warning restore CS8618
[GlobalSetup]
public void Setup() {
// Initialize collections with N items
_itemList = Enumerable.Range(1, NumberOfElements).Select(i => new Item { Id = i, Value = i }).ToList();
_itemDictionary = _itemList.ToDictionary(item => item.Id, item => item);
_itemConcurrentDictionary = new ConcurrentDictionary<int, Item>(_itemList.Select(item => new KeyValuePair<int, Item>(item.Id, item)));
// Prepare a list of IDs to search for, covering all elements
_searchIds = Enumerable.Range(1, NumberOfElements).ToList();
}
[Benchmark]
public void ListLoopSearch() {
// Modified to search for each ID
foreach (var id in _searchIds) {
foreach (var item in _itemList) {
if (item.Id == id)
break; // Found the item, move to the next ID
}
}
}
[Benchmark]
public void ListLinqSearch() {
// Modified to search for each ID
foreach (var id in _searchIds) {
var result = _itemList.FirstOrDefault(item => item.Id == id);
}
}
[Benchmark]
public void DictionarySearch() {
// Modified to search for each ID
foreach (var id in _searchIds) {
_itemDictionary.TryGetValue(id, out var result);
}
}
[Benchmark]
public void ConcurrentDictionarySearch() {
// Modified to search for each ID
foreach (var id in _searchIds) {
_itemConcurrentDictionary.TryGetValue(id, out var result);
}
}
}
@jonasH 询问元素在结构中按连续顺序排列这一事实是否与搜索有关。因此,我修改了代码以随机化结构和搜索中的元素。还添加了一个装有 1000 件物品的箱子。我得到了几乎相同的结果。
请注意,我没有获得 5% 或 10% 的速度奖励,它几乎快两倍!
随机结果
| Method | NumberOfElements | Mean | Error | StdDev |
|--------------------------- |----------------- |-----------------:|---------------:|---------------:|
| ListLoopSearch | 1 | 1.784 ns | 0.0163 ns | 0.0153 ns |
| ListLinqSearch | 1 | 17.368 ns | 0.1397 ns | 0.1239 ns |
| DictionarySearch | 1 | 4.178 ns | 0.0557 ns | 0.0465 ns |
| ConcurrentDictionarySearch | 1 | 3.361 ns | 0.0110 ns | 0.0102 ns |
| ListLoopSearch | 10 | 42.138 ns | 0.1538 ns | 0.1363 ns |
| ListLinqSearch | 10 | 367.041 ns | 7.3296 ns | 9.2696 ns |
| DictionarySearch | 10 | 33.073 ns | 0.0994 ns | 0.0929 ns |
| ConcurrentDictionarySearch | 10 | 18.996 ns | 0.1257 ns | 0.1176 ns |
| ListLoopSearch | 50 | 1,007.447 ns | 4.6698 ns | 4.1397 ns |
| ListLinqSearch | 50 | 6,424.562 ns | 127.1539 ns | 136.0533 ns |
| DictionarySearch | 50 | 161.110 ns | 0.5328 ns | 0.4984 ns |
| ConcurrentDictionarySearch | 50 | 87.332 ns | 1.4004 ns | 1.3100 ns |
| ListLoopSearch | 1000 | 324,126.481 ns | 1,032.4962 ns | 965.7976 ns |
| ListLinqSearch | 1000 | 1,961,426.994 ns | 38,245.5683 ns | 42,509.8478 ns |
| DictionarySearch | 1000 | 3,233.511 ns | 11.0090 ns | 10.2978 ns |
| ConcurrentDictionarySearch | 1000 | 1,825.452 ns | 19.3568 ns | 18.1064 ns |```
Updated code:
公共类SearchBenchmark {
[Params(1, 10, 50, 1000)] // 结构体中的元素数量
公共 int 元素数量;
私有列表_itemList;
私人词典
[GlobalSetup]
public void Setup() {
// Initialize collections with N items randomly ordered
Random random = new Random();
_searchIds = Enumerable.Range(1, NumberOfElements).OrderBy(_ => random.Next()).ToList();
// Initialize collections with N items randomly ordered (different order)
_itemList = Enumerable.Range(1, NumberOfElements).OrderBy(_ => random.Next()).Select(i => new Item { Id = i, Value = i }).ToList();
_itemDictionary = _itemList.ToDictionary(item => item.Id, item => item);
_itemConcurrentDictionary = new ConcurrentDictionary<int, Item>(_itemList.Select(item => new KeyValuePair<int, Item>(item.Id, item)));
// Prepare a list of IDs to search for, covering all elements
}
[Benchmark]
public void ListLoopSearch() {
// Modified to search for each ID
foreach (var id in _searchIds) {
foreach (var item in _itemList) {
if (item.Id == id)
break; // Found the item, move to the next ID
}
}
}
[Benchmark]
public void ListLinqSearch() {
// Modified to search for each ID
foreach (var id in _searchIds) {
var result = _itemList.FirstOrDefault(item => item.Id == id);
}
}
[Benchmark]
public void DictionarySearch() {
// Modified to search for each ID
foreach (var id in _searchIds) {
_itemDictionary.TryGetValue(id, out var result);
}
}
[Benchmark]
public void ConcurrentDictionarySearch() {
// Modified to search for each ID
foreach (var id in _searchIds) {
_itemConcurrentDictionary.TryGetValue(id, out var result);
}
}
}