今朝目覚めたら、Google が という面白そうなものを出していたので、 (PDF) をざっと読んでみました。で思ったのは、これは Google の 分散 OS ミドルウェア なのだな、ということ。

以下、自分が受け取ったことを書きます。ちゃんと知りたい方は、論文をあたってください。(参考: id:amachang による実践エントリ)

かんたんなおさらい

Native Client とは?

ブラウザの中で、x86のネイティブコードを実行できるようにする仕組みです。

何がうれしいの?

• 実行速度。スピード! とにかくもっとスピードを!!
• マシンの機能をフルに使える。ファイルアクセスも、マルチスレッドも、SIMDでさえも書けるよ!
• それでいてセキュア: 多段サンドボックス方式で、危険なことができないようになってます。

例として挙げられているのは、写真をあつかうWebアプリ。JS+HTMLでユーザインターフェイスを書いておいて、スピードが必要な画像処理はローカルのネイティブコードでやるという処理分担です。 ユーザは JS/HTML/ネイティブコード の3つを書くことになりますね。

それに加えて、Native Client 間の通信もサポートされています。先ほどの写真アプリだと、画像処理に加えてローカルストレージへのアクセスを提供するライブラリと組み合わせる、なんてことも難なくできるという。

みどころ

ランタイムシステムのところでは、とにかく OSっぽさ が随所にでてきますね。マイクロカーネルみたいなもんだよ、とか IPC とか UDP ライクな通信とかマルチスレッドとか。sbrk(), mmap(), malloc(), free() みたいな API を提供するとか。それでいて、 Windows/Mac/Linux といったマルチプラットフォームで動きますと。なので、ぼくはこれこそが Google OS なのだと思いました。下位に存在する OS レイヤをラップするような、それでいて低レベルなタスクをこなすミドルウェア。

Intel TBB (Threading Building Blocks) でさえ移植できたよ! というのもおもしろかったです。

どうやってセキュアにするのか

2段階のサンドボックスでアプリを閉じ込めます (3) 。Inner (HW, x86 アーキテクチャの機能を利用) と Outer (SW, ptrace とか使う) の2つ。ここの実装がバイナリハックス的に面白いですね。実行できる命令の種類に制限をつけるとか、GCCに手を入れて出力する機械語をサンドボックス用にするとかそういうあたり。論文読む方はこのへんを重点的にどうぞ。

3.1 の Inner Sandbox の性能について述べてるとこが楽しいですね。ユーザのコードがSandbox規約に違反してないかをチェックする Validator が、たった 500 statements の C コードであり、コンパイルすると 6000 バイトでしかないよ、と胸を張っているあたりにぐっときます。

Java とか Flash とかとどう違うの?

より低レイヤなことができる、ということなのかと思いました。 Java は思想的に近いだろうけど、さらに泥臭いことができるという。あと、 Java とか Flash だと、中間に VM というレイヤがあるのですが、 Native Client ではそこをすっとばしていきなりネイティブをさわりにいくというあたりが Google っぽいなと (参考: Google Chrome)。

そもそも、記述言語として使えるのが GCC toolchain が提供するものなので (3.6) 、まあ C/C++ になりますよね。そんなレベルでゴリゴリ書いたコードが Web アプリで動かせるという。データベースと回線の太さに律速されるようなふつうの Web アプリ屋さんにはオーバースペックになるかもしれませんが、 Goolge みたいな用途ではバリバリ使うのかしら。

疑問が残るところ

2.1 では、 UI を書く JS+HTML コードと .nacl なネイティブコードはプラットフォーム間でポータブルとあるのですが、その後の章でそれについて触れられていないのが気になりました。gcc toolchain を使うんだし、 Windows とかどうするんだろうな、と。そのままのバイナリでいけるのかな。

2008-12-10 01:33 追記: takuma104さんのブコメ によると、同じバイナリ (ELF フォーマット) が Mac でも Windows でもそのまま動いたとのこと。3.2 で書かれている、セキュア ELF ローダ (sel_ldr) とその先にあるランタイムで、プラットフォーム間の差異を吸収しているのでしょう。

あと、評価のところ (4.3) で、 H.264 decoder を Native Client のコードと元々のコードとで比較しているのですが、実測値がでてこず

Performance of the original and NaCl versions were comparable and limited by video frame-rate

としか書かれていなかったのが寂しかったです。

思うところ

• ブラウザの中で動く言語処理系とかを簡単につくれるのではないでしょうか。これまで JavaScript で実装した処理系とかいくつかありましたけれど、そういうのがもっと簡単につくれる (というか、移植できる) ようになる気が。
• GPGPUと組み合わせてみてもおもしろそうですね。ちょうど OpenCL 1.0 も出たところだし。
• 練習問題: Gears との関係は?

---

Native Client が流行るかといわれるとそうでもないかなーと思うんですが、やはり Google のインフラ技術はおもしろいですね。

に参加してます。

Qualification Round は A,B を解いて Score:50、Rank:2246 でした。Cむずいよ。 Rubyで書いてます。irbがつかえるこの幸せ。 irbでインタラクティブにデバッグしつつ、本番の入出力をケアするためのコードを最終行にいれてます。

A. Saving the Universe

さいしょ、レポートの出力形式を間違っていて (#0から出力してた)、なんでこれで違うんだろうと首をかしげてた。1回ぶんのmiss submit。

戦略は以下:

• 入力を先頭から順になめて、エンジンを set に追加
• すべてのエンジンが set にはいったら、カウンタをあげて、setをリセット

電車の中で、この単純な解法に気づいたときはうれしかった。

!/usr/bin/env ruby

Saving the Universe

at Google Code Jam 2008, QR A

#

use Ruby 1.8.6 (2008-03-03 patchlevel 114) [universal-darwin9.0]

#

author:mootoh

#
require 'logger'


$log = Logger.new(STDOUT)
$log.level = Logger::ERROR
$log.datetime_format = ''


def test(engines, queries)
  state = []
  count = 0


queries.each do |query|
    state.push query
    state.uniq!
    if state.size == engines.size
      $log.debug("change !")
      count += 1
      state = [query]
    end

$log.debug(state)

end


count.to_s
end


def main(file)
  n = file.gets.chomp.to_i
  n.times do |i|
    s = file.gets.chomp.to_i
    engines = []
    s.times {|j| engines.push file.gets.chomp}

q = file.gets.chomp.to_i
queries = []
q.times {|k| queries.push file.gets.chomp}

puts "Case ##{i+1}: " + test(engines, queries)

end
end


main(ARGF) unless $PROGRAM_NAME == 'irb'

Train Timetable

これも電車で解いた。 オブジェクト指向っぽく考えてたら、できそうな気がして。 遅いけど、実行時間は今回問われてないのでおk。

!/usr/bin/env ruby

Train Timetable

at Google Code Jam 2008, QR B

#

use Ruby 1.8.6 (2008-03-03 patchlevel 114) [universal-darwin9.0]

#

author:mootoh

#
require 'logger'


$log = Logger.new(STDOUT)
$log.level = Logger::ERROR
$log.datetime_format = ''


class Arrow
  attr_accessor :from, :to
  def initialize(from, to)
     = from;  = to
  end


def start_at?(at)
     == at
  end
  def to_s; "#{from} -> #{to}"; end
  def inspect; to_s; end
end # Arrow


class Train
  attr_accessor :available_at


def Train.tt=(x); @ = x; end
  def Train.tt; @; end


def initialize(at)
     = at
  end


def departure(to)
     = to + @
  end


def to_s; "Train@:#{}"; end
  def inspect; to_s; end
end # Train


class Station
  attr_accessor :trains, :arrows, :count


def initialize(arrows)
     = []
     = arrows
     = 0
  end


def train_available_at(at)
    t =  { |train| train.available_at <= at }
    if t
      (t)
      t
    else
       += 1
      Train.new(at)
    end
  end


def to_s
    'Station: ' + [
       {|x| x.to_s},
       {|x| x.to_s},
      
    ].join(' : ')
  end
  def inspect; to_s; end
end # Station


def parse(n, file)
  ret = []
  n.times do |i|
    x = file.gets.chomp.split(/\s+/).map do |x|
      h, m = x.split(/:/).map {|y| y.to_i}
      h * 60 + m
    end
    ret.push Arrow.new(x[0], x[1])
  end
  ret
end


def main(file)
  n = file.gets.chomp.to_i
  n.times do |j|
    tt = file.gets.chomp.to_i
    Train.tt = tt
    na, nb = file.gets.chomp.split(/\s+/).map {|x| x.to_i}

arrows = [na,nb].map {|x| parse(x, file)}
starts = (arrows[0] + arrows[1]).map {|x| x.from}.sort.uniq
stations = arrows.map {|x| Station.new(x)}

starts.each do |start|
  $log.debug("start at #{start} --------------------")
  2.times do |i|
    st_i = stations[i]
    st_o = stations[(i+1)%2]

    departures = st_i.arrows.find_all {|x| x.start_at?(start)}
    $log.debug("departures=#{departures.size}")
    departures.each do |d|
      train = st_i.train_available_at(start)
      train.departure(d.to)
      st_o.trains.push train
      $log.debug(train)
    end
    st_i.arrows -= departures

    $log.debug("#{i == 0 ? 'A' : 'B'}: #{st_i}")
    $log.debug("#{i == 0 ? 'B' : 'A'}: #{st_o}")
  end
  $log.debug('------------------------------------')
end
puts "Case ##{j+1}: #{stations[0].count} #{stations[1].count}"

end
end


main(ARGF) unless $PROGRAM_NAME == 'irb'

---

つぎからが本番ですね。がんばろう。

に登録しておきました。 来月ですね!

前回とちがって、TopCoderのアプリを使うわけではなさそうです。 自分はRubyを言語として選んでみました。できるのかな。

2006年に挑戦し、自分のふがいなさを思い知らされ、 そこからTopCoderで練習を積んできました。 2年経ったいま、自分はちゃんと進歩しているのだろうか。

当時のエントリ:

• Google Code Jam 2006
• Google Code Jam 2006 Practice 500
• Google Code Jam Practice
• Google Code Jam 2006 日程
• CodeJam Practice : 1000点問題
• CodeJam Qualification Round開始
• CodeJam Qualification Round 結果
• CodeJam Qualification Round 750点問題
• Google CodeJam 2006 で使ったテンプレート
• CodeJam Qualification Round : SystemTestとおった

をさわりだけ見てました。

Morning Glory = 朝顔 というところがいちばん心に残ったってのもどうかと思いました。oasisを思い出す朝です。

---

に行ってきました。都心遠い。

雑感

GoogleはWebだけでなく、Desktopアプリのプラットフォームにもなろうとしているみたい。 開発にはMarkup + JavaScriptで。これはActionScript3 (Flex 2) や、HD DVD規格とも同じ方向性ですね。

APIの説明を全面に出しつつ、リクルーティングしているということは、Googleはいまアイデア溢れるJavaScriptハッカーを求めているということなのかな? とか勘ぐりました。

あと、日本オフィスでシェフが腕をふるえないのはビルの制限(火が使えない)からだというところにガッテンでした。 自社ビルを構えるようになると楽しそうですね。

内容

APIのおはなしが3件とGoogleの中ってどんなの?という話が1件、SunのAjaxツールの宣伝が1件でした。

Google Maps

マウスホイールでシームレスなズームができるというところでかなり驚きました。これって常識なのでしょうか? これまでGoogle Mapsで不満だった点の一つが解消されてしまっています。

Google Maps APIはUIに関するAPIと認識しました。地図情報をoverlayして表示できるので、別に世界地図じゃなくてもスクロール/ズームが必要なアプリでも使えそうです。SimCityとか?

マーカーのドラッグはできるの? みたいな質問を英語でしてみました。答えは”Yes”。なるほどー。

今さら感がありますが、吹き出しの下に影をcastするのはどうやって実現しているのか気になりました。

ブラウザでコードを表示して、それを変更すると即座にMarkupに変更が反映されるというデモはとても説得力があってグッドです。

Google Gadget

Write once, run any site.

Google Personalized Page だけでなく、任意のサイトでGadgetは表示できるよ、と。でも、自分のサイトで表示させたいGadgetってどんなものがあるだろうかな? と想像してみても、なかなか浮かんできませんでした。 がんばれ想像力。

Desktop SDK

Mac OSX の Dashboard Widget のようなもの。Windows限定。 COMのインターフェイスを使ってネイティブアプリと通信できるということは、あんなことやそんなこともできそうですね。

Directoryに登録されると、ノベルティがもらえるよ!

• Google Hat
• Google Pen
• Special T-shirt

Life

人事の方による社内情勢の紹介。

個人事業主として動ける人を求めている、と解釈しました。つまり、

• 自分で目標を立て
• 優先度をつけ
• 確実に遂行する

ことができる人と。

懇親会

ちょっとだけピザとワインをつまんで撤収しました。だって家が遠いんだもの。 見知った顔がほんの少しだけいたので、お話できたらよかったのですが。

無料セミナーでこんなのって、やっぱりGoogleは潤っているんだなぁとか。この前のLispセミナーのときもそうでしたが。

まとめ

これまでMapやgadgetのAPIに興味はなかったのですが、ちょっと触ってみようかなという気にさせられました。

もらいもの

カラフルなGoogleストラップとiNTERNET magazine特別号が参加賞でした。ありがとうございました。

よかったー。 これでこのRoomでは11番ということになりました。750点問題が悔やまれてなりません。

しかし、こんなにもSystemTestでFailする人がいるとは… 早撃ちガンマンなだけではだめということなのですね。スピードと正確さでバランス良く解くのって難しそうだなぁと。

ランキングのスクリーンショット

ちょっと気になったのでとってみました。

Set 3の順位:

Set 3 Room 27の順位: ‘

こんな感じでした。

惨敗に終わったCodeJam 2006ですが、ちょっとだけTipsとか。

問題内容を公開してしまうのはルール上違反なのかもしれないので、問題とその解答は書きません。ですが、自分がCodeJamに望むにあたり、ちょっとでも早くコードを書き始めることができるようなテンプレートをつくっていました。 何かの役に立てればと思い公開してみます。

コードは続きにて。

工夫

• 問題のクラス、メソッドなどをマクロにして差し替え可能に
• テストケースをちょっとは簡単に記述できるように

使い方

• XXXが書かれているコメントのところを、問題に合わせて書き直し
• コンパイルオプションに -DLOCAL_TESTを加えて

やれば、動くんではないでしょうか。

---

/*
 * Google CodeJam 2006
 *
 * Template Code
 *
 * $Id: template.cc 320 2006-09-06 12:28:58Z takayama $
 */




/* ---------------------------------------------------------
 * XXX: 1. modify for each case
 */

define CLASS Hoge

define METHOD_RET int

define METHOD_NAME hoge

define METHOD_ARG_T vector < string >

define METHOD_ARG ss

// ---------------------------------------------------------

include

include

include

ifdef LOCAL_TEST

include

include

endif // LOCAL_TEST

define NELM(arr) ( sizeof((arr)) / sizeof((arr[0])) )

using namespace std;
typedef vector  VS_;
typedef vector ::iterator VSI_;
typedef vector  VI_;
typedef vector ::iterator VII_;


/* ---------------------------------------------------------
 * XXX: 2. Problem Solution
 */
class CLASS {
   public:
   METHOD_RET METHOD_NAME (METHOD_ARG_T METHOD_ARG);


private:
};


METHOD_RET CLASS::METHOD_NAME (METHOD_ARG_T METHOD_ARG) {
   return 0;
}


/* ---------------------------------------------------------
 * Test
 */

ifdef LOCAL_TEST

template 
void test (T &test_case, METHOD_RET assumption) {
   CLASS obj;
   METHOD_RET ret;


ret = obj.METHOD_NAME (test_case);


cout << "assumption = " << assumption << ", "
        << "result = " << ret << endl;


assert(assumption == ret);
}


void print_VS_(VS_& vs) {
   for (VSI_ i= vs.begin(); i != vs.end(); i++) {
      cout << *i << endl;
   }
}


/*
 * XXX: 3. add test cases here
 */
const int test_cases_length[] = {
   2,
   3,
};


const char *test_cases_arr[][256] = {
   {"hoge", "fuga"},
   {"moge", "yoga", "daru"},
};


/*
 * XXX: 4. add expected result here
 */
const int assumptions[] = {
   0,
   0,
};


vector  test_cases;


int main(int argc, char**argv) {
   size_t i;


for (i=0; i < NELM(test_cases_arr); i++) {
      VS_ vs = VS_(
            test_cases_arr[i],
            test_cases_arr[i] + test_cases_length[i]);

  test_cases.push_back(vs);

}


for (i=0; i < test_cases.size(); i++) {
      test(test_cases[i], assumptions[i]);
   }


return 0;
}

endif // LOCAL_TEST

---

C++のtemplateをつかったら、もっときれいに書けるんだろうなぁとか思いますが、時間がなかったのでついついマクロにしてしまったり、テストケースの書き方がstring専用になってしまっていたりと美しくありません。 でもまぁ今回に関しては実用に足りたかなと。

ぬおおっ、こっちの方が素早く解けてしまったっっっ!! しかも解答内容に自信あるし。テストケースちゃんと全部通るし。

しまったなぁ、こっちを最初からやっとけば300点くらいはとれたかもだなぁ。

とか言っても、けっきょく300点くらいではこのRoomのベスト10に入れるか入れないかくらいの成績でしかないわけで。きびしいなぁ。

あと、いま割とさっくりとできたのは時間外だからプレッシャーが少なかったというのもあると思います。やはりまだまだです。

ちなみに問題は、Permanentに関するものでした。

---

追記 :Official Rules and Regulations を読んでも特に問題なさそうなので、問題の概要を加えました。

91.62pts

だめだ… OTZ

詳細

• Qualification Set 3 Room 27
• C++で
• 250点問題のみ
• 問題の理解に11分
• ようやく全てのテストケースが通ったのでSubmitしたのが残り1分21秒、ぎりぎりすぎ
• そんなに難しい問題ではなかったのにぃ
• コードの行数 : 213 (テストコード含む)
• 750点問題は覗いただけ
• 現時点で自分のRoomの23番なのでだめでしょう
• 1位の得点がずばぬけてる (955.78 / 1000)。ありえない
• 2, 3位の得点は660-700とまだありえるレベル

これでSystem Testing Phaseで落とされたらさらにげんなりだなぁ。

もう少ししたら (あと1時間) 終了の時間です。 最終結果はどうなることやら。いちおう終わりのときを待ってみることにします。 待つ間に750問題をやってみよう。

反省

• 問題の理解遅すぎ
• いきあたりばったり
• gdbとかつかってると遅すぎ
• 普段からエラーチェックをコンパイラまかせにしてコードを書いてるから、一発で通るまともなコードが書けない
• 頭の回転遅め
• 解き方が2つあって、やや迷ってしまった
• Python覚えることにしよう
• というか、いまさらman atoiとかしてる時点でアウトかも >_< (どのヘッダをincludeしないといけないか忘れていた)

---

とにかく頭の回転を速くしないといかんと痛感しました。猛烈にトレーニングしないとまずすぎです。

しかし、決められた時間内で問題を解くなんて久しぶりでした。やっぱりこういうの好きなのかも。TopCoderで鍛え直そうかな。

いそいそと準備のためのコードとか書いてるうちにこんな時間になってしまいました…

今から参戦してきます。結果は1時間後に。