FastPropertyComparer

(さらに追記)
この日の日記のコードはいろいろ問題があるので、使わないでください。詳しくは id:siokoshou:20070507。
(さらに追記終わり)

(追記:訂正)
すみません、派手に間違っていました。
以下の FastPropertyComparer は、個別のエンティティ型にあわせて一つ一つのプロパティごとにソートを書いた場合より10程度遅かったです。計り間違いました…。
これはつまり、MSDNのコラムのリフレクション版だと、個別にソートを書いた場合の実に100倍かそれ以上遅いってことでもあります。
この10倍程度の差はなんだろう。JITコンパイルでインライン展開された差とかなのかな？
stringだと10倍程度遅いんですが、intだと初回で4倍くらい、2回目以降は2〜3倍遅い程度です。
(追記終わり)

---

昨日の続き。無事、PropertyComparer を IL で動的生成できました。
ILにしてみたら10〜30倍程度速くなりました。比較するプロパティがstringで10〜15倍程度、intで30倍程。元のMSDNのコラムのコードと比べると、実に20〜90倍も高速！でも、DataGridView の表示が遅いから体感できないんだけどねｗ
これはスゴイことに、BindingList を個別のエンティティ型にあわせて継承して ApplySortCore を一つ一つのプロパティごとにソートを書いた場合と同じくらいの速さです。値型なら x.Value.CompareTo( y.Value ); みたいなコードを書けばさらに2.5倍くらい速いんだけど、まあいいや。
いちいち型に合わせてコードを書かなくても同じ速さ。nice hackだ。

次の目標は Expression Tree で SortBy を作ることかな。C#3.0ならではの言語を拡張するってのをやってみたい。C#3.0はSQLだったりLispだったり、おもしろいですねぇ。

以下、FastPropertyComparer。はじめてのIL習作。C#だと1行で書けるけど、ILだとずいぶん苦労しました。Constrained は結局使い方がわからずじまい。どなたか解説してください！
プロパティを読む部分をIL化するついでに、ListSortDirection の if 文も動的に展開してます。これはILじゃなくてもできるけど、ついでなので。
バグなどありましたらコメント欄で教えてください。まだstringとintしか試していませんのでご注意を。動いたよって報告も歓迎です(他力本願…)。

以下、コード。

(注意)このコードはいろいろ問題があるので、使わないでください。詳しくは id:siokoshou:20070507。(注意ここまで)

interface IMakeComparison<T>
{
  Comparison<T> MakeComparison( PropertyDescriptor property, ListSortDirection direction );
}

public static class FastPropertyComparerFactory
{
  public static Comparison<T> Factory<T>( PropertyDescriptor property, ListSortDirection direction )
  {
    Type seed = typeof( FastPropertyComparer<,> );
    Type[] typeArgs = { typeof( T ), property.PropertyType };
    Type pcType = seed.MakeGenericType( typeArgs );

    IMakeComparison<T> factory = ( IMakeComparison<T> ) Activator.CreateInstance( pcType );
    return factory.MakeComparison( property, direction );
  }
}

public sealed class FastPropertyComparer<T, U> : IMakeComparison<T>
{
  /*
  public int Compare( T x, T y )
  {
    U xValue = x.Prop;
    U yValue = y.Prop;

    return Comparer<U>.Default.Compare( xValue, yValue );
    // or
    return Comparer<U>.Default.Compare( yValue, xValue );
  }
  */

  public Comparison<T> MakeComparison( PropertyDescriptor property, ListSortDirection direction )
  {
    Type t = typeof( T );
    MethodInfo tmi = t.GetProperty( property.Name ).GetGetMethod();

    if ( tmi == null )
      throw new ArgumentNullException( "T.Propがpublicではありません" );

    Type u = typeof( U );

    // メソッドを作る
    DynamicMethod dm = new DynamicMethod( "Compare", typeof( int ), new Type[] { t, t }, this.GetType() );
    ILGenerator ilgen = dm.GetILGenerator();

    // ローカル変数
    // U xValue, yValue;
    ilgen.DeclareLocal( u ); // xValue
    ilgen.DeclareLocal( u ); // yValue

    // U xValue = x.Prop;
    ilgen.Emit( OpCodes.Ldarg_0 );
    //ilgen.Emit( OpCodes.Constrained, t ); // ???
    ilgen.Emit( OpCodes.Callvirt, tmi ); // MethodInfo
    ilgen.Emit( OpCodes.Stloc_0 );

    // U yValue = y.Prop;
    ilgen.Emit( OpCodes.Ldarg_1 );
    //ilgen.Emit( OpCodes.Constrained, t ); // ???
    ilgen.Emit( OpCodes.Callvirt, tmi ); // MethodInfo
    ilgen.Emit( OpCodes.Stloc_1 );

    Type comparerT = typeof( Comparer<U> );

    // Comparer<U>.Default.Compare( xValue, yValue ); or Comparer<U>.Default.Compare( yValue, xValue );
    ilgen.Emit( OpCodes.Call, comparerT.GetProperty( "Default" ).GetGetMethod() ); // get_Default

    if ( direction == ListSortDirection.Ascending )
    {
      ilgen.Emit( OpCodes.Ldloc_0 );
      ilgen.Emit( OpCodes.Ldloc_1 );
    }
    else
    {
      ilgen.Emit( OpCodes.Ldloc_1 );
      ilgen.Emit( OpCodes.Ldloc_0 );
    }

    ilgen.Emit( OpCodes.Tailcall );
    ilgen.Emit( OpCodes.Callvirt, comparerT.GetMethod( "Compare" ) );

    // return
    ilgen.Emit( OpCodes.Ret );

    // デリゲートにする
    Comparison<T> comparison = ( Comparison<T> ) dm.CreateDelegate( typeof( Comparison<T> ) );
    return comparison;
  }
}

id:NyaRuRu:20070416、id:akiramei:20040410を参考にさせていただきました。ありがとうございます！

昨日の SortableBindingList から FastPropertyComparer を使うには、ApplySortCore を書き換えてください。念のため。

list.Sort( FastPropertyComparerFactory.Factory<T>( property, direction ) );

昨日の PropertyComparer も今日のコードもひっそりと IComparable じゃなかったら string で比較するって処理を消してます。元のMSDNコラムのコードとちょっと違うのでご注意を。

＃んー、FactoryだったりMakeだったり名前が一貫してないなぁ。