CoreFXで進化したLINQのお話
昔々のお話
こんなライブラリを作った記憶があったのですが、最近 C# パフォーマンスヤクザ[要出典]になりかけている僕に、 IReadOnlyCollection<T>
を使用することで、 リスト→LINQ→ToArray といった処理を効率化できるのではないだろうかと考えて、このライブラリをちゃんと書き直すぞ!と考えていた矢先、 CoreFX の System.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については、 Where
と Select
はよく使われるので、専用の Iterator
が用意されていましたし、2については ICollection<T>
ならば Count
プロパティを使うということをしていました。とはいえこれだけでは不十分なのは2で例に挙げたものからも明らかだと思います。
そこで、新たに導入されたのが、 IIListProvider
と IPartition
です。まずは定義を見てみましょう。
// 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) になったり、 ToArray
や ToList
で配列のアロケーション回数を減らしたりできます。
簡単な例を紹介します。
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 までしか出力されません。これは、 RangeIterator
が IPartition
を実装しており、 Select
で SelectIPartitionIterator
が使用され、うまく Skip
を省略することに成功しています。 IPartition
は Range
のほか、 Repeat
や OrderBy
の結果が実装しています。もちろん IList<T>
に Select
, Skip
, Take
を実行した場合にも IPartition
を実装した戻り値が生成されます。
また、 IIListProvider
単体は、 Distinct
や Union
など、すべて Set
に突っ込んだ結果を配列に移す操作がショートカットできる場所や、 Append
, Prepend
, Concat
のように ToList
を効率化できる場所に使用されています。
まとめ
Append
, Prepend
, Concat
が IPartition
を特別扱いしないのが気に食わないですが、とにかく、何も考えずに 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以下)でインストールしようとすると、こんな感じのエラーが出ることは知ってましたがリリースしてしまいました、が思ったより影響大きかった(エゴサ調べ)ので、なんとかしたお話。
原因
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のコンストラクタを許すな
String のコンストラクタ、ありえてはいけない存在だよな
— ウィンドウズ青山 (@azyobuzin) 2016年8月2日
ということは、コンストラクタを FCall にするとあり得ない型のインスタンスをお返しすることができるわけですね!!
— ウィンドウズ青山 (@azyobuzin) 2016年8月2日
というわけで始まりました深夜の 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 です。
Decimal のコンストラクタ
他にもコンストラクタが internalcall なものはないかと探していたら Decimal の float, double を引数にとるコンストラクタが internalcall でした。 decimal.cpp の InitSingle と InitDouble が呼び出されるメソッドです。今度は戻り値が void ですね。値型だと戻り値は不要のようです。そもそも値型のコンストラクタは newobj のほかに、普通に call で呼び出すこともあります(コンパイラ依存案件)し、そういうものなのでしょうか。よくわからん。
Unicode正規化を実装する (4) クイックチェック
バックナンバー
- Unicode正規化を実装する (1) UCDにふれる - アジョブジ星通信
- Unicode正規化を実装する (2) 正規分解・互換分解 - アジョブジ星通信
- Unicode正規化を実装する (3) 正規合成 - アジョブジ星通信
本当は正規化の高速化全般について書きたかったのですが、 UAX #15 に「トライ木使うといいんじゃね?」とか書いてあるんですけど、どういう木構造にしたらいいのかさっぱりわからず無事死亡しました。強い方、よろしくお願いします。
というわけで今回は、クイックチェックプロパティを使った、正規化済み判定と合成の高速化について説明していこうと思います。
続きを読むUnicode正規化を実装する (3) 正規合成
バックナンバー
PCの死亡を言い訳に3ヶ月空いてしまいましたが、その間に Unicode 9.0.0 がリリースされたようです。サンプルリポジトリに入っている UCD のコピーを 9.0.0 にアップデートしました。 NormalizationTest.txt のテストケースは前回のサンプルコードのまま問題なくクリアしています。
さて、今回は合成です。合成は分解テーブルのキーと値が逆のテーブルを作って、ひたすらルックアップしていく作業になります。ただし、合成できる文字には細かい規定があるので気をつけましょう。
前回同様、サンプルと見比べながら読み進めてもらえると良いです。結構ファイルが分散しているので、「定義へ移動」が使える Visual Studio を使うと読みやすいかと思います。
続きを読むツイートの新構造対応のメモ
これです。
CoreTweet 0.6.3 で API の変更には対応したのでその使い方について説明を書いておこうと思います。
1. とりあえず tweet_mode=extended をつけておく
新構造のデータを受信するには tweet_mode=extended
を指定する必要があります。 CoreTweet でこれをやるには、各 API 呼び出しで、 tweet_mode
引数に TweetMode.extended
を指定します。
サンプルコード
t.Statuses.HomeTimeline(tweet_mode: TweetMode.extended); // TweetMode 列挙体を使用 t.Statuses.HomeTimeline(tweet_mode => "extended"); // string で
で、このパラメータを指定すると、 text ではなく full_text フィールドにツイートの中身が入ってくるようになります。 CoreTweet では FullText プロパティになっています。
Unicode正規化を実装する (2) 正規分解・互換分解
前回: Unicode正規化を実装する (1) UCDにふれる - アジョブジ星通信
さて、前回 UnicodeData.txt の読み方をやりましたので、これを使って実際に正規分解・互換分解を実装してみましょう。
サンプルコードと見比べながら説明を読んでいただければと思います。
続きを読む