(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型のメソッドを呼ぶことになるので、ここで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 のリファクタリング機能でサクッと全部自動実装できる

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

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

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

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

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

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

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

UI スレッド復帰しないawait

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

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

TaskのデフォルトではConfigureAwaitはtrueに設定されており、この場合、同期コンテキストによる通知は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 のフレームワークを使ってアプリケーションを作る場合、多くの場合このループ部分がフレームワークとして隠蔽されているため特にループについて意識することはありませんが、同期コンテキストはこの部分で処理されています。

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

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

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

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

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

その後、ループ中でキューを見張っている UI スレッドによって、コールバックが実行され、まるでTaskをawait した続きの部分から 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も。あとは私にとっては基礎知識だったのでとくに勉強することなどなかった。過去問はもちろん解いたが。

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

• データ構造とアルゴリズム

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

• 信号処理

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

---

総評

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

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

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

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

---

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

解けない15パズル

15パズルってご存知ですか？

知ってても知らなくても15パズルの話をするんですが。はい。

あと、本記事は数学的な厳密な証明はせずに感覚的にエイッヤッ～とやっているので正確じゃないです。

でもたぶんあってる。はい。

これ

簡単に言いますと、1マス空いている4×4のマスでセルを移動させながら、 左上から順に数字を並べるパズルです。

アルゴリズムも単純でプログラミング初心者でも割と簡単に実装できるゲームです。

と思っていた時期が私にもありました。

15パズルの欠陥

というのは半分冗談で、ゲームのアルゴリズム自体は別に難しくないです。 問題はこの15パズルというゲームが持つ本質的な欠陥についてです。

端的に言うと、絶対に完成できない形が存在します。

これが完成形です。

そして、次が完成不可能な形の一例です。

このように完成形から1つだけ入れ替えた形は、どれだけパズルをグルグルまわしても 絶対に完成形にはならないことが知られています。

証明とかは省略します、というより私が知りません。昔の偉い人がそう言ったので信じます。

これをベースに、完成できる条件とは何かを考えていきます。

完成可能条件

先ほどの、完成形から隣接する2つのセルを1度だけ入れ替えたものを、完成形からの距離D=1と呼ぶことにします。

D=1状態が完成不可能なので、D=2の形について考えます。

D=2はD=1からもう一度隣接するセルを入れ替えた形の集合です。

D=2はD=1のところと同じ2セルを入れ替えた形も含むので、つまり完成形もD=2に含まれます。

ということは再帰的にD=2nは完成形を含むため、距離が偶数なら完成可能、奇数なら完成不能です。

(数学徒からは全然証明になってないので受精卵から人生やりなおせと言われそうですが、私は厳密な証明できないのでこの記事執筆後、受精卵からやり直します)

では次のような斜めの2つを入れ替えた形に距離を考えます。

完成形から順に入れ替えを手順を追っていきます。

# D=0
 9 10 11 12
13 14 15 __

↓ 14, 15を入れ替え

# D=1
 9 10 11 12
13 15 14 __

↓ 10, 15を入れ替え

# D=2
 9 15 11 12
13 10 14 __

↓ 14, 10を入れ替え

# D=3
 9 15 11 12
13 14 10 __

つまり、斜めのセルの入れ替えはD=3です。つまり完成形からは奇数距離です。

このように拡張していくと、任意の2つのセルの入れ替えは奇数距離であることが分かります。

ここから分かることは、任意の入れ替えが奇数距離であるため、入れ替え回数が偶数回なら偶数距離を保てるということです。

つまり、解ける15パズルとは、完成形から偶数回の「任意の2セル入れ替え」で得られる集合に含まれる形です。

なので、ランダムに初期状態を生成すると1/2の確率で完成不能なパズルができるということですね。。。。

おしまい

---

ソースコード(C#版/VB版)

github.com

二度とVBなんか書かねぇ

(C#) コレクションのカプセル化

コレクションの保護

クラスの不十分なカプセル化としてよく見られるのがコレクションです。 以下の例は、カプセル化されていないコレクションの例です。

public static class Database
{
    public static Person[] People { get; private set; }
}

public class Person
{
    public int Age { get; private set; }
    public string Name { get; private set; }
}

問題があるのは、DatabaseクラスのPeopleプロパティです。 一見、setterはprivateであるため、クラス外部からの変更は不可能なように見えますが、これはコレクションにありがちなミスです。

コレクションそのもののインスタンスは書き換え不可ですが、以下のように各要素については書き換えができてしまいます。

// これはsetterがprivateなので不可
Database.Person = new Person[5];

// これは可能
Database.Person[3] = new Person();

外部に対してforeachでPersonを回すことだけを想定している場合、外部からの要素の書き換えは危険です。これはArrayに限らずList<T>である場合も当然同様です。

public static class Database
{
    public static List<Person> People { get; private set; }
}
// -----------------------------------------------

// 想定外の要素の追加が可能
Database.People.Add(new Person());

foreachによる列挙を許可したい場合、適切な実装は以下のようにIEnumerable<T>を使うのが正しいです。

public static class Database
{
    public static IEnumerable<Person> People { get; private set; }
}

これで、外部からはイテレート以外の操作は受け付けません。 しかし、この場合、内部からの操作もIEnumerable<T>でしか操作できず、大変不便です。 以下のように実装すると内部では柔軟な操作が可能になります。

public static class Database
{
    private static readonly List<Person> _people = new List<Person>();
    public static IEnumerable<Person> People => _people;
}

これで外部からはイテレートしかできず、内部からは自由な操作が可能になります。

しかし、IEnumerable<T>は意外と不便で、index操作が使えない、要素数が取れない等の不便さが生じます。インデクサを定義しているのはIList、要素数を定義しているのはICollectionだからです。(IEnumerable<T>から要素数取得やインデックス指定可能な方法はありますが後述。)

なおIEnumerable、ICollection、IListおよびそのジェネリック版の関係は以下の図の通りです。

そこで、コレクションのカプセル化を実現しつつ、インデクサと要素数を利用できるのがSystem.Collections.ObjectModel.ReadOnlyCollection<T>です。

[2020/06/21 追記] .net standard 2.0 以降の環境では、保護したいものが配列の場合はReadOnlyMemory<T>やReadOnlySpan<T>を使った方が色々とパフォーマンスが良いです。Listとかの場合はReadOnlyCollection<T>を使わざるを得ませんが。

public static class Database
{
    private static readonly List<Person> _people = new List<Person>();
    public static ReadOnlyCollection<Person> People { get; } = _people.AsReadOnly();
}
// --------------------------------------------------------

// インデクサのsetterはないためこれは不可
Database.People[3] = new Person();

// getは可能
var person = Database.People[3];
// 要素数も取得可能
var count = Database.People.Count;

これで、インデクサ操作や要素数の要件を満たしつつ、適切なコレクションのカプセル化ができました。

インデクサ操作や要素数の取得が不要な場合、IEnumerable<T>でもReadOnlyCollection<T>でも外部から保護されている点では十分なのでどちらを用いてもよいでしょう。

補足1

ReadOnlyCollection<T>を用いた実装例で、

public static ReadOnlyCollection<Person> People => _people.AsReadOnly();

ではなく、

public static ReadOnlyCollection<Person> People { get; } = _people.AsReadOnly();

としています。2つの違いは、前者の実装ではgetterが呼ばれるたびにReadOnlyCollection<Person>のインスタンスが生成されますが、後者は最初の1回インスタンスが生成されるのみです。当然、後者の方がメモリ的には良いでしょう。(微々たる差ではありますが)

が、これは一見不思議な実装です。次の例を見てください。

public static class Database
{
    private static readonly List<Person> _people = new List<Person>();
    public static ReadOnlyCollection<Person> People { get; } = _people.AsReadOnly();

    public static Add(Person person) => _people.Add(person);
}
// --------------------------------------------------------

// ここで0が出力されるとする
Console.WriteLine(Database.People.Count);

// 要素追加
Database.Add(new Person());
// ここでは何が出力される？
Console.WriteLine(Database.People.Count);

さて問題です。最後の出力では何が出力されるでしょう？

ReadOnlyCollection<Person>のインスタンスが生成されるのがDatabaseクラス初期化時のみなので、一見0が出力されるように思えます。

が、実際は1がちゃんと出力されます。アラ不思議。

これはReadOnlyCollection<T>がList<T>のラッパーであるため、内部で元になったList<T>のインスタンスを持っているために起こります。参照型万歳。

補足2

IEnumerable<T>を使った隠蔽実装では要素数およびインデクサ操作ができないと前述しました。 しかし、実際はLINQのIEnumerable<T>.Count()やIEnumerable<T>.ElementAt(int)を使うことで可能です。

しかし、IEnumerable<T>は列挙可能であることを定義するだけのインターフェースであるため、Count()は先頭から順に全要素の数え上げを行いO(n)かかります。ElementAt(int)も同様です。

が、実はMicrosoftの公開しているLINQの実装を見てみると、Count()は実際のインスタンスがICollectionである場合はICollectionにキャスト後、ICollection.Countを返しています。同様に、ElementAt(int)もIListである場合はキャスト後にIList[int]を返しています。

本文で上げたIEnumerable<T>を用いた隠蔽実装の実体はList<T>であるため、ともにO(1)で返ります。つまり、要素数もインデクサ操作も実は何の不都合も存在せず使用可能なのです。

しかし、ここでもう一度否定します。

例で挙げたDatabaseクラスを外部から見ると、内部の実態がList<T>であることなど知る由もありません。IEnumerable<T>.Count()と使えばO(n)だと考えるのが自然です。実際はO(1)で返るのだとしても、そのような利用法を外部に公開するのはフレンドリーとはあまり言えないでしょう。

よって、要素数やインデクサを使わせたいのであれば素直にReadOnlyCollection<T>で公開すべきでしょう。