[C#].NET 9から導入されたOrderedDictionaryについて


この投稿は[C# Advent Calendar 2024](https://qiita.com/advent-calendar/2024/csharplang) 8日目の記事です。

はじめに
---
.NET 9からジェネリック版の[OrderedDictionary](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.ordereddictionary-2?view=net-9.0)が導入されました。  
`OrderedDictionary`の特徴は、要素を追加した順番を維持した状態でキーと要素を保持できる点になります。  
これだけなら .NET 9以前にも非ジェネリック版の[System.Collections.Specialized.OrderedDictionary](https://learn.microsoft.com/en-us/dotnet/api/system.collections.specialized.ordereddictionary?view=net-8.0)も同様の特徴をもっています。ただキーと要素が`Object`であるから、つねにボックス化が発生してしまい、パフォーマンスもあまり良いとはいえませんでした。  
ジェネリック版ではパフォーマンスも向上し、またジェネリック版から導入されたインデックスを用いたメソッドも追加されましたので、今回はこれらについて色々触れていきます。

確認環境
---

* Visual Studio Community 2022 (v17.12.0)
* .NET 9 (C# 13)

基本的な使い方
---

`Dictionary`と同じようにキーと要素の型を指定し、インスタンスを作成します。
追加、削除、検索、取得についても、`Dictionary`と同様のAPI群を使用して実行可能です。  
また順番を維持した状態で要素を保持しているため、要素を追加した順番で列挙します。

```csharp
// インスタンス作成
var dict = new OrderedDictionary<string, int>()
{
    { "A", 1 },
    { "B", 2 },
    { "C", 3 }
};

// キーと要素を追加
dict.Add("D", 4);
// キーに紐づく要素を作成
dict.Remove("D");
// キーと要素を追加
dict.Add("E", 5);

// キーに紐づく要素を検索し、見つかった場合には要素を取得する
if (dict.TryGetValue("A", out var value))
{
    Console.WriteLine(value); // 1
}

// 保持しているキーと要素を列挙する
// 追加した順番（登録した順番）で列挙する
foreach (var pair in dict)
{
    Console.WriteLine($"key = {pair.Key}, Value = {pair.Value}");
}
// key = A, Value = 1
// key = B, Value = 2
// key = C, Value = 3
// key = E, Value = 5
```

インデックスを用いた追加/削除/検索/取得
---

インデックスから要素へアクセスする方法が非ジェネリック版から変更されています。  
インデックスの要素の取得、更新は、非ジェネリック版はインデクサー（`this[int index]`）でしたが、ジェネリック版では`GetAt`メソッドと`SetAt`メソッドに変更されています。  
`GetAt`メソッドは、`KeyValuePair<TKey, TValue>`で返却するため、指定したインデックスの要素だけでなくキーも取得できます。  
`SetAt`メソッドは、指定したインデックスの要素だけでなく、キー自体も更新できます。

```csharp
// インスタンス作成
var dict = new OrderedDictionary<string, int>()
{
    { "A", 1 },
    { "B", 2 },
    { "C", 3 }
};

// index:1の要素を取得します
var value = dict.GetAt(0);
Console.WriteLine(value); // [A, 1]

// index:1の要素を更新します
dict.SetAt(1, 4);
// index:2のキーと要素をそれぞれ更新もします
dict.SetAt(2, "D", 5);

// key = A, Value = 1
// key = B, Value = 4
// key = D, Value = 5
```

指定したインデックスへキーと要素の挿入は、`Insert`メソッドで可能です。

```csharp
var dict = new OrderedDictionary<string, int>()
{
    { "A", 1 },
    { "B", 2 },
    { "C", 3 }
};

// index:1に["D", 4]を挿入します
dict.Insert(1, "D", 4);

foreach (var pair in dict)
{
    Console.WriteLine($"key = {pair.Key}, Value = {pair.Value}");
}

// key = A, Value = 1
// key = D, Value = 4
// key = B, Value = 2
// key = C, Value = 3
```

指定したインデックスのキーと要素の削除は、`RemoveAt`メソッドで可能です。

```csharp
var dict = new OrderedDictionary<string, int>()
{
    { "A", 1 },
    { "B", 2 },
    { "C", 3 }
};

// index:1のキーと要素を削除します。
dict.RemoveAt(1);

foreach (var pair in dict)
{
    Console.WriteLine($"key = {pair.Key}, Value = {pair.Value}");
}

// key = A, Value = 1
// key = C, Value = 3
```

`IndexOf`メソッドは、キーからインデックスを取得することが可能です。

```csharp
var dict = new OrderedDictionary<string, int>()
{
    { "A", 1 },
    { "B", 2 },
    { "C", 3 }
};

var index = dict.IndexOf("B");
Console.WriteLine(index); // 1

var pair = dict.GetAt(index);
Console.WriteLine($"key = {pair.Key}, Value = {pair.Value}");
```

パフォーマンス比較
---

ジェネリック版や通常の`Dictionary`と比べてどれくらいパフォーマンスが上がっているのか、[BenchmarkDotNet](https://github.com/dotnet/BenchmarkDotNet)を使用して確認しました。  

<details><summary>ベンチマークのソースコード</summary>

```csharp

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Columns;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Diagnosers;
using BenchmarkDotNet.Exporters;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;
using System.Runtime.InteropServices;

new BenchmarkSwitcher(
    [typeof(AddBenchmark), typeof(IndexerBenchmark)])
    .Run(["Release", "--filter", "*"]);

[Config(typeof(BenchmarkConfig))]
public class AddBenchmark
{
    private int count;
    private List<string> keys;

    [GlobalSetup]
    public void GlobalSetup()
    {
        count = 1000000;
        keys = Enumerable.Range(1, count).Select(i => i.ToString("x")).ToList();
    }

    [Benchmark(Baseline = true)]
    public void OrderedDictionary_Add()
    {
        var keys = CollectionsMarshal.AsSpan(this.keys);
        var dict = new OrderedDictionary<string, int>();

        for (int i = 0; i < keys.Length; i++)
        {
            dict.Add(keys[i], i);
        }
    }

    [Benchmark]
    public void OrderedDictionaryForNonGeneric_Add()
    {
        var keys = CollectionsMarshal.AsSpan(this.keys);
        var dict = new System.Collections.Specialized.OrderedDictionary();

        for (int i = 0; i < keys.Length; i++)
        {
            dict.Add(keys[i], i);
        }
    }

    [Benchmark]
    public void Dictionary_Add()
    {
        var keys = CollectionsMarshal.AsSpan(this.keys);
        var dict = new OrderedDictionary<string, int>();

        for (int i = 0; i < keys.Length; i++)
        {
            dict.Add(keys[i], i);
        }
    }
}

[Config(typeof(BenchmarkConfig))]
public class IndexerBenchmark
{
    private List<string> keys;
    private OrderedDictionary<string, int> orderedDict;
    private System.Collections.Specialized.OrderedDictionary orderedDictForNonGeneric;
    private Dictionary<string, int> dict;

    [GlobalSetup]
    public void GlobalSetup()
    {
        this.keys = Enumerable.Range(1, 1000000).Select(i => i.ToString("x")).ToList();

        orderedDict = new OrderedDictionary<string, int>();
        orderedDictForNonGeneric = new System.Collections.Specialized.OrderedDictionary();
        dict = new Dictionary<string, int>();

        var keys = CollectionsMarshal.AsSpan(this.keys);
        for (int i = 0; i < keys.Length; i++)
        {
            orderedDict.Add(keys[i], 1);
            orderedDictForNonGeneric.Add(keys[i], 1);
            dict.Add(keys[i], 1);
        }
    }

    [Benchmark(Baseline = true)]
    public void OrderedDictionary_Indexer()
    {
        var sum = 0;
        var keys = CollectionsMarshal.AsSpan(this.keys);
        for (int i = 0; i < keys.Length; i++)
        {
            sum += orderedDict[keys[i]];
        }
    }

    [Benchmark]
    public void OrderedDictionaryForNonGeneric_Indexer()
    {
        var sum = 0;
        var keys = CollectionsMarshal.AsSpan(this.keys);
        for (int i = 0; i < keys.Length; i++)
        {
            sum += (int)orderedDictForNonGeneric[keys[i]];
        }
    }

    [Benchmark]
    public void Dictionary_Indexer()
    {
        var sum = 0;
        var keys = CollectionsMarshal.AsSpan(this.keys);
        for (int i = 0; i < keys.Length; i++)
        {
            sum += dict[keys[i]];
        }
    }
}

internal sealed class BenchmarkConfig : ManualConfig
{
    public BenchmarkConfig()
    {
        AddExporter(MarkdownExporter.GitHub);
        AddDiagnoser(MemoryDiagnoser.Default);
        AddColumn(RankColumn.Arabic);
        AddColumn(StatisticColumn.Min);
        AddColumn(StatisticColumn.Max);

        //AddJob(Job.ShortRun);
        AddJob(Job.MediumRun);
    }
}
```

</details>

まず、1000000個のキーと要素を追加した場合の計測結果になります。

| Method                             | Mean      | Error     | StdDev    | Min       | Max       | Ratio | RatioSD | Rank | Gen0      | Gen1      | Gen2      | Allocated | Alloc Ratio |
|----------------------------------- |----------:|----------:|----------:|----------:|----------:|------:|--------:|-----:|----------:|----------:|----------:|----------:|------------:|
| OrderedDictionary_Add              |  59.48 ms |  1.144 ms |  1.566 ms |  56.07 ms |  62.07 ms |  1.00 |    0.04 |    1 | 1222.2222 | 1222.2222 | 1222.2222 |  71.95 MB |        1.00 |
| OrderedDictionaryForNonGeneric_Add | 379.71 ms | 11.404 ms | 16.716 ms | 357.69 ms | 419.80 ms |  6.39 |    0.32 |    2 | 8000.0000 | 7000.0000 | 2000.0000 | 131.08 MB |        1.82 |
| Dictionary_Add                     |  56.34 ms |  2.370 ms |  3.474 ms |  52.05 ms |  65.09 ms |  0.95 |    0.06 |    1 | 1222.2222 | 1222.2222 | 1222.2222 |  71.95 MB |        1.00 |

ジェネリック版と比較すると約6倍の高速化、アロケーションも約2倍削減とパフォーマンスがかなり向上しているようです。
また`Dictionary`と比較しても、同じぐらい（わずかにおそい程度）の速度で実行されていました。  
追加処理だけで計測したため、他処理と組み合わさった場合もう少し遅くなる見込みですが、それでもは向上していると思います。

次に1000000個のキーと要素が追加されている状態で、1000000回インデクサー経由で値を取得した場合の計測結果になります。

| Method                                 | Mean     | Error    | StdDev   | Min      | Max      | Ratio | RatioSD | Rank | Allocated | Alloc Ratio |
|--------------------------------------- |---------:|---------:|---------:|---------:|---------:|------:|--------:|-----:|----------:|------------:|
| OrderedDictionary_Indexer              | 28.18 ms | 1.671 ms | 2.449 ms | 24.70 ms | 33.72 ms |  1.01 |    0.12 |    2 |      12 B |        1.00 |
| OrderedDictionaryForNonGeneric_Indexer | 67.20 ms | 0.896 ms | 1.255 ms | 64.95 ms | 70.54 ms |  2.40 |    0.20 |    3 |      50 B |        4.17 |
| Dictionary_Indexer                     | 25.04 ms | 0.511 ms | 0.717 ms | 23.91 ms | 26.20 ms |  0.90 |    0.08 |    1 |      12 B |        1.00 |

ジェネリック版と比較すると約2倍の高速化、アロケーションも約4倍削減とこちらもパフォーマンスがかなり向上しているようです。
また`Dictionary`と比較しても、同じぐらい（わずかにおそい程度）の速度で実行されているため、要素取得についてもパフォーマンスは向上していると思います。

その他
---

`Dictionary`や`HashSet`に追加された[GetAlternateLookupメソッド](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.getalternatelookup?view=net-9.0)が`OrderedDictionary`には実装されていないため、キーに指定した型のみでしか検索できないようです。

おわりに
---

ちょっとしたアプリを作成しているときなどに、順番を保持したハッシュテーブルが必要になることがありました。そのたびに順番保持用の`List`を作成したりするなどちょっとした手間が発生していました。  
.NET 9からは、自前実装する必要なくパフォーマンスが良いジェネリック版を使用することができるため、積極的に使用していきましょう！  
C# Advent Calendar 2024、9日目は[@akiojin](https://qiita.com/akiojin)さんです。
よろしくお願いいたします！