ある日のXSLT

投稿者 nanki 2007-08-15 18:05:00 GMT

XSLで関数型プログラミング

<?xml version='1.0' encoding='utf-8'?>
<xsl:stylesheet version='1.0'
  xmlns:xsl='http://www.w3.org/1999/XSL/Transform'
  xmlns:common='http://exslt.org/common'>

  <xsl:template match="array">
    <xsl:call-template name="sum">
      <xsl:with-param name="array" select="."/>
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="sum">
    <xsl:param name="array"/>
    <xsl:choose>
      <xsl:when test="count(common:node-set($array)/element) = 0">
        <xsl:value-of select="0"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="sum">
          <xsl:call-template name="sum">
            <xsl:with-param name="array">
              <xsl:copy-of select="common:node-set($array)/element[position()&gt;1]"/>
            </xsl:with-param>
          </xsl:call-template>
        </xsl:variable>
        <xsl:value-of select="$sum + common:node-set($array)/element[1]"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

ナニコレ。

<!-- array.xml -->
<array>
  <element>1</element>
  <element>2</element>
  <element>3</element>
  <element>4</element>
  <element>5</element>
</array>
$ xsltproc sum.xsl array.xml 
<?xml version="1.0"?>
15

ext3 vs ReiserFS

投稿者 nanki 2007-08-08 11:51:00 GMT

ReiserFSは、ファイル名の探索にツリーを使うので、ひとつのディレクトリに大量にファイルを放り込んだ時などは、探索時間がかなり速くなるという。(extは線形サーチ)

かなり大量の画像を作成することになったので、どのくらい遅くなるのか気がかり。 レンタルサーバのHDDのファイルシステムを変更するわけにもいかないけど、原理的にはループバックマウントでも速くなるじゃん、と思いあたったので調べてみる。

下準備

想定する実環境は、大量の画像のうち何枚かをリクエストに応じて返すWebサーバ、画像のアクセスに偏りあり。

ext3上で、15KBの画像ファイルを、1, 1k, 100k個、同じディレクトリにコピーして1000回、ランダムなファイル名にアクセスしてみる。

# ランダムアクセス、中身は読まない。
$ ruby random_access.rb 1
$ ruby random_access.rb 10000
$ ruby random_access.rb 100000

#   user     system      total        real
0.030000   0.040000   0.070000 (  0.075712) - 1
0.040000   0.040000   0.080000 (  0.089055) - 10k
0.080000   3.110000   3.190000 ( 13.459518) - 100k

10k個では、速度差がほとんど出ないので、100k個を調査対象にする。

ちなみに、100k個のコピーを作るのは結構時間がかかった。 新しいファイルを作る際、ファイル名の重複チェックで、線形探索が必ず失敗に終わるので、最悪の条件・・・

ReiserFS

ext3上に、ReiserFSのループバックデバイスを作成し、10k個のファイルを作成する。(手を抜いた命名規則なので、本当は100001個)

# ランダムアクセス、中身は読まない。
# 10000 accesses
$ ruby random_access.rb 1
$ ruby random_access.rb 10000
$ ruby random_access.rb 100000
$ ruby random_access.rb 100001

#   user     system      total        real
0.180000   0.040000   0.220000 (  0.212465)  - 1
0.220000   2.090000   2.310000 (  2.318216)  - 10k
0.620000  35.820000  36.440000 ( 48.579632)  - 100k
0.170000   0.150000   0.320000 (  3.119429)  - 100k(ReiserFS)

ReiserFS速いなぁ。 やはり、ループバックデバイスでも恩恵が受けられるようだ。

実際の環境に近づけるため、ファイルの内容も読むようにしてみた。

# ランダムアクセス、中身も読む。

#   user     system      total        real
0.370000   0.360000   0.730000 (  0.786314)  - 1
0.480000   3.130000   3.610000 ( 55.070417)  - 10k
1.010000  37.740000  38.750000 (175.929946)  - 100k
0.510000   1.170000   1.680000 (147.424501)  - 100k(ReiserFS)

あぅ、差が縮まった。 real 以外の数字は大きくは変化していないので、ディスクからデータを読むのに時間がかかっている、と考えるのが妥当だ。 ファイル数が一個の時は、ディスクキャッシュが効きまくるので爆速。

もしもキャッシュがなかったら、と考えると恐ろしい。

目的変更

探索時間の占める割合が大したことなかったので、この辺りから本来の目的は忘れることにする。 キャッシュに関する条件を揃えるために、100k個のファイルの内、後ろの10k個をランダムアクセスの対象にする。 10kなら、15KBのファイルを全部キャッシュに載せたとしても、150MBで、キャッシュ全開状態で比較できる。

# 10000個のファイルを対象に、10000回アクセス、中身も読む。複数回。
$ ruby random_access.rb 10000

#   user     system      total        real
$ ruby random_access.rb 10000
0.530000   3.380000   3.910000 ( 61.111793)  - 10k(ext3)
0.470000   1.510000   1.980000 ( 23.133462)
0.350000   0.890000   1.240000 (  8.848809)
0.360000   0.610000   0.970000 (  4.122516)
0.330000   0.550000   0.880000 (  2.196685)
0.340000   0.520000   0.860000 (  1.318112)
0.330000   0.500000   0.830000 (  1.107528)
0.350000   0.480000   0.830000 (  0.926864)
0.360000   0.470000   0.830000 (  0.855938)
0.330000   0.480000   0.810000 (  0.853205)
0.350000   0.480000   0.830000 (  0.831397)
0.380000   0.460000   0.840000 (  0.843930)

$ ruby random_access_cache.rb 100000
0.620000  24.620000  25.240000 ( 80.425381)  - 100k(ext3)
0.470000   9.410000   9.880000 ( 31.053889)
0.400000   3.820000   4.220000 ( 11.995181)
0.370000   1.580000   1.950000 (  4.357358)
0.370000   0.900000   1.270000 (  2.170834)
0.350000   0.710000   1.060000 (  1.498341)
0.340000   0.540000   0.880000 (  1.074471)
0.350000   0.500000   0.850000 (  0.910847)
0.350000   0.490000   0.840000 (  0.860301)
0.360000   0.470000   0.830000 (  0.859827)
0.360000   0.470000   0.830000 (  0.834005)
0.340000   0.500000   0.840000 (  0.854500)

最初の何回か同士を比較すれば、real の差はほぼCPU時間(≒探索時間)の差となっているのが分かる。 それにしても劇的な速度改善。探索結果もキャッシュされるみたいだ。

大規模計算が目的なら影響があるけど、Webからのアクセスに応えるだけなら、ファイルシステムの探索時間なんてどうでもいい・・・

目的変更

もう完全に目的を忘れたので、キャッシュのすばらしさを堪能する企画(?)に変更。

キャッシュのヒット率を計算してみよう。 10000個のファイルに10000回アクセスしたときに、一回もアクセスされないファイルの割合(あるファイルが一度もアクセスされない確率)は、(9999/10000) ^ 10000で計算できる。

$ irb
>> (9999 ** 10000).quo(10000 ** 10000).to_f
/usr/local/lib/ruby/1.8/rational.rb:358: warning: Bignum out of Float range
/usr/local/lib/ruby/1.8/rational.rb:358: warning: Bignum out of Float range
=> NaN

がーん。そういえば、ruby-devかどこかで、概数を求められるようにする、とかいう話題があったようななかったような。

しょうがないので、

c = 0.0
a =  9999 ** 10000 * 1000
b = 10000 ** 10000
while a > 0
  a -= b
  c += 1
end

# c/1000 => 0.368

6割はキャッシュに載り、4割はキャッシュに載らずに、次回初めてアクセスされることになる。 先ほどの数字(一部切捨)を見てみると、だいたい前の回に比べて6割ずつくらい(たまたま?)速くなっているし、キャッシュされてないファイルが減ると、頭打ちになっている。

   time      dt uncached
-------------------------
  61.11            10000
  23.13   -0.62     3700
   8.84   -0.62     1369
   4.12   -0.53      507
   2.19   -0.47      187
   1.31   -0.4        69
   1.10   -0.16       26
   0.92   -0.16        9
   0.85   -0.08        4
   0.85    0           1
   0.83   -0.03        0

結論

というわけで、100k個程度では、ext3 にフラットに配置しても、大して違わないので、楽な方法をとることにしようかと思ったのもつかの間、 ファイル数が10倍の1M個になったら、100倍時間がかかって、1ファイルの探索時間が1秒とかになりそうなので、やっぱり使うしかない。

素直にディレクトリを掘りまくれば、 解決する気もするけど・・・


Rails開発用便利スクリプト

投稿者 nanki 2007-06-18 17:01:00 GMT
#!/usr/bin/env ruby

EDITOR = ENV['EDITOR'] || 'vim'

files = `find . -type f ! -path './tmp/*' ! -path './log/*' ! -path '*/.svn/*' #{ARGV.map{|v| "#{/^-/ === v ? '!' : ''} -path '*#{v.gsub(/^-/, '')}*' "}.join}`
system("#{EDITOR} #{files.split.join(' ')}")
puts files

というスクリプトをvifという名前でコマンドにしておいて、$ vif .jsでJavaScriptファイルを全て開いたり、$ vif controller -testとかで、テストを除くコントローラ関係のファイルをすべて開いたり。

EclipseのGoToFileみたい。


Erlang 勉強会#0

投稿者 nanki 2007-05-25 05:36:00 GMT

自称、日本初のErlang勉強会へ。

突然の召集にも、五人が集結。Rubyist率高い。

そんなこんなで、言語の基本要素をいくつか抑え、Erlangのシェルの使い方をいくつか覚えた後、実際に動くものが作りたい、ということで、FizzBuzzを作る。

% fizz.erl
-module(fizz).
-export([buzz/1]).

fizzbuzz(X) when X rem 16#f == 0 -> fizzbuzz;
fizzbuzz(X) when X rem 16#5 == 0 -> buzz;
fizzbuzz(X) when X rem 16#3 == 0 -> fizz;
fizzbuzz(X) -> X.

buzz(N) ->
  [fizzbuzz(X) || X <- lists:seq(1, N)].

と、(たぶん)Erlang以外の関数型言語でもこんな風になるだろうよ、というコードに。

実は関数型言語でプログラムを書くのは(たぶん)初めて。

色がつかないのが寂しい。

$ erl
Erlang (BEAM) emulator version 5.5.2 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.5.2  (abort with ^G)
1> c(fizz).
{ok,fizz}
2> fizz:buzz(15).
[1,2,fizz,4,buzz,fizz,7,8,fizz,buzz,11,fizz,13,14,fizzbuzz]

;と.一緒じゃだめなのか?とか(わかっていてもつい忘る)、<- を打ちなれない、とかいう細かい点は置いといて、

  • コンパイルしたものをUNIXのシェルから起動する方法がわからない。
  • Erlang を使う人をなんて呼ぶ?
  • n進法の基数は36まで。
  • Latin1・・・?

などなど、次回以降に期待。

さて、並列性を全く意識せずにできあがったプログラムが、n-CPUでn倍で動くところを見てみたいのだが・・・。


RubyInlineがすごい

投稿者 nanki 2007-03-12 14:14:00 GMT

Rubyコード中にCのコードを埋め込めるRubyInlineを使って、 ボトルネックとなっているメソッドを置き換える。

# rubyinline.rb
def benchmark
  s = "a" * 10000

  test = Test.new
  t = Time.now
  1000.times{test.string_xor(s, s)}
  Time.now - t
end
  
class Test
  def string_xor(str1, str2)
    result = str1.clone
    str1.length.times do |i|
      result[i] ^= str2[i]
    end
    result
  end
end
  
b1 = benchmark
  
begin
  require 'inline'
  class Test
    inline do |builder|
      builder.c <<-EOF
        VALUE
        string_xor(VALUE str1, VALUE str2)
        {
          VALUE result = rb_str_new(RSTRING(str1)->ptr, RSTRING(str1)->len);
          int i;
          for (i = 0; i < RSTRING(str1)->len; i++) {
            RSTRING(result)->ptr[i] ^= RSTRING(str2)->ptr[i];
          }
          return result;
        }
      EOF
    end
  end
rescue LoadError
end
  
b2 = benchmark
  
p b1/b2

長さ10000の文字列同士のxorを1000回取る、というプログラムでテスト。

$ ruby -rubygems rubyinline.rb
192.710154532523

192倍!

2007/4/6 追記:

そういえば、GCを切るのを忘れていたと思って、GC無しで実行したら、300倍になった。

参考:

RubyInline


今日のGreasemonkey - Table Filter

投稿者 nanki 2007-03-12 08:38:00 GMT

screenshot

はじめてのGreasemonkeyでもある。

10行以上のtableや、リストの上にインクリメンタルな検索ボックスが追加される。 使ってみると、いたるところに現れる。

vim で言うところの、SmartCaseも使える。

tablefilter.user.js


RubyのGeometry系ライブラリ - パース対決

投稿者 nanki 2007-03-06 18:29:00 GMT

必要だったのでベンチマーク対決してみた。 対象は、GEOS, GeoRuby, おまけで自分で実装したWKBパーサ。

GEOSは、JavaのJTSをC++に移植したもので、RubyのバインディングがSWIGで用意されている。

GeoRubyは、PureRuby実装。最近は、地図業界で使われることの多いShapeファイルや、xBaseファイルを扱うクラスも追加されたようだ。

最後のは、僕が初めてRubyで書いたまじめなコード。 大量のデータを処理する目的があったので、エラー処理もすっ飛ばして、可能な限り速く動くようにしてある。 中身はほとんどunpack<<[]

こんなコードで約二万件のMultiLineStringをパース。

# require やらARのモデル定義は省略
def benchmark
  roads = Road.find(:all).map{|road| road.the_geom[4..-1]}
  t = Time.now
  roads.each do |road|
    yield road
  end
  p Time.now - t
end
  
benchmark do |road|
  Geos::geom_from_wkb(road)
end
  
benchmark do |road|
  GeoRuby::SimpleFeatures::Geometry.from_ewkb(road)
end
  
benchmark do |road|
  Geometry::WKBParser.parse(road)
end

結果は、

0.375728  #Geos
5.319374  #GeoRuby
1.353812  #Geometry

やはりC++コードは速い。SWIGのオーバーヘッドはどれくらいなんだろう。

Rubyのコードもそこそこ。頑張れば数倍程度。思ったより遅くない。

さらに、YARVでもやってみた。 ActiveRecord は動かなかったので(大幅に仕様の変ったというsend でこけた時点であきらめた)Marshal.dumpしたデータを利用。 再コンパイルが面倒だったのと、実質のコードはほとんどRuby側じゃないのでGEOSは除外。

3.836262  #GeoRuby
0.699637  #Geometry

YARV速っ。

参考:

JavaScript URLMapper

投稿者 nanki 2007-02-13 15:03:00 GMT

ちょっと複雑なパス体系を持つRailsアプリでJSONでAJAXする人には役に立つかもしれない。 GoogleMapsとかね。

要 prototype.js

使い方はこんな風。

URLMapper.connect(
  "/user/:user_id/category/:category_id/entry/:action/:entry_id",
  {controller: 'entry', action: 'index', entry_id: null});
URLMapper.connect(
  "/user/:user_id/category/:action/:category_id",
  {controller: 'category', action: 'index', category_id: null});
URLMapper.connect(
  "/user/:action/:user_id",
  {controller: 'user', action: 'index', user_id: null});
URLMapper.connect(
  "/:controller/:action/:id",
  {action: 'index', id: null});

URLMapper.url_for({controller: 'entry'});
// -> "/entry/index/"
URLMapper.url_for({controller: 'entry', action: 'new'});
// -> "/entry/new/"
URLMapper.url_for({controller: 'category', action: 'new'});
// -> "/category/new/"
URLMapper.url_for({controller: 'category', action: 'new', user_id: 3});
// -> "/user/3/category/new/"
URLMapper.url_for({controller: 'category', action: 'update', user_id: 3, category_id: 2});
// -> "/user/3/category/update/2"
URLMapper.url_for({controller: 'entry', action: 'update', user_id: 3, category_id: 2, entry_id: 1});
// -> "/user/3/category/2/entry/update/1"

url_for は可変長引数をとって、引数をHashとしてマージするので、

//サーバからJSONを取得。
//[{user_id: 3, category_id: 2, entry_id: 1}, ...]
var entries = getJSON();

URLMapper.url_for({controller: 'entry', action: 'update'}, entries[0]);
// -> "/user/3/category/2/entry/update/1"

とか。

ソースはこんなの。

Hash.prototype.subtract = function(op2) {
  var result = $H().merge(this);
  this.remove.apply(result, $H(op2).keys());
  return result;
};


var URLMapper = {
  url_options: $A(),

  UrlOption: function(url, required, defaults, match) {
    this.url      = url.gsub(/\/:([A-z_][A-z0-9_]*)/, function(match) {return '/#{' + match[1] + '}'});
    this.required = required;
    this.defaults = defaults;
    this.match    = match;
  },

  extractParameters: function(url) {
    var params = $H();
    url.scan(/\/:([A-z_][A-z0-9_]*)/, function(match) {params[match[1]] = true});
    return params;
  },

  connect: function(url, defaults) {
    url = url.gsub(/%3A/, ':');
    var params = this.extractParameters(url);
    var required = params.subtract(defaults);
    this.url_options.push(new this.UrlOption(url, required, $H(defaults), $H(defaults).subtract(params)));
  },

  url_for: function() {
    var options = $A(arguments).inject($H(), function(r, v){return r.merge(v)});
    var detected = this.url_options.select(
      function(url_option) {
        return url_option.required.subtract(options).size() == 0 && url_option.match.all(function(pair){return options[pair.key] == pair.value});
      }
    ).sortBy(function(url_option) {
      return $H(options).subtract(url_option.required).subtract(url_option.defaults).size();
    }).first();


    if (!detected) {
      throw "no URL matches.";
    }

    return (new Template(detected.url)).evaluate($H().merge(detected.defaults).merge(options));
  }
}

今日のSQL - UPDATEでswap

投稿者 nanki 2007-02-12 09:03:00 GMT

XOR 交換アルゴリズム

使う機会が訪れるのだろうか、と思っていたけれど、SQLでカラム同士の値を入れ替えたい時に使える!

UPDATE relations SET id1 = id1 ^ id2, id2 = id1 ^ id2, id1 = id1 ^ id2 WHERE id1 > id2;

Rubyist SNS のURL

投稿者 nanki 2007-01-22 18:34:00 GMT

勉強会の途中で最新版にupdateして、コミュニティの新規作成機能でも実装しよう、と思って、 /community/new というURLを使おうとしたら、/community/:community_name という風にコミュニティに名前でアクセスする仕様になっているために使えなくなっている、どうしましょうか。

という話を、懇親会でかずひこさんとしていました。

解決方法はいくらでもあるけど、routes.rbで頑張りすぎると、機能が増える度にURLを考えないといけないし、Rails アプリケーションのサンプルコード的な、というお役目も考えると、お約束を積極的に破る、というのはどうなんだろう、ということもあって、ちょっと迷う。

acts_as_sluggableというのを使うと、link_toの結果が、/community/show/1-ruby-kansai みたいになるそうなんですが、これなんてどうでしょう。

参考

Rubyist SNS Trac