!kiyoka.blog.2010_10 RSSPLAIN

Related pages: !kiyoka.blog.list
155155522222222220222444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444443444444444444444444444344443434044455555555555555555555555555555555550555555555555555555555555555555555505555555555555555555555555555555555555555555555555555555555555555555555505
1

kiyoka日記。NendoSekkaの開発や、最近思うことなど

5

最新10件!kiyoka.blog   過去記事一覧!kiyoka.blog.list

5

kiyoka.blog_header 

1

このブログを書いている人: 西山 清香(kiyoka) - twitter: @kiyokaEXT

5

5

 

5

 

2

kiyoka.2010_10_22[Nendo] Nendo 0.3.5 リリース

2

Nendo 0.3.5をリリースしました。(リリースノート: Nendo.ReleaseNote)

2

rubygems_icon_128

2

今回の目玉は高速化です。

2

tak(竹内関数)でversion 0.3.4に対して約3倍の高速化が実現しました。

2

個人的にNendoでいろんなものを書いているので、今後も日々必要になったものを優先して実装していくつもりです。

2

 

2

おそらく、これからSekkaをgem化する時に見つかった不満点を追加していきます。

2

Sekkaがリリースできた時点で 0.4.0 というバージョン番号を付けてもいいかなと考えています。

2

 

0

comment (disabled)

2

2

 

2

 

4

kiyoka.2010_10_19[Ruby][Nendo] Nendoパフォーマンスチューニングメモ(1)

4
 ktdgO6
4

Nendo処理系のパフォーマンスチューニングを実施した際のメモを晒しておく。(こういう記録はブログとかWikiに書いとくのが一番だと思う)

4

 

4

Nendoの特性について

4

まず、何と比較するかという問題であるが、Nendoは1つのS式ごとにrubyプログラムを自動生成し、rubyでevalしながら走るので、手書きのrubyプログラムと速度比較するのがわかりやすだろう。

4

ただ、そうはいってもNendoを極限まで最適化しても、手書きのプログラムに勝ることは不可能であることは明白なため、Nendoの生成コードとして最大限狙える限界のコードと比較してみることにした。(参考までに手書きのコードも同時に示す)

4

Nendoが手書きコードに勝てない理由を書いておくと、動的にエラーチェックをする必要があることと、四則演算なども関数なので'+'や'-'を記述しただけでも関数呼び出しになる(Schemeのサブセットとして考えるとそうしないといけない)ので、同じアルゴリズムを記述した場合でも、Nendoのほうが多くの処理をする必要がある。

4

 

4

 

4

計測方法

4

計測ツールにはruby-profを使った。

4

マイクロベンチマークプログラムには、階乗計算と竹内関数EXT(別名:たらいまわし関数)を使う。

4

その他のベンチマークプログラムは、この次考えることにしよう。

4

 

4

 

4

計測に使ったコード

4

tak(竹内関数)への引数は全て tak(10, 5, 0) とした。

4

[ruby-tak]

4
 人間がrubyでプログラミングした一般的なコード
4
  def tak( x, y, z )
4
    if y >= x
4
      y
4
    else
4
      tak( tak( x-1, y, z ),
4
           tak( y-1, z, x ),
4
           tak( z-1, x, y ))
4
    end
4
  end
4

 

4

[ruby-tak3]

4
 Nendoが目指すべき生成コード
4
  def tak3( x, y, z )
4
    @inner_minus = Proc.new { |_a,_b|
4
      _a - _b
4
    }
4
    @inner_ge  = Proc.new { |_a,_b|
4
      _a >= _b
4
    }
4
    @inner_tak = Proc.new { |_x,_y,_z| 
4
      if ( @inner_ge.call( _y, _x ))
4
        _y
4
      else
4
        @inner_tak.call(
4
                        @inner_tak.call( @inner_minus.call(_x,1), _y, _z ),
4
                        @inner_tak.call( @inner_minus.call(_y,1), _z, _x ),
4
                        @inner_tak.call( @inner_minus.call(_z,1), _x, _y ))
4
      end
4
    }
4
    @inner_tak.call( x, y, z )
4
  end
4

 

4

[nendo-tak]

4
 人間がNendoでプログラミングした一般的なコード
4
(define (tak x y z)
4
  (if (>= y x)
4
      y
4
      (tak (tak (- x 1) y z)
4
           (tak (- y 1) z x)
4
           (tak (- z 1) x y))))
4

 

4

 

4

計測結果

4

[マシン環境]

4
 Hardware: MacBook Pro 13inch
4
 OS:       MacOS X Snow Leopard version 10.6.4
4
 CPU:      2.4GHz Intel Core 2 Duo
4
 Memory:   4GB 1067MHz DDR3
4
 ruby:     ruby 1.9.3dev (2010-10-14 trunk 29498) [x86_64-darwin10.4.0]
4

 

4

最適化前

4

Nendo 0.3.4リリース版の結果である。

4
tak   (ruby version)
4
      user     system      total        real
4
  0.040000   0.000000   0.040000 (  0.039284)
4
4
tak3  (ruby version)
4
      user     system      total        real
4
  0.220000   0.000000   0.220000 (  0.214475)
4
4
tak   (nendo version)
4
      user     system      total        real
4
 34.130000   0.730000  34.860000 ( 34.848524)
4

ruby-tak3 : nendo-tak = 1.0 : 155.13 (約155倍遅い)

4

 

4

引数リストを Listではなく、Arrayで渡すようにした。

4

ruby-profで計測した結果、引数リストをList型で渡しているところが重いことがわかった。

4

現状:     callProcedure( 'func', @_func, [ a, b, c ].to_list ) 形式は (cons a (cons b (cons c '()))) のようなList形で引数を渡している。

4

最適化後: 固定長引数の場合は、@_func.call( *[a, b, c] ) というlistを使わない呼びだし形式にした。

4

当然、ArrayのほうがRubyの組み込みクラスなので処理が軽い。

4

最適化の結果は以下のようになった。

4
tak   (ruby version)
4
      user     system      total        real
4
  0.030000   0.000000   0.030000 (  0.032908)
4
4
tak3  (ruby version)
4
      user     system      total        real
4
  0.210000   0.000000   0.210000 (  0.215441)
4
4
tak   (nendo version)
4
      user     system      total        real
4
 22.200000   0.720000  22.920000 ( 22.908085)
4

ruby-tak3 : nendo-tak = 1.0 : 105.71 (約106倍遅い)

4

 

4

 

4

シンボル変換処理をコンパイル時に持っていった。

4

まだ重い部分があったので調べてみると、tak関数が呼ばれる度に、Nendoの関数名をrubyの名前空間でのメソッド名に変換する処理が走っていることに気がついた。

3

Nendoの関数名はSchemeの識別子と同様に、'-' や '*' などのように rubyの識別子に使える範囲外の文字が使えるため、それらを変換してやる必要がある。

4

(例: aa-*bb を aa_MIMARK_ASMARKbb_METHOD に変換する処理)

4

最適化の結果は以下のようになった。

4
tak   (ruby version)
4
      user     system      total        real
4
  0.030000   0.000000   0.030000 (  0.033190)
4
4
tak3  (ruby version)
4
      user     system      total        real
4
  0.210000   0.000000   0.210000 (  0.217253)
4
4
tak   (nendo version)
4
      user     system      total        real
4
 10.020000   0.120000  10.140000 ( 10.130185)
4

ruby-tak3 : nendo-tak = 1.0 : 47.71 (約48倍遅い)

4

 

4

 

4

まとめ

4

引数リストの受け渡しにオーバーヘッドの大きいList型を使っていた問題と、シンボル変換をコンパイル時ではなくランタイム時に行っていた問題を改善することによって、takの計算時間を約1/3に改善することができた。

4

 

4

 

4

今後の高速化アイデア

3

今回の計測で、Nendoのビルトインの四則演算関数は可変長引数を受けるバージョンしかないため、可変長引数を扱うオーバーヘッドが依然大きいことがわかっている。

4

(+ 2 2) などのようにソースコード上で引数の数はわかっているわけなので、四則演算の2引数固定バージョンなどを用意して、コンパイル時に選択すればtakなどのマイクロベンチマークではかなり高速化できそうである。

4

ただ、メンテナンスの面からあまり良い方法とはいえないので、もっと良い方法が何か検討する。

4

 

4

ほかにも、mapやfilterなどはNendoで実装するのではなくRubyのネイティブのmapやselectをうまく利用してRubyの速度に近づけるアイデアもある。

3

但し、rubyのmapが使えるのは mapに1個のリストが与えられた場合のみであるが、それでもほとんどのNendoプログラムではmapやfilter関数に複数のリストを与えることは稀であることから十分有効なアイデアだと考える。

4

 

3

ちなみに、今回の改善は 0.3.5に入る予定です。

4

 

0

comment (disabled)

4

4

 

4

 

5

kiyoka.2010_10_15[Nendo] Nendoのベンチマークを開始

5
 ktdgO6
5

Nendoで書いたプログラムがPure rubyと比べてどれくらい遅いかを調べ始めた。

5

まずは最初の結果を示そう。

5

竹内関数の処理時間は以下の通り。 ※ 引数は tak( 10, 5, 0 )

5
  Ruby   0.03秒
5
 Nendo  38.89秒
5

その差 およそ1296倍。スゲー。

5

 

5

ソースコードは以下の通り。コーディングの仕方でどちらかが有利になるようなことはないだろう。

5

[Ruby]

5
  def tak( x, y, z )
5
    if y >= x
5
      y
5
    else
5
      tak( tak( x-1, y, z ),
5
           tak( y-1, z, x ),
5
           tak( z-1, x, y ))
5
    end
5
  end
5

 

5

[Nendo]

5
(define (tak x y z)
5
  (if (>= y x)
5
      y
5
      (tak (tak (- x 1) y z)
5
           (tak (- y 1) z x)
5
           (tak (- z 1) x y))))
5

 

5

まず、何から手を付けるか。

5

takは関数呼び出しが全て固定長なので、Nendoの引数の渡しかたを固定長の場合だけ最適化するだけで相当高速化するハズ。とういか以前、Nendoの出力したRubyコードを手で最適化した際にかなり効果があったので、その案を進めてみる。

5

難しい箇所としては、既にNendoに組込んである末尾再帰最適化を壊さないように今回の仕組みを入れないといけないところ。

5

2日程度で作業完了できればいいのだけどなぁ。そんなに簡単ではないんだろうなぁ。

5

 

0

comment (disabled)

5

5

 

5

 

5

kiyoka.2010_10_13[Ruby] fuzzy-string-match 0.9.0 リリース

5

二つの文字列同士を曖昧比較するライブラリ(gem)をリリースしました。

5
 rubygems_icon_128
5

lucene-3.0.2からJaro-Winkler distance アルゴリズムだけをポーティングしたものです。

5

キーワード検索でユーザーのタイプミスをある程度許容したい時なんかに使えると思います。

5

ちなみに、私はSekkaという日本語入力メソッドで使っています。

5

結果は上々で、ローマ字にタイプミスが混在してもそれなりに合っていれば漢字を探しだしてくれるので重宝しています。

5

限界速度ぎりぎりまで打鍵スピードを上げてもそれなりに漢字変換ができてしまうので非常に効果を感じています。

5

 

5

インストール方法

5

これだけです。

5
gem install fuzzy-string-match
5

依存ライブラリ群も自動的に解決されてインストールされます。

5

 

5

使いかた

5

factoryメソッドでインスタンスを作って、getDistance()メソッドに比較したい2つの文字列を渡すだけです。

5

結果が 0 ≦ x ≦ 1.0 の近似度で返ってきます。(1.0で完全一致です)

5
require 'fuzzystringmatch'
5
jarow = FuzzyStringMatch::JaroWinkler.new.create( :native )
5
p jarow.getDistance(  "jones",      "johnson" )
5

 

5

ソースコード

5

githubにあります。

5
 kiyoka's fuzzy-string-match at master - GitHubEXT
5

Jaro-Winkler以外のアルゴリズムが欲しい人はこのモジュールに追加して頂ければ幸いです。

5

作業はluceneのオリジナルJavaソースを慎重にRubyとC言語に変換するという簡単なお仕事です(笑)

5

 

5

Rubyの汎用的なライブラリをリリースしたのは今回が初めてです。(Nendoは汎用的だけどちょっと毛色が違うからね)

5

微力ながらRubyコミュニティーに貢献できた気がして嬉しいです。

5

 

5

 

0

comment (disabled)

5

5

 

5

 

5

kiyoka.2010_10_04[言語][Lisp] 俺言語処理系開発に挑戦したいなら「見るまえに跳べ」

5

Peter Norvig のエッセイを読んだのだが、自分の過去ならどう感じただろうかと思ったので…

5

俺言語処理系を作ってみた後では、当時高い壁だと思っていたものが、そうでも無いことを知った。

5

少しでも興味がある人は実際にトライしてみるべきだと思う。

5

 

5
 ((Pythonで) 書く (Lisp) インタプリタ)EXT から引用。
5
  * Lispyはとても小さい。コメントや空行を除くと90行で、ソースコードは
5
    4Kバイト以下だ。(最初のバージョンは96行だったが、Eric Cooperの示唆
5
    により、Procedureのクラス定義をなくし、代わりにPythonのlambdaを使う
5
    ことで短くなった。) 私がJavaで書いた最小のSchemeであるJschemeのソー
5
    スは1664行で57Kバイトあった。Jschemeは当初SILK (Scheme in Fifty
5
    Kilobytes、50キロバイトのScheme)と呼んでいたが、この制限を満たして
5
    いたのはソースコードではなくバイトコードで数えたときだけだった。
5
    Lispyはずっと良くなっている。これはアラン・ケイが「世界で最も強力な
5
    言語」を「1ページのコード」で定義できると1972年に言った言葉に合って
5
    いると思う。
5
    bash$ grep "^\s*[^#\s]" lis.py | wc
5
          90     398    3423
5

 

5

上のエッセイでも全ソースが掲載されているが、言語処理系の中でもLispは非常に少ないコードでおもちゃの処理系が作れる。特にPythonなどのスクリプト言語で書いた場合は特にそう。

5

言いたいことは、言語処理系を作ってみたいと思っているひとは躊躇せず一度試してみるべき、ということ。

5

おもちゃバージョンを作るところまでは上のエッセイ同様に余暇の数日でできるレベルだ。

5

その先は、飛び込んでみてから決めても遅くはない。実際に言語処理系を作ってみると、おもちゃバージョンの完成を迎えるころには、そこで終るのはもったいないほど楽しいことがわかってくる。まあ、そこから先、どう進むかは人それぞれだと思うけど。

5
 47600591_c90588870e_m 「見るまえに跳べ」
5

 

5

現在はNendoというRubyで書いたLisp処理系を開発しているのだが、私の思い出を語ると、当初なかなか始められなかったのを思いだす。

5

過去記事から、なんか自分がグチグチ書いているところを抜粋してみた。カッコわるい…(笑)

5

どうも、最初から完全オリジナルなフルセットの処理系を作ろうとか考えてたみたいだ。そんなこと考えたら誰にとっても壁は高いだろうに。

5

2008年8月くらいからグチグチ言いはじめて、実際に決心が付いたのが2009年2月末だった。

5

 

5
 kiyoka.2008_08_09[言語] そろそろオレ言語でもやっておくか(1)
5
  オレ言語(いわゆる言語を自作すること)に興味が出てきた。自分が実際に作っ
5
  てみるという観点で有名どころの言語仕様とか言語設計者のプレゼン資料と
5
  かを見ると、なかなか素人には恐ろしく高い壁に見える。
5
 kiyoka.2008_08_31[言語] そろそろオレ言語でもやっておくか(2)
5
 kiyoka.2008_09_03[言語] そろそろオレ言語でもやっておくか(3)
5

 

5

ここでGauche作者のshiroさんからもコメントを頂いたり。有り難いです。

5
 kiyoka.2008_09_23[言語] そろそろオレ言語でもやっておくか(4)
5
  なぜ、多くの処理系実装者が『オレ言語をデザインするのは大変なので
5
  Schemeを言語仕様どおり実装しました』という 結論になるのかという質問へ
5
  の答えにもなっていると思う。
5
  オレ言語に手を出すのは楽しいけど、あまりにハードルが高いということだ
5
  なぁ。どうするかなぁ。
5
 kiyoka.2009_02_28[言語] そろそろオレ言語でもやっておくか(5)
5
 kiyoka.2009_03_20[言語] そろそろオレ言語でもやっておくか(6)
5

 

5

このあたりで、作るものの方向性が見えてきて、Nendoという名前に落ちついたみたいだ。

5
 kiyoka.2009_03_25[言語][Nendo] そろそろオレ言語でもやっておくか(7)
5
 で、結局なにを作りたいの?
5
   S式でRubyプログラミングができたらどんな感じかを一度体験してみたいと
5
   いうのが作り始めた動機だ。S式のどこの節を千切って、あっちへ接木して
5
   というような柔軟なプログラミング体験はRubyではできない。
5
   Rubyの良い面も有るのでRubyのコードと混在できるようにするつもり。
5
   なので、ユーザインタフェース的な実験がメインになる。ということで、実
5
   用言語としてのパフォーマンスとかはあまり興味がないの。
5
   S式でプログラミングをするのは好きなんだけど、例えばTokyoCabinetみた
5
   いな最近話題のDBでちょっと使って遊んでみたいというような場合には、
5
   Rubyのようにバインディングが量産されてくる言語にのっかるのが楽という
5
   事情もある。
5

 

5
 kiyoka.2009_03_30[言語][Nendo] そろそろオレ言語でもやっておくか(8)
5
 kiyoka.2009_04_01[言語][Nendo] そろそろオレ言語でもやっておくか(9)
5
 kiyoka.2009_04_07[言語][Nendo] そろそろオレ言語でもやっておくか(10)
5
 kiyoka.2009_04_10[言語][Nendo] そろそろオレ言語でもやっておくか(11)
5

 

5

まあそんなわけで、躊躇してるくらいなら「見るまえに跳べ」ですよ。

5

 

0

comment (disabled)

5