自作行列ライブラリのGSL化

僕は車輪の再発明は大の得意(笑)で、『自作行列ライブラリ』などというものをこさえて使ってきました。しかしこの度、計算が怪しい(固有値分解で、対象が対角行列に近いと収束しないケースがある)や、計算速度をあげたい、という欲求に駆られましたので、表面では自作のライブラリを生かしつつ、裏側でごにょごにょして問題解決する、という方策をとってみることにしました。というと格好良く聞こえるかもしれませんが、実のところインターフェイスを変えてしまうと、今まで作成したプログラムのコードを全て変更しなければならず面倒くさいというのが本音です。

実はこの手の問題には今までチャレンジしたことがあります。というのもこの自作行列ライブラリをDSPに移植する際、高速化のために用意されたアセンブラルーチンに内部的に差し替えるということをしたことがあり、その際はC++言語の機能であるテンプレートの特殊化を使ってコードを差し替えました。

今回も同じ手法をとることにしますが、差し替え先のライブラリとしてGNU Scientific Library(GSL)を利用することにしました。行列演算のみならず、FFTや数値積分といった様々な算術アルゴリズムが用意されていること、OSを問わず使えること(Visual Studioでもコンパイル可能、Brian Gladmanさんが公開しているプロジェクトファイルを利用して構築可能)、Rubyへのポーティングがされていること(Ruby/GSL)、などが決め手になりました。行列についてはBlasのC版(CBlas)を基本にしているようですが、これを用途によって差し替えることによってさらにチューニングが可能であることも魅力です。

結果、できあがったのは元のmatrix.hに対するmatrix_gsl.h、complex.hに対するcomplex_gsl.h(チューニング途中であるため、今後も随時更新予定)です。テンプレートの特殊化によって、中身のアルゴリズムを入れ替えています。また、少しいいことがあってGSL自体はCのライブラリであるため、それ自体を扱おうとするとmalloc/freeをしっかりやる必要があるのですが、自作行列ライブラリについては参照カウンタを利用したフライウェイト・パターンになっているので、今回作成したライブラリを利用する限りはあまりメモリ管理を気にすることなく使えています。

アルゴリズムを実装することは理解も進んで僕にとっては楽しいのですが、一回つまり出すとなかなか前に進めないのが問題です。というわけで世の中の既存のツールをうまく活用できるようにもなりたいものです。

※2009/3/31追加、メモリが一部あふれていたので修正版に差し替えました。

23:59 fenrir が投稿 : 固定リンク |

| | コメント (0) | トラックバック
このエントリーのトラックバックURL: https://fenrir.naruoka.org/mt/mt-tb.cgi/690

C++でリフレクションもどき

物理法則に関係するプログラミングをしていると、変数に人間にわかる名前をつけておかないと大変な事態になります。特にその変数が配列であるときは悲劇で、インデックスが直打ちされている残念なコードを時たま見かけます。このようなコードはインデックスが少し違っただけで計算結果が発散してしまいデバックできなくなることは必至です。
少々経験を積むと、例えばCやC++言語ならdefineマクロやenum(列挙体)等を利用することによって、可読性を高めミスを防止できます。コンパイル時に名前とインデックスの対応関係がプリプロセッサまたはコンパイラによって解決されるためです。
しかし実行時にも似たような事態が発生します。例えば外部から値を取り込んで指定の変数に設定するプログラムがあるとしましょう。文字列として取り込まれた名前とインデックスの対応関係は、defineやenum自体でつけることができないので、ハッシュテーブルなどを使った変換表を別に用意する必要があります。あるいは言語によっては、リフレクションの機能を使うことによって、この対応関係を動的に求めることが可能です。

前置きが長くなりましたが、今回はリフレクションの機能を持たないC++言語で、実行時にも名前からインデックスを引けるような簡単な記述方法を模索してみることにしました。解はいくつかあると思いますが、結果は以下のようになりました。

とりあえず使う分には49行目までを別のヘッダにでも定義しておき、本体には51行目～55行目の4行を書くだけで、1) コードに書いた名前で配列にアクセス、 2) 実行時に外部から取り込んだ名前から配列のインデックスを求め配列にアクセス の両方が実現されています。1) の機能はMAKE_ALIASマクロ内で展開される関数定義によっています。2) の方は少々複雑で、テンプレートの特殊化によって対応しています。内部的にリンクリストを作成することで表引きを可能にしました。

注目なのは、リンクリストを実現するためのテンプレートの特殊化方法です。テンプレートの特殊化を行うのは、通常グローバルスコープ(簡易的に言えばmain()関数と同じレベル)なので、あるクラスの中でテンプレートの特殊化をすることはあまり機会がないと思います。しかしながらそのような方針をとると、MAKE_ALIASマクロを2つのマクロ、すなわち、1)の機能を実現する関数(クラス内にある必要がある)を定義するマクロと 2)の機能を実現するためのテンプレート特殊化マクロ(方針に従うのならクラスの外)に分けなければならなくなります。重要なことなので同じ名前に関して2回定義してもいいのですが(笑)、重複は悪なので1つのマクロにまとめたいという結果が今回のコードです。こうしておくとさらにいいことがあって、クラスの中でこのMAKE_TABLEやMAKE_ALIASマクロを使っても変数定義が同じようにできます。

テクニックとしては、クラスの中でテンプレート特殊化を行うためダミー型(コードではTで表記)を利用した部分特殊化を使っています。実は部分特殊化を使わず、完全特殊化であってもM$系のコンパイラなら通ってしまうのですが、それは独自拡張だそうなので仕様に準拠して部分特殊化としました。『c++スレより「クラスの内側で定義したクラステンプレートを特殊化する」』がとても参考になりました。

なお今回コードを紹介するにあたって利用したCodepadはweb上でコードが実行できる優れものです。とても有用なwebサービスだと思います。

12:27 fenrir が投稿 : 固定リンク |

| | コメント (0) | トラックバック
このエントリーのトラックバックURL: https://fenrir.naruoka.org/mt/mt-tb.cgi/691

RFPDFの高速化、StringIOを使う

RubyでPDFを生成したいと思い、RubyのPDFライブラリを物色していました。結果、プロジェクト管理ツールRedmineのプラグインとして開発されているRFPDFが、使いやすそう、かつ、日本語もある程度扱えるようだったので、使ってみることにしました。しかしながら速度が十分でなかったので、改造を施しパッチを作りました、というのが今回の話です。

クリックするとPDF

生成しようとしていたPDFは上のようなものです。今度の5月に開催されるMake: Tokyo Meeting 03に何かだせたらいいなぁ、ということでネタ出しをしている段階なのですが、それの検証用としして作成していたものです。ビットマップを読み込んで、モザイク画像を生成するスクリプト bmp_tiler.rb (後半に無理やり高速化をかけている痕跡がありますが、笑)で生成しました。円を沢山描きまくるスクリプトです。

このPDFを一枚完成させるのに、当初、およそ2分くらいかかっていました。どう考えても時間が掛かり過ぎておかしいと思ったので、チューニングをしてみることにしました。まずはどこがボトルネックとなっているのか、プロファイルを取ってみました。

このようにすると、何の関数が何回呼び出されて、どれだけ時間がかかっているか一覧で表示されます。実行してみた結果、String#+(文字列の連結)が最も時間がかかっており、10万回以上の呼び出しで120秒以上消費していることがわかりました。かなり以前ですが、Rubyをはじめた頃に、K上さんという方からRubyのString#+は特に遅いので、StringIO#writeを代替に使うといいよ、ということを教えてもらったので、それを実践することにします。

結果、RFPDFでStringIOを使用するようにしたパッチrfpdf_stringio.patchを公開します。これを使うことで、同じ条件下で実行時間を10秒程度にまで短縮することががきました。如何にString#+が遅いかが実感できています。

簡単にString#+とStringIO#writeの違いを体感したければ、以下のスクリプトを実行してみるといいと思います。ノートPC(Core Duo L2400 @ 1.66GHz)で実験したみたところ、100000回呼び出しでString#+が14.39秒、StringIO#writeが1.24秒でした。

このような話はRubyに限らず広くある話で、文字列の連結なら、JavaだとStringの代わりにStringBufferを使いましょう(もしかしたら今は最適化のお陰で効果はないかも?、Javaは久しく触っていません)とか、C++だとstringの代わりにstrstreamを使いましょう、といったことが知られていると思います。RubyのString#+が遅いのは、推測なのですが、GCが絡んでいる?とか、中でハッシュ値を計算しなおしている?(同一内容のStringはインスタンスが一つでシングルトンになっているんじゃなかったっけ?)あたりではないかと思います。もし正確なことをご存知の方がいましたら、つっこみお待ちしています(ソース読め、という話ですが、笑)。

10:57 fenrir が投稿 : 固定リンク |

| | コメント (2) | トラックバック
このエントリーのトラックバックURL: https://fenrir.naruoka.org/mt/mt-tb.cgi/692

Eclipseでgitプラグインの使い方

統合開発環境Eclipseを使って、gitで運用しているプロジェクトを扱っているのですが、gitプラグインの使い方がよくわからなかったので、一連の動作について試行錯誤した結果をメモとして残しておこうと思います。なおgitプラグインのインストールは、普段どおりUpdateサイトを利用して簡単に行うことができました。

ちょっと長くなりそうなので、続きをどうぞ。既存リモートリポジトリからクローンの作成、リモートリポジトリから更新があったかの確認、更新のローカルコミットとそれのリモートリポジトリへの反映についてまとめてあります。

15:13 fenrir が投稿 : 固定リンク |

| | コメント (0) | トラックバック
このエントリーのトラックバックURL: https://fenrir.naruoka.org/mt/mt-tb.cgi/693