続続 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

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