ネットワークで通信するプログラムを書いていると、ファイルディスクリプタ（ネットワークならソケット）をselectやpollで監視して、パケットが届いたら何かする、ということが良くあります。 しかしselectやpollは、*BSD で kqueue・kevent を使ってみようで書かれているように、どうも遅いらしい。C10K問題が取りざたされている昨今、Linuxにはepoll、BSDにはkqueue、Solarisには/dev/pollというより高速な仕組みが用意されているのですが、epollを使ってしまうとLinuxでしか動かないし、kqueueで書くとBSDでしか動かない。 というわけで、epollもkqueueも同じインターフェースで使えて、#defineで簡単に中身を切り替えられると嬉しい、とは誰しも一度は思うはず。そうに違いない。 もちろん先人も同じことを考えており、libev

はやいTCPサーバの書き方 - nyaxtのPC作業ログ で id:nyaxt さんが書いてらっしゃるように、 epoll や kqueue を使う TCP_NODELAY, TCP_DEFER_ACCEPT *1 等を活用する TCP パケットを意識する I/O システムコールの回数を最小にする sendfile といったあたりは、確実にやるべきことだと思います。一方で、TCP 関連以外のオーバーヘッドが実は結構あって、 接続のタイムアウト処理 ログの出力 メモリの確保や解放をやらない あたりにも気を配る必要がある、と思います。 接続のタイムアウト処理については、以前 Kazuho@Cybozu Labs: 高速なCometサーバを書いてみた件 に書いたように、ビットアレイのリングバッファを使うのがベストだと思います。 ログの出力について、複数行を１回のシステムコールにまとめてもいいかど

元の話題は int vs size_t problem のあたり。符号なし型の減算ループをどう書くかという話。 実は、一定数までカウントアップするよりも 0 を通り過ぎるまでカウントダウンする方が速度とコードサイズの両面で良い、ってのは最適化の定石だと思ってました。特にアセンブリレベルでは。 自分が使ってた 68000 だと、ずばり、「レジスタの値をデクリメントして -1 じゃなければジャンプ」という DBRA 命令がある (しかも速い) し、x86 でも、 loop: ... subl $1, %esi jns loopみたいな形で、カウンタが符号なし型であっても高速なループが書けるんじゃないかと。 でもそういえば Metrowerks のコンパイラはこの最適化をしてくれなかったような気がするけど GCC (4.0.1 (Apple Inc. build 5465)) だとどうなんだろと

It’s said that every Haskell programmer writes their own monad tutorial, and with good reason: once you finally understand the definition and capabilities of a monad, you’ll be eager to try and break the mystique surrounding the concept of monads as a whole. To the outsider, monads are an impenetrable barrier to truly understanding Haskell; they’re cursed with a very unfortunate name, have bizarre

『あんた、学振に通る見込みあるの？』と聞けば良いです。 まず、学振とは日本学術振興会特別研究員のことを指します。 特別研究員制度は、我が国トップクラスの優れた若手研究者に対して、自由な発想のもとに主体的に研究課題等を選びながら研究に専念する機会を与え、研究者の養成・確保を図る制度です。　（特別研究員−日本学術振興会） 採用者には年間100万程度の研究費と月額20万の「研究奨励金」という名の給与が与えられます。もし、博士課程1年から採用される特別研究員（DC1）になれたなら3年間で約1,000万円が国から支給される、学生に取っては素晴らしい制度です。 ちなみに、平成20年度のDC1の採用者数は698人です。つまり、最初の問いは以下のものと同義です。 『あんたは全国で700人の中に入る自信があるの？』 それでは息子（娘）の危険な反応について整理していきます。 え、学振ってなに？ 修士課程1年の

岡野原君が自然言語処理関連で2008年に読んだ論文のベスト5を紹介しています。それに倣って、僕も個人的にインパクトのあった2008年のデータベース研究のベスト５を集めてみました。 Michael J. Cahill, Uwe Röhm and Alan D. Fekete. Serializable Isolation for Snapshot Databases. SIGMOD 2008. (ACM DOI) 真っ先に思い浮かんできたのがこの論文。SIGMOD2008のベストペーパーでもあります。僕自身、トランザクション処理を長く研究していた経験から、Serializability（ディスクのread/writeの順番をあるプロトコルに従って入れ替えても、データベースの検索・更新結果に影響を与えない）を保障しつつ、一秒間あたりに処理できるトランザクションの数（つまりスループット）を上げる

新年すっかりあけてました。 今年もよろしくお願いします。 年末年始はドタバタして昨年を振り返られなかったのですが、せっかくなので2008年に読んだ論文で私個人のベスト５を以下に列挙してみます。 D. Sontag, et. al. "Tightening LP Relaxations for MAP using Message Passing", UAI 2008 [pdf] Graphical ModelのMAP推定問題で従来解けなかった規模の複雑さの問題を高速にしかも最大であるという保障付きで解けるようにした。書いたメンバーはこの問題に関するオールスターのような感じ。解く問題は、n個の頂点からなるグラフで、各頂点には変数x1...xnがついていて、各頂点と各枝に対し関数gi(xi)、gij(xi,xj)が与えられた時、∑i gi(xi) + ∑ij gij(xi,xj)が最大となるよう

予定を立てた途端にやりたくなくなる症候群に堪えて連載を続けるmikioです（こんな私でもエアーマンくらいは倒せます）。前回はDBMの基本について説明しましたが、それを忠実に実装しても実際には使いものにはならないことにも触れました。今回は、実用的なDBMに進化すべく、Tokyo Cabinet（およびその前身のQDBM）で考えた工夫についてお話します。 ハッシュ関数についてもう少し 前回の記事に関して、「ハッシュ関数はビットシフト使って実装した方が早いよ」という旨のお便りをいただきました（ありがとうございます）。まさにその通りで、乗算命令（ここではimull）より左シフト命令（ここではsall）の方が速いみたいです（Intelの資料によると、mulが15から18で、salが4とのこと）。しかし、DBMの場合はファイルI/Oにかかる時間が支配的になるというのが重要な点です。したがって、ハッシュ

約半年間の沈黙を破ってOSSの世界に戻ってきつつあるmikioです。先日、Tokyo Cabinet（以下「TC」と呼びます）というデータベースライブラリをリリースしました。今回から数回に分けて、TCの設計と苦労話について連載してみます。 DBMとは TCは、いわゆるDBMの系譜のデータベースライブラリで、単純なハッシュテーブルをファイル上で永続化するだけの機能を提供します。DBMはAT&Tの古代UNIXの時代から受け継がれる伝統芸能なのですが、私はそういう枯れた技術が大好きなのです。 プログラマの皆さんは、PerlやRubyではハッシュ（連想配列）と呼ばれ、JavaやC++ではmapと呼ばれるような、何らかのキーに関連づけてなんらかの値を記録するデータ構造って実によく使いますよね。例えばmixiでは、ユーザアカウントに関連する情報（名前とかニックネームとか）は、ユーザIDをキーにしたハッ

ホーム フォント紹介 M+フォントは高品質デザインでぜひ日常的に使いたいのですが、漢字がたりない‥‥そこでIPAゴシックから漢字を補完しました。どなたでも無料でお使いになれます。 2020-04-15Clampフォントを修正しました。詳細は変更履歴をご参照ください。 2020-03-07MigMix／Miguフォントをバージョンアップしました。変更点「M+ TESTFLIGHT 063a に同期」「Clampフォントを追加」など‥。詳細は変更履歴をご参照ください。 2015-07-12MigMix／Miguフォントをバージョンアップしました。変更点「M+ TESTFLIGHT 060に同期」など‥。詳細は変更履歴をご参照ください。 Webサイトをスマートフォン対応しました。画像をSVGにしたのでページを拡大表示すると（PCの場合Webブラウザの横幅を変えると）一部画像を大きく見ることが可能