続続 C は高級アセンブラ

C# は高級アセンブラ、続 C# は高級アセンブラの続きです。
C#ではおよそ最適化できることろがなくなってきていて、最後のブレイクスルーとして、altriveさんの

@haxe さんのコード見て、これ以上最適化できそうもないので、自分のコードも公開。https://t.co/rnekjQyrjx 工夫してるのは下記の2点。 ・標準入力が遅かったので、PInvokeでCのライブラリを呼び出し ・RadixSortを条件に合わせて最適化
— altrive (@altrive) December 6, 2013

を真似させてもらいました。標準入出力を扱うConsoleクラスはstaticメソッドになっているため、マルチスレッドセーフにするためにどうしても処理が重くなっていることはわかっていました。
代替手段としてMono.Posixアセンブリに含まれているMono.Unix.Native名前空間、Syscall.read()を使う案もありましたが、Assembly.Load()で読み込むことができずに没になりました。
仕方がないため、libcのread()を直接DllImportしています。
これによりめでたくCase3でも0.01のスコアを出すことができました。逆に言うと、Consoleクラスのオーバーヘッドが0.02秒存在していることになります。ソースコードはこちら。

---

ところでこの記事のタイトル「高級アセンブラ」ですが、どうも「私が『高級アセンブラ』とは『単にプリミティブっぽい処理を並べること』と解釈している」と誤解されている方がいるようなので説明しておきます。
私なりの解釈では高級アセンブラとは、その言語のコードから生成されるアセンブリが容易に想像でき、また生成されるアセンブリ内容を制御すべくコーディングすることにあると考えています。
例えば初回に公開したコードにはコメントに「引数4、変数4なので効率よく参照可能。」とあるようにレジスタ割り付けを考慮したコーディングを行っています。（C言語であればコンパイラにレジスタ割り付けを指示するregisterキーワードが存在しました。）
と言うだけでは何なので、C言語でも書いてみました。スコアは普通に0.01 / 0.01 / 0.01です。 なお、しょうもないところでは #include IO_H の行。インクルードするファイル名は直接の文字列でなくても文字列定数を使うこともできます。もちろんコンパイラの出力を貼り付けただけだろうと言わせないためにも、今どきのコンパイラが使用しない AAh なんかを使ってます…実際には効率悪いとは思いますが。
その他、C#とロジックは同じなので、÷10、÷100、÷1000、÷10000、÷100000が存在していますが、この辺りもコンパイラは逆数の乗算に変換します。…というだけなのも悔しいのでコードでは使用していませんが手計算で調べたメモを書いておきます。

• 0～99の範囲で x / 10 に相当するのは x * 205 >> 11
• 0～999の範囲で x / 100 に相当するのは x * 41 >> 12
• 0～9999の範囲で x / 1000 に相当するのは x * 8839 >> 23
• 0～99999の範囲で x / 10000 に相当するのは (int)(x * 429497L) >> 36)
• 0～999999の範囲で x / 100000 に相当するのは (int)(x * 687195L) >> 40)

コンパイラが生成する乗算の場合、被除数が特定できないため32bit精度を保証する逆数になりますが、被除数の範囲を絞り込むと必要となる有効精度が下がるため、乗数が小さくて済みます。
乗数を小さくする利点は、乗算が高速に完了することもありますが、更にもう１つ、LEA命令が視野に入ってきます。LEAはアドレス計算する命令ですがこれを応用すると乗算を更に高速化できます。
例えば、x * 41の場合、

LEA EBX, [EAX * 4 + EAX] ; EBX = EAX * 5 LEA EAX, [EBX * 8 + EAX] ; EAX = EBX * 8 + EAX = EAX * 41

と２命令で表現できます。そしてx * 205も３命令です。

LEA EBX, [EAX * 4 + EAX] ; EBX = EAX * 5 LEA EAX, [EBX * 8 + EAX] ; EAX = EBX * 8 + EAX = EAX * 41 LEA EAX, [EAX * 4 + EAX] ; EAX = EAX * 205

やりだすと本当に奥が深くなります。

続 C# は高級アセンブラ

C# は高級アセンブラの続きです。
何とかして高速化しようと思い試してみました。まずはボツ案から。
あ、はい、ごめんなさい。

---

時計屋さんからこのようなヒントを頂きました。

@haxe メモリが余裕ありそうなので、バケツぶっかけてどーなるか今から試してみよっかなって
— 時計屋 (@NetSeed) December 7, 2013

@haxe ソート自体をO(n)で完了してるんですが、逆に定数が若干多めって言うかなんていうか。。。その辺が問題じゃないかなって
— 時計屋 (@NetSeed) December 7, 2013

これを元にソート方法を見直し…というよりソート行為がほぼ不要になったためについでにzero copyも取り入れたところ、逆にコードがキレイになってしまいました。 スコアも上々で、0.02 / 0.02 / 0.03となりました。

---

更に続きを書きました。続続 C は高級アセンブラ

C# は高級アセンブラ

タイトルに意味はありません。
今、新人女子プログラマの書いたコードを直すだけの簡単なお仕事です！｜というオンラインハッカソンがアツいです。特に野田さんのニーソは素晴らしいです。
私はC#言語しか使えないので頑張って書いてみました。採点結果は0.02秒 / 0.02秒 / 0.05秒の100点になりました。これが私の限界のようなのでgistにソースコードを公開しておこうかと思います。
特筆することはない至極素直なコーディングに心がけましたが…ちょっとだけ解説を。

• Array.Sort()はネイティブコードで実行されるので速いはずですが、Monoの場合マネージコードで実行されます。
• Array.BinarySearch()とMonoのArray.Sort()はComparisonやIComparerで比較されますが、これは組み込みの比較演算子に比べて遅いです。
• もっと言うとIEnumrableは組み込み配列に比べて遅いです。
• stringインスタンス生成にはUnicodeへの変換などが絡むため遅いです。
• そもそもI/Oは遅いので呼び出し回数は可能な限り削減しましょう。
• MSILには４引数、４変数までは個別にオペコードが用意されていますが、それ以上の引数・変数に対してはオペランドでインデックス指定するため１バイトずつ長くなります。結局JITでネイティブのレジスタアクセスに変換されるので、気のせいといえば気のせいですが。

こんなところでしょうか。

---

さらにブレイクスルーがあったので続きを書きました。

IStructuralEquatableの使い方

IStructuralEquatableについて今までいまいちわからずにいました。ググって出てきたページを読んでいたら使い方が微妙で違和感を覚えたためじっくり調べてみました。そうしたらもうちょっと使いやすいものだということがわかりました。
StructuralComparisons.StructuralEqualityComparerはオブジェクトそのものではなく、その要素を比較するIEqualityComparerを提供します。これを使ってIEqualityComparer<T>の実装例を書いてみました。

public class StructuralEqualityComparer<T> : IEqualityComparer<T> where T: IStructuralEquatable { public bool Equals(T x, T y) { return StructuralComparisons.StructuralEqualityComparer.Equals(x, y); } public int GetHashCode(T obj) { return StructuralComparisons.StructuralEqualityComparer.GetHashCode(obj); } }

こう書いてしまえばどう使うのかわかりやすいでしょうか。このサンプルそのものは new StructuralEqualityComparer<int[]>() のように使えます。
なんでこんなクラスをわざわざ作るのかというと、LINQで要求される比較演算子はどれもIEqualityComparerでなくIEqualityComparer<T>だからです。

TransactionScope classの使い方

.NET Frameworkでtransactionを扱うにはTransactionScope classを使いますが、嵌りやすいのでメモっておきます。

class説明にはisolation levelについて記載されていませんが、デフォルトではSerializableになっています。例えばSQL ServerのデフォルトはReadCommittedなので勘違いしてしまいそうです。では、isolation levelを指定しようとすると、constructorにもpropertyにもそれらしいものがありません。実はpublic TransactionScope( TransactionScopeOption scopeOption, TransactionOptions transactionOptions )のTransactionOption classで指定することになります。 しかし今度は余計なparameterまで渡す必要があります。

• TransactionScopeOption…これはRequiredがデフォルトです。
• TransactionOptionsのIsolationLevel…これは指定したかったReadCommittedにします。
• TransactionOptionsのTimeout…これは指定しないと初期化されず0になってしまい、timeoutなしになってしまいます。デフォルトの値にするためにはTransactionManager.DefaultTimeoutを指定します。

結局、

using( var transaction = new TransactionScope( TransactionScopeOption.Required, new TransactionOptions{ IsolationLevel = IsolationLevel.ReadCommitted, Timeout = TransactionManager.DefaultTimeout, } ) ){ ...; transaction.Complete(); }

とやることになるでしょう。

IsDuplicated拡張メソッド

気が向いたので何となく書いてみました。

public static class Enumerable { public bool IsDuplicated<TSource>( this IEnumerable<TSource> source ) { var keys = new HashSet<TSource>(); return !source.All( keys.Add ); } public bool IsDuplicated<TSource, TKey>( this IEnumerable<TSource> source, Func<TSource, TKey> keySelector ) { var keys = new HashSet<TKey>(); return !source.Select( keySelector ).All( keys.Add ); } }

IsDuplicated() つまり重複があるかどうかを判断する拡張メソッドです。
巷にはDistinct()を使ったりして項目数を数えている方法もありますが、数えるということはIEnumerableを最後まで確認する必要があります。

しかし、重複があるかどうか知りたいだけ、同じものが１ヶ所でもダブっていればそれが知りたい、そんなときに最後まで確認するのは無駄です。IsUnique()でなくIsDuplicated()というメソッド名にしたのもそのためです。どうせダブってるんでしょ？ ダブってるなら早く教えてよ、と。

仕組みは簡単。HashSetを使います。HashSet.Add()メソッドは戻り値として重複の有無を教えてくれるのでそれを使います。
更にAll()拡張メソッドは１つでもfalseを見つけると即座に中断して返ってきます。

ImageLockMode.UserInputBuffer | ImageLockMode.WriteOnly

データからBitmapの生成をよくするんですが、だいたいこんなコードを書きます。

byte[] pixels;

var bitmap = new Bitmap( width, height, PixelFormat.Format32bppArgb );
var data = bitmap.LockBits( new Rectangle( 0, 0, width, height ), ImageLockMode.WriteOnly, PixelFormat.Format32bppArgb );
Marshal.Copy( pixels, 0, data.Scan0, pixels.Length );
bitmap.UnlockBits( data );

Marshal.Copy()が無駄に思えたのでImageLockMode.UserInputBufferを使ってみました。するとこんな風に書き換わります。

byte[] pixels;

var bitmap = new Bitmap( width, height, PixelFormat.Format32bppArgb );
bar handle = GCHandle.Alloc( pixcels, GCHandleType.Pinned );
try{
var data = new BitmapData{
PixelFormat = PixelFormat.Format32bppArgb,
Width = width,
Height = height,
Stride = stride,
Scan0 = Marshal.UnsafeAddrOfPinnedArrayElement( pixels, 0 ),
};
bitmap.LockBits( new Rectangle( 0, 0, width, height ), ImageLockMode.UserInputBuffer|ImageLockMode.WriteOnly,
PixelFormat.Format32bppArgb, data );
bitmap.UnlockBits( data );
}
finally{
handle.Free();
}

無駄なコピーが排除できた！ と喜んだものの、処理がかなり遅くなりました…。GCHandle.Alloc()のせいではなく、ImageLockMode.UserInputBufferが原因のようです。

C# 4.0 dynamic その2

というわけでサンプルコードを使って、C# 3.0とC# 4.0とでどのように変わってくるかを説明します。
サンプルは、Outlook 2007の受信トレイ以下のフォルダにある重複メール（Message-Idが一致するメール）をゴミ箱へ移動するコードです。Outlook 2007の新機能Tableオブジェクトを使用しているのでOutlook 2003以前では動作しません。

まずはC# 3.0でのコード

static class Program {
// Outlookを初期化し、受信トレイに対してVisit()を呼びます。
static void Main( string[] args ) {
var application = new Application();
Visit( application.Session.GetDefaultFolder( OlDefaultFolders.olFolderInbox ) );
}

// 各フォルダに対してProcess()を呼びます。また再帰的にフォルダを探索していきます。
static void Visit( MAPIFolder folder ) {
Process( folder );
foreach( MAPIFolder f in folder.Folders )
Visit( f );
}

// ちょっとだけ読みやすくなる拡張メソッドです。
static IEnumerable<Row> AsEnumerable( this Table table ) {
while( !table.EndOfTable )
yield return table.GetNextRow();
}

// 本題の処理です。Message-Id一覧を作成し、重複するものがあったらゴミ箱へ移動します。
static void Process( MAPIFolder folder ) {
var messageIds = new HashSet<string>();
var table = folder.GetTable( null, OlTableContents.olUserItems );
table.Columns.RemoveAll();
table.Columns.Add( "http://schemas.microsoft.com/mapi/proptag/0x1035001E" );
table.Columns.Add( "EntryID" );
var ns = folder.Session;
var trash = ns.GetDefaultFolder( OlDefaultFolders.olFolderDeletedItems );
foreach( var row in table.AsEnumerable() )
if( !messageIds.Add( (string)row[1] ) ) {
MailItem mailItem = (MailItem)ns.GetItemFromID( (string)row[2], null );
Console.WriteLine( "{0}", mailItem.Subject );
mailItem.Move( trash );
}
}
}

続いてC# 4.0でのコード。違いがあるのはProcess()メソッドだけです。

static void Process( MAPIFolder folder ) {
var messageIds = new HashSet<string>();
var table = folder.GetTable( TableContents: OlTableContents.olUserItems );
table.Columns.RemoveAll();
table.Columns.Add( "http://schemas.microsoft.com/mapi/proptag/0x1035001E" );
table.Columns.Add( "EntryID" );
var ns = folder.Session;
var trash = ns.GetDefaultFolder( OlDefaultFolders.olFolderDeletedItems );
foreach( var row in table.AsEnumerable() )
if( !messageIds.Add( row[1] ) ) {
MailItem mailItem = ns.GetItemFromID( row[2] );
Console.WriteLine( "{0}", mailItem.Subject );
mailItem.Move( trash );
}
}

まず、デフォルト引数に対応したため、本質的でないnull引数を記述しなくてもよくなっています。

次に、row[1]とrow[2]の実体はstring型ですが宣言はobject型でした。C# 4.0ではここがdynamic型になっているため、明示的なキャストなしでメソッド引数に使えます。
ns.GetItemFromID()の戻り値もobjectがdynamicに変わっています。実体はCOMオブジェクトです。dynamicのまま扱ってもSubjectプロパティやMove()メソッドは呼び出せますが、MailItem型ということがわかっていますのでキャストしています。その際にも明示的にキャスト式を書く必要はありません。

C# 4.0 dynamic

Visual Studio 2010 beta1で遊んでいます。
C# 4.0および.NET Framework 4.0で提供されるdynamicキーワードについて誤解していました。

dynamic宣言した変数はメソッド呼び出しを行っても、実行時にバインドされます。
ここまでは合ってます。

誤解していたのは、ソースコード上で明示的に宣言したもののみがdynamic変数になると考えていました。（object→dynamicにキャストするイメージでした。）しかし、Visual Studio 2010で試していてわかったのですが、PIAなどのクラスメソッドの戻り値がそもそもdynamicになっています。（C# 3.0まではobject型）
なので、今までstringなどの変数に代入するためにはobject→stringの明示的なキャストが必要でした。C# 4.0ではdynamicになっているため、stringに代入しようとするだけで自動的にキャストされます。C# 3.0のvarで受けた場合、dynamicのままでした。

文字だけなのでイメージがわきづらいですが、PIAを使った場合に思った以上にdynamicの恩恵が受けられそうです。

サンプルコードでも書けばわかりやすいかな？

DataContractJsonSerializerでDictionaryを表現

DataContractJsonSerializerはまじめなので、.NETとJSONとの双方向で型が復元されることを前提にしています。そのため、Dictionary<TKey,TValue>を素直にobject表現してくれません。（TKeyがstringに限定され、intなどが復元できないため。TValueの型が不明なため。）
具体的にどうなるかというと

new Dictionary<string,object>{ { "abc", 1 }, { "def", "ghi" } };

は

[{"Key":"abc","Value":1},{"Key":"def","Value":"ghi"}]

になります。
一般的にJSONを扱う人は

{"abc":1,"def":"ghi"}

を期待していることでしょう。

どうにかしたいと思い、必死に対策を考え、遂に実現しました。

class Surrogate: IDataContractSurrogate {
[Serializable]
class JsonDictionary: ISerializable {
Dictionary<string, object> Dictionary { get; set; }
public JsonDictionary( Dictionary<string, object> dictionary ) {
Dictionary = dictionary;
}
public void GetObjectData( SerializationInfo info, StreamingContext context ) {
foreach( var pair in Dictionary )
info.AddValue( pair.Key, pair.Value );
}
}

public Type GetDataContractType( Type type ) {
return type == typeof( Dictionary<string, object> ) ? typeof( JsonDictionary ) : type;
}
public object GetObjectToSerialize( object obj, Type targetType ) {
var dictionary = obj as Dictionary<string, object>;
if( obj == null )
throw new NotImplementedException();
return new JsonDictionary( dictionary );
}

#region NotImplemented
object IDataContractSurrogate.GetCustomDataToExport( Type clrType, Type dataContractType ) {
throw new NotImplementedException();
}
object IDataContractSurrogate.GetCustomDataToExport( MemberInfo memberInfo, Type dataContractType ) {
throw new NotImplementedException();
}
object IDataContractSurrogate.GetDeserializedObject( object obj, Type targetType ) {
throw new NotImplementedException();
}
void IDataContractSurrogate.GetKnownCustomDataTypes( Collection<Type> customDataTypes ) {
throw new NotImplementedException();
}
Type IDataContractSurrogate.GetReferencedTypeOnImport( string typeName, string typeNamespace, object customData ) {
throw new NotImplementedException();
}
CodeTypeDeclaration IDataContractSurrogate.ProcessImportedType( CodeTypeDeclaration typeDeclaration, CodeCompileUnit compileUnit ) {
throw new NotImplementedException();
}
#endregion
}

あとはDataContractJsonSerializerコンストラクタのIDataContractSurrogate引数にSurrogateインスタンスを渡せば、変換してくれます。
もちろん型保証が外れるため、deserializeはできません。

ファイルの高速コピー

Webサイトのコンテンツを更新するとき、ローカルディスクからWebサーバにアップロード（ファイルのコピー）をしていますが、ファイル数が多くてExplorerじゃとてもとても。
調べたところFastCopyとかコピーツールがありましたが、ふとC#で書いてみたらどうなるんだろう、と。

static void Copy( FileInfo source, FileInfo destination ) {
var src = new FileStream( source.FullName, FileMode.Open, FileAccess.Read, FileShare.None, 4096, true );
var buffer = new byte[ source.Length ];
src.BeginRead( buffer, 0, buffer.Length, rar => {
src.EndRead( rar );
src.Close();
if( destination.Exists )
destination.Attributes &= ~FileAttributes.ReadOnly;
var dst = new FileStream( destination.FullName, FileMode.Create, FileAccess.Write, FileShare.None, 4096, true );
dst.BeginWrite( buffer, 0, buffer.Length, war => {
　 dst.EndWrite( war );
dst.Close();
}, null );
}, null );
}
static void Copy( DirectoryInfo source, DirectoryInfo destination ) {
if( !destination.Exists )
destination.Create();
foreach( var src in source.GetDirectories() )
Copy( src, new DirectoryInfo( Path.Combine( destination.FullName, src.Name ) ) );
var srcfiles = source.GetFiles();
foreach( var dst in destination.GetFiles() )
if( !srcfiles.Any( src => String.Equals( src.Name, dst.Name, StringComparison.OrdinalIgnoreCase ) ) )
dst.Delete();
foreach( var src in srcfiles )
Copy( src, new FileInfo( Path.Combine( destination.FullName, src.Name ) ) );
}
static void Main( string[] args ) {
Copy( new DirectoryInfo( args[ 0 ] ), new DirectoryInfo( args[ 1 ] ) );
}

まずはお試しで、属性やタイムスタンプなどは保存しませんが。
で、コピー時間ですがFastCopyが740秒なのに対して、C#は200秒…。
何も考えずに並列でファイルオープンしているためハンドル数やバッファサイズなど問題点はいろいろあるとは思いますが、この所要時間の差はいったい…？！
ちなみにこのコード、途中に1回だけ30秒間ストールが発生しています。この問題を解決すれば更に30秒短くなるはず…。

ArraySegment classと拡張メソッド

C#で部分配列を扱いたくなったとき、unsafe fixedしてpointerを使うこともできますが、ArraySegment classでがんばってみようと思いました。ところがArraySegmentにはインデクサなどのアクセッサが用意されてなく扱いづらいです。

var array = new int[10];
var segment = new ArraySegment<int>( array, 5, 5 );
segment.Array[ segment.Offset + 3 ]; // array[8] 相当

ここで拡張メソッドを思い出しました。といっても拡張インデクサは実装できません。気を取り直してArray.GetValue()やArray.SetValue()の真似をしてみました。

public static class ArraySegmentUtility{
public static T GetValue<T>( this ArraySegment<T> segment, int index ){
return segment.Array[ segment.Offset + index ];
}
public static void SetValue<T>( this ArraySegment<T> segment, T value, int index ){
segment.Array[ segment.Offset + index ] = value;
}
}

こうすれば最初の例は

segment.GetValue( 3 );

おおいい感じ。
早速使ってみよう…

segment.Array[ segment.Offset + i ] ^= x;

ぽか～ん。アクセッサが用意されてない理由がわかった気がする…。

演算子の優先順位

自分でも呆れるくらいのミスを…
演算子の優先順位を勘違いしてました。
シフト演算<<や>>よりも先に二項演算子＋や－が結合されるんですね。

SslStream

Boost.Asioを書いたけど、.NET Frameworkにも同様にSslStreamクラスが用意されている。
使い方もほぼ同じで

var c = new TcpClient( "ホスト名", 443 );
var s = new SslStream( c.GetStream() );

s.AuthenticateAsClient( "ホスト名" );

s.Write( Encoding.Default.GetBytes( "GET / HTTP/1.0\r\n\r\n" ) );

var r = new StreamReader( s, Encoding.Default );
Console.WriteLine( r.ReadToEnd() );

こんな感じ。違いは

• Windows環境ではgetservbyname()が信用できないので直接443と書いている点
• .NET FrameworkはByteとCharを区別しているので明示的な変換が必要になる点
• Byte→Char変換を中断するのは面倒くさいのでReadToEnd()ですべて読み込んでしまっている点

でしょうか。

??演算子

C#で??演算子というものを見つけました。調べたところ、C# 2.0、つまりVS2005からあったそうで、ずっと気づいていませんでした。

a = b ?? c;

は

a = b != null ? b : c;

とほぼ等価です。違うのは、bが１回しか評価されないことです。Perlの||的な動きをすると言えばいいでしょうか。