アジョブジ星通信

進捗が出た頃に更新されるブログ。

書きはじめ

あけましたね、おめでとうございます。2016年の振り返りと2017年の抱負を豊富に書くのが恒例行事らしいのでやるか。知らんけど。AbemaTV ではっぴぃにゅうにゃあしながら書いてるので自分でも何書いてるかわからなくなりそう。

2016年の振り返り

去年のことは去年のうちに書き捨てておくべきでしたが、ソフィーのアトリエやってガキの使い見てたら年が変わってたので許してほしい。あと記憶力ゼロ太郎なので覚えてない。

大学に入学した

北千住駅の目の前のオタクが詰め込まれているあそこです。レポートを手書きさせられています。

勉強意欲のほうですが、中学生のころ並には回復してきました。高校生のときは受験受験いわれて完全にやる気を失っていたのでね、多少マシになった(勉強したいとは言ってない)。

あと帰宅部コミュ障なのでお友達が少ない。ほかに書くことないのかボケ。

アルバイ

正直クソツイート太郎なので、僕のツイアカウントを某社リストに入れられるのつらいんですけど、って感じには隠れていたいんですけど、ついにコード書いてお金がもらえるようになりました。こういうことしてます。

仕事力(いろいろな要素があります)高いマンを見てると、人間力がほしい~って気持ちになりますね(語彙力)。とりあえず役には立てているらしいので、精進していきます。

ほかなにしたっけ

パフォーマンスやくざになったり、 null 撲滅過激派になったりした記憶があります。みなさんも Rust を書いて安全なプログラミングについて考えましょう、という感じです。

ほんと日本語力も記憶力もねーなこいつ。

2017年だよ

今週のお題「2017年にやりたいこと」

宣言なんてするもんじゃなかった。

いつも通り C# 界隈の情報を追いつつ、 Rust 界隈の情報も得ていく活動を続けながら、大学で新しい技術を身に着けていきたいなぁといったところです。今年もよろしくお願いします。

CoreFXで進化したLINQのお話

昔々のお話

こんなライブラリを作った記憶があったのですが、最近 C# パフォーマンスヤクザ[要出典]になりかけている僕に、 IReadOnlyCollection<T> を使用することで、 リスト→LINQ→ToArray といった処理を効率化できるのではないだろうかと考えて、このライブラリをちゃんと書き直すぞ!と考えていた矢先、 CoreFXSystem.Linq.Enumerable が進化していることに気づいたのでまとめておきます。

なお、ここで紹介する内容は、 .NET Core 1.0 に含まれており、 .NET Core App で使うことができます。 .NET Standard 1.6 以上である必要があるので、 .NET Framework のほうで使えるようになるのは 4.6.3 になると思います。先が長い。

追記: .NET Framework 4.7.1 では IListProvider だけ導入されました。とはいえ、配列や List に対する最適化が入っていないので、変化はないでしょう。 IPartition は最後の例が示すように互換性に問題があるので .NET Framework には導入されないかもしれません。

追加されたメソッド

  • Append
  • Prepend

Append は最後に 1 要素追加、 Prepend は最初に 1 要素を追加するメソッドです。こんな感じに使えます。

var e = new[] { 1 }.Prepend(0).Append(2);
foreach (var x in e)
    Console.WriteLine(x);
// 0
// 1
// 2

これで .Concat(new[] { hoge }) とか書かなくてよくなりますね。やった。

最適化のお話

ではメインのお話行きましょう。今まで LINQ は「書きやすいけど遅い」という問題が付き物でした。原因は主に以下の 2 つだと考えています。

  • IEnumerator<T> を愚直にラップしまくっていく挙動をするので、1回 MoveNext を呼び出すだけで深いコールスタックが生まれる(しかもインターフェイスメソッド)
  • array.Select(x => ...).ToArray() のような出力される配列の長さが明らかな操作であっても、長さ 4 の配列を確保して足りなくなったら 2 倍して…という挙動をする

今までも対策がされていなかったわけではなく、1については、 WhereSelect はよく使われるので、専用の Iterator が用意されていましたし、2については ICollection<T> ならば Count プロパティを使うということをしていました。とはいえこれだけでは不十分なのは2で例に挙げたものからも明らかだと思います。

そこで、新たに導入されたのが、 IIListProviderIPartition です。まずは定義を見てみましょう。

// Copyright (c) .NET Foundation and Contributors

/// <summary>
/// An iterator that can produce an array or <see cref="List{TElement}"/> through an optimized path.
/// </summary>
internal interface IIListProvider<TElement> : IEnumerable<TElement>
{
    /// <summary>
    /// Produce an array of the sequence through an optimized path.
    /// </summary>
    /// <returns>The array.</returns>
    TElement[] ToArray();

    /// <summary>
    /// Produce a <see cref="List{TElement}"/> of the sequence through an optimized path.
    /// </summary>
    /// <returns>The <see cref="List{TElement}"/>.</returns>
    List<TElement> ToList();

    /// <summary>
    /// Returns the count of elements in the sequence.
    /// </summary>
    /// <param name="onlyIfCheap">If true then the count should only be calculated if doing
    /// so is quick (sure or likely to be constant time), otherwise -1 should be returned.</param>
    /// <returns>The number of elements.</returns>
    int GetCount(bool onlyIfCheap);
}

internal interface IPartition<TElement> : IIListProvider<TElement>
{
    IPartition<TElement> Skip(int count);

    IPartition<TElement> Take(int count);

    TElement TryGetElementAt(int index, out bool found);

    TElement TryGetFirst(out bool found);

    TElement TryGetLast(out bool found);
}

corefx/Partition.cs at release/1.1.0 · dotnet/corefx · GitHub

このインターフェイスを実装しているイテレーターは、インターフェイスのメンバーにある処理が普通にループを回すのに比べて省略可能だということを表します。これによって操作が最適化され、可能な場合には ElementAt, Last が O(1) になったり、 ToArrayToList で配列のアロケーション回数を減らしたりできます。

簡単な例を紹介します。

var e = Enumerable.Range(0, 100)
    .Select(x =>
    {
        Console.WriteLine(x);
        return x;
    })
    .Skip(95);

foreach (var _ in e);

このコードを .NET Framework 4.6.2 で実行すると、 0 から 99 までコンソールに出力されますが、 .NET Core で実行すると 95 から 99 までしか出力されません。これは、 RangeIteratorIPartition を実装しており、 SelectSelectIPartitionIterator が使用され、うまく Skip を省略することに成功しています。 IPartitionRange のほか、 RepeatOrderBy の結果が実装しています。もちろん IList<T>Select, Skip, Take を実行した場合にも IPartition を実装した戻り値が生成されます。

また、 IIListProvider 単体は、 DistinctUnion など、すべて Set に突っ込んだ結果を配列に移す操作がショートカットできる場所や、 Append, Prepend, Concat のように ToList を効率化できる場所に使用されています。

まとめ

Append, Prepend, ConcatIPartition を特別扱いしないのが気に食わないですが、とにかく、何も考えずに LINQ を使っても圧倒的無駄な処理にならずに済むようになるのはとても大きいと思います。というわけで早く .NET Framework 4.6.3 出してくれ。

取り急ぎ古いNuGetでもインストールできるパッケージをつくる

CoreTweet 0.7.0.339 を NuGet 2.x 系を使う環境(Visual Studio 2013 でアップデート入れてない or MonoDevelop/Xamarin Studio 6.0.x以下)でインストールしようとすると、こんな感じのエラーが出ることは知ってましたがリリースしてしまいました、が思ったより影響大きかった(エゴサ調べ)ので、なんとかしたお話。

f:id:azyobuzin:20160811000149p:plain

原因

0.7.0.339 の nuspec ファイルの依存パッケージが記述されている部分がこちら。

<dependencies>
    <group targetFramework="net35">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="portable-win81+wpa81">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="portable-net45+dnxcore50+win8+wpa81+MonoAndroid+xamarinios+MonoTouch">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="monoandroid">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="monotouch">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="xamarinios">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="netstandard1.1">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
        <dependency id="System.Dynamic.Runtime" version="4.0.11" />
        <dependency id="System.Globalization" version="4.0.11" />
        <dependency id="System.Linq" version="4.1.0" />
        <dependency id="System.Linq.Expressions" version="4.1.0" />
        <dependency id="System.Net.Http" version="4.1.0" />
        <dependency id="System.Reflection.Extensions" version="4.0.1" />
        <dependency id="System.Runtime.Extensions" version="4.1.0" />
        <dependency id="System.Text.RegularExpressions" version="4.1.0" />
        <dependency id="System.Threading" version="4.0.11" />
    </group>
    <group targetFramework="netcoreapp1.0">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
        <dependency id="System.Dynamic.Runtime" version="4.0.11" />
        <dependency id="System.Globalization" version="4.0.11" />
        <dependency id="System.IO.FileSystem" version="4.0.1" />
        <dependency id="System.Linq" version="4.1.0" />
        <dependency id="System.Linq.Expressions" version="4.1.0" />
        <dependency id="System.Net.Http" version="4.1.0" />
        <dependency id="System.Reflection.Extensions" version="4.0.1" />
        <dependency id="System.Runtime.Extensions" version="4.1.0" />
        <dependency id="System.Security.Cryptography.Algorithms" version="4.2.0" />
        <dependency id="System.Text.RegularExpressions" version="4.1.0" />
        <dependency id="System.Threading" version="4.0.11" />
    </group>
</dependencies>

この中で、 NuGet 2.x 系で対応していないフレームワークは netstandard1.1 と netcoreapp1.0 の2つです。さて、 NuGet 内部では対応していないフレームワークはまとめて「Unsupported 0.0」として扱われます。つまりこういう状況。

<dependencies>
    <group targetFramework="net35">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="portable-win81+wpa81">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="portable-net45+dnxcore50+win8+wpa81+MonoAndroid+xamarinios+MonoTouch">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="monoandroid">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="monotouch">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="xamarinios">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
    </group>
    <group targetFramework="Unsupported,Version=0.0">
        <dependency id="Newtonsoft.Json" version="9.0.1" />
        <dependency id="System.Dynamic.Runtime" version="4.0.11" />
        <dependency id="System.Globalization" version="4.0.11" />
        <dependency id="System.Linq" version="4.1.0" />
        <dependency id="System.Linq.Expressions" version="4.1.0" />
        <dependency id="System.Net.Http" version="4.1.0" />
        <dependency id="System.Reflection.Extensions" version="4.0.1" />
        <dependency id="System.Runtime.Extensions" version="4.1.0" />
        <dependency id="System.Text.RegularExpressions" version="4.1.0" />
        <dependency id="System.Threading" version="4.0.11" />

        <dependency id="Newtonsoft.Json" version="9.0.1" />
        <dependency id="System.Dynamic.Runtime" version="4.0.11" />
        <dependency id="System.Globalization" version="4.0.11" />
        <dependency id="System.IO.FileSystem" version="4.0.1" />
        <dependency id="System.Linq" version="4.1.0" />
        <dependency id="System.Linq.Expressions" version="4.1.0" />
        <dependency id="System.Net.Http" version="4.1.0" />
        <dependency id="System.Reflection.Extensions" version="4.0.1" />
        <dependency id="System.Runtime.Extensions" version="4.1.0" />
        <dependency id="System.Security.Cryptography.Algorithms" version="4.2.0" />
        <dependency id="System.Text.RegularExpressions" version="4.1.0" />
        <dependency id="System.Threading" version="4.0.11" />
    </group>
</dependencies>

こうすると Unsupported で2個同じパッケージが含まれているので、検証で殺されて、スクリーンショットのエラーメッセージが出るようになるわけです。

この問題は、 netstandard, netcoreapp に対応した 2.11 で解決しています。

どう対処する?

A. 諦めるか、古い NuGet が非対応のフレームワークを1つまでにする

とりあえず CoreTweet 0.7.1.345 では依存パッケージの宣言から netcoreapp を消し去りました(消し去るために少しコードもいじりましたが)。

というわけで、なかなか厳しい状況なので、早く NuGet 3 系が広まって欲しい。 Xamarin Studio 6.1 はよ。

System.Stringのコンストラクタを許すな

というわけで始まりました深夜の CoreCLR ソースコードリーディングのお時間。司会は早くこの記事を書き終えてアニメを見たいazyobuzinがお送りいたします。

普通のコンストラクタ

コンストラクタは、名前「.ctor」、戻り値の型 void で定義されるインスタンスメソッドと考えることができます。そしてオペコード newobj でコンストラクタが指定されると、そのクラスのインスタンスが作成され、第0引数に入れられコンストラクタが呼び出されます。つまり、「メモリ確保 → コンストラクタ呼び出し」という順番になります。

String のコンストラクタ

mscorlib の String クラスのコンストラクタは、すべて [MethodImplAttribute(MethodImplOptions.InternalCall)] が付与されていています(ILでは internalcall 属性, 通称 FCall)。 FCall は ecalllist.hマッピングされた関数を呼び出します。

マネージドメソッドとして定義されたコンストラクタ

では、 String のコンストラクタを呼び出した時に、実際に呼び出される関数を見ていきましょう。まずは FCDynamicSig で定義されているこの5つ。

FCDynamicSig(COR_CTOR_METHOD_NAME, &gsig_IM_ArrChar_RetVoid, CORINFO_INTRINSIC_Illegal, ECall::CtorCharArrayManaged)
FCDynamicSig(COR_CTOR_METHOD_NAME, &gsig_IM_ArrChar_Int_Int_RetVoid, CORINFO_INTRINSIC_Illegal, ECall::CtorCharArrayStartLengthManaged)
FCDynamicSig(COR_CTOR_METHOD_NAME, &gsig_IM_PtrChar_RetVoid, CORINFO_INTRINSIC_Illegal, ECall::CtorCharPtrManaged)
FCDynamicSig(COR_CTOR_METHOD_NAME, &gsig_IM_PtrChar_Int_Int_RetVoid, CORINFO_INTRINSIC_Illegal, ECall::CtorCharPtrStartLengthManaged)
FCDynamicSig(COR_CTOR_METHOD_NAME, &gsig_IM_Char_Int_RetVoid, CORINFO_INTRINSIC_Illegal, ECall::CtorCharCountManaged)

https://github.com/dotnet/coreclr/blob/release/1.0.0/src/vm/ecalllist.h#L214-L218

これらは最後に「Managed」がついてることからわかるように、マネージドメソッドを呼び出します。最初の「CtorCharArrayManaged」に対応するメソッドを探すと String クラスに CtorCharArray メソッドがありました。(ecall.h, ecall.cpp を読むと、 String 型のメンバーを舐めているのがわかります。)

CtorCharArray はインスタンスメソッドで、 String を返します。……は?とりあえず、この戻り値が newobj の実行結果となるようです。

アンマネージドのほう

C++で書かれたメソッドを呼び出すものは FCFuncElementSig で定義されています。

FCFuncElementSig(COR_CTOR_METHOD_NAME, &gsig_IM_PtrSByt_RetVoid, COMString::StringInitCharPtr)
FCFuncElementSig(COR_CTOR_METHOD_NAME, &gsig_IM_PtrSByt_Int_Int_RetVoid, COMString::StringInitCharPtrPartial)

https://github.com/dotnet/coreclr/blob/v1.0.0/src/vm/ecalllist.h#L219-L220

COMString クラスのメンバーの実装は stringnative.cpp にあります。

StringInitCharPtr を見てみると

_ASSERTE(stringThis == 0);      // This is the constructor

なんてコードがありますね。つまり this として null が渡されているようです。ということはマネージドのほうも this は null なのだと思われます。

戻り値はオブジェクトの参照、つまり String です。

まとめると

コンストラクタを internalcall にすると、 FCall で this が null なインスタンスメソッドとして呼び出され、戻り値が生成されたインスタンスとして扱われます。

Decimal のコンストラクタ

他にもコンストラクタが internalcall なものはないかと探していたら Decimal の float, double を引数にとるコンストラクタが internalcall でした。 decimal.cpp の InitSingle と InitDouble が呼び出されるメソッドです。今度は戻り値が void ですね。値型だと戻り値は不要のようです。そもそも値型のコンストラクタは newobj のほかに、普通に call で呼び出すこともあります(コンパイラ依存案件)し、そういうものなのでしょうか。よくわからん。

Unicode正規化を実装する (4) クイックチェック

バックナンバー

  1. Unicode正規化を実装する (1) UCDにふれる - アジョブジ星通信
  2. Unicode正規化を実装する (2) 正規分解・互換分解 - アジョブジ星通信
  3. Unicode正規化を実装する (3) 正規合成 - アジョブジ星通信

本当は正規化の高速化全般について書きたかったのですが、 UAX #15 に「トライ木使うといいんじゃね?」とか書いてあるんですけど、どういう木構造にしたらいいのかさっぱりわからず無事死亡しました。強い方、よろしくお願いします。

というわけで今回は、クイックチェックプロパティを使った、正規化済み判定と合成の高速化について説明していこうと思います。

続きを読む

Unicode正規化を実装する (3) 正規合成

バックナンバー

  1. Unicode正規化を実装する (1) UCDにふれる - アジョブジ星通信
  2. Unicode正規化を実装する (2) 正規分解・互換分解 - アジョブジ星通信

PCの死亡を言い訳に3ヶ月空いてしまいましたが、その間に Unicode 9.0.0 がリリースされたようです。サンプルリポジトリに入っている UCD のコピーを 9.0.0 にアップデートしました。 NormalizationTest.txt のテストケースは前回のサンプルコードのまま問題なくクリアしています。

さて、今回は合成です。合成は分解テーブルのキーと値が逆のテーブルを作って、ひたすらルックアップしていく作業になります。ただし、合成できる文字には細かい規定があるので気をつけましょう。

前回同様、サンプルと見比べながら読み進めてもらえると良いです。結構ファイルが分散しているので、「定義へ移動」が使える Visual Studio を使うと読みやすいかと思います。

続きを読む