天泣記

2015-08-24 (Mon)

#1

Math.exp(x) = 1.0 となる x はどのような範囲か調べてみた。

% ruby -e '
u1 = (-1.0..1.0).bsearch {|x| 1.0 <= Math.exp(x) }
u2 = (-1.0..1.0).bsearch {|x| 1.0 < Math.exp(x) }
p [u1, "%a" % u1, Math.exp(u1)]
p [u2, "%a" % u2, Math.exp(u2)]
'
[-5.551115123125783e-17, "-0x1p-54", 1.0]
[1.1102230246251565e-16, "0x1p-53", 1.0000000000000002]

-5.551115123125783e-17 以上 1.1102230246251565e-16 未満のようだ。

0x1p-53 などとぴったりな値なのは... exp(x) は x=0 で y=1 で傾きが 1 なんだから、そりゃそうなるか。

2015-07-30 (Thu)

#1

Coq で extract したコードを ocamlopt で native code にコンパイルしたら、tail call optimization が効かなくて悲しい。

coq-bugs 4312: ocamlopt can not optimize tail call in a extracted function.

OCaml と Coq のどちらの問題か迷うところだが、Coq のほうに報告してみた。

2015-06-25 (Thu)

#1

Coq で、Coq.Arith.Compare_decCoq.Numbers.Natural.Peano.NPeano の両方に leb が定義されているのはなんでかな。

実装は違うが、以下のように等価性を証明できるので、意味が違うということではないようだ。

Require Import Compare_dec.
Require Import NPeano.

Goal forall (n m:nat), Compare_dec.leb n m = NPeano.leb n m.
Proof.
  intros n.
  induction n.
    intros m.
    simpl.
    reflexivity.
  intros m.
  simpl.
  destruct m.
    reflexivity.
  apply (IHn m).
Qed.

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 するのに使える。



田中哲