ネコのために鐘は鳴る

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

(C#) ReadOnlyCollection<T> を Unsafe.As で違法に書き換える

System.Runtime.CompilerServices.Unsafe クラス

System.Runtime.CompilerServices.Unsafeクラスは C# において safe なコンテキストで unsafe なことができる、.NET の標準ライブラリにある公式黒魔術書です。Unsafeという名前から明らかですが、safe で使える (ポインタをかかない) にもかかわらず unsafe と同等かそれ以上に危険なことができます。

むしろUnsafeクラスが提供しているメソッドの内容は C# の表現力ではコードとして書き表せないものが大半です。

なのでUnsafeクラスのソースコードは直接 IL で書かれています。.NET Core 3.1 のUnsafeクラスのソースコードはこれです。

github.com

各メソッドでどんなことができるのかは MSDN を見るか、このページが分かりやすいです。

blog.meilcli.net

Unsafe.As メソッド

いろいろあるUnsafeクラスの中でもかなり危険だと (個人的に) 思うのが、T Unsafe.As<T>(object) where T : classメソッドで、継承関係に関わらず強制的に型変換できるというものです。

// ClassA と ClassB は互いに継承関係にない class 

ClassA a = new ClassA();          // ClassA のインスタンス
ClassB b = Unsafe.As<ClassB>(a);  // 強制型変換 (本来はキャスト不可)

これが何の例外も出ずに実行できてしまいます。一体何が起こっているのかさっぱり分からないのでUnsafeクラスのソースコードを覗いてみましょう。ソースコードは前述の通り IL です。

.method public hidebysig static !!T As<class T>(object o) cil managed aggressiveinlining
{
    .custom instance void System.Runtime.Versioning.NonVersionableAttribute::.ctor() = ( 01 00 00 00 )
    .maxstack 1
    ldarg.0
    ret
} // end of method Unsafe::As

スマートすぎる、天才か?

  • 1行目 : .custom instance ...はおまじないです。(このメソッドの属性の宣言)
  • 2行目 : 使用するスタックの数の宣言 (スタック数 1)
  • 3行目 : 引数をスタックの0番目にロード
  • 4行目 : スタックの先頭を return

仰々しく書いたがやっていることは完全に素通しです。IL にとっては引数のobject oが何の型だろうが知ったことではなく、所詮はただの参照、それをT型として返すだけ。

こんな単純なことなのに C# の表現力ではこれは書けません。如何に C#コンパイラによって安全に守られているか分かります。

 

しかし、これは IL が素通しで型を変えただけであるため、それが C# の型としてメモリ上で有効な状態になっている保証は一切ありません。レイアウトが異なる型を変換すると、意図したプロパティとは違うプロパティが呼ばれてしまう、アクセスできないメモリを参照しようとしてクラッシュして落ちる、等おかしな挙動が起きます。

つまり、型情報や仮装関数テーブルを経由するメソッド呼び出しは、本来ありえない型のテーブルを引くため未定義動作になります。(たいていはAccessViolationException等を吐いて落ちますが、たまたま有効な別メソッドを引くこともできるので動きは未定義)

継承関係にないがメモリレイアウトが同じ型のキャストを無理やり実行したい、というのが使い道です。 勘違いしそうですが、このメソッドは実行時のインスタンスの動的型を変える魔法ではなく、静的型をすり替えてコンパイラの型チェックをごまかすだけです。  

ちなみにUnsafe.Asメソッドにはもう一つオーバーロードがあって、Unsafe.As<TFrom, TTo>(ref TFrom)です。先ほどのはclass用なので、構造体を見かけ上、別の構造体として扱いたいときはこちらです。

ロジックは先ほどと同じで、あくまで参照を素通しして見かけの型を変えるものであるため、入力・出力ともにrefです。`構造体を値のコピーではなくダイレクトに別のものとして叩き込みたい、のようなアグレッシブな場面で使えます。

ReadOnlyCollection<T> の中身を書き替え

Unsafe.As<T>(object)の悪用(?)法として、System.Collections.ObjectModel.ReadOnlyCollection<T>の中身を書き替えてみたい、というのが今回の本題。

.NET Core のReadOnlyCollection<T>のソースは[これです]。(https://source.dot.net/#System.Private.CoreLib/ReadOnlyCollection.cs)

メソッドとプロパティがいっぱいありますが、メモリ上でのレイアウトに関係ないものを取っ払うと、以下のようになってます。

public class ReadOnlyCollection<T>
{
    private IList<T> list;
}

本当にただIList<T>を read only にラップしただけなのがよくわかります。要はこのprivateな変数を引っこ抜いてこれば書き換えができます。普通ならリフレクションでprivateフィールドを取ってくるんですが、今回の趣旨はUnsafeクラスを使ってやります。

Unsafe.As<T>(object)を使って、ReadOnlyCollection<T>を同じメモリレイアウトで中身がpublicな別の型にすり替えます。

// ReadOnlyCollection<T> と同じメモリレイアウトを持つクラス
public class IllegalExposure<T>
{
    public IList<T> Content;
}

これを使って型をすり替えます

// もとになる ReadOnlyCollection
ReadOnlyCollection<int> collection = ###;

// 強制キャストで型をすり替える
var illegal = Unsafe.As<IllegalExposure<int>>(collection);
// 中身が public になったので抜き出す
var content = illegal.Content;

content[0] = 1234;  // 中身を書き替える

抜き出した中身を書きかえると、元のReadOnlyCollection<T>の中身も当然書き換わります。

これ自体はリフレクションでも全く同じことができるのですが、速度が桁違いです。リフレクション経由でのprivateフィールドの取得などは余裕で2, 3桁実行速度が遅くなるのに対し、この強制キャストの中身は先ほど見た通り参照素通しなので爆速です。比になりません。

 

Unsafeクラス、フォースの暗黒面は素晴らしい

(C#) 配列の for の JIT 最適化処理

[前提] C#コンパイルJIT コンパイル

C# --> [コンパイル] --> IL -> [JIT] --> バイナリ の流れを知ってる人は読み飛ばしてください

 

forの最適化の話をする前に、C#ソースコードが実行可能バイナリ (アセンブリ) にコンパイルされるまでの流れをおさえておきます。

C#Java等と同じで中間言語コンパイルされます。JavaJava 仮想マシン (JVM; Java Virtual Machine) 上で動く Java バイトコードコンパイルされるように、C# .NET 上で動く MSIL (通称 IL; Microsoft Intermediate Language) にコンパイルされます。その後、実行時に実行プラットフォーム (OSとかCPUのアーキテクチャ) に合わせた実行可能バイナリに再度コンパイルされることで実行されます。

この IL からアセンブリへのコンパイルのことを JIT コンパイル (Just in Time Compile) と呼びます。

f:id:ikorin2:20200113014417p:plain

C# で作られたソフトウェア (Windows の場合 exe ファイル) はこの IL の状態であるため、プラットフォームによらず同一のプログラムファイルで実行できます。つまりC#製の exe の場合、Windows で動かしている exe ファイルをそのまま Mac にコピーすれば動きます。(まあモノに依りますが。monoだけに)

で、なぜかと言うと IL は .NET という仮想マシン向けの命令だからです。プラットフォーム間の差異は .NET が吸収してくれるので IL はプラットフォーム非依存になります。(JavaバイトコードJVM という仮想マシン上で動くのと全く同じです。と言うか C#Java の真似して作られた)

 

わざわざ JIT コンパイルという二度手間を踏んでまで中間言語コンパイルする意味は、いろいろメリットがあるからなんですが、ここではその話は省略します。

あと余談ですが、Unity の iOS 向けビルド(など)で行われる IL2CPP は 事前コンパイル (AOT: Ahead of Time compile) の一種で、本来実行時に JIT コンパイルされる IL を、あらかじめアセンブリまでコンパイルしてしまうものです。メリット・デメリット双方あります。

for の配列アクセスの最適化

本題です。

以下に簡単なサンプルコードを書きました。2種類のやり方でint配列の合計をforで回して計算しているだけのメソッドです。

public class C
{
    public int L = 10000000;

    public int M1()
    {
        var array = new int[L];
        int sum = 0;
        for(int i = 0; i < array.Length; i++)
        {
            sum += array[i];
        }
        return sum;
    }

    public int M2()
    {
        var array = new int[L];
        int sum = 0;
        for(int i = 0; i < L; i++)
        {
            sum += array[i];
        }
        return sum;
    }
}

配列の要素は全て0なのでどっちも答えは0ですが、計算に特に意味はありません。2つのメソッドの違いはforの終了条件に配列のLengthプロパティを使うか否かだけです。

結果から言うと、M1()メソッドの方が実行速度が速いです。JIT コンパイル時に最適化がかかるからです。

実際に逆アセンブルしてアセンブリを見てみましょう。(C#コンパイルは Release ビルド、アセンブリAMD64)。逆アセンブルツールはいろいろありますが、パッと簡単なコードの結果を見たいだけの時は sharplab がすごく簡単です。ソースをコピペして2秒で見れます。今回もこれを使いました。

; Core CLR v4.700.19.51502 (coreclr.dll) on amd64.

C..ctor()
    L0000: mov dword [rcx+0x8], 0x989680; L = 10000000
    L0007: ret                          ; return

C.M1()
    L0000: sub rsp, 0x28                ;
    L0004: mov edx, [rcx+0x8]           ;
    L0007: movsxd rdx, edx              ;
    L000a: mov rcx, 0x7ffec35ef000      ;
    L0014: call 0x7fff230847e0          ; array = new int[L]
    L0019: xor edx, edx                 ; sum = 0
    L001b: xor ecx, ecx                 ; i = 0
    L001d: mov r8d, [rax+0x8]           ;
    L0021: test r8d, r8d                ; if (i >= L)
    L0024: jle L0035                    ;     goto -------┐
    L0026: movsxd r9, ecx               ;            <----|--┐
    L0029: add edx, [rax+r9*4+0x10]     ; sum += array[i] |  |
    L002e: inc ecx                      ; i += 1          |  |
    L0030: cmp r8d, ecx                 ; if (i < L)      |  |
    L0033: jg L0026                     ;     goto -------|--┘
    L0035: mov eax, edx                 ;            <----┘
    L0037: add rsp, 0x28                ;
    L003b: ret                          ; return sum

C.M2()
    L0000: push rsi                     ;
    L0001: sub rsp, 0x20                ;
    L0005: mov esi, [rcx+0x8]           ;
    L0008: movsxd rdx, esi              ;
    L000b: mov rcx, 0x7ffec35ef000      ;
    L0015: call 0x7fff230847e0          ; array = new int[L]
    L001a: xor edx, edx                 ; sum = 0
    L001c: xor ecx, ecx                 ; i = 0
    L001e: test esi, esi                ; if (i >= L)
    L0020: jle L0039                    ;     goto ---------------┐
    L0022: mov r8d, [rax+0x8]           ;                         |
    L0026: cmp ecx, r8d                 ; if (i < 0 or i >= L) <--|--┐
    L0029: jae L0041                    ;     goto ----------┐    |  |
    L002b: movsxd r9, ecx               ;                    |    |  |
    L002e: add edx, [rax+r9*4+0x10]     ; sum += array[i]    |    |  |
    L0033: inc ecx                      ; i += 1             |    |  |
    L0035: cmp ecx, esi                 ; if (i < L)         |    |  |
    L0037: jl L0026                     ;     goto ----------|----|--┘
    L0039: mov eax, edx                 ;             <------|----┘
    L003b: add rsp, 0x20                ;                    |
    L003f: pop rsi                      ;                    |
    L0040: ret                          ; return sum         |
    L0041: call 0x7fff231aef00          ; throw Exception <--┘
    L0046: int3                         ;

アセンブリを眺めてスラスラ読める宇宙人の方はいいですが、人間には厳しいので、隣に高級言語的に意味ある部分に疑似コードを書き足しておきました。あくまで左はアセンブリなので高級言語の命令と1対1には対応しません、だいたいです。

 

処理の流れは右の疑似コードを見てもらえば、きちんと元のC#のソースと同じことをしているのが理解できます (当たり前だけど)。2つのメソッドの違いは、M2()メソッドの L0026, L0029 の部分の有無です。

これは配列の境界チェックです。C#では配列外のインデックスにアクセスすると、必ずIndexOutOfRangeExceptionの例外が発生します。

var array = new int[10];
array[15] = 4;        // ← throw new IndexOutOfRangeException()

C++とかだとこの辺の境界外アクセスは未定義なので色々と危険なことが起こります (起こせます) が、C#はメモリの安全性が言語として担保されてます。ここで、例外が発生するということは内部的にはインデックスが0以上かつ配列長未満であるかをチェックしているということで、これがM2()メソッドの L0026, L0029の部分です。

安全性が担保されているのはいいことですが、これは実行速度とトレードオフで、このチェックはループ毎にインデックスアクセスで行われるため、オーバーヘッドが発生します。

ではなぜM1()メソッドの方はこのチェックがないのかと言うと、M1()forの条件は初期値がi=0で終了条件がi < array.Length、更新条件がi++なため、原理的に配列の境界外にアクセスが発生せず、JIT コンパイラがそれを認識して高速化のために境界値チェックを削除したためです。

ならばM2()メソッドの方も境界外アクセスが発生しないのは自明な気がしますが、この最適化が行われるのは終了条件にarray.Lengthプロパティを使った時のみ行われます。Lがpublicだから、あるいはクラスフィールドだから途中で非同期から変更される可能性があるためチェックを排除できない、というのもありますが、これに関してはメソッド内のローカル変数にLを置いてもチェックは消えません。あくまでarray.Lengthの時のみ高速化されます。

一応補足しておきますが、この最適化が行われるのは JIT コンパイル時です。JIT コンパイラがもう少し頑張って処理の流れを追って解析すればarray.Lengthプロパティ以外でも必ず安全性が保たれる場合なら最適化できそうな気もします。が、JIT コンパイルは実行時に行われるため、処理の解析と最適化に時間をかけることができないという理由もあって、たぶん行われていません。IL の状態では、上記2つのインデックスアクセスの部分は全く同じ IL 命令にコンパイルされています。

ベンチマーク

最後に上記の2つのメソッドが本当に速度差があるのかベンチマークを取っておきましょう。測定はいつも通り Benchmark.NET を使います。github から取ってこなくても Nuget からパッケージを取ってこられます。

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18362
Intel Core i5-4300U CPU 1.90GHz (Haswell), 1 CPU, 4 logical and 2 physical cores
.NET Core SDK=3.0.100
  [Host]     : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), X64 RyuJIT
  DefaultJob : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), X64 RyuJIT
Method Mean Error StdDev Ratio RatioSD
M1 34.59 ms 0.805 ms 2.374 ms 1.00 0.00
M2 35.14 ms 1.013 ms 2.971 ms 1.02 0.09

……誤差の範囲では……?思ったよりも差が出なかったです。最後の最後で話の腰を折られてしまった気がする。

が、事実としてLengthプロパティをforの終了条件として使うか否かだけでJITコンパイルの最適化結果のアセンブリが異なりますよ、という記事でした。

[追記] この話は2020/01月現在、 .NET Core 3.0 (およびそれ以前の .NET のバージョン) での JIT の話です。将来的にはJITがもっと賢くなって変わる可能性もあります。可能性は低いと思いますが。

(C#) string で発生するガベージを抑える (String Interning)

C# においてstringは参照型で、そのインスタンスはヒープメモリに生成されます。 当然、参照されなくなったstringは次回のガベージコレクションで回収されます。

少しでもガベージは減らしたいものですが、文字列は生成するたびに同じ内容でも別インスタンスを生成してしまい無駄になります。

一度生成した同一の内容のstringを有効活用する方法として String Interning という方法が .NET では用意されています。

String Interning

String Interning は、インターンプールという場所に生成した文字列を格納しておくことで、それ以降同じ内容の文字列を生成する時、インターンプール内に登録されていれば、登録されている文字列を取得することで新たなインスタンスの生成をしない、というものです。 String Interning という仕組み自体は、C# 固有のものではなくJava, Python, PHP などメジャーな言語でも同様にサポートされています。

String Interning - Wikipedia

インターンプールは内部的には文字列のハッシュテーブルになっており、.NETが管理しています。文字列の登録のみが可能で、削除等インターンプール内部を直接触ることはできません。登録された文字列はランタイムの終了時までインターンプールに保持され続けるためガベージコレクションの対象にもなりません。

(これは裏を返すと、巨大な文字列を登録すると終了時まで解放されずメモリを占有し続けるということです)

頻繁に登場する比較的小さな文字列が大量に生成され、ガベージコレクションに捨てられるのを防ぐというのがよい使い方と思います。

C# で文字列をインターンプールに登録するには

string a;

/* ここで a に何らかの文字列が代入される */

// a をインターンプールに登録し登録した文字列を取得
// a が登録済み (つまり a が既にプール内文字列)の場合は何も起こらない
a = string.Intern(a);

// これ以降 a と同じ文字列を生成しようとした場合、インスタンスの新規生成はされない

で登録できます。

リテラル文字列における String Interning

ソースコード中にハードコーディングされているリテラル文字列はランタイムから特殊扱いされ、初めからインターンプールに登録済みの文字列として .NET に保持されます。

// a と b のアドレスは同一(インターンプール内の同一インスタンスを指す)
string a = "hoge";
string b = "hoge";

上記の二つのstringインスタンスはともにリテラルですが、この場合初めからインターンプールに登録済みの文字列となり、同一のインスタンスを指しています。unsafe で二つのアドレスを見ると、同一であることが確認できます。

で、気になるのが最初からインターンプールに登録済みとなる条件は何かということです。

私、気になります。

nameof$文字で文字列を挿入された文字列 (string interpolation) などはどうなるのでしょうか?

結果は以下の通り。

「文字列」がソースコード中の記述、「出力」が実際に生成される文字列、「Interned」は「出力」の文字列が最初からインターンプルに登録済みの文字列として生成されるか、を表しています。

文字列 出力 Interned 備考
"hoge" "hoge"
"hoge" + "piyo" "hogepiyo" ×
nameof(Piyo) "Piyo"
$"hoge{"piyo"}" "hogepiyo"
$"hoge{nameof(Piyo)}" "hogePiyo"
4.ToString() "4" ×
"hoge" + 4.ToString() "hoge4" ×
$"hoge{4.ToString()}" "hoge4" ×
$"hoge{a}" "hogepiyo" × var a = "piyo"; // (a は Interned)
$"hoge{$"pi{"foo"}yo"}" "hogepifooyo"
$"hoge{$"pi{4.ToString()}yo"}" "hogepi4yo" ×

(その他)

// a はプール内文字列
var a = "1234";

// ここで新たに "1234" が確保される
var b = 1234.ToString();

// c は a と同一インスタンス
var c = string.Intern(b);

// a と b は別アドレス
var refEqualsAB = object.ReferenceEquals(a, b);
Console.WriteLine(refEqualsAB);    // False

// a と c は同じアドレス
var refEqualsAC = object.ReferenceEquals(a, c);
Console.WriteLine(refEqualsAC);    // True

結論

  • リテラルは最初から Interned な文字列 (プール内インスタンス) である
  • nameofリテラル扱いを受ける (値の解決はコンパイル時に行われる。IL上ではリテラルに置き換わっている)
  • $文字列も中身にリテラル (nameofを含む) しか入っていない場合はInterned。$文字列が複合的に存在しても再帰的に条件に当てはまっていればInternedになる。
  • $文字列内に非リテラルが存在すると Interned にはならない。中の非リテラルが Internedかどうかは無関係

余談

インターンプール内の文字列を参照している場合、同一のインスタンスを参照しているため unsafe で書き換えると悪さができてしまいます。ダメ絶対

// a と b は同一インスタンス
var a = "hoge";
var b = "hoge";

unsafe
{
    fixed(char* ptr = a)
    {
        ptr[0] = 'A';
    }
}

Console.WriteLine(a);    // "Aoge"
// a と同一インスタンスなので b も変わる
Console.WriteLine(b);    // "Aoge"

参考文献

C# における String Interning の日本語記事が以下のページぐらいしかヒットしなくて、んーーっと思ったので本記事を書きました。

まあ過度にメモリを気にするゲーム用途とかシビアな状況でしか必要にならないし、仕方ないかなとも思いますけどね。(下のページも Unity の省メモリ化についての解説ですし)

engineering.grani.jp

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

  • この記事の要点
    • 自分で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型のメソッドを呼ぶことになるので、ここでstructobjectにキャストされ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リファクタリング機能でサクッと全部自動実装できる

(C#) 同期コンテキストと Task, async/await その2

この記事は前回の記事の続き、および補足です。

前回記事 (C#) 同期コンテキストと Task, async/await - ネコのために鐘は鳴る

UI スレッドへの復帰コスト

前回の記事で上げた GUI ループでのキューの監視は、ループごとにキューにコールバックがPostされていないか確認しています。

しかし、GUIのループは基本的に描画速度に依存し、60FPSを前提とする環境では1ループ最短で 16ms かかります。つまり、キューを確認した直後に非同期からコールバックをPostされた場合、UI スレッドがきちんと回っている場合でも、コールバックを拾うまでに最長 16ms 遅れます。

これは、わざわざコールバックで UI スレッド復帰する必要がない場合、不要なコストです。

UI スレッド復帰しないawait

Taskawaitのコールバックを UI スレッドに戻す必要がない場合、Task.ConfigureAwaitメソッドを使うことで、UI スレッドに復帰せずにそのままコールバックを実行できます。

// ここは UI スレッド
Debug.WriteLine("Start");
var task = await Task.Run(() => 
{
    // ここはワーカースレッド
    Debug.WriteLine("Worker Thread");
}).ConfigureAwait(false);    // スレッド復帰しない
// ここは同じワーカースレッド
Debug.WriteLine("Callback");

TaskのデフォルトではConfigureAwaittrueに設定されており、この場合、同期コンテキストによる通知はSynchronizationContext.Postメソッドによって行われます。(前回記事参照)

Task.ConfigureAwait(false)にした場合、通知はSynchronizationContext.Sendによって行われ、同期的に実行されます。混乱しそうですが、ワーカースレッドから見て同期的ということは、コールバックは同じワーカースレッドで実行されるということです。

つまり、Task中の処理の続きで連続して行われるため、UI スレッド復帰によるコストは発生しません。

ありがちな罠

// ここは UI スレッド
var task1 = await Task.Run(() => 
{
    // ここはワーカースレッド1
}).ConfigureAwait(false);

// ここはワーカースレッド1
var task2 = await Task.Run(() => 
{
    // ここはワーカースレッド2
}).ConfigureAwait(true);

// ***注意***
// ここはワーカースレッド2

上記のコードの場合、一番下の部分はConfigureAwait(true)の後なので UI スレッドのように見えますが、UI スレッドではありません

ならば、task2を呼び出したのはワーカースレッド1なのだから、ここはスレッド復帰してワーカースレッド1なのかというと、それも違います。正解はワーカースレッド2です。

そもそも 非 UI スレッドの同期コンテキストはスレッド復帰を行わない (前回記事参照) ので最後の部分はワーカースレッド2で実行されます。

 

最後の部分で UI スレッドに復帰したい場合はTask.ContinueWithメソッドを使います。

// ここは UI スレッド
var task = await Task.Run(() => 
{
    // ここはワーカースレッド1
}).ContinueWith(() => 
{
    // ここはワーカースレッド1
}).ConfigureAwait(true);

// ここは UI スレッド

説明のためConfigureAwait(true)をつけていますが、もともとtrueなのでなくても動作は同じです。

ライブラリ作成時の注意点

Taskを内部で使って非同期処理を行うようなライブラリを作る場合、awaitを使う場合原則としてConfigureAwait(false)を必ず付ける必要があります。

つけ忘れると、意図しない部分でスレッドが UI スレッドに復帰してしまう上、コンパイルされたライブラリ dll の利用者から見ると、そのライブラリが中でawaitをつかったスレッド復帰をしているかどうかを確認する術がありません。

なので、基本的にライブラリとして他者に使ってもらう前提のコード中のTaskにはConfigureAwait(false)を必ず付ける必要があります。


前回記事 ikorin2.hatenablog.jp

(C#) 同期コンテキストと Task, async/await

.NET framework 4 で追加されたTaskおよび .NET framework 4.5 で追加されたasync, awaitキーワードによって、C# の非同期処理は非常にに簡単になりました。

Windows Form, WPF, UWP, Unity など各種フレームワーク上の場合、非同期処理はスレッドやコールバック処理など面倒なことはほぼ完璧に隠蔽され、難しいことを意識することなく直感的に記述できるようになりました。

 

しかし、例えば上記のような既存のフレームワークを使わず、独自の GUI フレームワークを作りたいような場合、同期コンテキストについて知っておく必要があります。

(GUIフレームワークを自分で作る人がいるのかという疑問はひとまず置いておいて……)

なお、ここでいうフレームワークとは、開発者がその上でアプリケーションを作成することを目的としているような、基盤となるようなライブラリ群のことを指しています。

GUI とスレッド

C# に限らず、GUI のアプリケーションは基本的に UI の操作はシングルスレッドから行うことを前提とし、UI スレッドは特別視されます。理由は、スレッドセーフにGUI フレームワークを作ることは実装面のコストが大きく、実行速度面から見ても不利であるためです。それなら初めから GUI はシングルスレッド前提の設計をしてしまおう、というのが定石です。

しかし、UI スレッドで時間のかかる処理を実行することは、UI のフリーズを意味します。そこで、重い処理は非同期に実行し、実行結果を UI スレッドにコールバックするのが普通です。

void SyncMethod()
{
    // 同期的に計算処理を行う
    int result = HeavyCalculation();
    Debug.WriteLine(result);
}

async Task AsyncMethod()
{
    // 非同期に計算処理を行う
    // ここは UI スレッド
    // 別スレッドに重い処理を実行させる
    int result = await Task.Factory.StartNew(HeavyCalculation);
    // ここは UI スレッドに戻ってきている
    Debug.WriteLine(result);
}

int HeavyCalculation()
{
    int result = 0;

    // ここで重い計算処理をおこなう

    return result;
}

上のSyncMethod()AsyncMethod()はともに同じresultを得ますが、SyncMethod()は同期的に実行されるため、例えば計算処理に10秒かかる場合、10秒間 UI がフリーズします。

一方、AsyncMethod()は計算処理部分を別スレッドに投げ、結果が出た時に再び UI スレッドに処理が戻ってくるため、計算中に UI がフリーズしません。

 

実際に別スレッドで実行され、実行後にUIスレッドに戻ってきているのか確認してみましょう

static async Task CheckThreadID()
{
    // ここは UI スレッド
    var uiThread = Thread.CurrentThread.ManagedThreadId;
    Debug.WriteLine($"UI Thread : {uiThread}");        // 1
    // 別スレッドに重い処理を実行させる
    await Task.Factory.StartNew(AnotherThread);
    // ここは UI スレッドに戻ってきている
    var callbackThread = Thread.CurrentThread.ManagedThreadId;
    Debug.WriteLine($"Callback Thread : {callbackThread}");        // 1
}

static void AnotherThread()
{
    var anotherThread = Thread.CurrentThread.ManagedThreadId;
    Debug.WriteLine($"Another Thread : {anotherThread}");        // 2
}

このCheckThreadID()実行すると、

UI Thread : 1
Another Thread : 2
Callback Thread : 1

のように出力されます。(スレッド ID の数字は実行環境によって変わります)

非同期処理を呼び出した後、呼び出し元のスレッドに処理が戻ってきていることが確認できます。

コンソールアプリケーションの場合

では、GUI フレームワークを使わない環境、つまりコンソールアプリケーションの場合どうなるのでしょうか。

 

なお、コンソールアプリケーションでTaskを使う場合、非同期処理が終了する前にMainメソッドを抜けてしまうとアプリケーションが終了してしまうため、以下のように書きます。

class Program
{
    static void Main(string[] args) => MainAsync(args).Wait();

    static async Task MainAsync(string[] args)
    {
        // ここに普通にMain関数の中身を書く
        await CheckThreadID();    // スレッドIDを確認する
    }
}

ここに先ほどの非同期スレッドのスレッド ID を確認するプログラムを書いてみた場合、結果は以下のようになります。

UI Thread : 1
Another Thread : 2
Callback Thread : 2

(スレッド ID の数字は実行環境によって変わります)

UI スレッド (この場合Main関数が走っているメインスレッド) の ID が 1なのに対し、非同期処理から戻ってきたときのスレッドは、元のスレッドとは別のスレッドになっています。

これはどうしてなのでしょうか。

同期コンテキスト (SynchronizationContext)

System.Threading名前空間SynchronizationContextというクラスがあります。これが同期コンテキストです。

実はTaskが非同期処理からどのスレッドに帰ってくるかはこの同期コンテキストが関係しています。

 

System.ComponentModel名前空間AsyncOperationManagerというstaticクラスがあり、これがSynchronizationContextというstaticプロパティを持っています。

このプロパティは、このプロパティを呼び出したスレッドに紐づいている同期コンテキストを取得することができます。

この同期コンテキストというのは各スレッドごとに1つあり、nullまたはSynchronizationContextクラスのインスタンスです。

(以降、スレッドに紐づいている同期コンテキストがnullまたはSynchronizationContextインスタンスの状態のことを、デフォルトの同期コンテキストと呼ぶことにします)

 

デフォルトの同期コンテキストは、実質何も処理をしないため、Taskによる非同期処理のコールバックは元のスレッドに戻ってくることはありません。

では Windows Form や WPF などのフレームワークではどうして元のスレッドに戻ってくるのでしょうか。

GUI フレームワークの同期コンテキスト

Win Form の場合の同期コンテキストを見てみましょう。

Win Form の場合、System.Windows.Forms名前空間WindowsFormsSynchronizationContextというクラスが定義されており、このクラスはSynchronizationContextを継承しています。

Win Form の UI スレッドは、デフォルトの同期コンテキストではなくこのWindowsFormsSynchronizationContextインスタンスを同期コンテキストとして持っています。

この Win Form 用の同期コンテキストによって、UI スレッドからTaskで非同期処理を実行した場合、コールバックがUIスレッドに戻ってきます。

GUI のループと同期コンテキスト

GUI アプリケーションは大きく見れば常にループすることによって成り立っています。例えばゲームなどの場合、1フレームが1回のループと考えていいでしょう。

GUIフレームワークを使ってアプリケーションを作る場合、多くの場合このループ部分がフレームワークとして隠蔽されているため特にループについて意識することはありませんが、同期コンテキストはこの部分で処理されています。

以下に簡単なループの図を示します。

f:id:ikorin2:20191220185655p:plain

図のユーザー処理の部分でTaskによる非同期処理が実行されたとします。

図の黄色の部分は UI スレッドで実行され、青色の部分が別スレッドで非同期に開始されます。

UI スレッドはawaitの時点でこのメソッドを打ち切って抜け、あとは通常通りに実行が続きます。(GUIのループがUIスレッドで回り続けます)

一方、ワーカースレッドは処理が終わった時点で、元スレッド (UI スレッド) の同期コンテキストにコールバック処理 (await後のこのメソッドの未実行の処理、つまり赤色の部分) をPostし、キューにコールバックが登録されます。

その後、ループ中でキューを見張っている UI スレッドによって、コールバックが実行され、まるでTaskawait した続きの部分から UI スレッド再開されたように実行されます。


小ネタ

図の右側は、ボタンをクリックした時に非同期処理が走るようなコードですが、awaitによる中断は、その部分でメソッドを打ち切って残りをコールバックとしているだけなので、UI スレッドはそのまま GUI ループに戻っていきます。つまり、非同期処理 (青の部分) がまだ終わっていない状態で、次回以降のループでもう一度ボタンがクリックされた場合、また別の非同期処理を走らせてしまうことになります。(いわゆる再入)

再入を防ぎたい場合は、図のようにisRunningのようなフラグを用意しておくことで再入を防げます。


  このループは GUI フレームワークによって実装されるため、Postされたコールバック処理をためておくキューは当然フレームワークによって異なります。そのため、各 GUI フレームワークごとに専用の同期コンテキストを実装する必要があります。

とはいえ、基本的にはコールバック処理をポストする場所が異なるだけです。

SynchronizationContext.Postメソッドはvirtualで定義されており、overrideすることで専用の実装をすることができます。

これによって、Win Form には Win Form 用の同期コンテキスト、WPF には WPF 用の同期コンテキストクラスが定義されています。

例えば Win Form の同期コンテキストWindowsFormsSynchronizationContextの実装はこれです。

referencesource.microsoft.com

 

つまり、自分でこの GUI ループ処理を書いて、Taskのコールバックが UI スレッドになるような同期コンテキストクラスを定義すれば、WPF などと同じようにTaskが使えるようになります。

もちろん、ループが開始する前に UI スレッドに対してこの同期コンテキストを紐づけておく必要があります。

// 現在のスレッドの同期コンテキストとして、自作の同期コンテキストを設定
AsyncOperationManager.SetSynchronizationContext(new MySynchronizationContext());
while(true)
{
    // GUI スレッドのループ
}

その他

前述したように、各種 GUI フレームワークの UI スレッドの同期コンテキストは、そのフレームワーク専用の同期コンテキストとなっていますが、非 UI スレッドの同期コンテキストはデフォルトの同期コンテキストです。

そのため、await後に元のスレッドに戻ってくるのは UI スレッド上の awaitのみです。

ワーカースレッド上でのawait後のコールバックは、元と同じワーカスレッドには戻ってきません。(しかし、UI スレッド以外で元と同じスレッドでないと困るようなことは基本的にないため、問題にはなりませんが)

<追記>

この続きの記事書きました

ikorin2.hatenablog.jp

参考文献

.NET クラスライブラリ探訪-040 (System.Windows.Forms.WindowsFormsSynchronizationContext)(SynchronizationContext, 同期コンテキスト, Send, Post) - いろいろ備忘録日記

async/await と SynchronizationContext (1) - 鷲ノ巣

大学院受験の感想

ただの日記です。

この日記執筆時点では大学院受かりました、とはまだ断言できないのですがまあ受かりました

 

積極的に人に言わないだけで別に隠していることでもないですが、去年も同じところの大学院を受けました。なんとまぁ去年も大学院に受かりました。2年連続同じ大学院に受かるという経験をした人はおそらく稀有でしょう。

同じ大学院の同じ研究科に2年連続受かるとはどういうこと??と疑問符が浮かぶ方は3秒ほど考えてください。世の中不思議ですね (不思議ではない)

 

以下感想

 

基礎科目

線形代数フーリエ変換複素解析ラプラス変換・統計確率・電磁気学(2題)・電気回路(2題)の中から好きな5問を選んで解きます。線形・複素・ラプラス・回路2問の5問を解きました。

固有値/固有ベクトル、対角化、ジョルダン標準形などの基本をきちんと押さえて、問題の流れに沿って解答していけば6割以上は安定しました。問題自体はそれらを基本に据えたやや応用的な問題が主ですが、問題自体の核となる知識は大体これです。

 

留数・留数定理・曲線/閉曲線上での積分、コーシーリーマンなどの基本的な問題です。しかし、私自身が複素関数論にそれほど勉強時間を費やさなかったので包括的に内容を説明できるほど分かってないままだったという印象。

 

後述する電気回路でどうせ使うため選択した。最低限の計算とラプラス変換対などは覚えたが、これもそこまで得点源とできるほど勉強をしなかったため、深い理解は得ていない。あくまで回路解析のためのツールとして覚えたついでという側面が強い。

 

  • 電気回路1, 2

電気回路1は一般的なRLCを含む交流回路の過渡解析と定常解析。過渡解析・定常解析・複素インピーダンスノートン等価回路・テブナン等価回路・ゲインと位相のボード線図・複素電力・ラプラス変換などを覚えておけばかなりの高得点で安定して解ける。

電気回路2はMOSFETオペアンプによる増幅回路の問題。例年この2パターンしか出題されていないため、勉強もしやすく安定する。今年はMOSFETは線形領域と飽和領域の問題が出たが、例年の簡単さに少し舐めていたため多少勉強不足で線形領域の問題が解けなかった。オペアンプは反転・非反転・微分回路・積分回路ぐらいは覚えていて損はないが、例年それらが直接出るというよりそれらの単純な回路にRLCがいくつか追加されたような問題が出るため、暗記即答ゲーとはいかないが、問題に沿って回路解析を行っていけば問題なく解ける。

 

専門科目

「通信方式」「通信ネットワーク」「光・電波工学」「情報理論」「信号処理」「論理回路と計算機システム」「データ構造とアルゴリズム」「情報セキュリティ」の9題から好きな3題を選択して解く。 普通にプログラミングとかする人なら論理回路アルゴリズムの2題は確定で解いていい。簡単。残りはきちんと勉強すれば好きなのを取ればいい。私は上記2題と信号処理を解いた。

論理回路は与えられた問題文の条件から真理値表・最簡積和形が導き出せて論理回路が書ければ普通に満点が取れる。年によってNANDだけで組めという問題もあるのでAND, NOT, OR, XORをNANDだけで表す回路ぐらいは暗記しておく方がいい。あとhalf adderとfull adderも。あとは私にとっては基礎知識だったのでとくに勉強することなどなかった。過去問はもちろん解いたが。

計算機システムは教科書1 を丸暗記すれば全部解ける。過去問と教科書を見ればわかるが、実際この本からしか出ていないので何も解説することがない。全部覚える。

 

ソート・ハッシュテーブル・木構造・ヒープ・キュー・スタック・計算量など。これこそプログラミングを日常的にする人にとっては当たり前すぎて勉強するまでもない。過去問を解いて、解けて悦に浸るだけ。たまに変な問題が出題されるがどうせ誰も解けない上、この科目はほぼ全員が選択するのでそこで得点差はつかない。その問題を捨てるだけ。

 

  • 信号処理

フーリエ級数・連続時間フーリエ変換(FT)・サンプリング・離散時間フーリエ変換(DTFT)・離散フーリエ変換(DFT)・高速フーリエ変換(FFT)・窓関数・信号システムと伝達関数(Z変換)など、信号処理の全般が出題される。難易度は上記2つと比べるとやや高く、これらの内容を包括的に理解しておく必要がある。単純な計算問題ではなく、意味をきちんと理解しているかどうかなどの出題が多く、表面的に計算だけを覚えていたりすると足をすくわれやすい。信号システムが出た場合はきちんとZ変換伝達関数や出力信号が求められればいいため難易度は下がる。

 


 

総評

全体で半分点数があれば受かるため、躍起になって1問もミスしてはいけないと完璧を目指す必要は特にない。

私の場合、特に専門の計算機・アルゴリズムがほぼ満点で信号処理も平均で7割は安定して取れたため専門科目の得点率は安定して高かった。なので基礎科目は実質4割程度でも全然問題なかった。基礎科目の電気回路2つがだいたい解けるので数学は実質適当にしか勉強しなかった。

 

面接終了後、研究室で担当教官から言われた言葉「さすが2回目という点数だった」

[2020/01/17 追記] 思い出したので追記。受かってたので点数開示しなかったんだけど、担当教官から点数は3位だったというのを聞いた。


  1. 計算機システム-ハードウェアの基礎-(中前幸治/藤岡弘)