2014年6月9日月曜日

艦これ 司令部室について

F# 談話室の15回に参加し、艦これ 司令部室について発表してきました。これに合わせてGitHubでリポジトリも公開しました。
COMの素晴らしさを力説し、また布教してきました。比較的に好感触でした。
たいしたことをは書いていませんが、発表に使ったプレゼンテーションはこちら

時刻: 22:50 0 コメント

ラベル: , ,

2014年3月12日水曜日

WinFormsのTextBox ControlでのIME制御

WinFormsのTextBox Controlの話題です。とても基本的なControlですが落とし穴がありました。IMEで漢字変換中にフォーカスを失うと未確定文字はそのままIMEが持って行ってしまいます。 WinFormsがこのような挙動をすることを知らず何も制御していなかったために、自作のアプリケーションがクソ呼ばわりされる事態に陥ってしまいました。 とても悲しかったのでTextBoxを派生して挙動を改良してみました。 IMEが開いているかどうかはImeContext.IsOpen()で調べることができますが、そのあと同じハンドルを使用して処理することになるため、IsOpenは使いませんでした。

時刻: 23:58 0 コメント

ラベル:

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秒存在していることになります。ソースコードはこちら。
ところでこの記事のタイトル「高級アセンブラ」ですが、どうも「私が『高級アセンブラ』とは『単にプリミティブっぽい処理を並べること』と解釈している」と誤解されている方がいるようなので説明しておきます。
私なりの解釈では高級アセンブラとは、その言語のコードから生成されるアセンブリが容易に想像でき、また生成されるアセンブリ内容を制御すべくコーディングすることにあると考えています。
例えば初回に公開したコードにはコメントに「引数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
やりだすと本当に奥が深くなります。

時刻: 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# は高級アセンブラの続きです。
何とかして高速化しようと思い試してみました。まずはボツ案から。
あ、はい、ごめんなさい。

時計屋さんからこのようなヒントを頂きました。
これを元にソート方法を見直し…というよりソート行為がほぼ不要になったためについでにzero copyも取り入れたところ、逆にコードがキレイになってしまいました。 スコアも上々で、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 コメント

ラベル:

登録: 投稿 (Atom)