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

研究室で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)の曲線になってませんな…。

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

昨日ちゅんさんと話していた話題。select(2)中に監視対象のディスクリプタを別スレッドからclose(2)したらどうなるの？epoll(2)だと？
以下のような事を試してみた。
[code]
thread1 thread2
——————————–
(r,w) <-pipe()
select(fdset = {r})
close(r)
close(w)
(r2, w2) <- pipe() // 同じfdになる
write(w2)
[/code]

select(2)版コード

[code]
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;
}
[/code]

epoll(2)版コード

[code]
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 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;
}
[/code]

実行結果

[code]
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
[/code]
[code]
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
[/code]
[code]
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
[/code]

結果

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

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

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

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

• バックグラウンドプロセス (Service, Intent, Intent Receiver)
• Android IDLを使ったInterProcessCommunicationの仕組み
• データベース (SQLiteDatabase)
• アプリケーション管理 (PackageManager)
• Socket (DatagramSocket, ServerSocket, Socket)

そのほか、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の部分とか普通に面白かった。

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