2007年11月23日

What Every Programmer Should Know About Memory

What Every Programmer Should Know About Memory

udrepper大先生の大作、心して読ませて頂きます。触りの部分は授業やらCPU実験で学んだけれど、ここまで深くメモリについて掘り下げた文章は無いんじゃないだろうか・・・。

# 明日から台北

2007年11月20日

epoll(2)とselect(2)の計算量

研究室でid:yama6がepollとか言っていて、mixi Engineers' Blog さんの「Linux Programming、epollの話」を思い出した。

パフォーマンスの方はselect(2)とpoll(2)のtime complexityがO(n)に対しepollはO(1)と無視のできない性能の差を実現しています。

これこれ、書こうとして忘れてた。僕の理解だとepoll(2)はO(n)でselect(2)がO(n^2)です。この差はsignificantですよ!

例えば1万個のソケットを管理しているとします。で、ソケットが1個づつ順番に読み込み可能になるという最悪のシチュエーションを考えて見ます。select(2)だと10000 * 10000のループが回ります。epoll(2)だと10000 * 1回のループが回ります。

そういう上手いペースで接続をする方法を思いつかないので、実データで示せないのが申し訳ないですが。libeventのグラフもO(n ^ 2)の曲線になってませんな...。

2007年11月17日

MHF

上位進出。1ヶ月かかった・・・。鯖2に居るのでやってる方は是非誘ってくださいまし。

2007年11月16日

close(2) while select(2)ing

昨日ちゅんさんと話していた話題。select(2)中に監視対象のディスクリプタを別スレッドからclose(2)したらどうなるの?epoll(2)だと?

以下のような事を試してみた。

thread1             thread2
--------------------------------
(r,w) <-pipe()
select(fdset = {r})
                    close(r)
                    close(w)
                    (r2, w2) <- pipe() // 同じfdになる
                    write(w2)

select(2)版コード

void* fd_consumer(void *writefd_){
  int* pipefd = (int*)writefd_;
  sleep(1);
  close(pipefd[0]);
  close(pipefd[1]);
  cerr << "close(2) pipe" << endl;
  sleep(1);
  if(pipe(pipefd)){ perror("Failed to make pipe"); exit(1); }
  cerr << "pipe(2) in another thread: " << pipefd[0] << ", " << pipefd[1] << endl;
  sleep(1);
  cerr << "write(2) to pipe" << endl;
  char buf[] = "a";
  write(pipefd[1], buf, 1);
  return NULL;
}

int main(void){
  int pipefd[2];
  if(pipe(pipefd)){
    perror("failed to make pipe");
    exit(1);
  }
  cerr << "pipe(2): " << pipefd[0] << ", " << pipefd[1] << endl;
 
  fd_set rfds;
  fd_set wfds;
  fd_set efds;

  pthread_t thread;
  pthread_create(&thread, NULL, fd_consumer, (void *)pipefd);

  FD_ZERO(&rfds);
  FD_ZERO(&wfds);
  FD_ZERO(&efds);
  FD_SET(pipefd[0], &rfds);
  FD_SET(pipefd[0], &wfds);
  FD_SET(pipefd[0], &efds);

  struct timeval tv; tv.tv_sec = 5; tv.tv_usec = 0;
  int r = select(pipefd[0]+1, &rfds, &wfds, &efds, &tv);
  if(r < 0){
    cerr << "select(2) error" << endl;
  } else if (r == 0){
    cerr << "select(2) timedout" << endl;
  }else{
    cerr << "select(2) catched " << r << " elements" << endl;
  }
  if(FD_ISSET(pipefd[0], &rfds))
    cerr << "pipefd[0] set(rfds)" << endl;
  if(FD_ISSET(pipefd[0], &wfds))
    cerr << "pipefd[0] set(wfds)" << endl;
  if(FD_ISSET(pipefd[0], &efds))
    cerr << "pipefd[0] set(efds)" << endl;
  return 0;
}

epoll(2)版コード

void* fd_consumer(void *writefd_){
  int* pipefd = (int*)writefd_;
  sleep(1);
  close(pipefd[0]);
  close(pipefd[1]);
  cerr << "close(2) pipe" << endl;
  sleep(1);
  if(pipe(pipefd)){ perror("Failed to make pipe"); exit(1); }
  cerr << "pipe(2) in another thread: " << pipefd[0] << ", " << pipefd[1] << endl;
  sleep(1);
  cerr << "write(2) to pipe" << endl;
  char buf[] = "a";
  write(pipefd[1], buf, 1);
  return NULL;
}

int main(void){
  int epfd = epoll_create(10);

  int pipefd[2];
  if(pipe(pipefd)){
    perror("failed to make pipe");
    exit(1);
  }
  cerr << "pipe(2): " << pipefd[0] << ", " << pipefd[1] << endl;

  struct epoll_event epev;
  memset(&epev, 0, sizeof(epev));
  epev.events = EPOLLIN;
  epev.data.fd = pipefd[0];
  epoll_ctl(epfd, EPOLL_CTL_ADD, pipefd[0], &epev);

  pthread_t thread;
  pthread_create(&thread, NULL, fd_consumer, (void *)pipefd);

  struct epoll_event events[10];
  int r = epoll_wait(epfd, events, 10, 5000);
  if(r < 0){
    cerr << "epoll(2) error" << endl;
  } else if (r == 0){
    cerr << "epoll(2) timedout" << endl;
  }else{
    cerr << "epoll(2) catched " << r << " elements" << endl;
  }

  for(int i=0; i<r; i++){
    if(events[i].events & EPOLLIN)
      cerr << "EPOLLIN" << endl;
    if(events[i].events & EPOLLOUT)
      cerr << "EPOLLOUT" << endl;
    if(events[i].events & EPOLLERR)
      cerr << "EPOLLERR" << endl;
    if(events[i].events & EPOLLHUP)
      cerr << "EPOLLHUP" << endl;
  }
  return 0;
}

実行結果

mac% g++ seltest.cpp -Wall; time ./a.out
pipe(2): 3, 4
select(2) error
pipefd[0] set(rfds)
pipefd[0] set(wfds)
pipefd[0] set(efds)
./a.out  0.00s user 0.01s system 0% cpu 1.011 total
linux% g++ -Wall seltest.cpp -lpthread; time ./a.out
pipe(2): 3, 4
close(2) pipe
pipe(2) in another thread: 3, 4
write(2) to pipe
select(2) catched 1 elements
pipefd[0] set(rfds)
./a.out  0.00s user 0.00s system 0% cpu 5.007 total
linux% g++ -Wall epolltest.cpp -lpthread; time ./a.out
pipe(2): 4, 5
close(2) pipe
pipe(2) in another thread: 4, 5
write(2) to pipe
epoll(2) timedout
./a.out  0.00s user 0.00s system 0% cpu 5.007 total

結果

select(2)だとMacOS XとLinuxで挙動が違う。未定義動作?

Macの方の動作を意図してselect(2)を使ったプログラムを書いていたので、ちょっと困った。代替となるportableな方法無いかなぁ。

2007年11月14日

Android Review

- Android - An Open Handset Alliance Project
- Google's Android OS early look SDK now available
- グーグルが広げる携帯電話の可能性--Andoroidファーストルック

HelloWorldを書くのは既にんぱか大先生にやられてしまったので、もうちょっと先を追ってみよう。iアプリからプログラミングを始めた人間としてクラス一覧を眺めていて気になったのは次のような機能。

そのほか、iアプリに有る機能は大体揃っているという印象。UIは2D Graphicsでなんとでもなる。権限周りはかなり気を付けてAPIが策定されている気がする。

バックグラウンドプロセスが作れるのは大きい。GmailをポーリングしてAIDLでフォアグラウンドプロセスにnotificationさせれば、もうそれだけで僕は使う。後はDatagramSocket使えるとネットワークゲームも作りやすくなるかもしれませんね。今まで手動でやらせていたソフトウェアの自動更新もPackageManagerを使うことによって自動的に行えるかも?なかなか素晴らしい。

というわけでソース見てみる。まずはemulator。

pficore% ls
README  build-emulator.sh  qemu  sdl
pficore% find . -type f | xargs grep Google
./qemu/android_skin.h:/* Copyright (C) 2007 Google, Inc.
./qemu/hw/platform_interrupt.c:** Copyright 2007, Google Inc.
./qemu/hw/platform_fb.c:** Copyright 2007, Google Inc.
./qemu/hw/platform_timer.c:** Copyright 2007, Google Inc.
./qemu/hw/events_device.c: * Copyright 2006, Google Inc.
./qemu/hw/platform_device.c:** Copyright 2007, Google Inc.
./qemu/hw/platform_switch.c:** Copyright 2007, Google Inc.
./qemu/hw/android_arm.c:** Copyright 2007, Google Inc.
./qemu/hw/platform_tty.c:** Copyright 2007, Google Inc.
./qemu/hw/platform_device.h:** Copyright 2007, Google Inc.
./qemu/hw/platform_mmc.c:** Copyright 2007, Google Inc.
./qemu/hw/platform_audio.c:** Copyright 2007, Google Inc.
./qemu/android_userdata_img.h:/* Copyright (C) 2007 Google, Inc.
./qemu/android_icons.h:/* Copyright (C) 2007 Google, Inc.
./qemu/varint.h:// Copyright 2006 Google Inc.  All Rights Reserved.
./qemu/dcache.h:// Copyright 2006 Google Inc.  All Rights Reserved.
./qemu/android_sdl.c:/* Copyright (C) 2006-2007 Google, Inc.
./qemu/trace_common.h:/* Copyright (C) 2006-2007 Google, Inc.
./qemu/android.h:/* Copyright (C) 2007 Google, Inc.
./qemu/dcache.c:// Copyright 2006 Google Inc.  All Rights Reserved.
./qemu/trace.c:/* Copyright (C) 2006-2007 Google, Inc.
./qemu/varint.c:// Copyright 2006 Google Inc.  All Rights Reserved.
./qemu/trace.h:/* Copyright (C) 2006-2007 Google, Inc.

qemuだ。qemuにhw依存のコードだけ追加して、後は実環境のバイナリを食わせればエミュレーターになる訳ですね。コード的には追加は約1万行。今のReference ImplementationはQualcomm MSM7200 (ARM)で動いているらしいので、クロスコンパイルしてバイナリ作ったらエミュレーターで動くはず。調べてみたら既にやってる人がいた

アプリケーションが走る肝心のDalvik VMのソースは?と探したが中の人によると「Unfortunately source code is not yet available, so you won't be able to dig into Dalvik just yet. 」らしい。

ただohadev.comに少しだけ情報が出ていて、どうやらApache Harmony Java VMに手を加えたものではあるらしい。まぁソースは公開予定らしいのでそれを待ちましょう。しかしGoogleはqemuやHarmonyをもっとアピールして上げても良いのになーと思う。そのほかユーザーランド周りは先ほどのクロスコンパイラーの人が調べている

最後はカーネル。gitリポジトリが公開されている。"2007-10-09 Linus Torvalds"と書いてある以降のcommitがandroid用の変更にあたる。昔から携帯向けの最底辺のコードを見てみたかったので結構有り難い。開発してる方々の名前でググらせて頂くとと2人ともBeOSを開発されていた方らしい。

適当にdiff見てみただけだけど、MSM 7200向けにLinuxをポーティングしたのと後は各種デバイス向けのドライバ。あとRPCを共有メモリ上で実現したり。後は僕はあんまりデバドラ書いた経験が無いのでTTYとかSerialPortの部分とか普通に面白かった。

早く日本でも実機が出るといいですね。こういうのは実機が無いと全然開発する気が起きない。あとエミュレーターと実機では挙動が違うというのはよくある話。しかし出るんですか

2007年11月09日

Unknown: チームライブラリ公開

Unknown: チームライブラリ公開

チームライブラリというのは、紙に印刷してコンテストに持ち込めるコード片です。有名なアルゴリズムのコードを持ち込んで、問題に合わせて改変して使うことが有ります。

とはいえ実質はid:nyaasanが1年のときから作り溜めてきたmasterpieceです。

2007年11月06日

そして

絶望的な脱力感に襲われ中。なーんもやる気せん・・・が、やる事は山積み。

2007年11月05日

ACM/ICPC アジア地区予選東京大会

ACM/ICPC アジア地区予選東京大会に参加してきました。

- 問題
- NHKニュース
- Unknown id:nyaasanのレポート
- echizen.bat oxyさんのレポート
- TalesOfCoders ymatsuさんのレポート
- __________ id:kiwi_xpさんのレポート

チームUnknownとして、id:nyaasan, id:ushioda、コーチchunさんと共に出場、結果は2位でした。

1位はoxyさん率いる京都大学echizen.batでした。終了1分前にひっくり返されました。それまでは時間でダントツで勝っていただけに悔しい。最後の最後でechizenの底力に負けました。優勝おめでとうございます。

3位は北京大学。3位は東京大学Makegumi。4位は北京大学A New Startでした。ちなみに中国勢に日本勢が勝ったのは10年間で初めての事らしいです。やりましたぜ。

しかし正直nyaさんとushたんがいなければこんな成績を取れるはずがなかったと思う。Red Coderであるnyaさんのコーディング力とushたんのアルゴリズム発想能力は本当に神。僕は2人の役割調整、ペアプロでのバグの指摘、他チームの状況把握、時間&問題スケジューリングなどなど、2人の能力が最大限活かせるように行動していただけです。

僕は普段泥臭いシステムソフトウェアばっかり書いていて、アルゴリズミックなコードを素早く書き上げるのは全然得意じゃないんだけど、二人のお陰でここまで来れた気がします。本当にありがとう。そして世界大会行ける様に頑張りましょう。

あと個人的な事情ですが、echizenのoxyさんとは2年前に一緒に未踏ソフトウェアをやって、その時は高田先生の評価にも有るように主だった成果を出すことが出来なかったのですが(期間中の9ヶ月は死に物狂いで頑張ってたんだけど)、今回この様な形で1,2フィニッシュを飾ることが出来て結構嬉しかったりします。

せっかく2位になったので"Sake Challenge"は気合を入れて、いつものPFI飲み会のノリでばかばか飲みまくる。冷酒冷酒冷酒。周りの人にも薦めまくる。ushたんとかnak?の人たちとか。後半はあまり良く覚えてないのですが、次の日はすっきり起きられたのでまだまだ昔の勢いは戻ってこないですね・・・。

という訳で2日間がっつり楽しんできました。今月末に海外派遣という名目で台湾大会に行かせて頂く事ができるみたいなので、そこでもっと強い中国勢とまた戦う予定。

# 最後に東京大学競技プログラミング部において練習会を企画して下さったISの先輩方、ICPC運営してくれた全ての方々に感謝。