天泣記

2009-09-01 (Tue)

#1

那須

2009-09-02 (Wed)

#1

那須

2009-09-03 (Thu)

#1

キャッシュのシミュレーションに priority queue が使えるか考えてみる。

... 使えないか。

Cell を先頭にもってくるときに、もとあった場所を記録する必要があるが、その場所を求めるのが容易でない。

2009-09-04 (Fri)

#1

二分木の構造をイメージするとき、

bintree1.asy:

size(100mm,100mm);

void bintree(pair p, int n) {
  fill(shift(p)*unitcircle);
  if (n != 0) {
    pair p1 = shift(-(2**n),-2) * p;
    pair p2 = shift(+(2**n),-2) * p;
    draw(p--p1);
    draw(p--p2);
    bintree(p1, n-1);
    bintree(p2, n-1);
  }
}

bintree((0,0),4);

というような普通の描き方をすると、根の方が膨らんでいる感じになるが、この感じは根に近いノードの数を多めに感じていることになるので、

bintree2.asy:

size(100mm,100mm);

void bintree(pair p0, int i, int n) {
  pair p1 = (i*2-2**n+1,-n*2);
  draw(p0--p1);
  fill(shift(p1)*scale(0.5)*unitcircle);
  if (n != 4) {
    bintree(p1, i*2, n+1);
    bintree(p1, i*2+1, n+1);
  }
}

bintree((0,0),0,0);

というように、ノードを中央に集めて横方向の距離を一定にすると、根の方がくびれて、根に近いノードの数を正しく感じられる。

2009-09-12 (Sat)

#1

ふくらみとくびれがちょうど合いそうだなぁ、と思って合わせてみると合った

bintree3.asy:

size(200mm,100mm);

pair pos1(int i, int h) {
  int y = -1;
  real x;
  int tmp = i;

  while (0 < tmp) {
    tmp = (int)(tmp / 2);
    y += 1;
  }

  x = (i-2**y) * 2**(h-y-1) - (2**(h-1)-2**(h-y-1))/2;
  return (x, y);
}

pair pos2(int i, int h) {
  int y = -1;
  real x;
  int tmp = i;

  while (0 < tmp) {
    tmp = (int)(tmp / 2);
    y += 1;
  }

  x = (i-2**y) - (2**y-1)/2;
  return (x, y);
}

typedef pair pos_t(int i, int h);

void bintree(picture pic, int i, int h, pos_t pos) {
  int j = i * 2;
  int k = i * 2 + 1;
  pair p0 = pos(i, h);
  pair p1 = pos(j, h);
  pair p2 = pos(k, h);

  draw(pic, p0--p1);
  draw(pic, p0--p2);

  if (2**(h-1) <= j)
    return;

  bintree(pic, j, h, pos);
  bintree(pic, k, h, pos);
}

picture p1, p2;
bintree(p1, 1, 5, pos1);
bintree(p2, 1, 5, pos2);

add(shift(-15,0)*p1);
add(shift(-7.5,4)*scale(1,-1)*p2);
add(p1);
add(shift(7.5,4)*scale(1,-1)*p2);

#2

縦に並べるとイチョウなかんじ?

bintree4.asy:

size(100mm,100mm);

pair pos1(int i, int h) {
  int y = -1;
  real x;
  int tmp = i;

  while (0 < tmp) {
    tmp = (int)(tmp / 2);
    y += 1;
  }

  x = (i-2**y) * 2**(h-y-1) - (2**(h-1)-2**(h-y-1))/2;
  return (x, y);
}

pair pos2(int i, int h) {
  int y = -1;
  real x;
  int tmp = i;

  while (0 < tmp) {
    tmp = (int)(tmp / 2);
    y += 1;
  }

  x = (i-2**y) - (2**y-1)/2;
  return (x, y);
}

typedef pair pos_t(int i, int h);

void bintree(picture pic, int i, int h, pos_t pos) {
  int j = i * 2;
  int k = i * 2 + 1;
  pair p0 = pos(i, h);
  pair p1 = pos(j, h);
  pair p2 = pos(k, h);

  draw(pic, p0--p1);
  draw(pic, p0--p2);

  if (2**(h-1) <= j)
    return;

  bintree(pic, j, h, pos);
  bintree(pic, k, h, pos);
}

picture p1, p2;
bintree(p1, 1, 5, pos1);
bintree(p2, 1, 5, pos2);

for (int i = 0; i < 3; ++i) {
  for (int j = 0; j < 3; ++j) {
    add(shift(    15*i,  8*j)*p1);
    add(shift(7.5+15*i,4+8*j)*scale(1,-1)*p2);
    add(shift(7.5+15*i,4+8*j)*p1);
    add(shift(    15*i,8+8*j)*scale(1,-1)*p2);
  }
}

2009-09-13 (Sun)

#1

うぅむ。行単位のカバレッジと後置 if は相性が悪い。

2009-09-16 (Wed)

#1

PLATEAU 2009 に accept されたので準備をせねば。

2009-09-18 (Fri)

#1

priority queue を拡張して、優先順位が大きいほうからも小さいほうからも取り出せるようにすると、double-ended priority queue になる。これをヒープで実装する方法はいくつも論文が出ている。(Google Scholar で min-max-heap を検索するとか)

priority queue を拡張して、同じ優先順位の要素は、先に入れたものが先に取り出されるようにすると、stable priority queue になる。(一般的な用語かどうかは知らない) 単なる priority queue を使ってこれを実装できるのは自明である。要素に対し挿入順に通し番号をふって、与えられた優先順位が同じ場合は通し番号が小さいほうを優先すればいい。これは元の優先順位と通し番号のペアを優先順位とすれば実現できる。

では、両方の拡張を同時に実現できるか。つまり、double-ended stable priority queue はどう実装できるか。

単純に、通し番号をつけた優先順位で double-ended priority queue をつくると、小さいほうから取り出すときはいいが、大きいほうから取り出すときに後から入れたものが先に取り出されてしまう。(優先順位が一番大きい要素の中で通し番号が一番大きいものが取り出されるから。)

これは「先に入れたものが先に取り出される」という先に述べた stable の定義に合わない。小さいほうから取り出しても、大きいほうから取り出しても、通し番号については小さいものから先に取り出されてほしい。

pdeque.rb のような、min-heap と max-heap をスイッチするような実装でこれを実現するのは簡単であるが、それはここでは禁止する。ちゃんと要素の取り出しが O(log n) で済むものが考えたい話である。

このことをしばらく考えていたのだが、可能なような気がする。

min-max-pair heap をベースにして、通し番号も考慮してヒープ構造を維持すれば、min も max も通し番号が小さいほうから取り出せる構造になるのではないか。

2009-09-19 (Sat)

#1

バイナリヒープは二分木で、あるノードの値 (優先順位) は子孫のノードの値よりも小さいか等しい。(右の子と左の子の間には大小関係の制約はない) これにより、根にはいちばん小さな値が存在することになる。

たとえば、こういうやつである。

binary-heap.asy:

size(200mm,100mm);

pair pos[] = {
                      (14,6),
          (6,4),                     (22,4),
     (2,2),     (10,2),       (18,2),       (26,2),
  (0,0),(4,0),(8,0),(12,0),(16,0),(20,0),(24,0),(28,0)
};

void tree(int n) {
  for (int i = 0; i < n; ++i) {
    int j1 = i*2+1;
    int j2 = i*2+2;
    if (j1 < n) draw(pos[i]--pos[j1]);
    if (j2 < n) draw(pos[i]--pos[j2]);
  }
}

void circle(int i) {
  filldraw(shift(pos[i])*unitcircle, white);
}

void circle(int i, string s) {
  filldraw(shift(pos[i])*unitcircle, white);
  label(s, pos[i]);
}

tree(11);

circle(0, "0");
  circle(1, "1");
    circle(3, "2");
      circle(7, "8");
      circle(8, "3");
    circle(4, "1");
      circle(9, "4");
      circle(10, "3");
  circle(2, "2");
    circle(5, "9");
    circle(6, "8");

// 2 1 9 8 4 8 2 1 3 0 3

こういう大小関係の制約下において、要素の挿入や削除は木の高さに比例するコストで可能である。挿入は最後 (いちばん下のいちばん右。上の例では 9 の左の子) に入れた後、大小関係の制約を満たすよう根の方に浮かべていく。削除は、削除したところに最後の要素を移動して、移動したものが制約を満たすよう浮かべるか沈めるかする。

なお「小さいか等しい」ではなく、「大きいか等しい」とすると、根はいちばん大きな値になる。どちらでもいいのだが、どちらにしても、いちばん小さな値といちばん大きな値を両方得ることはできない。

#2

min-max-pair heap はいちばん小さな値といちばん大きな値を両方得られるようにしたものである。

バイナリヒープと同じく二分木を使うのだが、各ノードにはふたつの値を入れる。(要素数が奇数だったら、最後のノードだけはひとつの値になる)

そして、あるノードの右の値には子孫のノードにあるすべての値より小さいか等しい値、左の値には子孫のノードにあるすべての値より大きいか等しい値を入れる。これにより、根には最小値と最大値が入る。

たとえば、こうである。

min-max-pair-heap.asy:

size(200mm,100mm);

pair pos[] = {
                      (14,6),
          (6,4),                     (22,4),
     (2,2),     (10,2),       (18,2),       (26,2),
  (0,0),(4,0),(8,0),(12,0),(16,0),(20,0),(24,0),(28,0)
};

void tree(int n) {
  for (int i = 0; i < n; ++i) {
    int j1 = i*2+1;
    int j2 = i*2+2;
    if (j1 < n) draw(pos[i]--pos[j1]);
    if (j2 < n) draw(pos[i]--pos[j2]);
  }
}

void circle(int i) {
  filldraw(shift(pos[i])*unitcircle, white);
}

void circle(int i, string s) {
  filldraw(shift(pos[i])*unitcircle, white);
  label(s, pos[i]);
}

void circle2(int i, string smin, string smax) {
  filldraw(shift(pos[i])*unitcircle, white);
  draw((pos[i]-(0,1))--(pos[i]+(0,1)));
  label(smin, pos[i]-(0.5,0));
  label(smax, pos[i]+(0.5,0));
}

tree(6);

circle2(0, "0", "9");
  circle2(1, "1", "8");
    circle2(3, "2", "2");
    circle2(4, "1", "3");
  circle2(2, "3", "8");
    circle(5, "4");

// 2 1 9 8 4 8 2 1 3 0 3

min-max-pair heap でも、要素の挿入や削除は木の高さに比例するコストで可能である。

挿入は最後 (いちばん下のいちばん右。上の例では 4 が入っているノードに入れられるもうひとつの値) に入れた後、大小関係の制約を満たすよう根の方に浮かべていく。ここで、単なるバイナリヒープと異なり小さい値のほうを動かしていくか、大きい値のほうを動かしていくかというふたつの可能性があるが、それは挿入した値の大小で決まる。

削除は、削除したところに最後の要素を移動して、移動したものが制約を満たすよう浮かべるか沈めるかする。ここで、削除したものがあるノードの左の値(小さい値)なら、移動してきた値がより小さければ浮かべ、大きければ沈める。右の値なら逆である。そして、沈めていって、葉に到着してもまだ大小の制約を満たせなければ、折り返して逆側で浮かべていく。

#3

min-max-pair heap で、最小・最大を得られるが、優先順位が等しい要素が複数ある時、最初に入れたものが最初に出てくるとは限らない。そこでそれをどうにかすることを考える。

先に述べたように、通し番号を優先順位に付加するだけでは最小と最大のどちらかで、最後に入れたものが出てきてしまう。そこでヒープのアルゴリズムの中で、明示的に通し番号を扱う。

min-max-pair heap で、最小・最大として取り出されるのは根の値なので、優先順位が同じ要素は、通し番号が小さいものほど根に近くなるよう配置すればいい。これを stable-min-max heap と呼ぶことにしよう。

つまり、ある要素は、子に同じ優先順位の要素があったとき、通し番号は子よりも小さいという制約をつける。(通し番号は重複がないが、重複を考えるなら、小さいか等しい、とする)

あと、ひとつのノードに入っている要素ふたつが同じ優先順位をもっているときは、左側に通し番号が小さいものをおくことにする。

例えば、こうである。各ノードには、上に優先順位、下に通し番号を書いてある。左が優先順位が小さいほう、右が大きいほうである。

stable-min-max-heap.asy:

size(200mm,100mm);

pair pos[] = {
                      (14,6),
          (6,4),                     (22,4),
     (2,2),     (10,2),       (18,2),       (26,2),
  (0,0),(4,0),(8,0),(12,0),(16,0),(20,0),(24,0),(28,0)
};

void tree(int n) {
  for (int i = 0; i < n; ++i) {
    int j1 = i*2+1;
    int j2 = i*2+2;
    if (j1 < n) draw(pos[i]--pos[j1]);
    if (j2 < n) draw(pos[i]--pos[j2]);
  }
}

void circle(int i) {
  filldraw(shift(pos[i])*unitcircle, white);
}

void circle(int i, string s) {
  filldraw(shift(pos[i])*unitcircle, white);
  label(s, pos[i]);
}

void circle2(int i, string smin, string smax) {
  filldraw(shift(pos[i])*unitcircle, white);
  draw((pos[i]-(0,1))--(pos[i]+(0,1)));
  label(smin, pos[i]-(0.5,0));
  label(smax, pos[i]+(0.5,0));
}

void circle4(int i, string smin, string tmin, string smax, string tmax) {
  filldraw(shift(pos[i])*unitcircle, white);
  draw((pos[i]-(0,1))--(pos[i]+(0,1)));
  draw((pos[i]-(1,0))--(pos[i]+(1,0)), gray);
  label(smin, pos[i]+(-0.5,0.3));
  label(tmin, pos[i]+(-0.5,-0.3));
  label(smax, pos[i]+(0.5,0.3));
  label(tmax, pos[i]+(0.5,-0.3));
}

void circle2v(int i, string smin, string tmin) {
  filldraw(shift(pos[i])*unitcircle, white);
  draw((pos[i]-(1,0))--(pos[i]+(1,0)), gray);
  label(smin, pos[i]+(0,0.3));
  label(tmin, pos[i]-(0,0.3));
}

tree(6);

circle4(0, "0", "9", "9", "2");
  circle4(1, "1", "1", "8", "3");
    circle4(3, "2", "0", "2", "6");
    circle4(4, "1", "7", "3", "8");
  circle4(2, "3", "10", "8", "5");
    circle2v(5, "4", "4");

// 2 1 9 8 4 8 2 1 3 0 3
// 0 1 2 3 4 5 6 7 8 9 10

上の例で、通し番号の制約が効力を発揮しているところはふたつある。いちばん左下のノードの要素ふたつは優先順位が両方とも 2 なので、通し番号が 0 と小さいほうを左においてある。その親と右のノードはそれぞれ左の要素の優先順位が両方とも 1 なので、通し番号が 1 と小さいほうが上 (親) になっている。

例には現れていないが、右の要素で優先順位が同じものがあっても、通し番号が小さいものを上に配置する。

極端な話、すべての要素の優先順位が同じなら、ノードにふたつの要素が入っているという点を除けば、通し番号を優先順位と考えたバイナリヒープのようになる。

挿入と削除は、基本的には min-max-pair heap と基本的には同じである。ただし、浮かべるときと沈ませるときに、動かしている要素以外は制約を満たしておかなければいけない。これは優先順位だけの話なら min-max-pair heap と同じだが、通し番号があると、気をつけることが増える。

まずある要素を浮かべるときのことを考えると、代わりに沈む要素があるわけである。その沈む要素が、もともとあるノードに入っているわけだが、そのノードに入っているもうひとつの要素と優先順位と同じだった場合、通し番号が小さいほうを沈めてしまうと、通し番号の制約が壊れてしまう。そこで、まずそのノード内で左右を交換してから沈める。さらに、沈んだ要素が沈んだ先のノード内でもうひとつの要素と優先順位が同じ可能性がある。その場合、通し番号が小さいものが左になるよう必要なら交換する。

同様に、ある要素を沈めるときには、代わりに浮かぶ要素がある。こちらも、浮かぶ要素は優先順位の許す範囲で通し番号が小さいものを選び、浮かべた後にノード内で優先順位が同じになれば必要に応じて左右を交換する。

そうやって、要素を移動していって、優先順位の制約を満たすようになった後、さらに (優先順位が同じ要素の範囲で) 通し番号の制約を満たすよう移動する。通し番号が小さければ浮かべ、大きければ沈める。このとき、左右両方をしらべる必要がある。浮かべる場合、同じノードの左、親の右、親の左、という順に (優先順位が同じ範囲で) 浮かべていく。沈める場合、同じノードの右、左の子の左、左の子の右、右の子の左、右の子の右という、5つを考慮する必要がある。左の子と右の子の通し番号はどちらが小さいかは両方の可能性があるので、沈めるときには小さいほうを選ばなければならない。

ここで、通し番号での移動は優先順位が同じ範囲でしか行わないので、min-max-pair heap の性質を壊さないのは自明である。つまり、優先度が最小・最大の要素が根に配置される。

また、優先順位が最小・最大の中で最初に挿入したものが根に配置されることもわかる。ここはちょっと自明ではないのだが、優先順位が最小のすべて要素について、その要素が入っているノードから根へのパス上のすべてのノードにその優先順位の要素が存在する。それにより、通し番号に関する大小関係の制約から、根には通し番号が最小のものが配置される。

#4

【実習】Ruby on IBM i 「IBM iでのRubyを体験していただきます。RubyのフレームワークであるRuby on Railsにてアプリケーションの 作成とIBM i での稼働方法を実習いたします。」

という実習コースがあるのを知って驚愕する。

IBM i っていうのが AS/400 の流れのやつだとすると、ポインタと同じ大きさの整数型がないとか、とてもまともに Ruby が動くとは思えない環境だったはずなのだが。(たしか、ポインタはセグメントとオフセットからなっている 16byte だったと思う。で、16byte な整数型がない。仮にあったとしても簡単ではないだろうが。)

調べてみると、i5/OS PASE というのが、AIX の ABI のサブセットを提供していて、その上で AIX 用のバイナリが動かせるようだ。 i5/OS PASE concepts

残念ながら、Ruby をポインタと同じサイズの整数型がない環境でも動くようにするパッチがあるという話ではなさそうである。

2009-09-20 (Sun)

#1

なんで、stable-min-max heap を考えたかというと、pdeque.rb の API を検討するためである。

が、実際に pdeque.rb に組み込むかというと、短期的には微妙である。(pdeque.rb とは別に、動くことを確認するためのプロトタイプは作ったが。)

というのは、あまり使われないことが予想されるからである。

にもかかわらずなんで考えたかというと「優先順位が同じ要素は delete_min でも delete_max でも入れた順に出てきてほしい」という要求と、「delete_min と delete_max を両方使った時には両方 O(log n) で動くという可能性を残したい」という要求の両立が問題であった。

前者は、現実的に要求がある。

delete_min と delete_max は比較関数を変えればどちらかだけでもいいのだが、比較関数を変えるのは問題領域とのギャップが広がって間違いやすいという理由で両方つけた。

そして、delete_min でも delete_max でも、入れた順に出てきたほうが動作がわかりやすい。とくに、delete_max の応用として想定されるスケジューラは、まさに入れた順で出てきてもらわないと困るアプリケーションである。

後者の O(log n) な要求はちょっと微妙で、delete_min と delete_max を両方使うアプリケーションがそもそも少なそうである。SMA* (Simplified Memory Bounded A*) という探索アルゴリズムでは使うようなのだが、それ以外のものが見つからない。

だが、いつかだれかが使うかもしれない (あるいは、少なくとも文句を言ってくる人がいるかもしれない) ので、delete_min と delete_max の仕様をそれが不可能なものにしてしまうのは避けたい。

というわけで、前者の要求を満たしても、後者の要求を満たせなくなるわけではないということを示したのが stable-min-max heap である。(後者の要求がなければ、ふつうの min-heap と max-heap をスイッチするというやりかたで、前者の要求は簡単に満たせる)

示せたので、後顧の憂いなく、前者の要求を満たすことができる。

#2

external quicksort というものでも使うようだ。

うぅむ。組み込んだほうがいいのか？

2009-09-23 (Wed)

#1

けっきょく、組み込んで、external quicksort を試しに書いてみる。

external quicksort は、ピボットをひとつの要素じゃなくて、たくさん使う。

ふつうの quicksort と同様に、ピボットよりも小さいか大きいかで分類するのだが、ピボットよりも小さいという条件のかわりに、ピボットの最小よりも小さいという条件を使う。同様に、ピボットよりも大きいという条件のかわりに、ピボットの最大よりも大きいという条件を使う。

そして、ピボットの範囲の中の要素に出会ったら、ピボットに入れ、ピボットの最小ないし最大を外す。外したものは小さいないし大きいものとして分類する。

で、ピボットのところに double-ended priority queue を使う。毎回、最小最大の要素が必要だし、要素は増減し、減るときは小さいほうが減ることもあるし大きいほうが減ることもある。たしかに double-ended priority queue が必要なアルゴリズムである。

2009-09-24 (Thu)

#1

ハミング数 (2**i * 3**j * 5**k ただし i,j,k は非負整数) を求めてみる。

v2 = 1
q3 = []
q5 = []

while true
  q, n = nil, v2
  q, n = q3, q3.first if !q3.empty? && q3.first < n
  q, n = q5, q5.first if !q5.empty? && q5.first < n
  p n
  if q.nil?
    v2 *= 2
    q3 << n * 3
    q5 << n * 5
  elsif q.equal?(q3)
    q3.shift
    q3 << n * 3
    q5 << n * 5
  else
    q5.shift
    q5 << n * 5
  end
end

最初、priority queue を使っていたのだが、よく考えたらいらないようだ。

q3, q5 の内容が単調増加なことは、それぞれに追加するのは n の 3倍、5倍であり、かつ、n は単調増加であることからわかる。

2009-09-25 (Fri)

#1

1964年の ALGORITHM 232 HEAPSORT (J. W. J. Williams) を読んでみた。

ヒープの実装しか書いてない。そしてなんと min-heap である。

現在、ふつうヒープソートといえば、max-heap を使う。配列内でヒープを構成し、いちばん大きなものを最後と交換してヒープを縮めていくので、最大の要素を取り出せる max-heap が都合がいい。

だが、オリジナルのヒープソートは min-heap を示してソートに使える、という感じなので、そういうところはなかったのだな。

#2

なんで読んだかというと、max-heap の起源を疑ったからなのだが、その予想は外れた。

ダイクストラとか、ハフマン符号化とか、いくつか priority queue を使うアルゴリズムを調べたのだが、どうもどれも min-heap が都合がいい。

ヒープソートは例外的に max-heap がいいのだが、ライブラリとして提供するときはソートという API になるので、priority queue の API の用法にはならない。

では、実際にいくつかのライブラリを調べてみると、両方ある。もちろん、比較関数を変えられるのが普通なので一般性は失わないのだが、考え方およびデフォルトとしてどちらを選ぶか、という話である。

• min-heap
  • Ruby priority-queue by Brian Schroeder
  • Python heapq
  • Java java.util.PriorityQueue
  • 1964 heapsort by J. W. J. Williams
• max-heap
  • Ruby pqueue.rb by K.Kodama
  • PHP SplPriorityQueue
  • C++ STL priority_queue
  • ふつうの heapsort
  • Perl Heap::Priority (切り替え可能)

どうも予想外に max-heap が多い。

そんなに max-heap がいいのかなぁ。なにか大きな用法を見逃しているのだろうか。

2009-09-28 (Mon)

#1

IPA の情報セキュリティ技術動向調査の 2009 年上期のが公開された。

今回は Python の Untrusted search path vulnerability について書いてみた。

そういえば、前回のは日記に書かなかった気がするが、 テンポラリファイル について書いた。

2009-09-29 (Tue)

#1

ふと、noclobber で検索していると、以下が見つかった。

環境変数の設定 (Solaris ユーザーズガイド (上級編)) - Sun Microsystems :

| noclobber 変数
|
| cp コマンドを使ってファイルをコピーするときに、誤ってファイルを
| 上書きするのを防ぐには、set noclobber を使います。この変数は、
| Bourne Again シェル、C シェル、Korn シェル、および TC シェルに
| 適用できます。ユーザプロファイルファイル内に次の行を入力します。
|
| ┌─────────────────────────────┐
| │set noclobber                                             │
| └─────────────────────────────┘

えー、なにこれ。いくつ間違ってんの?

日本語の問題かとも思ったが、英語のでも同じ。

10. Customizing Your Working Environment (Solaris Advanced User's Guide) - Sun Microsystems :

| noclobber Variable
|
| Use set noclobber to prevent unintentional overwriting of
| files when you use the cp command to copy a file. This
| variable affects the Bourne Again, C, Korn, and TC shells.
| Type the following in your user profile file:
|
| ┌────────────────────────────┐
| │set noclobber                                           │
| └────────────────────────────┘

1. 環境変数じゃない
2. これはリダイレクトに対する設定で cp コマンドは関係ない
3. set noclobber は csh, tcsh 用。bash, ksh (というか POSIX shell) では set noclobber は $1 に noclobber を設定することになる。set -o noclobber か set -C としなければならない

(version 7 の) Bourne shell には set -C はなかった...

2009-09-30 (Wed)

#1

(x86 で) -fomit-frame-pointer は有効なのか？

検索したら、「x86 系の CPU では，かえって逆効果となってしまう場合もある」 という話もあるようだ。

ruby の trunk は今デフォルトで -O3 -fomit-frame-pointer なので、ちょっと試してみよう。

% uname -a
Linux nute 2.6.26-1-486 #1 Fri Mar 13 17:25:45 UTC 2009 i686 GNU/Linux

-O3 -fomit-frame-pointer (デフォルト):

% valgrind --tool=cachegrind ./miniruby -e ''              
==26841== Cachegrind, a cache and branch-prediction profiler.
==26841== Copyright (C) 2002-2007, and GNU GPL'd, by Nicholas Nethercote et al.
==26841== Using LibVEX rev 1854, a library for dynamic binary translation.
==26841== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==26841== Using valgrind-3.3.1-Debian, a dynamic binary instrumentation framework.
==26841== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==26841== For more details, rerun with: -v
==26841== 
==26841== 
==26841== I   refs:      9,370,973
==26841== I1  misses:       16,396
==26841== L2i misses:        5,440
==26841== I1  miss rate:      0.17%
==26841== L2i miss rate:      0.05%
==26841== 
==26841== D   refs:      4,479,783  (2,905,951 rd   + 1,573,832 wr)
==26841== D1  misses:       32,644  (   21,069 rd   +    11,575 wr)
==26841== L2d misses:       13,979  (    3,363 rd   +    10,616 wr)
==26841== D1  miss rate:       0.7% (      0.7%     +       0.7%  )
==26841== L2d miss rate:       0.3% (      0.1%     +       0.6%  )
==26841== 
==26841== L2 refs:          49,040  (   37,465 rd   +    11,575 wr)
==26841== L2 misses:        19,419  (    8,803 rd   +    10,616 wr)
==26841== L2 miss rate:        0.1% (      0.0%     +       0.6%  )

-fomit-frame-pointer を外して -O3 だけ:

% valgrind --tool=cachegrind ./miniruby -e ''
==26847== Cachegrind, a cache and branch-prediction profiler.
==26847== Copyright (C) 2002-2007, and GNU GPL'd, by Nicholas Nethercote et al.
==26847== Using LibVEX rev 1854, a library for dynamic binary translation.
==26847== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==26847== Using valgrind-3.3.1-Debian, a dynamic binary instrumentation framework.
==26847== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==26847== For more details, rerun with: -v
==26847== 
==26847== 
==26847== I   refs:      9,133,682
==26847== I1  misses:       11,399
==26847== L2i misses:        5,189
==26847== I1  miss rate:      0.12%
==26847== L2i miss rate:      0.05%
==26847== 
==26847== D   refs:      4,445,172  (2,854,183 rd   + 1,590,989 wr)
==26847== D1  misses:       30,750  (   19,734 rd   +    11,016 wr)
==26847== L2d misses:       13,374  (    3,267 rd   +    10,107 wr)
==26847== D1  miss rate:       0.6% (      0.6%     +       0.6%  )
==26847== L2d miss rate:       0.3% (      0.1%     +       0.6%  )
==26847== 
==26847== L2 refs:          42,149  (   31,133 rd   +    11,016 wr)
==26847== L2 misses:        18,563  (    8,456 rd   +    10,107 wr)
==26847== L2 miss rate:        0.1% (      0.0%     +       0.6%  )

いきなり逆効果である。

minieruby -e '' だけでも、命令実行数 (I refs) が -fomit-frame-pointer なしの方が小さい。

#2

しかし、

repeat 100 ./miniruby -e '10000000.times {}; p Process.times.utime'

として実行時間を測ってみると、-fomit-frame-pointer をつけた方がいくらか速いようだ。

omit-fp.R:

n <- seq(0, 99)

with_omit_frame_pointer = c(
  1.8, 1.54, 1.55, 1.5, 1.57, 1.53, 1.52, 1.51, 1.54, 1.52,
  1.52, 1.48, 1.53, 1.52, 1.53, 1.47, 1.62, 1.55, 1.53, 1.5,
  1.5, 1.5, 1.45, 1.5, 1.52, 1.45, 1.5, 1.5, 1.51, 1.52,
  1.49, 1.45, 1.44, 1.49, 1.5, 1.45, 1.5, 1.5, 1.44, 1.49,
  1.49, 1.5, 1.44, 1.53, 1.45, 1.5, 1.48, 1.45, 1.5, 1.51,
  1.5, 1.46, 1.49, 1.49, 1.48, 1.5, 1.45, 1.49, 1.53, 1.53,
  1.55, 1.56, 1.52, 1.47, 1.54, 1.45, 1.53, 1.51, 1.48, 1.55,
  1.53, 1.45, 1.57, 1.55, 1.57, 1.48, 1.45, 1.54, 1.51, 1.5,
  1.5, 1.51, 1.5, 1.55, 1.51, 1.52, 1.47, 1.5, 1.48, 1.5,
  1.52, 1.45, 1.46, 1.5, 1.51, 1.49, 1.5, 1.5, 1.5, 1.44)


without_omit_frame_pointer = c(
  1.63, 1.49, 1.5, 1.5, 1.58, 1.48, 1.51, 1.52, 1.53, 1.5, 
  1.47, 1.48, 1.52, 1.52, 1.58, 1.5, 1.48, 1.52, 1.52, 1.54, 
  1.49, 1.48, 1.53, 1.5, 1.49, 1.51, 1.47, 1.53, 1.54, 1.52, 
  1.5, 1.5, 1.5, 1.47, 1.47, 1.53, 1.52, 1.54, 1.52, 1.56, 
  1.55, 1.5, 1.59, 1.58, 1.56, 1.73, 1.5, 1.56, 1.62, 1.56, 
  1.52, 1.56, 1.57, 1.6, 1.48, 1.56, 1.52, 1.49, 1.47, 1.49, 
  1.56, 1.52, 1.64, 1.57, 1.52, 1.5, 1.48, 1.71, 1.62, 1.54, 
  1.52, 1.53, 1.48, 1.52, 1.5, 1.51, 1.48, 1.51, 1.49, 1.49, 
  1.47, 1.49, 1.54, 1.47, 1.47, 1.52, 1.52, 1.51, 1.52, 1.6, 
  1.5, 1.5, 1.51, 1.64, 1.68, 1.57, 1.58, 1.56, 1.6, 1.54)

plot(n,with_omit_frame_pointer, xlab="", ylab="t[sec]", ylim=c(1,2))
abline(mean(with_omit_frame_pointer), 0)
par(new=T)
plot(n,without_omit_frame_pointer, xlab="", ylab="", ylim=c(1,2), pch=2)
abline(mean(without_omit_frame_pointer), 0, lty=2)
legend(50, 1.2, c("-O3", "-O3 -fomit-frame-pointer"), pch=c(2,1), lty=c(2,1))

[latest]