2013年12月14日土曜日

続続 C は高級アセンブラ

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

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

ところでこの記事のタイトル「高級アセンブラ」ですが、どうも「私が『高級アセンブラ』とは『単にプリミティブっぽい処理を並べること』と解釈している」と誤解されている方がいるようなので説明しておきます。
私なりの解釈では高級アセンブラとは、その言語のコードから生成されるアセンブリが容易に想像でき、また生成されるアセンブリ内容を制御すべくコーディングすることにあると考えています。
例えば初回に公開したコードにはコメントに「引数4、変数4なので効率よく参照可能。」とあるようにレジスタ割り付けを考慮したコーディングを行っています。（C言語であればコンパイラにレジスタ割り付けを指示するregisterキーワードが存在しました。）
と言うだけでは何なので、C言語でも書いてみました。スコアは普通に0.01 / 0.01 / 0.01です。
#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;
}
view raw CPoh.c hosted with ❤ by GitHub
なお、しょうもないところでは #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
やりだすと本当に奥が深くなります。

時刻: 1:31 0 コメント

ラベル: , ,

F# と OCaml

　この記事はF# Advent Calendar 2013に参加しています。14日目を担当させてもらいます。

F#とは

F#についてはMSDNでは
F# は、従来のオブジェクト指向プログラミングと命令型 (手続き型) プログラミングに加えて、関数型プログラミングをサポートするプログラミング言語です。 Visual F# 製品は、F# アプリケーションの開発と F# コードを使用した他の .NET Framework アプリケーションの拡張をサポートします。 F# は、.NET Framework 言語のファースト クラスのメンバーであり、関数型言語の ML ファミリに著しく似ています。
…と説明されています。MLファミリと書かれていますが、中でもオブジェクト指向的要素が追加されたOCamlとはかなりの類似点していて、F#で提供されるコアライブラリの基本部分はOCamlのモジュールと一致しています。そこでOCamlとF#の違い、その理由について探ってみようと思います。

F#とOCamlの違い

何よりも大きいのはオブジェクトおよびガベージコレクタでしょうか。F#は.NET Framework上で動作するため、すべてのオブジェクトは.NETオブジェクトでありSystem.Objectの派生クラスです。このことは全てのオブジェクトはSystem.Typeを通じてRTTI; Run-Time Type Infomationが得られることを意味します。対してOCamlは独自のGCでありSystem.TypeのようなRTTIは提供されていません。元々コンパイル時に型チェックされているため、実行時に型情報は不要なわけです。そのため実行時にObj.magicを用いてデータを強引にキャストしてしまうこともできます。これはC++言語でいうreinterpret_castであり、F# / .NETでは不可能な行為です。
　構文に対する細かい優先順位もところどころ違います。もちろん構文の違いといえばF#には独自の軽量構文がありますし私自身便利に使っていますが、OCamlとの比較においては論外ということで、それ以外について。 F#では.NET Frameworkで提供されるnamespaceが扱え、「.」(ピリオド)で区切ります。更にプロパティやメソッドも「.」でつながれ、正しいメンバー参照である限りどこまででもつなぐことができます。例えばSystem.String.Empty.Count.ToString()とか。しかしOCamlではUIDとLIDしかありません。UIDとは大文字から始まる識別子、LIDとは小文字から始まる識別子です。先ほどのObj.magicはObjがUIDでmagicがLIDとなります。namespaceはなくクラスメソッド参照は「#」となるため「.」の優先順位が異なります。
　構文といえば独自に新しい演算子が作成できる点、これはF#とOCamlと共通で、通常の.NET Frameworkからするとかなり異質な行為です。逆にコンピュテーション式はF#独自の機能です。コンピュテーション式内は通常のF#構文のままですが、書かれた式は直接コンパイルされるのではなく、構文解析後、コンピュテーション式のビルダークラスのメソッド呼び出しへと変換されてコンパイルされます。このような機能はOCamlにはありません。
　…というのは嘘で、Camlp4という特殊なモジュールがあります。Camlp4とはPre-Processor-Pretty-Printer for OCamlという意味です。一般的にコンパイラというのは、構文パーサーがソースコードからAST; Abstract Syntax Treeを構築し、ASTを何等かのバイナリに変換を行います。OCamlでは通常の構文パーサー以外にCamlp4が提供する別のParserに差し替えることが可能です。といってもただ構文パーサーを差し替えても同じ構文しか使えないのでは実装が２種類あるだけ何も面白くありません。独自のParserを作成しそれに差し替えることもできます。 ただし、独自のParserを全て作り上げるのは大変なことなので、新たに構文を増やさないのであればFilterというASTを別のASTに変換する機能もあります。これはF#のコンピュテーション式に近い行為ですが、どのように変換するかをプログラム的に制御できるため自由度は高いです。 また、ParserとFilterまで用意するならついでということでPrinterも用意されています。こちらはASTをコンパイルするのではなく別のデータ形式に変換することができます。それ以外にもいろいろありますが、あまり詳しくないのでこの辺りまでで。
　実はCamlp4はRevisedというOCamlとは別の構文で書かれています。つまりCamlp4をコンパイルするにはCamlp4のRevised Parserが必要であり、ある種のセルフホスト状態になっています。なぜそうなっているかというとOCamlの構文が気に食わないそうで、funとfunctionは同じものだからキーワードを分ける意味がないとか、変数と関数を同じletにすべきではないとか、どこかに書かれていました。

FSharp Printer for Camlp4

というわけで、Camlp4に含まれているOCaml Printerを元にFSharp Printerを作ってみました。Camlp4がparse可能なソースコードをF#コードに変換して出力できることになります。patch形式にしているのは、修正個所がわかりやすくなるのとASTの変更に追従を考えて、ですが…無意味かな？
　先に使い方を説明しておくと、コンパイルするにはコンパイラとパッチ元ファイルのバージョンを一致させる必要があります。現時点でリポジトリに含めているのは4.01.0向けのソースになります。コンパイル方法は、通常のOCamlと少し異なり、Camlp4を使います。
$ ocamlc -I +camlp4 -pp camlp4rf -c Camlp4FSharpPrinter.ml
でCamlp4FSharpPrinter.cmoが生成されます。
　使うためにはこのファイルを参照可能なディレクトリならどこでも構わないですがとりあえず、
$ cp Camlp4FSharpPrinter.cmo $ocaml/lib/camlp4/Camlp4Printers/
とコピーします（尚、パッチ元のOCaml.mlのあるディレクトリとは別です）。その上で、OCamlソースコードをF#コードに変換するには
$ camlp4of -printer Camlp4FSharpPrinter -o fsharp-source.ml ocaml-source.ml
と実行します。
　ということでコードをペタペタ。

F#とOCamlの違い

またですが…FSharp Printerを作っていて気づいた点をいくつか。
　F#の軽量構文はインデントで表現するため、メンバーの無いクラスを表現することができません。ごくまれに存在するmarker interfaceのようなことが表現できなくて困ったりします。こういう場合でも冗長構文なら表現することができます。
　OCamlはモジュールをまたぐ構造体メンバーアクセスの際にはモジュール名を挟みます。someObject.ModuleName.memberNameという感じにいきなりモジュール名が出現するため心臓に悪いです（最初の方に書いたUID / LIDはこのことです）。F#では型情報は全て把握できているためsomeObject.memberNameになります。
　F#では配列を含むindexerが全て .[] 演算子で表現されます。そのため .[] が出現した時点でindexerの存在する型に確定していないとコンパイルできません。対してOCamlにはindexerという汎用的な概念はなく、配列要素にアクセスする .() と文字列にアクセスする .[] のみとなっています。つまり、F#とは逆でこれらの演算子から型推論することができます。この型推論条件の違いを埋め合わせるために、FSharp PrinterではArray.get / String.getに置き換えています。
　OCamlの==演算子、!=演算子も困ったことに。単純に=演算子、<>演算子に置き換えることはできません。とりあえずわかる範囲でパターンマッチに展開することにしました。この辺りの細かいOCamlの動作（及びそれに相当するF#のコード）はよくわかっていません。
　OCamlはパターンマッチに'0'..'9'のように文字範囲を表現することができますがF#にはありません。こちらはwhen句に展開しています。
　F#ではクラス内のletはprivateスコープですが、OCamlはいわゆるprotectedスコープであり派生クラスから参照可能です。こういった違いはさすがにFSharp Printerで埋め合わせることはできません。コンストラクターの書式も違いますがこちらは結構強引に対応させています。
　もっと大きな問題として、OCamlにあってF#に存在しないモジュールの呼び出し…これについてはF# PowerPackを使ってください。
　最後にどうにもならない爆弾を…。F#というか.NETには値型があるため効率のいい配列操作ができますが、OCamlはこれができません。そのため、stringがbyte arrayのように使われています。つまりOCamlのstringはmutableです。対してF#のstringはimmutableです。この違いはどうにも吸収できません。OCamlソースをF#に移植する際には、mutableに扱われているstringをbyte[]に変換するところから始まると言ってもいいでしょう。

以上、とりとめもないF#とOCamlの比較でした！ Camlp5…？ 知らない子ですね。

ところでこのblogのテーマ読み辛い…。元々Pタグでレイアウトするつもりでスタイルを書いてたのに、エディターが更新されてDIVタグ＆BRタグしか埋めてくれない…。

時刻: 0:07 0 コメント

ラベル: ,

2013年12月9日月曜日

続 C# は高級アセンブラ

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

<#@ template debug="false" hostspecific="true" language="C#" #>
<#@ assembly name="System.Core" #>
<#@ import namespace="System.IO" #>
<#@ import namespace="System.Linq" #>
<#@ output extension=".cs" #>
using System.Reflection;
class UnsafePoh {
static readonly byte[] bytes = new byte[]{
<#= string.Join(Environment.NewLine, File.ReadAllBytes(Host.ResolvePath("Unsafe.dll")).Select((b, i) => new { b, i }).GroupBy(a => a.i / 16, a => string.Format("0x{0:X2}, ", a.b), (_, g) => string.Concat(g))) #>
};
static void Main() {
Assembly.Load(bytes).GetType("Unsafe").InvokeMember("Main", BindingFlags.Public|BindingFlags.Static|BindingFlags.InvokeMethod, null, null, null);
}
}
view raw gistfile1.cs hosted with ❤ by GitHub
あ、はい、ごめんなさい。
時計屋さんからこのようなヒントを頂きました。
これを元にソート方法を見直し…というよりソート行為がほぼ不要になったためについでにzero copyも取り入れたところ、逆にコードがキレイになってしまいました。
using System;
static class CsPoh {
static int Calculate(byte[] input, byte[] prices, byte[] output) {
int ii = 0, temp, oi = 0, price;
var itemCount = 0;
while ((temp = input[ii++] - '0') >= 0)
itemCount = itemCount * 10 + temp;
var days = 0;
while ((temp = input[ii++] - '0') >= 0)
days = days * 10 + temp;
while (--itemCount >= 0) {
price = 0;
while ((temp = input[ii++] - '0') >= 0)
price = price * 10 + temp;
prices[price] = 1;
}
var low0 = 10;
while (prices[low0] == 0)
low0++;
while (--days >= 0) {
var targetPrice = 0;
while ((temp = input[ii++] - '0') >= 0)
targetPrice = targetPrice * 10 + temp;
price = 0;
/* TODO: 同一価格商品２つにはならない模様
if (targetPrice % 2 == 0 && prices[targetPrice / 2] > 1)
price = targetPrice;
else */ {
var low = low0;
var high = targetPrice - low;
while (prices[high] == 0)
high--;
do {
temp = low + high;
if (temp == targetPrice) {
price = temp;
break;
}
if (temp < targetPrice) {
if (price < temp)
price = temp;
while (prices[++low] == 0)
;
} else
while (prices[--high] == 0)
;
} while (low < high);
}
#if true
/* TODO: 商品は必ず見つかり 0 にならない模様
if (price == 0)
output[oi++] = (byte)'0';
else */ {
temp = 100000 <= price ? 1000000 <= price ? 1000000
: 100000
: 10000 <= price ? 10000
: 1000 <= price ? 1000
: 100 <= price ? 100
: 10;
do {
output[oi++] = (byte)('0' + price / temp);
price %= temp;
temp /= 10;
} while (temp > 1);
output[oi++] = (byte)('0' + price);
}
#else
if (100000 <= price) {
if ((temp = price / 1000000) > 0) {
output[oi++] = (byte)('0' + temp); price %= 1000000;
}
output[oi++] = (byte)('0' + price / 100000); price %= 100000;
output[oi++] = (byte)('0' + price / 10000); price %= 10000;
output[oi++] = (byte)('0' + price / 1000); price %= 1000;
output[oi++] = (byte)('0' + price / 100); price %= 100;
output[oi++] = (byte)('0' + price / 10); price %= 10;
} else if ((temp = price / 10000) > 0) {
output[oi++] = (byte)('0' + temp); price %= 10000;
output[oi++] = (byte)('0' + price / 1000); price %= 1000;
output[oi++] = (byte)('0' + price / 100); price %= 100;
output[oi++] = (byte)('0' + price / 10); price %= 10;
} else if ((temp = price / 1000) > 0) {
output[oi++] = (byte)('0' + temp); price %= 1000;
output[oi++] = (byte)('0' + price / 100); price %= 100;
output[oi++] = (byte)('0' + price / 10); price %= 10;
} else if ((temp = price / 100) > 0) {
output[oi++] = (byte)('0' + temp); price %= 100;
output[oi++] = (byte)('0' + price / 10); price %= 10;
} else if ((temp = price / 10) > 0) {
output[oi++] = (byte)('0' + temp); price %= 10;
}
output[oi++] = (byte)('0' + price);
#endif
output[oi++] = 10;
}
return oi;
}
static void Main() {
const int valueLength = 2 + 200000 + 75;
var input = new byte[valueLength * 7];
Console.OpenStandardInput().Read(input, 0, valueLength * 7);
var output = new byte[75 * 7];
Console.OpenStandardOutput().Write(output, 0, Calculate(input, new byte[1000001], output));
}
}
view raw CsPoh.cs hosted with ❤ by GitHub
スコアも上々で、0.02 / 0.02 / 0.03となりました。
更に続きを書きました。続続 C は高級アセンブラ

時刻: 8:03 0 コメント

ラベル:

2013年12月6日金曜日

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でネイティブのレジスタアクセスに変換されるので、気のせいといえば気のせいですが。
こんなところでしょうか。
さらにブレイクスルーがあったので続きを書きました。

時刻: 19:02 0 コメント

ラベル:

2013年8月25日日曜日

F#の%a書式指定はとても扱いづらい

F#のPrintfモジュールはある程度の書式指定ができるようになっていますが、基になっているOCamlが貧弱なせいもあってString.Format()ほどの表現力はありません。 何か手はないかと考えたところ %a 書式指定を思い出しました。Core.Printf モジュールには

2 つの引数を必要とする一般的な書式指定子。 1 つ目の引数は、2 つの引数を受け取る関数です。この関数の 1 つ目の引数は、指定した書式設定関数 (TextWriter など) に対応する型のコンテキスト パラメーターです。2 つ目の引数は出力する値であり、この値によって、該当するテキストを出力するか、返すかを指定します。
2 つ目の引数は、出力する特定の値です。

とあります。いまいちわかりづらいので英語版ドキュメントも確認しましたが同じ内容で意味がよくわかりません。念のためOCamlのmodule Printfも確認します。

user-defined printer. Take two arguments and apply the first one to outchan (the current output channel) and to the second argument. The first argument must therefore have type out_channel -> 'b -> unit and the second 'b. The output produced by the function is inserted in the output of fprintf at the current point.

なるほどわかりません。

とりあえずF#で書いてみたところ、非常に面倒くさいことが判明しました。１つ目の引数の説明「TextWriter など」が罠です。 なんとprintfとsprintfとで要求される関数が違いました。具体的に関数を挙げた方がわかりやすいので、現在時刻をコンソール出力してみます。

let formatter_for_printf (textWriter : TextWriter) (dateTime : DateTime) = textWriter.Write("{0:MM/dd HH:mm}", dateTime) let formatter_for_sprintf () (dateTime : DateTime) = String.Format("{0:MM/dd HH:mm}", dateTime) printfn "%a" formatter_for_printf DateTime.Now sprintf "%a" formatter_for_sprintf DateTime.Now |> Console.WriteLine

つまり同じ %a でも

  • printfで出力する時は(TextWriter -> 'T -> unit) 'Tが必要
  • sprintfで出力する時は(unit -> 'T -> string) 'Tが必要

ということのようです。

OCaml側は確認していませんがドキュメントからはそう読み取れないため、F#の（限りなくバグに近い）仕様かなと思います。

時刻: 9:55 0 コメント

ラベル:

2013年5月29日水曜日

DataContractJsonSerializerでDictionaryを表現 再び

以前、DataContractJsonSerializerでDictionaryを表現という記事を書きましたが、あれから４年半経ち時代が変わりました。 .NET Framework 4.5からDataContractJsonSerializer constructorはDataContractJsonSerializerSettings classを引数に取り、このclassはUseSimpleDictionaryFormat propertyを持っています。 そう、つまり…標準機能でDictionaryが表現できるようになっていました。

時刻: 22:50 0 コメント

ラベル: ,

2013年2月16日土曜日

F#の||>演算子について

F#言語仕様には|>演算子と||>演算子と|||>演算子が定義されています。|>演算子はシンボルと演算子のリファレンスにも掲載されていますし、比較的よく使われています。

x |> f
とすると f(x)が実行されるものです。さて残りの２つ、これらは言語仕様には存在だけが記されており、それぞれop_PipeRight2、opPipeRight3にコンパイルされることしかわかりません。調べたところ、これらは
let inline (|>) x f = f x let inline (||>) (x,y) f = f x y let inline (|||>) (x,y,z) f = f x y z
のようなものだということがわかりました。つまり左辺にはタプルを受け、右辺の関数にタプルの値を展開して引数として適用するものです。

結論。高度に発達した関数型言語はググラビリティが非常に高い。（op_PipeRight2でググったけどこの話題が全然見つからなかった…。）

時刻: 15:41 0 コメント

登録: 投稿 (Atom)