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秒存在していることになります。ソースコードはこちら。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| using System.Runtime.InteropServices; | |
| static class CsPoh { | |
| static int Calculate(byte[] buffer, byte[] prices) { | |
| int ii = 0, oi = 0, temp; | |
| var itemCount = 0; | |
| while ((temp = buffer[ii++] - '0') >= 0) | |
| itemCount = itemCount * 10 + temp; | |
| var days = 0; | |
| while ((temp = buffer[ii++] - '0') >= 0) | |
| days = days * 10 + temp; | |
| do { | |
| var price = 0; | |
| while ((temp = buffer[ii++] - '0') >= 0) | |
| price = price * 10 + temp; | |
| prices[price] = 1; | |
| } while (--itemCount > 0); | |
| var low0 = 10; | |
| while (prices[low0] == 0) | |
| low0++; | |
| do { | |
| var targetPrice = 0; | |
| while ((temp = buffer[ii++] - '0') >= 0) | |
| targetPrice = targetPrice * 10 + temp; | |
| var low = low0; | |
| var high = targetPrice - low0; | |
| while (prices[high] == 0) | |
| high--; | |
| var price = 0; | |
| do { | |
| temp = low + high; | |
| if (temp == targetPrice) { | |
| price = targetPrice; | |
| break; | |
| } | |
| if (temp < targetPrice) { | |
| if (price < temp) | |
| price = temp; | |
| while (prices[++low] == 0) | |
| ; | |
| } else | |
| while (prices[--high] == 0) | |
| ; | |
| } while (low < high); | |
| if (100000 <= price) | |
| goto l100000; | |
| if (10000 <= price) | |
| goto l10000; | |
| if (1000 <= price) | |
| goto l1000; | |
| goto l100; | |
| l100000: | |
| buffer[oi++] = (byte)('0' + Math.DivRem(price, 100000, out price)); | |
| l10000: | |
| buffer[oi++] = (byte)('0' + Math.DivRem(price, 10000, out price)); | |
| l1000: | |
| buffer[oi++] = (byte)('0' + Math.DivRem(price, 1000, out price)); | |
| l100: | |
| buffer[oi++] = (byte)('0' + Math.DivRem(price, 100, out price)); | |
| buffer[oi++] = (byte)('0' + Math.DivRem(price, 10, out price)); | |
| buffer[oi++] = (byte)('0' + price); | |
| buffer[oi++] = 10; | |
| } while (--days > 0); | |
| return oi; | |
| } | |
| [DllImport("libc")] | |
| static extern int read(int fd, IntPtr buf, int count); | |
| [DllImport("libc")] | |
| static extern int write(int fd, IntPtr buf, int count); | |
| static void Main() { | |
| const int valueLength = 2 + 200000 + 75; | |
| var buffer = new byte[valueLength * 7]; | |
| var handle = GCHandle.Alloc(buffer, GCHandleType.Pinned); | |
| var pbuf = Marshal.UnsafeAddrOfPinnedArrayElement(buffer, 0); | |
| read(0, pbuf, valueLength * 7); | |
| var length = Calculate(buffer, new byte[1000001]); | |
| write(1, pbuf, length); | |
| handle.Free(); | |
| } | |
| } |
ところでこの記事のタイトル「高級アセンブラ」ですが、どうも「私が『高級アセンブラ』とは『単にプリミティブっぽい処理を並べること』と解釈している」と誤解されている方がいるようなので説明しておきます。
私なりの解釈では高級アセンブラとは、その言語のコードから生成されるアセンブリが容易に想像でき、また生成されるアセンブリ内容を制御すべくコーディングすることにあると考えています。
例えば初回に公開したコードにはコメントに「引数4、変数4なので効率よく参照可能。」とあるようにレジスタ割り付けを考慮したコーディングを行っています。（C言語であればコンパイラにレジスタ割り付けを指示するregisterキーワードが存在しました。）
と言うだけでは何なので、C言語でも書いてみました。スコアは普通に0.01 / 0.01 / 0.01です。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #ifdef _MSC_VER | |
| #define IO_H "io.h" | |
| #define _CRT_NONSTDC_NO_WARNINGS | |
| #define __attribute__(X) | |
| #else | |
| #define IO_H "unistd.h" | |
| #define __pragma(X) | |
| #define __declspec(X) | |
| #define __fastcall | |
| #endif | |
| #include IO_H | |
| __pragma(code_seg(".text")) __declspec(allocate(".text")) const char calculate[] __attribute__((section(".text#"))) = { | |
| 0x53, | |
| 0x51, | |
| 0x56, | |
| 0x57, | |
| 0x55, | |
| 0x8b, 0xf1, | |
| 0x8b, 0xf9, | |
| 0x8b, 0xea, | |
| 0x33, 0xc9, | |
| 0x0f, 0xb6, 0x06, | |
| 0x46, | |
| 0x83, 0xe8, 0x30, | |
| 0x72, 0x08, | |
| 0x8d, 0x0c, 0x89, | |
| 0x8d, 0x0c, 0x48, | |
| 0xeb, 0xef, | |
| 0x33, 0xdb, | |
| 0x0f, 0xb6, 0x06, | |
| 0x46, | |
| 0x83, 0xe8, 0x30, | |
| 0x72, 0x08, | |
| 0x8d, 0x1c, 0x9b, | |
| 0x8d, 0x1c, 0x58, | |
| 0xeb, 0xef, | |
| 0x33, 0xd2, | |
| 0x0f, 0xb6, 0x06, | |
| 0x46, | |
| 0x83, 0xe8, 0x30, | |
| 0x72, 0x08, | |
| 0x8d, 0x14, 0x92, | |
| 0x8d, 0x14, 0x50, | |
| 0xeb, 0xef, | |
| 0xc6, 0x44, 0x15, 0x00, 0x01, | |
| 0xe2, 0xe6, | |
| 0xb9, 0x09, 0x00, 0x00, 0x00, | |
| 0x41, | |
| 0x80, 0x7c, 0x0d, 0x00, 0x00, | |
| 0x74, 0xf8, | |
| 0x33, 0xd2, | |
| 0x0f, 0xb6, 0x06, | |
| 0x46, | |
| 0x83, 0xe8, 0x30, | |
| 0x72, 0x08, | |
| 0x8d, 0x14, 0x92, | |
| 0x8d, 0x14, 0x50, | |
| 0xeb, 0xef, | |
| 0x51, | |
| 0x53, | |
| 0x57, | |
| 0x8b, 0xfa, | |
| 0x2b, 0xf9, | |
| 0xeb, 0x01, | |
| 0x4f, | |
| 0x80, 0x7c, 0x3d, 0x00, 0x00, | |
| 0x74, 0xf8, | |
| 0x33, 0xdb, | |
| 0x8d, 0x04, 0x39, | |
| 0x3b, 0xc2, | |
| 0x74, 0x1f, | |
| 0x77, 0x0f, | |
| 0x3b, 0xc3, | |
| 0x0f, 0x47, 0xd8, | |
| 0x41, | |
| 0x80, 0x7c, 0x0d, 0x00, 0x00, | |
| 0x74, 0xf8, | |
| 0xeb, 0x08, | |
| 0x4f, | |
| 0x80, 0x7c, 0x3d, 0x00, 0x00, | |
| 0x74, 0xf8, | |
| 0x3b, 0xf9, | |
| 0x77, 0xdc, | |
| 0x8b, 0xc3, | |
| 0x5f, | |
| 0x5b, | |
| 0x3d, 0xa0, 0x86, 0x01, 0x00, | |
| 0x73, 0x15, | |
| 0x3d, 0x10, 0x27, 0x00, 0x00, | |
| 0x73, 0x1c, | |
| 0x3d, 0xe8, 0x03, 0x00, 0x00, | |
| 0x73, 0x23, | |
| 0x83, 0xf8, 0x64, | |
| 0x73, 0x2c, | |
| 0xeb, 0x34, | |
| 0x33, 0xd2, | |
| 0xb9, 0xa0, 0x86, 0x01, 0x00, | |
| 0xf7, 0xf1, | |
| 0x0c, 0x30, | |
| 0xaa, | |
| 0x8b, 0xc2, | |
| 0x33, 0xd2, | |
| 0xb9, 0x10, 0x27, 0x00, 0x00, | |
| 0xf7, 0xf1, | |
| 0x0c, 0x30, | |
| 0xaa, | |
| 0x8b, 0xc2, | |
| 0x33, 0xd2, | |
| 0xb9, 0xe8, 0x03, 0x00, 0x00, | |
| 0xf7, 0xf1, | |
| 0x0c, 0x30, | |
| 0xaa, | |
| 0x8b, 0xc2, | |
| 0xb1, 0x64, | |
| 0xf6, 0xf1, | |
| 0x0c, 0x30, | |
| 0xaa, | |
| 0x0f, 0xb6, 0xc4, | |
| 0xb1, 0x0a, | |
| 0xf6, 0xf1, | |
| 0x66, 0x0d, 0x30, 0x30, | |
| 0x66, 0xab, | |
| 0xc6, 0x07, 0x0a, | |
| 0x47, | |
| 0x59, | |
| 0x4b, | |
| 0x0f, 0x85, 0x4c, 0xff, 0xff, 0xff, | |
| 0x8b, 0xc7, | |
| 0x5d, | |
| 0x5f, | |
| 0x5e, | |
| 0x59, | |
| 0x5b, | |
| 0x2b, 0xc1, | |
| 0xc3, | |
| }; | |
| #define VALUE_LENGTH (2 + 500000 + 300) | |
| int main() { | |
| static char buffer[VALUE_LENGTH * 7] = {0}; | |
| static char prices[1000001] = {0}; | |
| read(0, buffer, VALUE_LENGTH * 7); | |
| int length = (*(int(__fastcall __attribute__((fastcall)) *)(char *, char *))calculate)(buffer, prices); | |
| write(1, buffer, length); | |
| return 0; | |
| } |
その他、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命令が視野に入ってきます。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やりだすと本当に奥が深くなります。
0 件のコメント:
コメントを投稿