yaotti's diary

Software is Eating the World

remote work1日目

今日から会社でリモートでの仕事を試験的に部分導入してみた。
思っていた以上に不便は少なく、良い形で仕事することが出来たように思う。Google hangout便利。
しばらくは毎週月曜は各自リモートで仕事するようにし、良さそうなら順次割合を増やして完全リモートでも回る形にしたい。
リモートの善し悪しについては、数週間ほど試してからまとめる。

Increments.age++

Increments株式会社は2013/03/01で(正確には2/29創業ですが)1歳になりました. そして同じタイミングで初の社員が入社し(welcome @camelmasa!!(Incrementsに入社しました。 - @camelmasaの開発日記)),またオフィスもお世話になった(と一言では済ませられないほどですが…)Open Network Labから恵比須駅近くへの新オフィスへと移転しました. 他にもtwitterQiita寿司祭りがあったりと,2013/03/01は忘れられない一日となりました.Qiitaは寿司屋ではありません

第1号社員としてcamelmasaが++に入社!そして会社設立1周年、オフィス移転のお知らせ - The Official Qiita Blog

f:id:yaotti:20130302162829p:plain

会社にしてからもうそんなに経ったのだなあと感傷に浸りそうになりますが,振り返りエントリーを書くには時期尚早だと思うので書きません.まあとにかく色々と恵まれているなというのがこの一年の感想です.期待に応えます.

また最近個人的に大きかったのはRailsのコントリビューターとなったことでした.(1コミットだけだけど) Qiitaも大きなサービスになってきたので,Railsを始めとしたOSSの世界にも色々貢献してお返ししたいと思っています.

今後も社名の通りじわじわと積み上げていきますので,Qiita/Kobitoをよろしくお願いします.

f:id:yaotti:20130301142529j:plain

P.S. Incrementsの誕生日祝いを買ってプレッシャーを一段とかけたい応援したい方はこちらからどうぞ :) New Office & Increments創業​1年ウィッシュリスト

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

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ハッカソンをやるので,一緒にコードを書きましょう.