Linux カーネルのコンテキストスイッチ処理を読み解く - naoyaのはてなダイアリー
Linux カーネルのプロセススケジューラの核である kernel/sched.c の schedule() を読み進めていくと、タスク切り替え(実行コンテキスト切り替え)はその名も context_switch() という関数に集約されていることが分かります。2.6.20 の kernel/sched.c だと以下のコードです。 1839 static inline struct task_struct * 1840 context_switch(struct rq *rq, struct task_struct *prev, 1841 struct task_struct *next) 1842 { 1843 struct mm_struct *mm = next->mm; 1844 struct mm_struct *oldmm = prev->active_mm; 1845 184
ithreads でスレッドプール - naoyaのはてなダイアリー
マルチスレッドなサーバー実装を色々模索していて、Perl の ithreads で遊ぶ。ithreads は Linux の pthread にリンクさせた perl なら一応 NPTL で動いてくれるので、pthread アプリケーションの設計を試すのにも良い。 試しににやってみたのは、たとえば mod_perl とかで重い SQL でブロックするのが嫌なときとかにそれを別プロセスに丸投げしてやる、その丸投げされる側のサーバー実装。(やりたいことだけに関して言うと、TheSchwartz に似てる) クライアントとサーバーの IPC は UNIX ドメインソケット メッセージングのプロトコルは JSON サーバーはクライアントからのリクエストをバッファリングしたら、SQL を実行する前にクライアントとの接続を切断 この時点でクライアントは制御が戻る サーバーは内部ではフロントエンド /
マルチスレッドのコンテキスト切り替えに伴うコスト - naoyaのはてなダイアリー
また Linux カーネルの話です。 Linux では fork によるマルチプロセスと、pthread によるマルチスレッドでの並行処理を比較した場合、後者の方がコストが低く高速と言われます。「スレッドはメモリ空間を共有するので、マルチプロセスとは異なりコンテキストスイッチ時にメモリ空間の切り替えを省略できる。切り替えに伴うオーバーヘッドが少ない。」というのが FAQ の答えかと思います。 が「オーバーヘッドが少ない」と一言にいわれても具体的にどういうことなのかがイメージできません。そこで Linux のスレッド周りの実装を見て見ようじゃないか、というのが今回のテーマです。 3分でわかる(?) マルチプロセスとマルチスレッド まずはうんちく。マルチプロセスとマルチスレッドの違いの図。以前に社内で勉強会をしたときに作った資料にちょうど良いのがあったので掲載します。Pthreadsプログラミ
γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー
通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビット
Perl でローカルのアドレスを取得する - naoyaのはてなダイアリー
ifconfigの出力をsedでパース — ありえるえりあ まだ Linux を触り始めて間もない頃に、サーバーを構築していてローカルの IP アドレスをシェルスクリプトから利用する必要があって、どうやって取得するべきだろうかと小一時間悩んだのですが結局分からず Perl の正規表現で ifconfig を parse したことがありました。ioctl() を使ってデバイスを操作する必要がある、ということを知ったのは数年後、割と最近のことです。なんということでしょう。 では、Perl で IP アドレスを取得する場合ですがモジュールを使ってよいのであれば IO::Interface がよいだろうと思っています。IO::Interface は Pure Perl ではありませんが、XS で ioctl() を呼び出しているので比較的高速且つ素直な実装だと思います。 #!/usr/local/
naoyaのはてなダイアリー - Perl のクロージャ
いつもお世話になってるあの人とかあの人とかが山口家の逆襲->perl-解説->クロージャというクロージャの解説ページをブックマークしてるのをきっかけに、 Perl のクロージャについて自分もちゃんと理解できてるのかというのを考えてみましたが、どうも微妙です。 クロージャについて、何でいまいち理解しきれてない感じがあるのかというと、クロージャがどういうものであるかは知ってるけど、クロージャをどういう時に使うと良いのかが具体的にあれとこれという感じで思い付かないからなのではないかと思った。 なので、Perl でクロージャを使ってる実装とかを見て、どんなときに使われるものなのかをリストアップして理解を深めてみよう..のコーナーです。 クラスにデータを保持するためのクロージャ 僕がぱっと思いついたのは Class::DBI の中で使われている Ima::DBI におけるデータベースハンドラのキャッ
pmtools - naoyaのはてなダイアリー
Journal of Mark Leighton Fisher (4252) で Tom Christiansen が 1999 年に書いた pmtools なるツール群があるという話が挙がってました。pmtools という名前を初めて聞いたもんで、試しにインストールしてみました。 pmtools は Perl のモジュールや POD に関する小さなコマンドラインツールがいろいろ同梱されてるパッケージです。インストールはアーカイブ落としてきて perl Makefile.PL; make; sudo make install で OK。それぞれのコマンドの使い方は README 見るなり man 見るなりで見ることができます。 基本的に Perl のコード数行からなる簡易ツールで、ワンライナーとかでやることが多いものをコマンドひとつで呼べるようにしてるとか、そういうものがほとんどでした。1
naoyaのはてなダイアリー - HTML::TagCloud
del.icio.us / miyagawa 経由で見つけた CPAN モジュール HTML::TagCloud。Tag Cloud (はてなブックマークの右側に出てくるタグ一覧みたいなやつ) を生成する CPAN モジュールです。 出力はどんな感じかなと思って使ってみました。 #!/usr/local/bin/perl use strict; use HTML::TagCloud; my $tags = [ { tag => 'blog', count => 20}, { tag => 'ajax', count => 10}, { tag => 'mysql', count => 5}, { tag => 'hatena', count => 12}, { tag => 'bookmark', count => 30}, { tag => 'rss', count => 1}, { t
naoyaのはてなダイアリー - Perlでモダンなネットワークサーバーを書くには
Comet については、普及するかどうかという以前に、どう使えばいいのか、正しく使った場合に何をどこまでできるのか、という理解が共有されていないように思います。なので、(あくまで私見ですが) 使用したスライドの一部を公開したいと思います。よろしければごらんください。 サイボウズラボの奥さんによる Comet のサーバー周りの資料。すばらしい。C10K に対してどのようなアーキテクチャをとるのが良いかとの考察が特に勉強になりました。 また、問題や改善すべき点があれば、教えていただければ幸いです。 というので問題、改善すべきというわけではないですが Perl 周りの話で少し補足を。 資料中の「初心者へのオススメが PoCo::Server::HTTP でパフォーマンスが欲しい人には Sys::Syscall qw/:epoll/」の点。おそらく Perl でも epoll を使えますよというこ
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
prefork サーバーと thundering herd 問題 - naoyaのはてなダイアリー
Catalyst を POE で動かす Engine の Catalyst::Engine::HTTP::POE という実装が CPAN にあります。"Single-threaded multi-tasking Catalyst engine " だそうです。"Single-threaded" と言いつつも実装を覗いてみると環境変数 CATALYST_POE_MAX_PROC を 1 よりも大きく設定することで prefork する実装になってます。POEシングルスレッドではアプリケーション内で発生するブロックを避けることが難しいのでそのための実装じゃないかなと思います。 ところでこの Catalyst POE エンジン、prefork の実装はどのように行っているかというと POE から prefork と名の付いたイベントが発生するとおもむろに子プロセスを生成する、というのもの。複数の
第11回 Kansai.pm / スペルミス修正プログラムを作ろう - naoyaのはてなダイアリー
昨日は第11回 Kansai.pm でした。 今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。 PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資料) は圧巻でした。伊奈さんの本文抽出の話 (発表資料)、はこべさんのコルーチンの話 (発表資料)、いずれも難解になりがちなところを凄く分かりやすく解説されていて、さすがだなと思いました。各々ショートトークも、いずれも良かったです。 スペルミス修正プログラムを作ろう 自分も 20 分ほど時間をいただいて、スペルミス修正プログラムの作り方について発表しました。 スペルミス修正プログラムを作ろうView more presentations from Naoya Ito. スペルミス修正プログラムについてはずばり スペル
naoyaのはてなダイアリー - コネクションプーリングの話
かなりながーいエントリになる予定なので,結論だけ最初に書くとこんな感じ. この話題については自分も あとで書く と言って書いてなかったので書いてみますよ。2006年の下期にもなってコネクションプーリングかよというツッコミもありそうですが、あとで書くといったら書くの。あとで読むといったら読む。 普通「コネクションプーリング」と言ったら、主に二つの役割があると思います。話を簡単にするためにウェブアプリケーションに限定して言及します。 ウェブアプリケーションから DB への接続を開けっ放しにして、接続に必要とされるオーバーヘッドをカットして双方の負荷を下げる。 ウェブアプリケーションと DB への接続を「使いまわす」ことで、同時接続本数を節約する。 というもの。 mod_perl で DB と接続維持するとコネクション数増えて云々という話は主に前者のみについての話になります。Apache::DB
WEB+DB PRESS Vol.49 はてなブックマーク構築ノウハウ大公開 - naoyaのはてなダイアリー
WEB+DB PRESS Vol.49 にて「はてなブックマーク構築ノウハウ大公開」という特集記事を執筆しました。 WEB+DB PRESS Vol.49 作者: arton,桑田誠,角田直行,和田卓人,伊藤直也,西田圭介,岡野原大輔,縣俊貴,大塚知洋,nanto_vi,徳永拓之,山本陽平,田中洋一郎,下岡秀幸,ミック,武者晶紀,高林哲,小飼弾,はまちや2,WEB+DB PRESS編集部出版社/メーカー: 技術評論社発売日: 2009/02/23メディア: 大型本購入: 10人 クリック: 373回この商品を含むブログ (45件) を見る 現在サービス中の新しいバージョンのはてなブックマークの開発には9ヶ月の期間を要しました。システムは一から作り直しを行っています。なぜシステムの作り直しを行う必要があったのか、どのような方法/設計でシステム再構築を行ったのか、新システムで利用しているソフト
Latent Semantic Indexing - naoyaのはてなダイアリー
情報検索におけるベクトル空間モデルでは、文書をベクトルとみなして線形空間でそれを扱います。この文書ベクトルは、文書に含まれる単語の出現頻度などを成分に取ります。結果、以下のような単語文書行列 (term document matrix) が得られます。 d1 d2 d3 d4 Apple 3 0 0 0 Linux 0 1 0 1 MacOSX 2 0 0 0 Perl 0 1 0 0 Ruby 0 1 0 3 この単語文書行列に対して内積による類似度などの計算を行って、情報要求に適合する文書を探すのがベクトル空間モデルによる検索モデルです。 見ての通り、単語文書行列の次元数は索引語の総数です。文書が増えれば増えるほど次元は増加する傾向にあります。例えば索引語が100万語あって検索対象の文書が 1,000万件あると、100万次元 * 1,000万という大きさの行列を扱うことになりますが、単
OGC2009 での発表資料 - naoyaのはてなダイアリー
昨日開催されました OGC2009 にて、はてなブックマークのコミュニティについて発表させていただきました。 INTERNET Watch さんなどでも取り上げていただいてます。 http://internet.watch.impress.co.jp/cda/event/2009/02/05/22342.html http://game.watch.impress.co.jp/docs/20090206/ogc_net.htm 以下に発表資料を公開します。(ウェブでの公開用に少々編集を行いました) OGC2009 はてなブックマークについてView more presentations from Naoya Ito. (tags: hatena) 後半時間が足りずに飛ばしてしまったので、記事では触れられていませんが、まだまだ課題が山積みです。今後も継続的に改善していきたいと思っています。
naoyaのはてなダイアリー - Linuxのページキャッシュ
世間では PHP が、Perl が、と盛り上がっているようですが空気を読まずまたカーネルの話です。今回はページキャッシュについて。 /dev/shm に参照系ＤＢを持っていくと I/O 負荷が激減した件（当たり前だけど） - drk7jp で、ディスク上にあったファイルを /dev/shm (tmpfs) に移したら I/O 待ちがなくなって負荷がさがった、ということなんですがおそらくこれは tmpfs に置く必要はないかなと思います。Linux (に限らず他の OS もそうですが) にはディスクの内容を一度読んだらそれはカーネルがキャッシュして、二度目以降はメモリから読む機構 = ページキャッシュがあります。tmpfs にデータを載せることができた、ということは物理メモリの容量に収まるだけのデータサイズかと思うので、放っておけば該当のファイルの内容すべてがメモリ上にキャッシュされて io
KOF 2008 の発表資料 - naoyaのはてなダイアリー
KOF 2008 での発表資料「はてな流大規模データ処理」を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/081108huge_data.ppt 一部参考文献からの引用 (Introduction to Information Retrieval から Vector space model の図、たつをの ChangeLog から転置インデックスの図) があります。この場を借りて感謝。 環境によってはおそらくフォントの表示がいまいちだと思いますが、ご了承ください。 追記 SlideShare にアップロードしました。 081108huge_data.pptView SlideShare presentation or Upload your own. (tags: linux mysql) 追記: メモリはディスクの 150 倍について
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
YAPC::Asia 2日目 「はてなブックマークのシステムについて」 - naoyaのはてなダイアリー
YAPC::Asia 2009 1日目 「Perlで圧縮」の資料 - naoyaのはてなダイアリー