ネコのために鐘は鳴る

寺院に住み着くパソコ〇好き

(C#) 知らぬ間に起こるstructのboxingを回避する

c# programming
  • この記事の要点
    • 自分でobjectにキャストしなくてもboxingは起こるよ
    • structは等価比較を実装しないとパフォーマンスが落ちますよー

ボックス化 (boxing) とは

C# には値型と参照型があり、structは値型です。値型のオブジェクトは参照型のメンバ変数である場合を除き、スタックメモリに積まれます。参照型に比べ、ヒープメモリを汚さないことでGC (ガベージコレクション) に影響を及ぼさない、生成が速いという利点があります。

しかし、.NETのすべての型はobject(System.Object)から派生しており、structも例外ではありません。

従って、値型であるstructも参照型であるobjectにキャストすることが可能であり、この時スタックメモリにあるstructのインスタンスを、新たに確保したヒープメモリにコピーするという操作が走ります。これがboxingです。

boxingについては MSDN や ++C++ に詳しく書かれているのでそちらを参照。

で、structを使っても自分で明示的にobjectにキャストする、あるいはobject型の変数に代入するようなコードを書かなければboxingは発生しないのか、というと落とし穴があります。

等価比較です。

structの等価比較によるboxing

等価比較というのは単純に言うと==です。

とはいっても、==はそもそも演算子が定義されていないと使えないものなので、厳密にいうとobject.Equals(object)です。

もうお分かりかと思いますが、等価比較をするとobject型のメソッドを呼ぶことになるので、ここでstructがobjectにキャストされboxingが発生してしまいます。

等価比較が厄介なのは、あらゆるライブラリの中で普通に使われていることです。(逆に言うとあらゆる場面で必要になるからこそ初めからobject型に定義されていると言ってもいいです)

例えばList<T>です。

struct SampleData
{
    public int Num;
}

// ~~~~~~
var data = new SampleData();
var list = new List<SampleData>();
list.Add(data);

// リストに要素が含まれているかを確認する
bool contains = list.Contains(data);    // ここで等価比較が走る

例として、簡単にSampleDataというstructを定義しました。

このインスタンスをリストに追加し、その後リストに含まれているかどうかを確認しています。 この時リストに含まれているかどうかは、内部でリストの全要素と等価比較を行っているため、前述のとおりboxingが発生します。

等価比較によるboxingの回避

ではどうすればboxingを回避できるのかと言うと、等価比較時にobjectにキャストされるのが問題であるので、このstructに等価比較を実装すればよいです。

struct SampleData : IEquatable<SampleData>
{
    public int Num;

    // object.Equals(object) のオーバーライド
    public override bool Equals(object obj)
    {
        return obj is SampleData data && Equals(data);
    }

    // IEquatable<SampleData> の実装
    public bool Equals(SampleData data)
    {
        return Num.Equals(data.Num);
    }
}

まずobject.Equals(object)はvirtualで定義されているので、オーバーライドします。そして、IEquatable<T>を継承し、IEquatable<T>.Equals(T)を実装します。

これでSampleData同士の等価比較はobjectを経由しないため、boxingが発生しません。

後これはついでですが、お好みで==と!=演算子を定義しておきます。

struct SampleData : IEquatable<SampleData>
{
    public int Num;

    // object.Equals(object) のオーバーライド
    public override bool Equals(object obj)
    {
        return obj is SampleData data && Equals(data);
    }

    // IEquatable<SampleData> の実装
    public bool Equals(SampleData data)
    {
        return Num.Equals(data.Num);
    }

    public static bool operator ==(SampleData left, SampleData right)
    {
        return left.Equals(right);
    }

    public static bool operator !=(SampleData left, SampleData right)
    {
        return !(left == right);
    }
}

ハッシュ値取得のoverride

これでめでたくboxing回避できたわけですが、実はEquals()だけをoverrideすると色々と不整合が起こります。絶対にしてはいけません。

object.Equals(object)をoverrideした場合、必ずobject.GetHashCode()もoverrideする必要があります。オブジェクトのハッシュ値はDictionary<TKey, TValue>などで使われますが、

  • なるべく高速に
  • 同一オブジェクト(等価比較がtrueのもの)は同一のハッシュ値を返す
  • 異なるオブジェクト(等価比較がfalseのもの)はなるべく異なるハッシュ値を返す

が必要です。1つ目の条件は自明ですが、3つ目の条件についてはハッシュ値が衝突すると再ハッシュが起こるので当然無駄な処理が発生し、辞書型などのパフォーマンスが落ちます。

が、最悪2つ目の条件が守れていれば不整合は起きないので

public override int GetHashCode() => 1;

と書いていても不整合は起きません。(が、ハッシュ衝突でパフォーマンスが最悪になるのであくまで極端な例であって、絶対に書いてはダメです)

で、これらの条件を満たすハッシュ関数を自前で書くのはそこそこ難しいです。例のようにメンバが1つのみの場合はそのメンバ変数のハッシュ値を返せばいいのですが、C#でメンバ変数が1つしかないstructを書く意味も機会も特にないと思うため、現実的にはメンバが複数あり困ります。

これはどう実装すればよいのかと言うと、Visual Studio の機能で自動実装してしまうのが丸いです。

実は、ここまでの話は等価比較とハッシュ値取得を目的のstructに実装を追加する必要があるという話でしたが、ここまでの実装は全て Visual Studio のリファクタリング機能で一発で自動実装できます。

必要なメンバ変数だけを定義した最初の状態のstructで、型名にカーソルを置いてCtrl+.でクイックアクションを呼び出すと、「Equals および GetHashCode を生成する...」というメニューが出てくるので選択します。

出てきたポップアップウィンドウに「IEquatable を実装する」「演算子を生成する」のチェックボックスがでてくるためチェックをつけOKを押すと、ここまでの実装が全て自動で出てきます。

試しに、先ほどの例の構造体にもう一つメンバをつけ足した構造体で自動実装してみます。

    public struct SampleData : IEquatable<SampleData>
    {
        public int Num1;
        public int Num2;

        public override bool Equals(object obj)
        {
            return obj is SampleData data && Equals(data);
        }

        public bool Equals(SampleData other)
        {
            return Num1 == other.Num1 &&
                   Num2 == other.Num2;
        }

        public override int GetHashCode()
        {
            var hashCode = 8012265;
            hashCode = hashCode * -1521134295 + Num1.GetHashCode();
            hashCode = hashCode * -1521134295 + Num2.GetHashCode();
            return hashCode;
        }

        public static bool operator ==(SampleData left, SampleData right)
        {
            return left.Equals(right);
        }

        public static bool operator !=(SampleData left, SampleData right)
        {
            return !(left == right);
        }
    }

ここで自動実装されるGetHashCode()を見てみると、メンバ変数のハッシュ値を組み込んだ式でハッシュ値を生成していることが分かります。(環境は .NET Framework 4.8)

この実装が

  • なるべく高速
  • 同一オブジェクト(等価比較がtrueのもの)は同一のハッシュ値を返す

を満たすのは分かりますが、これがうまくハッシュの衝突を避けてくれるのかは正直分かりません。

が、何の根拠もなくVisual Studio および Microsoft が適当なハッシュ生成式を自動実装するわけがないので、たぶんよいハッシュを生んでくれるのでしょう。そこは信用します。(少なくとも、私自身は自前でハッシュ値生成するよりも Microsoft のプログラマを信用します)

上記の自動実装のアルゴリズムは .NET Framework 4.8 での自動実装なのですが、.NET Core 環境

[2020/04/03追記] .NET Standard 2.1 以上のAPIを持つ .NET 環境 では以下のように実装されるようです。また .NET Standard 2.0 以下の環境でも Microsoft.Bcl.HashCode パッケージを nuget から導入されているならば、自動で認識されて以下の実装が挿入されます。

public override int GetHashCode()
{
    return HashCode.Combine(Num1, Num2);
}

このようにアルゴリズム自体が隠蔽されています。この中がどうなっているのかは調べていません (.NET Core 自体はオープンソースなので気になる人はソースコードを見てください)

中身は xxhash で実装されています。ソースコードは以下。

source.dot.net

どちらにせよ、適切なハッシュ値のアルゴリズムをを自分で書くのはパフォーマンスの面からよろしくないので、自動実装に任せてしまいましょう。

で、ここまで実装してようやくboxingを回避する構造体を書いたことになります。

まとめ

  • 構造体の等価比較によるboxingを避けるためにはobject.Equals(object)のoverrideが必要
  • 等価比較のoverrideをするとobject.GetHashCode()のoverrideも必要
  • Visual Studio のリファクタリング機能でサクッと全部自動実装できる