天泣記

2016-07-02 (Sat)

#1 SP会

Unix domain socket APIのポータビリティ問題」というのを発表した。

テストに使ったソース: <URL:https://github.com/akr/socket-test>

2016-06-29 (Wed)

#1 「幸せな未来は「ゲーム」が創る」を読んだ

ゲーミフィケーションの話。幸せは低コストで作れるし、そうなっていないものは良くデザインされていないということだと思った。

2016-05-28 (Sat)

#1 東京Ruby会議11

東京Ruby会議11にいってきた。

2016-04-16 (Sat)

#1 いろいろな sum メソッド

Ruby 2.4 には Array#sum メソッドが入るのだが、sum メソッドはすでにさまざまな gem が提供している。いくつかの実装を比べてみよう。

activesupport-4.2.6:

module Enumerable
  def sum(identity = 0, &block)
    if block_given?
      map(&block).sum(identity)
    else
      inject { |sum, element| sum + element } || identity
    end
  end
end

facets-3.0.0:

module Enumerable
  def sum(*identity, &block)
    if block_given?
      map(&block).sum(*identity)
    else
      reduce(*identity) { |sum, element| sum + element }
    end
  end
end

simple_stats-1.1.0:

module Enumerable
  def sum(&block)
    return map(&block).sum if block_given?
    inject(0) { |sum, x| sum + x }
  end
end

production_log_analyzer-1.5.1:

module Enumerable
  def sum
    return self.inject(0) { |acc, i| acc + i }
  end
end

hash-utils-2.2.0:

class Array
  def sum
    self.inject(:+)
  end
end

gcstats-1.0.4:

class Array
  def sum
    inject {|a, e| a + e }
  end
end

gauntlet-2.1.0:

class Array
  def sum
    sum = 0
    self.each { |i| sum += i }
    sum
  end
end

さまざまな実装があることがわかる。

こうもいろいろとあると、実は今までにも互換性の問題が発生していたかもしれないな。

Ruby 2.4 では (現在の実装では) Array に定義して、与えられたブロックは適用し、要素がなかったときの値を指定でき、指定しなければ 0 を返し、指定した場合は結果に加えられる。まぁ、ブロックを使わない (無視する) ようにすると、エラーもなく値が変わって不幸だし、map するように変えるのは呼出側のコードが長くなっちゃうしな。要素がなかったときの値は悩みどころだが、結果に加えた方が仕様の中の場合分けが少なくなるのでいいだろう。

2016-04-10 (Sun)

#1 Coq の Error: Dependent type error in rewrite

Coq で、Dependent type error in rewrite というエラーに出会った。

たとえば、以下のようにすると (最後の rewrite Hxy のところで) 発生する。

From Ssreflect Require Import ssreflect ssrbool eqtype ssrnat.

Record Rec : Type := rec { m : nat; n : nat; c : m < n }.

Goal forall x y z cx cy, x = y -> m (rec x z cx) = m (rec y z cy).
Proof.
  move=> x y z cx cy Hxy.
  rewrite Hxy.

実際のエラーメッセージは以下のようなものである。

Error: Dependent type error in rewrite of (fun _pattern_value_ : nat =>
                                           m {| m := _pattern_value_; n := z; c := cx |} =
                                           m {| m := y; n := z; c := cy |})

Hxy は x = y なので、x を y に書き換えられるとおもいきや、エラーになる。

エラーメッセージを眺めて想像すると、cx が x < z の証明であって、y < z の証明ではないのが問題なのだろう。

x < z の証明と x = y の証明から自動的に y < z の証明を作ってくれても良いと思うのだが、rewrite はしてくれないようだ。

2016-04-05 (Tue)

#2 省メモリな PDF 生成スクリプト

rcairo を使ってちょっと書いてみた。

images2pdf:

#!/usr/bin/ruby

# usage:
#   images2pdf img1 img2 ... output.pdf

require 'gdk3'
require 'cairo'

output = ARGV.pop
inputs = ARGV

surface = Cairo::PDFSurface.new(output, 0, 0)
context = Cairo::Context.new(surface)

inputs.each {|input|
  pixbuf = Gdk::Pixbuf.new(input)
  surface.set_size pixbuf.width, pixbuf.height
  context.set_source_pixbuf(pixbuf)
  context.paint
  context.show_page
  GC.start
}

surface.finish

同様にグラフを描いてみると以下のようになり、メモリ消費がページ数に依存しないようになっていることがわかる。

images2pdf-pdf-gen.png

なお、このようにちゃんと省メモリにするには、GC.start を明示的に呼び出す必要があった。たぶん、Gdk::Pixbuf がかなり大きなメモリを消費していることに Ruby が気がつかないため、GC が起動しないせいだと思う。

これは RTypedData を使えば (rb_data_type_struct の dsize を設定すれば) メモリを消費していることに GC が気がついて、自動的に GC が動くようにできると思うが、確認していない。

#1 ImageMagick の convert による PDF 生成のメモリ消費

ImageMagick の convert で PDF を生成する場合、どんな感じでメモリを消費するだろうか。

まず、1000x1000 の白い PBM ファイルを (netpbm の) pbmmake で生成する。このファイルのサイズは 125kB くらいである。

% pbmmake -white 1000 1000 > white.pbm
% wc -c white.pbm
125013 white.pbm

このファイルから convert で n ページの PDF を生成し、その途中の /proc/pid/status の VmSize を 0.01秒間隔で観測する。

% ruby -e '
STDOUT.sync = true
puts "n,t[s],vmsize[kB]"
1.upto(100) {|n|
  args = ["convert"] + ["white.pbm"]*n + ["x.pdf"]
  t1 = Process.clock_gettime(Process::CLOCK_MONOTONIC)
  pid = spawn(*args)
  until Process.waitpid(pid, Process::WNOHANG)
    status = File.read("/proc/#{pid}/status")
    vmsize = status[/VmSize:\s*(\d+)\s*kB/, 1].to_i
    t2 = Process.clock_gettime(Process::CLOCK_MONOTONIC)
    puts "#{n},#{t2-t1},#{vmsize}"
    sleep 0.01
  end
}
' > convert-pdf-gen.csv

グラフを描くと次のようになる。

convert-pdf-gen.R:

library(ggplot2)
d <- read.csv("2016-04/convert-pdf-gen.csv")
p <- ggplot(d, aes(t.s.,vmsize.kB.,color=n,group=n)) +
  geom_line() +
  scale_x_continuous("t[s]") +
  scale_y_continuous("VmSize[kB]")
print(p)

convert-pdf-gen.png

これをみると、ページ数に比例するメモリを最初に確保(消費)し、ページ数に比例する時間の処理を行い、終了する、という挙動がみてとれる。

VmSize のピークは、n=100 だと 931912kB、n=1 だと 153524kB なので、だいたい 1ページ増えるごとに 8MB 弱増加するようだ。画像のサイズは 1000x1000 なので、8byte/pixel で消費しているのかな。

処理時間がページ数に比例するのはしかたがない。でも、メモリ量がページ数に比例するのはよくないと思う。

PDF は基本的には先頭からページ単位に生成していけるはずで、少なくともすべての画像を同時にメモリに置いておく必要はないだろう。1ページごとに画像を読み込んでは解放するようにしていけば、こんなにメモリを使わなくて済むのではないか。

そういう省メモリなツールはないのかな。

たぶん、1ページごとに convert で PDF に変換した後に、PDFの連結ツールを使えばいいとは思うのだが、一発でやるツールがあってもおかしくないのではないか。

まぁ、cairo あたりを使って実装してもそれほど難しくはないと思うけれど。

2016-03-29 (Tue)

#1 フィボナッチ数のベンチマーク

ふと、フィボナッチ数を求めるプログラムを4つ書いてみた。素朴な再帰版、ループ版、行列版、浮動小数点版の4つで、おおざっぱには最初の方が遅いはずである。行列版、浮動小数点版はフィボナッチ数の一般項を利用したものである。

require 'matrix'

def fib_rec(n)
  return n if n <= 1
  fib_rec(n-2) + fib_rec(n-1)
end

def fib_iter(n)
  return n if n <= 1
  f0, f1 = 0, 1
  (n-1).times { f0, f1 = f1, f0 + f1 }
  f1
end

def fib_mat(n)
  return n if n <= 1
  (Matrix[[1,1],[1,0]] ** (n-1))[0,0]
end

Root5 = Math.sqrt(5)
C1 = (1 + Root5) / 2
C2 = (1 - Root5) / 2
def fib_flt(n)
  v = (C1**n - C2**n) / Root5
  v.finite? ? v.round : nil
end

とりあえず小さい値について結果を表示してみると、期待通りどれも一致する。

0.upto(10) {|n|
  p %i[fib_rec fib_iter fib_mat fib_flt].map {|m|
    self.send(m, n)
  }
}
#=>
[0, 0, 0, 0]
[1, 1, 1, 1]
[1, 1, 1, 1]
[2, 2, 2, 2]
[3, 3, 3, 3]
[5, 5, 5, 5]
[8, 8, 8, 8]
[13, 13, 13, 13]
[21, 21, 21, 21]
[34, 34, 34, 34]
[55, 55, 55, 55]

fib_flt は Float を使っていて誤差があるので、そのうち失敗する(正しくない値を返す)わけだが、どこで失敗するか調べてみると、fib(71) で失敗するようだ。そのときの結果の値は49ビットであり、IEEE754倍精度なら(仮数部は53ビットあるので)まだ表現できるはずなので、うまく計算すればもうちょっといけるかもしれない。

0.upto(100) {|n|
  f1 = fib_iter(n)
  f2 = fib_flt(n)
  if f1 != f2
    p [n, f1, f2, f1.bit_length]
    exit
  end
}
#=>
[71, 308061521170129, 308061521170130, 49]

さらに大きくなると fib_flt は内部的に Infinity になってしまって、nil を返すはずである。調べてみると、fib(1475) でそうなるようだ。

0.upto(2000) {|n|
  f = fib_flt(n)
  if f.nil?
    p n
    exit
  end
}
#=>
1475

実行時間を測ってみよう。

require 'csv'
puts 'alg,n,t[s]'
%i[fib_rec fib_iter fib_mat fib_flt].each {|m|
  0.upto(10000) {|n|
    t1 = Process.clock_gettime(Process::CLOCK_THREAD_CPUTIME_ID)
    v = self.send(m, n)
    t2 = Process.clock_gettime(Process::CLOCK_THREAD_CPUTIME_ID)
    break if !v
    t = t2-t1
    puts [m,n,t].to_csv
    break if 1 < t
  }
}
#=>
alg,n,t[s]
fib_rec,0,4.8079999999950385e-06
fib_rec,1,1.582999999999446e-06
...

グラフにしてみると以下のようになる。だいたいは予想通りで、fib_rec はすぐに激しく遅くなり、fib_iter はそこそこ、fib_mat は n が大きければ速い。fib_flt はとても速いが、71以上で誤差があるし、1475以上は概数さえ求められない。

fib_iter より fib_mat が速くなるのはかなり n が大きくなってからで、行列を扱うのはけっこうオーバーヘッドがあるようだ。

あと、なんか fib_iter と fib_mat が二股になっているが、よくわからない。真面目に調べていないが、とりあえず GC のせいかもしれないといっておこう。(可能性はあると思うが、確信はない)

fib.R:

library(ggplot2)
d <- read.csv("2016-03/fib.csv")
p <- ggplot(d, aes(n, t.s., shape=alg, color=alg)) +
  geom_point() +
  scale_x_log10() +
  scale_y_log10("t[s]")
print(p)

fib.png



田中哲