天泣記

2015-05-25 (Mon)

#1

Solaris の posix_spawn_file_actions_addclosefrom_np() は本当に不要な fd をすべて close させるのに使えるだろうか。

考えてみると、あまり自明ではない。

0,1,2,4 が必要な fd だとすると、5以降を close するのは posix_spawn_file_actions_addclosefrom_np() で可能として、3をどうするかが問題である。

3 がもともと open されていれば posix_spawn_file_actions_addclose() で指定すればよい。

しかし、close されていた場合でも、他のスレッドやシグナルハンドラが絶妙なタイミングで open する可能性を否定できないので、念のために close しなければならない。ところが、close されている状態で posix_spawn_file_actions_addclose() で指定すると posix_spawn() 内で close() が失敗して、posix_spawn() 自体が失敗するかもしれない。が、Solaris の posix_spawn_file_actions_addclose() の man を読むと、これは失敗しないと明記されている。ちゃんと考えられているようだ。

SUSv4 の記述だと close の失敗も posix_spawn() の失敗 (あるいは子プロセスの exit status 127) になる感じだが。

まぁ、posix_spawn_file_actions_adddup2() で fd を open 状態にした後に posix_spawn_file_actions_addclose() とすれば、SUSv4 どおりの挙動でもどうにかなるか。

Mac OS X の POSIX_SPAWN_CLOEXEC_DEFAULT のほうがやりたいことに対して素直で良いな。

2015-05-22 (Fri)

#2 Ruby と posix_spawn

Ruby では現在プロセスの起動に vfork()/fork() を使っているが、これはもともと fork() を使っていたからである。なぜ fork() を使っていたかといえば、それは posix_spawn() より Ruby のほうが古いからだろう。

まぁ、これから posix_spawn に全面移行することはないだろうな。できないことがいろいろとあって、Ruby 側で対応できないから。

#1 posix_spawn で何ができて何ができないのか

posix_spawn は子プロセスを起動する関数なので、できるできないというのは子プロセスの属性をどう制御できるかというのが基本である。

posix_spawn は POSIX 2004 (IEEE Std 1003.1, 2004) で導入され、以下の属性を設定できる。これは IEEE Std 1003.1-2008 でも変わっていない

OS によっては独自拡張もある。見つけられた範囲では以下が存在する。(プロセスの属性を設定する以外の機能もある)

プロセスの属性はこれだけかというと、もちろんそうではない。指定できない属性としては、たとえば以下があげられるだろう。

プロセス属性には OS固有のものもある。

現実的には、working directory が指定できないことがよく問題になるようだ。

いずれにせよ、すべてのプロセス属性を posix_spawn で指定可能な OS は見当たらない。(そのようにする方向性の OS さえ見当たらない)

また、指定できる属性でも、不完全なことがある。

いろいろなプロセスの属性を設定しコマンドを実行するには、様々な失敗の機会があるが、失敗したときの posix_spawn の挙動も問題である。

まず、POSIX としては失敗した時に、posix_spawn が失敗するのと、posix_spawn は成功して子プロセスが exit status 127 で終了するのと、どちらの挙動も許している。O でも、exit status は wait しないと取得できず、起動したプロセスがすぐに終わらないかもしれない場合には、wait すると長期間ブロックしてしまうので困る。

そして、失敗がちゃんと posix_spawn の失敗になる実装でも、わかるのは errno だけで、どこで (どのシステムコールで) が失敗したのかは分からない。

あと、posix_spawn は古い環境に存在しないという問題もなくはないかな。

もし、OS の立場から posix_spawn を勧めるなら、なにはともあれ、すべてのプロセス属性を指定可能にするくらいの気概は見せていただきたいところだ。実装がないと POSIX にも入らないし。

2015-04-09 (Thu)

#1 in-place radix sort

ふと、in-place で radix sort ができるか調べてみると、1bit 単位で quick sort みたいなことをすればできるようだ。

試しに書いてみた。

def inplace_radix_sort(ary)
  max = 0
  ary.each {|v|
    unless v.is_a? Integer
      raise ArgumentError, "non-integer element"
    end
    if v < 0
      raise ArgumentError, "negative integer"
    end
    if max < v
      max = v
    end
  }
  inplace_radix_sort_internal(ary, 1 << (max.bit_length-1), 0, ary.length-1)
  ary
end

def inplace_radix_sort_internal(ary, mask, i0, j0)
  if mask == 0
    return
  end
  i = i0
  j = j0
  while i <= j
    if ary[i] & mask == 0
      i += 1
    elsif ary[j] & mask != 0
      j -= 1
    else
      ary[i], ary[j] = ary[j], ary[i]
      i += 1
      j -= 1
    end
  end
  # assert i == j+1
  mask >>= 1
  inplace_radix_sort_internal(ary, mask, i0, i-1)
  inplace_radix_sort_internal(ary, mask, j+1, j0)
end

ary = (0...10).to_a.shuffle
p inplace_radix_sort(ary) #=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

再帰の深さは最大要素のビット数で、それぞれの深さにおいて結局は全ての要素を調べるので、O(n log max) か。

複数ビット単位でやるには、入れ替える前に要素の数を数えておけば可能なようだ。

2015-03-31 (Tue)

#1

Solaris には posix_spawn_file_actions_addclosefrom_np というのがあって、posix_spawn で、ある fd 以降をすべて close することができるようだ。

Mac OS X には POSIX_SPAWN_CLOEXEC_DEFAULT というのがあって、これも余計な fd を close するのに使える。

2015-02-28 (Sat)

#1

以下の本を読んだ。

両方とも、数学を認知科学から考えたような話。

前者は人間以外の動物がどんな能力を持っているかというのが主な話。チュニジアの砂漠アリが、いろいろ歩き回って餌を見つけた後、巣穴へ一直線に戻るという話はおもしろかった。たしかに人間が同じことをやろうとしたら数学を使う必要があるだろうな。

後者は人間の脳のどの部分がどういう働きをしているかという話を調べているというのが主な話。まぁ、初歩的なところは分かりはじめているわけだな。

2015-01-27 (Tue)

#2 Coq の Permutation

順列組み合わせについてもけっこう悩んだ。ふたつのリストが順列組み合わせの関係にあるという Permutation という述語は以下のように定義される。

Inductive Permutation : list A -> list A -> Prop :=
| perm_nil: Permutation [] []
| perm_skip x l l' : Permutat|on l l' -> Permutation (x::l) (x::l')
| perm_swap x y l : Permutation (y::x::l) (x::y::l)
| perm_trans l l' l'' : Permutation l l' -> Permutation l' l'' -> Permutation l l''.

空リストと空リストは順列組み合わせ (perm_nil)、順列組み合わせとなっている l, l' があったときに先頭に同じ要素を前置したものは順列組み合わせ (perm_skip)、長さ2以上のリストで、先頭の2要素をひっくり返したものは順列組み合わせ (perm_swap)、推移律 (perm_trans)

これらで生成されるものが順列組み合わせであることは明らかなのだが、すべての順列組み合わせがこれらで生成できるというのは納得できなかった

納得するまでにけっこう時間がかかったのだが、こういうことだろう。

先頭要素が異なるリスト a::l と b::l' が順列組み合わせなら、l の中には b が入っているはずで、そうすると l と b::l'' が順列組み合わせになるように l'' を選べる。そうやって選んだ l'' を使うと、perm_skip により a::l と a::b::l'' は順列組合わせ。a::b::l'' と b::a::l'' は perm_swap により順列組み合わせ。a::l'' と l' は順列組み合わせのはずなので、perm_skip により b::a::l'' と b::l' も順列組み合わせ。だからひとつ短いリストの順列組み合わせの関係に帰着できる。

ここで、「はず」というのが 2回でてくる。l と b::l'' および a::l'' と l' の順列組み合わせの関係は、リストの長さがひとつ短いものに対する関係なので、帰納法みたいな感じで仮定してよい。というか、これはリストの長さに関する帰納法をやっているわけだよな。

#1 Coq の False

最近、少し Coq を勉強していて、False について納得するのに困難を感じていた。

悩んでいた話を忘れる前に書いておこう。

2014-12-27 (Sat)

#3 端末における反転の使い方

結局、端末で反転 (文字の背景をデフォルトではない色にすること) はとても目立つため、いちばん目立ってほしいところに使うのは問題ないけれど、それ以外の場所に使うと(とくに使いすぎると)そっちが目立ってしまってよろしくない、という話なのだろう。

#2 test-unit の色の改善

と、書いたら、すとうさんがかなり直してくれて、以下のようになった。

result-latest.png

ここで目立っているものは以下の順だろう。

  1. 最後のサマリ行
  2. 失敗した行
  3. Failure

最後のサマリの行はユーザから見るといつもそこにあるので、ここまで目立たなくてもいいと思う。

失敗した行と Failure はどちらも失敗と対応している。どちらかが十分に目立てば、もっとも目立つものと失敗が対応することになる。

すとうさんは実際に失敗したところが気になるということなので、失敗した行のほうが目立つのは理にかなっているのだろう。

というわけで、その意図を進めるのであれば、サマリ行と Failure をもうちょっと目立たないようにするのがよいのではないか。

#1 test-unit の色の使い方はよくない

Ruby 2.2 から、(Ruby の外部で) require 'test/unit' とすると gem の test-unit が使われるようになって、しばらく使っていたのだが、どうも出力から素早く情報を読み取れない。

最初は慣れていないせいかな、と思っていたのだが、時間がたっても相変わらずで、これはたぶん出力が良くないのだということで、すこし真面目に考えてみた。

以下のテストを考える。

% cat tst.rb
require 'test/unit'

class C < Test::Unit::TestCase
  def test_a
    assert_equal(1, 2)
  end

  def test_b
    assert_equal(1, 1)
  end

  def test_c
    assert_equal(1, 3)
    raise
  end
end

これを Ruby 2.1 と Ruby 2.2 で比較してみた。

出力からまず読み取れる情報はまず個々の文字よりも大きな形や色である。というわけで、出力をぼかしてみてみよう。

Ruby 2.1 では以下のような結果になる。

result-210-blur.png

Ruby 2.2 では以下のような結果になる。

result-220-blur.png

これからいくつかのことがわかる。

テストが失敗した時には、たいていの場合、結局はぜんぶ直すわけだが、どのテストから直すかという選択は必要で、そのためにそれぞれの失敗を眺めることになる。そのときに、個々の失敗をすばやく認識できるとありがたい。Ruby 2.1 ではもっとも目立つ部分が失敗と対応していてそれが容易だったが、Ruby 2.2 ではもっとも目立つ部分は失敗と対応しなくなっていて、これはよくないと思う。結局のところ、テストの結果の表示は、失敗の並びなので、もっとも目立つ構造を個々の失敗が対応していないというのは結果の構造の認識を困難にしている

思うに、色の使い方はずいぶんと改善の余地があるのではないだろうか。

なお、ぼかさない結果は以下のようになる。

result-210.png

result-220.png

これをみると、Ruby 2.2 で出力が大きいのは、失敗した場所のソースを表示していること、予期された結果と実際の結果を 2回 (... expected but was ... と diff で) 表示しているのが原因である。

ソースの表示は、役に立つこともあるだろう。

結果を 2回表示しているのは、このケースではほぼ同じ情報を 2回表示しているだけで役に立っていない。役に立つ場合もあるのだろうが、役に立たない場合は表示しないでくれるとよいのだが。

考えた結果、個人的にもっとも気に入らないのは色の使い方で、失敗をすばやくみてとるのに不適切ということだと感じられる。



田中哲