yaotti's diary

Software is Eating the World

複製に基づくインクリメンタルコンパクションのアルゴリズム

Garbage Collection Advent Calendar 2012の12日目の記事です．激しく遅れましたごめんなさい．
研究で取り組んでいたインクリメンタルコンパクションについて説明します．

なお，ヒープコンパクションやGCの基本的な用語は知ってる前提です．コンパクションの説明とか用語説明入れるとめっちゃ長くなったので適当にぐぐってください

コンパクションの問題

  1. コンパクション対象領域にあるオブジェクトの移動
  2. 移動させたオブジェクトを指しているポインタの更新

コンパクションでは上記2つの重い処理が走るが，オブジェクトの移動やポインタ更新中にはミューテータの処理を行えないためミューテータを長時間止めなければならない．
これを避けるためいくつかインクリメンタルコンパクションの手法が提案されている．

複製に基くインクリメンタルコンパクション

ここでは複製に基くインクリメンタルコンパクションのアルゴリズムを紹介する． 論文: http://www.computer.org/csdl/proceedings/isorc/2008/3132/00/3132a516-abs.html

コンパクション中にミューテータを動かしたときに問題となるのは"移動させたオブジェクトの移動元への書き込みや参照"なので，移動元及び移動先のオブジェクトを常に同じオブジェクトとして扱うことが出来れば良い．
この手法では(重い)リードバリアは利用せず，オブジェクトの複製と3種のバリアを利用する．

処理の流れ

  1. コンパクション対象領域にある各オブジェクトの複製を連続した空き領域に作る
  2. 複製元オブジェクトを指しているポインタを複製先を指すよう更新する
  3. 複製元オブジェクトを一掃する(これにより連続した大きな空き領域ができる)

疑似コードで書くと以下みたいな処理

compaction_source_area = choose_fragmented_area
compaction_destination_area = allocate ENOUGH_SIZE
# 1. オブジェクトの複製作成
objects_in(compaction_source_area).each do |object|
  object.clone_in compaction_destination_area
end
# 2. 複製元を指すポインタを複製先を指すよう更新
objects_in(heap_area).each do |object|
  object.update_pointers_pointing_to compaction_destination_area
end
# 3. 複製元のオブジェクトを指すポインタはなくなったので，領域を開放
compaction_source_area.free

ここで1及び2の処理は，後述するバリアによって並列に実行可能となる．

3種のバリア

ただ複製しただけでは複製元と複製先を同じオブジェクトとしては扱えないため，以下の問題が生じる．

  1. 複製先(もしくは複製元)への書き込みがもう一方に反映されない
  2. 複製間での一貫性が保たれない
  3. ポインタ更新処理中(上記2の処理)にミューテータの処理によって複製元ポインタが書き込まれる可能性がある
  4. ポインタ更新が終わったオブジェクトで起きると，複製元を指すポインタが残り続けてしまう(null pointerになる)
  5. 複製元と複製先を比較すると別オブジェクトとみなされfalseが返る

それぞれの問題の疑似コード．

A2 = A.clone # 複製の作成
# 問題1. 
A.foo = 'bar'
A2.foo #=> 'bar'にならない
# 問題2. 
B.a = A # Bのポインタ更新処理が終わった後にこれが実行されると，B.aは複製元(A)を指し続けてしまう
# 問題3. 
A == A2 #=> false. trueとなるべき

これらの問題を解決するために3種のバリア(ライトバリア，ポインタ更新バリア，比較バリア)を利用する．

  1. ライトバリア: 書き込み処理の対象が複製されたオブジェクトなら,対応するオブジェクトにも同じ書き込みを行う→一貫性が保たれる
  2. ポインタ更新バリア: 更新後のポインタが複製元オブジェクトを指す場合は，複製先オブジェクトを指すように更新する
  3. 比較バリア: 複製元と複製先を比較した場合はtrueを返すようにする

以上の工夫により，「オブジェクトの複製中」「ヒープ内オブジェクトのポインタの更新処理」の部分を並列に実行できる．

まとめ

この説明では厳密さよりも平易さを優先しているため(ルートセットとか無視)，詳しく知りたい人は論文を参照してください．
http://www.computer.org/csdl/proceedings/isorc/2008/3132/00/3132a516-abs.html

札幌RubyKaigi2012

9/14~9/16の札幌RubyKaigiに参加してきた．

最近はビジネスモデルや思考のフレームワークを理解していくのが面白くてプログラミングについて考える時間が減っていたけれど，今回尊敬するプログラマ達の思想に触れたり(刺身さんの発表はレガシーコードの辛さやRubyへの想いが伝わってきて今思い出しても感極まるし，初の生miyagawaさんの発表は本当にやる気が出るものだった)また刺激的な技術トピック(kakutaniさんの話していたDCIはもっと調べてみたい．@tenderloveがサラミ監視システムで使っていたArduinoはちょうど@hmskさんに薦められて買ったところだったので色々遊びたい)を聞けて改めてプログラミングいいなあ，と思った．

一時期は通勤時とかに色んなコード読みまくってたけど最近はビジネスの構造化ばかり考えてたし，ビジネスと技術へ定期的に振り切っては戻ってきてを繰り返してる．もっと振り幅を大きくするとより楽しそう．

札幌Ruby会議の"We Code"というテーマはすばらしいと思う．会議に良い雰囲気を作り出していた理由の1つじゃないかな．

ぼくはあまり人と一緒にコードを書けていないので，今後は自分から頑張って一緒にコード書く機会を増やしていきたい．社外の人に適当に声かけてペアプロとかしよう． 札幌Ruby Kaigiスタッフの方々，とても楽しい会をありがとうございました．

宣伝: We Codeする機会として Qiitaハッカソンをやるので，一緒にコードを書きましょう．

技術/組織としてどうスケールするか at GitHub

会社をスケールさせていくために組織面，技術面で何を行ってきたか．以下簡単なまとめ

組織面

従業員をよりhappyにするために，面白い仕組みを導入している．ミーティングがない，オフィスに来なくても良い．やりとりはpull requestとcampfire．
他にも組織として強くなるために，個人に依存しすぎない(知識共有を促進する)，internal talk(tech talkみたいなのかな?それとも普通の会話?)は将来の従業員のために全て記録する*1，など．

技術面

  • 自動化可能なことを手作業でやり続けることによるコストは，手間だけではない．新規メンバーに学習コストが発生することになる．
  • masterブランチは常にデプロイ可能な状態に保ち，1日に5~30回デプロイを行なっている．
  • 意味のあるメトリクスをグラフ化しよう．全体でのレスポンスタイム平均がXXXms，というのは意味がない．
  • リリース以降今までインフラがどう変遷してきたか．ナイーブな実装だとストレージを無駄遣いしていたので，net-shardというCoWっぽい形で節約できるように変えた．


最後の"Continually refine your process + workflow"は心に留めておきたい．

ハッカーのためのハッカソン

毎日blog書くつもりだったけれど綺麗に3日坊主になってしまった．

1/4, 1/5はWantedly開催のHackathonに参加してきた．目的は「エンジニアのスキルがわかるようなプロフィールを作る」こと．
ハッカソンの様子など詳しくはこちら:) ウォンテッド超絶ハッカソン!! - ウォンテッド 航海日誌
そして2日間のハッカソンにより出来たのがこれ．

GitHubの情報を使って，ある人が使っている言語やフォロワー数などがグラフで見られるようにするサービス．自分がpublicな活動を全然してないなーとか，あの人はruby書きまくってるなーとか．
ログインなどは必要ないのでGitHubアカウントを持っている人はどうぞ．
Hackedly

Qiitaとしても各エンジニアがどういうスキルを持っていて，どれだけコードを書くのか/書けるのかをユーザーページで表現できるようにしたいと思っているので，今回のハッカソンは色々発見があり楽しめました!:)

顧客開発プロセス：アントレプレナーの教科書

年末年始はアントレプレナーの教科書
を読んでいる．方法論をきちんと学ばないといけないな，ということで技術書以外にもアンテナを張るようにしています:P

この本の前にはThe Lean Startup: How Today's Entrepreneurs Use Continuous Innovation to Create Radically Successful Businesses
を読んだのだけれど，
「スタートアップ=自分達のアイディアを元にとにかく頑張って素晴しい製品を作り，それが使ってもらえると成功，そうでなければ失敗」
という自分の既成概念が壊された．
自分達のアイディアや仮定を頻繁に検証し，進んでいる方向が正しいのか間違っているのか常にチェックすることで無駄を減らす．時間と手間をかけて優れたサービスを作っても，誰にも使われなければ意味がない．
この本(アントレプレナーの教科書)では，新製品の開発プロセスはどう進めていくべきかということがより詳しく書かれている．