Zenn
📖

C#におけるベクトル的データ構造のパフォーマンス比較①

2022/09/21に公開
.NET
C#
benchmark
tech

概要

C# にて数値ベクトルを表すデータ構造の速度比較を行った．
大量にインスタンスを生成し演算を行うタスクにおいて，UnityEngine.Vector2 が最も速く，次点でタプルに拡張methodを定義し演算を行ったもの， System.Numerics.Vector2 が速かった．

背景

C# ではベクトル演算を行うデータ構造として System.Numerics.Vector2 などが提供されているが，単精度浮動小数点数で2次元から4次元までに限られており，他の数値型を使用したい場合や5次元以上のベクトルを用いたい場合など，ユーザー定義のデータ構造を定義したい場面がある．
本記事ではまず単精度浮動小数点数の2次元の場合に限り，様々な実装でのパフォーマンス比較を行った．

実験方法

ベンチマーク用ライブラリ BenchmarkDotNet を用いてベンチマークを行った．
環境は以下の通り．

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22000.918/21H2)
Intel Core i7-10700T CPU 2.00GHz, 1 CPU, 16 logical and 8 physical cores
.NET SDK=6.0.302
  [Host]     : .NET 6.0.7 (6.0.722.32202), X64 RyuJIT AVX2
  DefaultJob : .NET 6.0.7 (6.0.722.32202), X64 RyuJIT AVX2

ベンチマークは (1, 0) \times k + (0, 1) \times k が (1, 1) \times k と等しいかを確認するというタスクを各データ構造について行った．
この演算には生成・スカラー倍・加算・等値比較の操作が含まれているため，各データ構造の実装でこれらの操作が演算子のオーバーロードまたはメソッド呼び出しで行えることを必要要件とした．

比較対象のデータ構造として以下のものを用いた．

  • System.Numerics.Vector2
  • UnityEngine.Vector2
  • ユーザー定義struct
  • ユーザー定義class
  • タプル(System.ValueTuple)
    • 拡張method
    • structによるラッパー
  • System.Tuple
    • 継承class
    • 拡張method
    • structによるラッパー
  • 配列(System.Array)
    • 拡張method
    • structによるラッパー
  • System.Collections.Generic.List
    • 継承class
  • System.Numerics.Vector< T >

以下でそれぞれの実装について説明する．
ソースコードは GitHub で公開しているため，詳細についてはこちらを参照のこと．

System.Numerics.Vector2

参照：Vector2 Struct (System.Numerics)

float型の2つのフィールドX, Yを持つstructである．
また，(1,0), (0,1), (1,1) を表すstaticプロパティ UnitX, UnitY, One を持つ．
以降の実装はこの構造体のAPIを参考にする．

ベンチマーク内容は以下の通り．
以降も同様にする．

using SN = System.Numerics;
//...中略
[Params(0, 1, 2, 12, 123, int.MaxValue)]
public int I { get; set; }
//...中略
[Benchmark]
public void Vector2() {
    var x = SN::Vector2.UnitX * I;
    var y = SN::Vector2.UnitY * I;
    var z = SN::Vector2.One * I;
    return x + y == z;
}
//...後略

なお，最適化により消されないよう比較結果を返している．
詳しくは 第②回#返り値による最適化の影響 で述べる．

UnityEngine.Vector2

参照：Unity - Scripting API: Vector2

Unityでのベクトル演算に用いられる構造体．
System.Numerics.Vector2 とはAPI名が違う．
．NET Framework用にビルドされているため互換保証外である．

ユーザー定義構造体

フィールド X, Y，メソッド Add, Multiple，演算子 +, * を定義したstructを定義する．

//...前略
internal struct MyStructVectorF2: IVectorF2<MyStructVectorF2>
{
    public MyStructVectorF2(float x, float y) {
        X = x;
        Y = y;
    }

    public float X { get; }

    public float Y { get; }

    public MyStructVectorF2 Add(MyStructVectorF2 other) => Add(this, other);

    public MyStructVectorF2 Multiple(float other) => Multiple(this, other);

    public static MyStructVectorF2 Add(MyStructVectorF2 left, MyStructVectorF2 right) =>
        new(left.X + right.X, left.Y + right.Y);

    public static MyStructVectorF2 Multiple(MyStructVectorF2 left, float right) =>
        new(left.X * right, left.Y * right);

    public bool Equals(MyStructVectorF2 other) =>
        X == other.X && Y == other.Y;

    //...中略

    public static MyStructVectorF2 operator +(MyStructVectorF2 left, MyStructVectorF2 right) => Add(left, right);

    public static MyStructVectorF2 operator *(MyStructVectorF2 left, float right) => Multiple(left, right);

    public static bool operator ==(MyStructVectorF2 left, MyStructVectorF2 right) => left.Equals(right);

    public static bool operator !=(MyStructVectorF2 left, MyStructVectorF2 right) => !left.Equals(right);

    public override bool Equals(object? obj) =>
        obj is not null && Equals((MyStructVectorF2)obj);

    public override int GetHashCode() => HashCode.Combine(X, Y);

    // Static Properties
    public static MyStructVectorF2 UnitX { get => new(1f, 0f); }

    public static MyStructVectorF2 UnitY { get => new(0f, 1f); }

    public static MyStructVectorF2 One { get => new(1f, 1f); }

}
//...後略

演算の他フォーマットや比較などを継承したinterface IVectorF2 を定義している．
詳細はソースコード参照．

ユーザー定義クラス

比較のため，上記と同様の内容をclassでも実装した．

タプル

参照：ValueTuple<T1,T2> Struct (System)

拡張method

タプル (float, float) にスカラー倍・加算の拡張methodを定義する．

//...前略
using VecF2 = ValueTuple<double, double>;
internal static class ValueTupleExtensions
{
    public static float X(this VecF2 @this) => @this.Item1;
    public static float Y(this VecF2 @this) => @this.Item2;

    public static VecF2 Add(this VecF2 left, VecF2 right) =>
        (left.X() + right.X(), left.Y() + right.Y());

    public static VecF2 Multiple(this VecF2 left, float right) =>
        (left.X() * right, left.Y() * right);
	
    public static VecF2 VecF2_UnitX() => (1f, 0f);

    public static VecF2 VecF2_UnitY() => (0f, 1f);

    public static VecF2 VecF2_One() => (1f, 1f);
    
    //...中略
}
//..後略.

これを用いて以下のようにベンチマークを行った．

//...前略
[Benchmark]
public void ValueTupleF2_Bench() {
    for(int i = 0; i < N; i++) {
        var x = ValueTupleExtensions.VecF2_UnitX().Multiple(i);
        var y = ValueTupleExtensions.VecF2_UnitY().Multiple(i);
        var z = ValueTupleExtensions.VecF2_One().Multiple(i);
        if(x.Add(y) != z)
            throw new Exception("assert error");
    }
}
//...後略

ラッパー構造体

拡張methodではstaticプロパティや演算子のオーバーロードは行えないため演算の記述が煩雑になってしまう．
これらを使うため，タプルをprivateフィールドに持つラッパー構造体を定義した．

//...前略
internal struct WrapValueTupleVectorF2: IVectorF2<WrapValueTupleVectorF2>
{
	(float X, float Y) _values { get; }

	public WrapValueTupleVectorF2(float x, float y) {
	    _values = (x, y);
	}

	public float X { get => _values.X; }

	public float Y { get => _values.Y; }
	//... 以降 MyStructVectorF2 と同様
}
//...後略

System.Tuple

参照：Tuple<T1,T2> Class (System)

C#7から導入されたタプル(System.ValueTuple)の他に，タプルを表すデータ構造として System.Tuple<T1, T2> が存在する．
これはクラスであるのでラッパーではなく直接継承できるので，新たに演算を定義した子クラスを定義した．

また，System.ValueTupleとの比較のため拡張methodによる定義も行った．

System.Vector< T >

参照：Vector< T > Struct (System.Numerics)

大規模な並列計算のために定義された，任意の数値型を型パラメータに取るSystem.Vector<T>が存在する．
これはCPUと対象の型に依存して固定の個数の数の組をまとめて処理するための構造体で，ハードウェアアクセラレーションの恩恵を受けられるよう最適化されている．
今回のようなシングルスレッドの演算には適さないが，比較のため実行した．

配列・List

参照：Array Class (System), List< T > Class (System.Collections.Generic)

単に2要素を扱うには過剰であると思われるが，一般次元への拡張を考慮し，実体として配列を用いるデータ構造も定義する．
Arrayは特殊クラスであるため継承できないので拡張methodとラッパー構造体を，Listは継承した子クラス・拡張methodを作成した．
内容はこれまでと同様のため省略する．
また，一度IEnumerableやParallelQueryに変換し，途中計算をLINQやPLINQのクエリによって行う拡張methodも作成した．

//...前略
public static ParallelQuery<float> Add_Parallel(
        this ParallelQuery<float> left, ParallelQuery<float> right) =>
    left.Zip(right, (l, r) => l + r);

public static ParallelQuery<float> Multiple_Parallel(
        this ParallelQuery<float> left, float right) =>
    left.Select(l => l * right);

public static bool Equals_Parallel(
        this ParallelQuery<float> left, ParallelQuery<float> right) =>
    left.Zip(right, (l, r) => (l, r)).All(lr => lr.Item1 == lr.Item2);
//...後略

結果

ベンチマークは掛ける数 k を 0, 1, 2, 12, 123, 2147483647 とした場合についてそれぞれ行った．
また，特にarrayなど生成コストが大きいものを考慮し，ベンチマーク外で (1,0), (0,1), (1,1) のインスタンスを予め生成した場合の速度も計測し，比較した．
処理速度の平均 Mean と99.9%信頼区間の半値幅 Error を以下の表に記す．

Method名 手法 Mean (ns) Error (ns) Mean(init) (ns) Error(init) (ns)
Vector2 System.Numerics.Vector2 0.93 0.01 0.92 0.01
UnityEngine UnityEngine.Vector2 0.28 0 1.63 0.01
MyStruct ユーザー定義struct 13.3 0.06 14.28 0.1
MyClass ユーザー定義class 27 0.13 18.62 0.16
ValueTuple_Extend タプル (拡張method) 0.44 0.01 1.46 0.01
ValueTuple_Wrap タプル (ラッパーstruct) 38.74 0.17 21.95 0.11
Tuple_Class System.Tuple (継承class) 28.21 0.6 18.53 0.15
Tuple_Extend System.Tuple (拡張method) 85.34 2.64 76.23 0.73
Tuple_Wrap System.Tuple (ラッパーstruct) 25.82 0.31 17.34 0.3
Array_Extend float[] (拡張method) 33.3 0.27 23.7 0.13
Array_Wrap float[] (ラッパーstruct) 31.02 0.76 21.06 0.65
List_Class List<float> (継承class) 113.54 0.85 67.94 0.53
List_Extend List<float> (拡張method) 147.8 2.5 96.13 1.09
List_ExtendEnumerate List<float> (IEnumerable) 305.8 1.78 未計測 未計測
List_ExtendParallel List<float> (ParallelQuery) 22152.08 120.02 21533.01 157.56
VectorT_Static Vector<float> 37.87 0.17 0.69 0.01

下図は初期化を行わない場合の平均処理時間について昇順にして対数プロットしたものである．

初期化を行わない場合，UnityEngine.Vector2 が最も速く，次いでタプルの拡張method，System.Numerics.Vector2 が続くという結果になった．

UnityEngine.Vector2 やタプルの拡張methodでは，初期化を行った場合逆に速度が低下した．
これには，変数として保持したことでコンパイラによる最適化が効かなくなった，ベンチマークソフトによるオーバーヘッドの補正が変わったなどの原因が考えられるが詳細は不明である．

Vector<T> は初期化の有無により大幅に速度が変化した．
Vector<float> の生成の際に毎回ランタイムに依存する長さの配列を生成しているため，時間がかかっていると思われる．これについては 第②回#Vector< T >の検証 にてさらに検証する．

ユーザー定義classとユーザー定義structの比較ではstructの方が速かった．
今回のタスクでは2倍ほどの差であるが，生成を連続して大量に行うタスクではさらに差が大きくなる．classとstructでは生成したインスタンスがヒープに置かれるかスタックに置かれるかという違いがある．今回のような大量にインスタンスを生成するタスクではstructが有利となり，予期された通りの結果である．

classとstructの違いがあるTupleとValueTupleとの比較でも最速の場合同士の比較では後者のほうが速い．
しかし，ValueTupleはラッパーstructを介すと大幅に速度が低下し，Tupleの速い場合よりも遅くなるということがわかった．原因は明らかではないが，それぞれユースケースに合わせた最適化がされており，それから外れる使い方は遅くなるのではないかと思われる．
いくつかのケースでのパフォーマンス比較を 第②回#ValueTupleの検証 にまとめる．

まとめ

今回計測したタスクではUnityEngine.Vector2・ValueTupleの拡張method・System.Numerics.Vector2・事前に初期化した場合のSystem.Numerics.Vector<float>が速いということがわかった．

structであるValueTupleとくらべclassであるTupleのほうが遅いことなど，予測通りとなった結果も多かったが，拡張メソッドを用いたときと継承やラッパーによりclassを作った場合で大きく結果が異なり，さらにValueTupleとTupleでその効果が逆になるなど，予想に反した結果も多かった．

さらに高次元や型の入り混じったベクトルの場合，タスクとして別の計算や連続して計算を続ける場合など調査すべきシチュエーションは多くあるので，今後検証を進めたい．

参考
BenchmarkDotNet の使用方法 【.NET/C#】BenchmarkDotNetを使って、メソッドのパフォーマンスを簡単に集計する - Qiita

Discussion