K.Sasada's Home Page

Diary - 2016 March

研究日記

弥生

_31(Thu)

事情により、朝早くから頑張って会社に行った。

_30(Wed)

st の読み会であった。

_29(Tue)

RA 理事会だった。 貢献出来てるんだろうか。

_28(Mon)

https://cakes.mu/posts/12353 美人が居る。

_27(Sun)

小崎さんが来てくれると言うことで、色々準備。

_26(Sat)

絶好の花見日和! 天気は良かったが、桜さっぱり咲いてなかった。でも、人は多かったな。

_25(Fri)

ベラルーシのビザを取りに、白金台から五反田の方へ。 こういう大使館もあるんだな。

_24(Thu)

ヨドバシで色々買えると言うことを知る。 凄い企業努力だなぁ。 (誰の、かはよくわからんが)

_23(Wed)

オブジェクトって何個くらい作ってるんだろ、って気になったときに便利スクリプト。

require 'objspace'

def check_object_count
  # once
  ObjectSpace.count_objects
  ObjectSpace.count_tdata_objects
  ObjectSpace.count_imemo_objects

  h1_obj = {}; h2_obj = {}
  h1_tdata = {}; h2_tdata = {}
  h1_imemo = {}; h2_imemo = {}

  ObjectSpace.count_objects(h1_obj)
  ObjectSpace.count_tdata_objects(h1_tdata)
  ObjectSpace.count_imemo_objects(h1_imemo)
  yield
  ObjectSpace.count_objects(h2_obj)
  ObjectSpace.count_tdata_objects(h2_tdata)
  ObjectSpace.count_imemo_objects(h2_imemo)
  r = {}
  [[h2_obj, h1_obj], [h2_tdata, h1_tdata], [h2_imemo, h1_imemo]].each{|(h_after, h_before)|
    h_after.each{|k, v|
      r[k] = v - h_before[k] if v - h_before[k] > 0
    }
  }; r
end

str = 'foo'

obj = Object.new
p check_object_count{obj.dup}
p check_object_count{obj.clone}

obj = 'foo'
p check_object_count{obj.clone}
p check_object_count{obj.dup}

obj = 'foo' + 'bar'
p check_object_count{obj.clone}
p check_object_count{obj.dup}

_22(Tue)

GSoC で何かされたい、という方と相談。 面白いことをやってくれるといいのだけど。

_21(Mon)

ちょっと京王線のほうまで。

_20(Sun)

徹夜明けだけど、なんかいろいろ。

_19(Sat)

水じゃ無くて酒で作る鍋を頂いた。 私は、正直水でつくってもいいんでないの、って感じだったが...。

_18(Fri)

メソッドオブジェクトを取り出す文法が欲しい、という話。 https://bugs.ruby-lang.org/issues/12125

def m obj, mid
  Proc.new{|*args|
    obj.send(mid, *args)
  }
end

try = []
try << Dir.glob('*/*.rb').map{|path| File.basename(path)}
try << Dir.glob('*/*.rb').map(&->(x){File.basename(x)})
try << Dir.glob('*/*.rb').map(&File.method(:basename))
try << Dir.glob('*/*.rb').map(&m(File, :basename))
     # Syntax ideas
     # Dir.glob('*/*.rb').map(&File.:basename)
     # Dir.glob('*/*.rb').map(&File:.basename)
     # Dir.glob('*/*.rb').map(&File@.basename)
     # Dir.glob('*/*.rb').map(&File.@basename)
     # Dir.glob('*/*.rb').map(&File->basename)


class Symbol
  def apply obj
    Proc.new{|*args|
      obj.send(self, *args)
    }
  end
  alias < apply
  alias > apply
  alias << apply
  alias >> apply
  alias ^ apply
  alias + apply
  alias - apply

  def [](obj, *args1)
    Proc.new{|*args2|
      obj.send(self, *args1, *args2)
    }
  end
end
try << Dir.glob('*/*.rb').map(&:basename.apply(File))
try << Dir.glob('*/*.rb').map(&:basename<File)
try << Dir.glob('*/*.rb').map(&:basename>File)
try << Dir.glob('*/*.rb').map(&:basename<<File)
try << Dir.glob('*/*.rb').map(&:basename>>File)
try << Dir.glob('*/*.rb').map(&:basename[File])
try << Dir.glob('*/*.rb').map(&:basename^File)
try << Dir.glob('*/*.rb').map(&:basename+File)
try << Dir.glob('*/*.rb').map(&:basename-File)

色々考えてみた。コメントアウトしていないのは、今でも動くやつ。

順番は変わるけど、:basename>File とか気持ち悪くていいよね。


しかし、Symbol#[] は、すでにあるんだなぁ。


Dir.glob('*/*.rb').map(&:basename^File) とか気持ち悪すぎて好き。

_17(Thu)

東京11では映像撮影を業者さんにお願いすることにしたので、その打ち合わせ。 それから、仕事を引き受けてくれた方々と会議。

_16(Wed)

Ruby開発者会議。 なんか疲れた。 今回とか、卜部君が凄いきちんとやってくれて、ぼーっと参加しているだけだった。

_15(Tue)

東京11のプログラム編成。

_14(Mon)

何も覚えていない...。

AirBnB で近所を見てたら、同じマンションが貸し出されていたことがわかって驚愕。 なるほど、だから外国の方が多いのか(いや、それだけでもないのだが)。

_13(Sun)

ちょっと散歩。

_12(Sat)

_11(Fri)

鰯の煮付け http://cookpad.com/recipe/2234553

ニラのスープ http://cookpad.com/recipe/3655544


確定申告終わった。なんというか、凄くしんどかった。ふるさと納税、沢山入力した後で「実はまとめて1つでもいいよ」というメッセージを見つける。悔しい。しかも、計算してみると、自己負担なしの限界を間違っていて(社会保険料を計算し忘れていた)、すごいオーバーしていることが発覚して、ちょっととても辛い。

_10(Thu)

IPSJ 全国大会で、表彰されました。ありがたい話です。受賞頂いたのは、世代別GCの話。発表はしておくものですね。

写真:


三好さんがラズパイに FPGA くっつけるボードを 12,000 円で売ってたので、お金が出来たら買おうと思う。https://twitter.com/miyox/status/707742990870032385


しかし、日吉も矢上もすげー久しぶりでありました。 相変わらず、立派な建物だね。 回りの家も、とても豪華なものが多かった。

_9(Wed)

今日は看病モード。


メモリ管理(GCを含む)のパラメータチューニングの大前提、「メモリが足りないならメモリを増やす」という部分について、もう一度考え直している。

色々、コードを整理して、今までゴチャゴチャだった部分を綺麗にした。お陰で、gc_tracer で挙動を観察していると、きっちりカッチリ予測可能になった。

それはともかく。

現状では、メモリ確保の戦略は次の通り。なお、パラメータはデフォルトのものを使う。

  • 領域の全体の大きさ、管理できるオブジェクト数の最大値を T(Total)とする
  • マークしたオブジェクトの数を M(Marked)とする
  • これから作ることのできるオブジェクトの数を F(Free)とする

ちなみに、T = M + F。

このとき、

  • (1) M/T が 0.7 より大きければ(つまり、空き領域が 0.3 * T より小さければ)、T の 1.8 倍に増やす(メモリ確保)。
  • (2) M/T が 0.2 より小さければ(つまり、空き領域が 0.8 * T より大きければ)、解放できるものを解放しようとする。ただし、たまたまページ(16KBなので、400個くらいオブジェクトが詰まっている)が全部空いている場合に限り、ページ単位で解放する。

というのが、基本戦略。これはつまり、T に対して、空き領域 F を、0.3 * T < F < 0.8 * T にしたい、ということになる。

ちなみに、この 0.3 とか 0.8 というのはハードコーディングされていて、外からいじれない。また、Ruby 2.0 までは、このパラメータは 0.2、0.65 だった。空き領域を増やせば速くなるよね、って思ってなんとなく変えたんだったと思う。

というのが現状。


まぁ、直感的に、空き領域は 0.5 * T くらい欲しいよね、っていう感覚だと思うんだけど、はてさて、これはどのような理由から正当化できるか。

定期的に悩む話題ではあるのだけれど、さて、どの程度研究されているのかなぁ。普通、GC の研究では、容量は決められていて、その中でどうこうする話が多いので、あまりこういう話にはならないんだよね。


一応、若干の修正はしてみて、そこそこ悪くない数字になった気はする。

改善案:

  • 空き領域 F の容量のゴールを F = 0.5 * T と決める(これが理想である、という仮説のもとで進める)
  • 空き領域 F が、F < 0.3 * T と、基準値を下回ると、T に 1.8 を無条件でかける(既存の挙動)、のではなく、F' = 0.5 * T' となるような T' を求める。F' = T' - M = 0.5 * T' で、T' を T の f 倍として整理すると、f = 2 (M/T) となる。ゴール 0.5 を G として一般化すると、f = M / ((1-G) * T) となる。

(別の考え方をすると、F/T = (T - M)/T = r(全体での空き領域の割合)が低いので、T を弄ることで r = 0.5 に持っていこう、ということになる。そこで、(f * T - M) / f * T = 0.5 となるので、f = 2 (M/T) となる)

要するに、1.8 という定数をやめて、もうちょっとなんとかならんかな、と考えた、という話。


しかし、ここに書いていて良かった。なんかコードでは間違えた計算をしていた。


とまぁ、そこまでは何となく考えたんだけど、そもそも、「空き領域 F の容量のゴールを F = 0.5 * T と決める」というのはどのくらい妥当なんだろうか? この話の根拠は、「まぁ、メモリがあったら、半分くらいは自由に使わせて欲しいよね」という程度でしかない。


ちなみに、世代別が絡むので、世の中ははもうちょっと複雑。インクリメンタルは、多分絡まない、んじゃないかなぁ。


なぜ、空き容量を増やすのか。世代別がない世界(ついでに、保守的GCもない世界)を考える。

実行時間は最悪だが、空間は一番節約出来る方法は、空き容量を、オブジェクト生成時に 1 ずつ増やす方法である。この方法では、オブジェクトを作るごとに、GC を行なう。そして、空き容量が見つからなければ、そのオブジェクトのために空き容量を 1 つ追加する。このとき、オブジェクトはすべて生きていることが保証される。M = T の世界。もし、プログラムに N 回のオブジェクト生成が必要であれば、GC 回数 Cg は N 回起こる。

まぁ、そんなことするとしんどいでの、空き容量をある程度あけておく。話を単純にするために(こんなことはないのだけれど)、オブジェクトの寿命が十分に短い、つまり、いつ GC しても、オブジェクトはすべて死ぬ、という特殊な話を考える。

こうすると、プログラムが終了するまでに、GC 回数 Cg は Cg = N/T となる。だって、T 個オブジェクトを生成すると、空き領域が無くなるので GC が起こるから。この場合、戦略としては、Cg を減らすことが最優先である、となれば、とにかく T を大きくする、という戦略になる。

まぁ、世の中、そんなにうまくはいかないもので、メモリには制限があるし、大きくすれば大きくするだけ、オブジェクトの場所がメモリ上に散らばってつらい(キャッシュや TLB ミス)、みたいな話がないこともない(のだろうか)。

例えば、GC が一瞬で終わるような魔法のような技術があるのなら、実はこの理想状態(すべのオブジェクトはすぐ死ぬ)では、たいした領域を使わない方が、メモリ局所性向上からの性能改善に寄与する、という話になる。のかなぁ。

メモリ局所性とか考えると、その辺までモデル化しないといけないからつらいなぁ。


さて、一瞬で終わるような魔法に近いものを目指している技術の一つに、世代別 GC がある。最近(といっても 2013 年) Ruby にも実装されている。

これを単純化するために、世の中には一瞬で死ぬオブジェクト(即死オブジェクト)と、絶対に死なないオブジェクト(不死オブジェクト)の2つがあると考える。不死オブジェクトが増えると、T の中で、ワーキングスペースに使える数が減ってしまう。不死オブジェクトの数は、プログラムが進むにつれて増えていくと考えることが妥当だろう。例えば、20% の確率で死なないオブジェクトが現れると考える。つまり、5個オブジェクトを作ると、1 個は死なない。最初の GC を考えると、T 個オブジェクトを作ったんだから、1/5 * T は死なないオブジェクトだ。そうすると、4/5 * T 個しか作らないうちに、次の GC が発生してしまう。このうち、(4/5) / 5 T + 1/5 * T 個 = 9/25 * T 個は死なないオブジェクトになる。以下同じ。

ええと、これだと、ずーっと続くと空き領域に使える領域は無くなっちゃうね。なので、空き領域を増やす必要がある。

しかし、増やすべき容量はどの程度か。増やすのは時間コストがかかる(と思う、多分)ので、まぁなるべくやりたくは無いので、一気にやりたい。そうすると、単純にはやはり、現在の 2 倍、みたいな、適当なところで手打ちにしたいところ。

増やさないと行けない回数 Ci の数を見積もってみると、ええと、面倒くさいな。最終的に 1/5 * N が不死オブジェクトになるので、まぁ、そいつが収まる程度、と。なんか log とか出てくる奴。


こう考えると、「空き領域をどうこうするために全体の空間を広げる」という話にはならないんだよな。とすると、今の「空き領域を一定数広げるために、計数を計算する」という戦略は間違い、なのかしらん。

厳密に議論するには、空間が広がったときのペナルティとか、きちんと導入しないといけないんだろうけど。そうじゃなければ、とにかく取れるだけ取れるのが一番いいって話に。


空き領域 == 不死オブジェクトが入る余剰、と考えれば、全体じゃなくて空き領域で考えても、話は同じなのか?

世代別GCで考えると、ほんとは新世代領域の領域は、オブジェクトの寿命が十分途切れるくらい GC を起こさないような広さであれば、良いのだろうが。これって計算出来るのかな。


ちなみに、増やす戦略の話は書いたが、減らす戦略の話は、以前と変わらず。これも、何かあるのかなぁ。

本当は、それを促進するための 4KB ページ、というのが、ここ最近のテーマだったんだけど、はてさて。


旧世代オブジェクトの増加速度から、新世代の十分な広さを見積もる、みたいな話もあるのだろうが。本質的に寿命が長いのか、単に新世代に十分な広さがないから旧世代になってしまうのか、という判断は、どうやったら出来るんだろうか?

_maeda(Wed Mar 16 11:40:07 +0900 2016)

 GCハンドブック11.11「ヒープサイズの選択」にいくつか文献やその概要が書いてあります.

_8(Tue)

例のハッシュのコード https://github.com/ruby/ruby/pull/1264/files を読んでいたが、細かいところは突っ込み甲斐がありそうだなぁ、と。ただ、大筋では入ると思う。

_7(Mon)

git worktree を教えて貰った。

_6(Sun)

100均で買い物。欲しいものがあって行ったのだけど、セロテープは横幅が大きすぎた。 鍋の取っ手が壊れていたんだけど、それがあって買ってしまった。こんなもんまで売ってるんだな。

_5(Sat)

デニーズで缶詰。

_4(Fri)

妻と初めてカラオケに行った。カラオケ行ったの、何年ぶりだろ。10年はたってないような気がするが、いや、そうでもないかもしれない。

_3(Thu)

ひな祭りだけど、餃子食べてた。

_2(Wed)

RA 評議会。なぜか品川シーサイド駅そば、未だにやっている。

これについて、どういう立ち位置で行くかなあ。


パラレルワールド・ラブストーリーを読み始めているのだけれど、そういうわけで、山手線で品川まで行った。併走する車両はなかった。

_1(Tue)

歯医者。


秋ヨドで飯。なんか、雰囲気がだいぶ変わって、オープンになったよね。


仕事の方は、工夫を色々入れているんだけど、あんまり巧くいかない感じ。 ううん。


2月半ばから日記を更新していなかったので、記憶を掘り起こす。twitter 見てると、なんとなく思い出すな。

今年は毎日日記を付けようとしているのだけれど、なかなか。

Sasada Koichi / ko1 at atdot dot net
$Date: 2003/04/28 10:27:51 $