2007年11月23日
What Every Programmer Should Know About Memory
udrepper大先生の大作、心して読ませて頂きます。触りの部分は授業やらCPU実験で学んだけれど、ここまで深くメモリについて掘り下げた文章は無いんじゃないだろうか・・・。
# 明日から台北
2007年11月20日
研究室で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万個のソケットを管理しているとします。で、ソケットが１個づつ順番に読み込み可能になるという最悪のシチュエーションを考えて見ます。select(2)だと10000 * 10000のループが回ります。epoll(2)だと10000 * 1回のループが回ります。
そういう上手いペースで接続をする方法を思いつかないので、実データで示せないのが申し訳ないですが。libeventのグラフもO(n ^ 2)の曲線になってませんな...。
2007年11月17日
上位進出。1ヶ月かかった・・・。鯖２に居るのでやってる方は是非誘ってくださいまし。
2007年11月16日
昨日ちゅんさんと話していた話題。select(2)中に監視対象のディスクリプタを別スレッドからclose(2)したらどうなるの？epoll(2)だと？
以下のような事を試してみた。
thread1 thread2
--------------------------------
(r,w) <-pipe()
select(fdset = {r})
close(r)
close(w)
(r2, w2) <- pipe() // 同じfdになる
write(w2)
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;
}
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 - 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日
チームライブラリというのは、紙に印刷してコンテストに持ち込めるコード片です。有名なアルゴリズムのコードを持ち込んで、問題に合わせて改変して使うことが有ります。
とはいえ実質はid:nyaasanが１年のときから作り溜めてきたmasterpieceです。
2007年11月06日
絶望的な脱力感に襲われ中。なーんもやる気せん・・・が、やる事は山積み。
2007年11月05日
ACM/ICPC アジア地区予選東京大会に参加してきました。
- 問題
- NHKニュース
- Unknown id:nyaasanのレポート
- echizen.bat oxyさんのレポート
- TalesOfCoders ymatsuさんのレポート
- __________ id:kiwi_xpさんのレポート
チームUnknownとして、id:nyaasan, id:ushioda、コーチchunさんと共に出場、結果は２位でした。
１位はoxyさん率いる京都大学echizen.batでした。終了1分前にひっくり返されました。それまでは時間でダントツで勝っていただけに悔しい。最後の最後でechizenの底力に負けました。優勝おめでとうございます。
3位は北京大学。3位は東京大学Makegumi。4位は北京大学A New Startでした。ちなみに中国勢に日本勢が勝ったのは１０年間で初めての事らしいです。やりましたぜ。
しかし正直nyaさんとushたんがいなければこんな成績を取れるはずがなかったと思う。Red Coderであるnyaさんのコーディング力とushたんのアルゴリズム発想能力は本当に神。僕は２人の役割調整、ペアプロでのバグの指摘、他チームの状況把握、時間&問題スケジューリングなどなど、２人の能力が最大限活かせるように行動していただけです。
僕は普段泥臭いシステムソフトウェアばっかり書いていて、アルゴリズミックなコードを素早く書き上げるのは全然得意じゃないんだけど、二人のお陰でここまで来れた気がします。本当にありがとう。そして世界大会行ける様に頑張りましょう。
あと個人的な事情ですが、echizenのoxyさんとは2年前に一緒に未踏ソフトウェアをやって、その時は高田先生の評価にも有るように主だった成果を出すことが出来なかったのですが(期間中の9ヶ月は死に物狂いで頑張ってたんだけど)、今回この様な形で１，２フィニッシュを飾ることが出来て結構嬉しかったりします。
せっかく２位になったので"Sake Challenge"は気合を入れて、いつものPFI飲み会のノリでばかばか飲みまくる。冷酒冷酒冷酒。周りの人にも薦めまくる。ushたんとかnak?の人たちとか。後半はあまり良く覚えてないのですが、次の日はすっきり起きられたのでまだまだ昔の勢いは戻ってこないですね・・・。
という訳で２日間がっつり楽しんできました。今月末に海外派遣という名目で台湾大会に行かせて頂く事ができるみたいなので、そこでもっと強い中国勢とまた戦う予定。
# 最後に東京大学競技プログラミング部において練習会を企画して下さったISの先輩方、ICPC運営してくれた全ての方々に感謝。