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

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

Visual Studio 2010 beta1 C++でのinclude

なんでもVC++が進化しているそうなので試してみたく。
プログラムを書こうとして#include <...>まで書いて気がついた。はてさて、header fileのdirectoryはどう設定するの？

Visual Studio 2008までは ツール - オプション - プロジェクトおよびソリューション - VC++ディレクトリ という設定項目があり、そこにディレクトリを入力できた。が、2010 beta1ではそこがなくなっている。
もちろんプロジェクトのプロパティに設定してもコンパイルできることにはできるが、システムにインストールしたheader fileのdirectoryをプロジェクトごとに書くのはおかしい。

プロジェクトファイルを参照したところ答えがあった。

<ImportGroup Label="PropertySheets">
<Import Project="$(LocalAppData)\Microsoft\VisualStudio\10.0\Microsoft.Cpp.$(Platform).user.props"
Condition="exists('$(LocalAppData)\Microsoft\VisualStudio\10.0\Microsoft.Cpp.$(Platform).user.props')" />
</ImportGroup>

つまり$(LocalAppData)\Microsoft\VisualStudio\10.0\Microsoft.Cpp.$(Platform).user.propsに書けば取り込まれます。

べき乗 pow() xy

ふとべき乗計算を考えてみた。

double pow( double x, int y ){
return y > 0 ? pow( x, y - 1 ) * x : 1;
}

整数の時は簡単。

実数になると

__declspec(noinline) double pow( double x, double y ){
__asm{
fld y
fld x
fyl2x
fst ST(1)
frndint
fxch ST(1)
fsub ST(0), ST(1)
f2xm1
fld1
faddp ST(1), ST(0)
fscale
}
}

なんかinline assemblerを使ってしまった。うん、何やってるのかさっぱりです。命令とそのときのスタック状態を表にすると

命令	ST(0)	ST(1)	ST(2)
fld y	y
fld x	x	y
fyl2x	y×log2x
fst ST(1)	y×log2x	y×log2x
frndint	⌊y×log2x⌋	y×log2x
fxch ST(1)	y×log2x	⌊y×log2x⌋
fsub ST(0), ST(1)	y×log2x-⌊y×log2x⌋	⌊y×log2x⌋
f2xm1	2y×log2x-⌊y×log2x⌋-1	⌊y×log2x⌋
fld1	1	2y×log2x-⌊y×log2x⌋-1	⌊y×log2x⌋
faddp ST(1), ST(0)	2y×log2x-⌊y×log2x⌋	⌊y×log2x⌋
fscale	2y×log2x-⌊y×log2x⌋×2⌊y×log2x⌋

ここで2^{y×log₂x-⌊y×log₂x⌋}×2^{⌊y×log₂x⌋} = 2^{y×log₂x-⌊y×log₂x⌋+⌊y×log₂x⌋} = 2^y×log₂x = x^yです。
はい、さっぱりわかりませんでした。

swprintf()とwsprintf()

Cランタイムライブラリにsprintf()があります。同様の機能を持つwsprintf()がUSER32.dllにもあります。実はsprintf()はntdll.dllにもあります。

これらの関係を整理すると

宣言	DLL	TCHAR.Hのルーチン	ANSI版	Unicode版
tchar.h	MSVCRT90.dll	_stprintf()	sprintf()	swprintf()
windows.h	USER32.dll	wsprintf()	wsprintfA()	wsprintfW()
-	ntdll.dll	-	sprintf()	swprintf()

となります。

ちなみに注意点がいくつか。
swprintf()の第２引数はバッファサイズで書式指定文字列は第３引数にずれています。他のものは第２引数が書式指定文字列です。代わりに他のものと互換のある_swprintf()も第２引数が書式指定文字列になっています。
wsprintf()は指定できる書式に制限があります。例えば浮動小数（%f）がサポートされていません。
ntdll.dllに含まれるsprintf()は使用方法が公開されてなく、サポートされている機能も公開されていません。ただし、全てのプロセスにロードされるDLLなので何かの役に立つかも。

演算子の優先順位

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

fwrite()と改行コード

fwrite()は任意のバイナリデータをstreamに書き込むライブラリ関数だと理解していましたが、今更ながらstreamがテキストモードの場合、任意文字列を書き込むものだと知りました。具体的にはバイナリデータを文字列と見なし、その中からNL（0x0A）をCR-LF（0x0D-0x0A）に置き換えられてはまりました。
テキストとバイナリを混在させたstreamの場合、その都度モードを切り替える必要があるそうです。

FILE* stream;
_setmode( _fileno( stream ), _O_BINARY );