【C#】IComparable、IComparer、Comparison にパフォーマンスの違いはあるのか？

# はじめに
リストのソートの実装方法は一般的に３つがあると思っています。

- 格納するアイテムのクラスに``IComparable`` を継承する
- ``IComparer``を継承した比較クラスを作成する
- ``Comparison``デリゲートで比較メソッドを作成する

本稿はこれらの実装方法において、実行速度に違いがあるのか検証したものになります。

# 各実装方法のおさらい
簡単な例として、下記の ID のみを持つ``Data``クラスをIDの昇順にソートする方法を考えてみます。
```C#
class Data {
  public int Id { get; set; }
}

class Program {
  static void Main(string[] args) {
    // ソートしたいリスト
    var list = new List<Data>() {
      new Data { Id = 20000000 },
      new Data { Id = 19999999 },
      ...
    }
  }
}
```

## IComparable
``Data``に``IComparable``を継承して、``CompareTo(T obj)``を実装します。比較対象も比較方法も一緒に管理出来るので楽ですが、比較方法が一つしか指定出来ない点（※）、``Data``の実装を見ないとソート方法が不明瞭な点がデメリットですかね。

※ IDと名前を持つクラスがあったとして、時にはIDで、時には名前でソートといった使い分けが出来ない。

```C#
class Data : IComparable<Data> {
  public int Id { get; set; }
  // インターフェースを実装
  public int CompareTo(DataComparable obj) {
    return Id - obj.Id;
  }
}

class Program {
  static void Main(string[] args) {
    // ソートしたいリスト
    var list = new List<Data>() {
      new Data { Id = 20000000 },
      new Data { Id = 19999999 },
      ...
    }
    // 引数なしのSortを呼び出し
    list.Sort();
  }
}
```

## IComparer
``IComparer``を継承したクラスを実装します。クラスが必要で手間ですが、比較方法が複数指定出来ますし、ソート使用者側でソート方法を選択出来るので便利です。

```C#
// 省略

class Comparer : IComparer<Data> {
  public int Compare(Data x, Data y) {
    return x.Id - y.Id;
  }
}

class Program {
  static void Main(string[] args) {
    // ソートしたいリスト
    var list = new List<Data>() {
      new Data { Id = 20000000 },
      new Data { Id = 19999999 },
      ...
    }
    // 引数にComparerを指定してSortを呼び出し
    list.Sort(new Comparator());
  }
}
```

## Comparison
``int Comparison<in T>(T x, T y)``デリゲートにあったメソッドを実装します。イメージとしてはクラスが不要となった``IComparer``でしょうか。コード量が減りますし、変数チックに扱えるので個人的に一番好きです。

```C#
// 省略

class Program {
  static void Main(string[] args) {
    // ソートしたいリスト
    var list = new List<Data>() {
      new Data { Id = 20000000 },
      new Data { Id = 19999999 },
      ...
    }
    // 比較メソッドを作成
    Comparison<Data> comparison = (x, y) => x.Id - y.Id;
    // 引数にComparisonデリゲートを指定してSortを呼び出し
    list.Sort(comparison);
  }
}
```

# 本題の実行速度の違いは？
結論から述べると検証結果としては``Comparison``で実装したソートが20%程実行速度が早かったですが、環境による差なので本当は``IComparer``が早いんじゃね？です。

以降では結論に至った過程をだらだらと説明していきます。

## 検証方法
2000万レコードの``Data``をID降順に並べたListを、ID昇順にソートするのに掛かった時間を計測しました。用意したプログラムの全量は最後に載せておきます。

```C#
// タイマーを用意して
var sw = new Stopwatch();
// データを作成して
var list = new List<Data>();
for (var id = 20000000; id > 0; id--) {
  list.Add(new Data { Id = id });
}
// ソートする時間を計測
sw.Start();
list.Sort();
sw.Stop();
```

## 検証結果
下記の通り、``Comparison``が``IComparable``、``IComparer``よりも20%ほど処理速度が早い結果となりました。いやいや、流石にこの差はおかしいだろという事で、``List#Sort``が内部で何をしているのか確認してみます。

| |IComparable|IComparer|Comparison|
|---|---|---|---|
|1回目|10,917|11,616|8,700|
|2回目|11,749|11,701|8,687|
|3回目|11,039|11,523|8,707|
|4回目|10,768|11,917|8,707|
|5回目|10,946|11,602|8,762|
|合計 |55,419|58,359|43,563|
|平均 |11,083|11,671|8,712|

## （理解出来る場所まで）内部処理を確認する
まず``IComparable``と``IComparer``の処理は下記のとおりです。

### IComparable、IComparer

#### 1. List#Sort() を呼び出す
``IComparable``の場合は``comparer``に``null``を設定して呼び出します。
```C#
public void Sort() {
  Sort(0, Count, comparer);
}
```

#### 2. List#Sort(int, int, IComparer) を呼び出す
エラーチェックをして、Array#Sortを呼び出します。``List``も内部的には``Array``で要素を管理していますからね。
```C#
public void Sort(int index, int count, IComparer<T> comparer) {
  if (index < 0) {
    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  }

  if (count < 0) {
    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  }

  if (_size - index < count) { 
    ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
  }

  Array.Sort(_items, index, count, comparer);
  _version++;
}
```

#### 3. Array#Sort<T>(T[] array, int index, int length, IComparer<T> comparer) を呼び出す
配列のエラーチェックをして、何やかんやで``ArraySortHelper#Sort``を**多分**呼び出します。
```C#
public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer) {
  if (array == null) {
    throw new ArgumentNullException("array");
  }

  if (index < 0 || length < 0) {
    throw new ArgumentOutOfRangeException((length < 0) ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  }

  if (array.Length - index < length) {
    throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  }

  if (length > 1 && ((comparer != null && comparer != Comparer<T>.Default) || !TrySZSort(array, null, index, index + length - 1))) {
    ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
  }
}
```

#### 4. ArraySortHelper#Sort(T[] keys, int index, int length, IComparer<T> comparer) を呼び出す（多分）
要素の比較方法とソートに使うアルゴリズムを選択します。``IComparable``の場合は``comparer``が``null``なので、``comparer``の取得処理を行います。

```C#
public void Sort(T[] keys, int index, int length, IComparer<T> comparer) {
  try {
    if (comparer == null) {
      comparer = Comparer<T>.Default;
    }

    if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) {
      IntrospectiveSort(keys, index, length, comparer);
    } else {
      DepthLimitedQuickSort(keys, index, length + index - 1, comparer, 32);
    }
  } catch (IndexOutOfRangeException) {
    IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
  } catch (Exception innerException) {
    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), innerException);
  }
}
```

#### 5. Comparer<T>.Default で Comparer を取得する（多分）
Runtimeほにゃらら系が何を行っているのかさっぱり理解出来ませんが、単語を拾うに``IComparable``を``Comparer``に変換しているのだと思います。 

```C#
private static readonly Comparer<T> defaultComparer = CreateComparer();

public static Comparer<T> Default {
  get {
    return defaultComparer;
  }
}

// ???
private static Comparer<T> CreateComparer() {
  RuntimeType runtimeType = (RuntimeType)typeof(T);
  if (typeof(IComparable<T>).IsAssignableFrom(runtimeType)) {
    return (Comparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericComparer<int>), runtimeType);
  }

  if (runtimeType.IsGenericType && runtimeType.GetGenericTypeDefinition() == typeof(Nullable<>)) {
    RuntimeType runtimeType2 = (RuntimeType)runtimeType.GetGenericArguments()[0];
    if (typeof(IComparable<>).MakeGenericType(runtimeType2).IsAssignableFrom(runtimeType2)) {
      return (Comparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableComparer<int>), runtimeType2);
    }
  }
  return new ObjectComparer<T>();
}

```

#### 7. ArraySortHelper#IntrospectiveSort(T[], int, int, int, IComparer<T>) を呼び出す（多分）
``IntrospectiveSort``と``DepthLimitedQuickSort``のどちらを呼び出すのか不明ですが、ひとまず``IntrospectiveSort``を使用しているとします。ついに配列の各要素を比較している部分が見えてきました。

```C#
internal static void IntrospectiveSort(T[] keys, int left, int length, IComparer<T> comparer) {
  if (length >= 2) {
    IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer);
  }
}

private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer<T> comparer) {
  while (hi > lo) {
    int num = hi - lo + 1;
    if (num <= 16) {
      switch (num) {
        case 1:
          break;
        case 2:
          SwapIfGreater(keys, comparer, lo, hi);
          break;
        case 3:
          SwapIfGreater(keys, comparer, lo, hi - 1);
          SwapIfGreater(keys, comparer, lo, hi);
          SwapIfGreater(keys, comparer, hi - 1, hi);
          break;
        default:
          InsertionSort(keys, lo, hi, comparer);
          break;
      }

      break;
    }

    if (depthLimit == 0) {
      Heapsort(keys, lo, hi, comparer);
      break;
    }

    depthLimit--;
    int num2 = PickPivotAndPartition(keys, lo, hi, comparer);
    IntroSort(keys, num2 + 1, hi, depthLimit, comparer);
    hi = num2 - 1;
  }
}
```

#### 8. ArraySortHelper#SwapIfGreater(T[], IComparer<T>, int, int) を呼び出す
やっとここで``Comparer``を使って比較を行います・・・長かった・・・。

```C#
private static void SwapIfGreater(T[] keys, IComparer<T> comparer, int a, int b) {
  if (a != b && comparer.Compare(keys[a], keys[b]) > 0) {
    T val = keys[a];
    keys[a] = keys[b];
    keys[b] = val;
  }
}
```

### Comparison

#### 1. List#Sort(Comparison<T>) を呼び出し


```C#
public void Sort(Comparison<T> comparison) {
  if (comparison == null) {
    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  }

  if (_size > 0) {
    IComparer<T> comparer = new Array.FunctorComparer<T>(comparison);
    Array.Sort(_items, 0, _size, comparer);
  }
}
```

#### 2. Array#FunctorComparer を作成
簡潔に述べれば``Comparison``を``Comparer``に変換しているだけです。デザインパターンで言うところの``Adapter``パターンですね。

```C#
internal sealed class FunctorComparer<T> : IComparer<T> {
  private Comparison<T> comparison;
  public FunctorComparer(Comparison<T> comparison) {
    this.comparison = comparison;
  }

  public int Compare(T x, T y) {
    return comparison(x, y);
  }
}
```

#### 3. 以降の処理は``IComparable``の3以降の処理と同じ！

## 分かった事
長々と眺めて来ましたが、``IComparerable``も``Comparison``も結局は``Comparer``に変換されて使われるという事が判りました。更に``Comparison``に関しては、``Comparer#Compare()``から``Comparison``デリゲートを呼び出しているので、呼び出しのオーバーヘッドで遅くなりそうなイメージです。

# 困ったときの stack overflow
理解の限界を超えたので、検索してみると案の定同じ疑問を投げかけている方がいました。stack overflow の下記投降です。

[Is performance of List.Sort() by Comparison is better than custom IComparer?](https://stackoverflow.com/questions/52459054/is-performance-of-list-sort-by-comparison-is-better-than-custom-icomparer)

こちらの回答によれば、「俺の環境では``IComparer``の方がむしろ早かった。インターフェースのメソッドとデリゲートの呼び出しには速度差があり、インターフェースの方が高速なのだろう。」と結論付けていました。

# まとめ
内部処理的にはどの実装方法でも速度差はない印象です。そしてここまで調べておいてなんですが、そんなところを気にするよりは、見やすく分かりやすい実装方法を選択するのがベストだと思います・・・。

# 付録
検証で使ったソースコード
```C#
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace ConsoleApp1 {

  internal class Program {

    [MethodImpl(MethodImplOptions.NoInlining)]
    static void Main(string[] args) {
      long total;
      int repeatCount = 20000000;
      var sw = new Stopwatch();

      total = 0;
      Console.WriteLine("<IComparable>");
      for (var i = 0; i < 5; i++) {
        var dataList = new List<DataComparable>();
        for (var id = repeatCount; id > 0; id--) {
          dataList.Add(new DataComparable { Id = id });
        }
        sw.Start();
        dataList.Sort();
        sw.Stop();
        total += sw.ElapsedMilliseconds;
        Console.WriteLine($"[{i + 1}] {sw.ElapsedMilliseconds}ms");
        sw.Reset();
      }
      Console.WriteLine($"Total: {total}ms Average: {total / 5}");

      total = 0;
      Console.WriteLine("<IComparer>");
      for (var i = 0; i < 5; i++) {
        var dataList = new List<Data>();
        for (var id = repeatCount; id > 0; id--) {
          dataList.Add(new Data { Id = id });
        }
        sw.Start();
        dataList.Sort(new Compartor());
        sw.Stop();
        total += sw.ElapsedMilliseconds;
        Console.WriteLine($"[{i + 1}] {sw.ElapsedMilliseconds}ms");
        sw.Reset();
      }
      Console.WriteLine($"Total: {total}ms Average: {total / 5}");

      total = 0;
      Console.WriteLine("<Comparison>");
      Comparison<Data> comparizon = (x, y) => x.Id - y.Id;
      for (var i = 0; i < 5; i++) {
        var dataList = new List<Data>();
        for (var id = repeatCount; id > 0; id--) {
          dataList.Add(new Data { Id = id });
        }
        sw.Start();
        dataList.Sort((Comparison<Data>)((x, y) => x.Id - y.Id));
        sw.Stop();
        total += sw.ElapsedMilliseconds;
        Console.WriteLine($"[{i + 1}] {sw.ElapsedMilliseconds}ms");
        sw.Reset();
      }
      Console.WriteLine($"Total: {total}ms Average: {total / 5}");

dataList.Add(new Data { Id = id });
      Console.ReadLine();
    }

  }

  internal sealed class Data {
    public int Id { get; set; }
  }

  internal sealed class DataComparable : IComparable<DataComparable> {
    public int Id { get; set; }

    public int CompareTo(DataComparable obj) {
      return Id - obj.Id;
    }
  }

  internal sealed class Compartor : IComparer<Data> {
    public int Compare(Data x, Data y) {
      return x.Id - y.Id;
    }
  }

}
```