February 10, 2008

Re: 私の peephole 最適化

xhlメモに触発されて久しぶりにプログラミング関連の記事。ほとんどの項目はxhlメモで網羅されてしまっているが、いくつか自分がやることを追加してみる。

ライブラリのソースを読む
特にSTLを使っている場合。STLの内部で実際どのようにコードが走るのかを知ることで糸口が見つかる場合がある。自分の例では、使っていたSTLが自分と思っていたのと違う動作をしていたという例があった。

メモリアロケーションに注意
STLのsetやmapを多用しているとヒープからのメモリの確保や解放が頻発する。アルゴリズムのコアな部分でこれが起きると、下手するとアロケータが何割かのCPU時間を使うこともあるので注意が必要。動的メモリアロケーションがアルゴリズムの本質上どうしても必要なら、自前のより軽量かつ目的に特化したアロケータを書いてみたり、汎用的なインターフェースを持ちながらも高速なアロケータに取り替えてみる(参考)等してみるといいかも。

本当は「プログラムを最適化する10の方法」とかいって10個並べると格好いいが、まあ思いつかないのでこんなところで。ちなみに話題のもととなった某氏のコードが純粋計算系のプログラムだったので今回は扱っていないが、I/Oやシステムコールを多用するプログラム(サーバアプリケーションとか)になるとまた違った視点からの最適化も必要であるとは思う。

| | Comments (0) | TrackBack (0)

September 09, 2007

Linux: ifconfigコマンドの実装

何度となく実装しているはずだがいつもやりかたが思い出せなくなって時間を無駄にしている気がするので、ここにメモ。

ifconfigコマンドで出てくるようなネットワークインターフェースの情報を直接取得したいときにはどうするか?(Linux限定)

まずはインターフェースのアドレスなどの情報を取得する方法についてはnetdevice(7)にある。基本的にはソケット(種類は何でもいいらしい)を作ってそのソケットに対してioctlすることになる。

次にインターフェースの送受信したバイト数やパケット数等の情報は/proc/net/devから読んでいるようだ。システムが現在認識しているインターフェースの一覧もここから得ることができる。

余談であるが、netdeviceのマニュアルを読むと、デバイスのマルチキャストMACアドレスを設定したり削除したりする方法が示唆されている(SIOCADDMULTI, SIOCDELMULTI )。マルチキャストアドレスの現在の設定については/proc/net/dev_mcastで読むことができる。マルチキャストアドレスを自由に設定するツールは少なくとも標準的にはないような気がするので、知っておくと便利かもしれない。(もしあればコメント欄にツッコミをよろしく)

| | Comments (0) | TrackBack (0)

June 17, 2007

今日の夢

東大の入試(2次試験)を受ける夢。そういう夢自体は時々見るのだが、今日のは問題文が謎だった。

数学の問題で、「文脈自由文法の定義と性質について述べ、それが現在のコンピュータ科学においてどのような役割を果たしているか具体的に述べよ」云々、というもの。最近は情報が必修になったとはいえこれはマニアックすぎないか?などと考えながら解答している夢であった。

寝る前にIRCでCの式と文の違いとかそういう話を延々としていたからかもしれない。

| | Comments (0) | TrackBack (0)

June 05, 2006

codeblogのgonzui

Apacheのソースを読みたいんだけどgrepもやってられないしどうしたものか、cscopeもいまいちわからんし手元にgonzui立てるか、とか思っていたら、codeblogというサイトにgonzuiがあっていろいろ登録されてるのを発見した。codeblogというURLはちょくちょく目にしていた気がするが、IPAの事業だったのか。

Linuxカーネルは研究室のlxrを使うとして、それ以外のツールのコード読みはここのgonzuiを使わせてもらうことにしよう。

Continue reading "codeblogのgonzui"

| | Comments (1) | TrackBack (0)

February 10, 2006

メモ

超ローカルで意味不明なメモ。

ptrace対象の子プロセスがシグナルを食らったときにはptraceしている親に対して通知が行くが、親がその通知を受け取った時点で、子プロセスのスタックにはsignal frameがセットアップされているようである(arch/i386/kernel/signal.c:setup_frameもしくはsetup_rtframe)。ということでSIGSEGVを受け取った時点でespからごにょごにょすればsigcontextにアクセスできるか。

こんなことしてないでさっさとスライド直しなさい。

| | Comments (0) | TrackBack (0)

February 05, 2006

究極のprintfデバッグ

コードの任意の箇所に画面出力を入れて値を出力させたり、そもそもそこに到達したことを示すメッセージを出力させたりする、いわゆる"printfデバッグ"は多くのプログラマが日常的に実践していることだろう。俺などは無精なので未だにgdbの使い方を覚えておらず、printfデバッグに頼り切りだったりする。

さて、システム系のあやしいコードを書いていると、時にコードの状態がめちゃくちゃになって、printfデバッグすら怪しくなることがある。ライブラリの関数を呼ぼうとするとクラッシュするといった具合だ。そんなときに使えるのがint3デバッグ。「果たしてどこまでは正常に動いているのか」を知りたいときに、「ここまでは来てるんじゃないかな?」という箇所に

__asm__ __volatile__("int3");
と書く。この命令はプロセッサにデバッグ例外を生じさせ、通常はそれがOSによって捕捉され、シグナルの形でプロセスに送られてくる。それまでsignal 11(SIGSEGV)で落ちていたのがこのint3によってsignal 5(SIGTRAP)に変わったら、少なくともそこまではちゃんと実行されたということがわかる。このようにしてクラッシュしている範囲を絞り込んでいくことができる。

以上、x86/Linux限定の超どうでもいい話でした。でも同様のことはどんなOS/アーキテクチャでも適宜値を読み替えれば使えるはず。

| | Comments (0) | TrackBack (0)

January 08, 2006

STLコンテナとSSE

「vector<double>に対してSSEを適用したいんだけど」と某氏に相談されたので、相談料代わりにネタにさせていただく。

x86はデータのalignmentに対してはかなり制約が緩やかで、大抵の場合は(性能上のペナルティはあるにせよ)alignmentを無視していても正しく動作する。ただし、SSE命令は例外で、16byte alignといったalignmentを要求する命令がある。(違反すると何らかのexceptionが起きる)

vectorは勝手にメモリを確保してくれるので普段は便利なのだが、SSEを適用しようとすると、「勝手に確保された」メモリが果たしてalignmentを守っているか?という疑念が生じるわけだ。対策としては4つ考えられる。

1.alignmentを満たすallocatorを自前で書き、vector<double, aligned_allocator<double> >のようにして使う。一番正統だがallocatorをきちんと書くのは結構大変そう。
2.SSEを使うときだけalignmentを守った別のdouble配列にコピーする。SSEによる高速化が顕著で、配列サイズが小さくないと意味がない。よく考えるととっても意味のない方法に思えてきた。
3.vectorを諦めてaligned配列を手動管理する。現実的。
4.SSEを諦める。ある意味現実的。

ちなみにvectorのメモリの連続性については連続である、ということで決着済みなのでまあ連続であるとしてよいだろう。

ちょっと調べてみたところ、STLPortのallocatorはソースをちょびっといじるとalignmentを設定できるようだ。それから、allocatorを書くのもそれほど大変ではなさそう?真の意味でのallocator(フリーリストの管理やら云々)をするともちろん大変だけど、alignmentを揃えるだけで、後は既存のoperator newなんかを使い回そうと考えれば、インターフェースを定義するだけなので簡単かも知れない。

| | Comments (0) | TrackBack (0)

C++のリファレンス

Microsoftの「Get! Visual Studio 2005」キャンペーンに釣られて入手などしてみた。VS.NET 2005 AcademicはStandard相当であり、ProfessionalのAcademic割引はない見込みである。よってこれがProfessionalを安く入手する唯一の機会となるわけだが、StandardとProfessionalを比べて、うれしい点は64bitコンパイラがついてくることくらいか。まあこの先64bitコンパイラを持っていないのもどうかと思うので、安いしよしとしよう。

ダウンロード時に「CD1」「CD2」というボタンがあって、それをクリックするとダウンロードできるのだが、どうもFirefoxとは相性が悪いらしく、application/octet-streamな謎の412KBのデータが落ちてくる。実はこれがダウンロード用の実行ファイルなので、適当にdisc1.exeなどとリネームして実行するとダウンロードできる。unno氏は何も言っていなかったがOperaだと大丈夫なのかな?

さて、VS.NET 2005であるが、以前から指摘されている通りC++、特にSTL関連のヘルプがめちゃくちゃ使いにくい。何度もリンクを辿らされる上に気づいたら元の場所に戻っていたりして、欲しい情報にはたどり着けないことが多く、ストレスがたまる。そこでC++についてはMSDNのヘルプを諦め、外部のサイトを使うことにしている。

よく使うのはC/C++ Referenceとその翻訳版、あるいはC++ Referenceといったところ。後者はIOstreamのクラス継承図があって大変わかりやすい。

書籍では前にも挙げたC++標準ライブラリチュートリアル&リファレンスがよいと思うのだが、書いたとおり絶版であり入手困難。最近では、C++ライブラリクイックリファレンスあたりはどうなのだろうか?詳しく読んだことはないが、地下で誰か持っていたような。「リファレンス」というからには説明的要素は少ないのだろうか。とすると微妙かも。

ところで最大の問題は最近C++を使う機会が全くないため、C++の細かな作法をすっかり忘れてしまっている点にあるわけだが。例えば、coutで16進表示する方法(printfの%x)とか、std::sortにcomparatorを渡せることだとか。カーネル開発もC++でやりたいもんだねぇ…。

追記。

あれ? そういえば、もう2005年じゃないじゃん。
本当だ。

| | Comments (2) | TrackBack (0)

January 07, 2006

優先順位

コーディングのはまりどころを日記に書くのが流行っているようなので便乗。

慣れない言語では演算子の優先順位に対する誤解や認識不足から謎のコンパイルエラーやバグに悩まされることがある。例えばOCamlでは、「関数適用が何にもまして強い」という性質がC等の経験者には特異に感ぜられ、最初の頃は結構苦労した。

ではCなら大丈夫かというとそんなことはなく、Cでも優先順位で間違いを冒すことは時たまある。最もわからないのがビット演算子の強さだ。ここ数日はまっていたコードは次のようなものだ。(実際には、このコードに問題があるということにすら全く気づかず、あれこれprintkをはさんでvm_flagsの値がおかしいことを突き止めてからようやくこのコードに思い至ったわけだが)

unsigned long flags = vm_flags | (vm_flags & VM_SHARED) ? VM_REMOTE : 0;

意図していたのは、
vm_flags | ((vm_flags & VM_SHARED) ? VM_REMOTE : 0)
という結合。しかし、実際には
(vm_flags | (vm_flags & VM_SHARED)) ? VM_REMOTE : 0
と解釈される、らしい。まるまる2日つぶしてしまった……。

ところで先日、"spinlock recursion"なる恐ろしげなエラーメッセージを見た。やはり何度かは強烈なkernel panicを出さないとカーネルいじってる気がしないよね。

| | Comments (5) | TrackBack (0)

December 25, 2005

古い技術書

ただでさえ忙しい年末に大掃除をすることにしたのは誰だ、と毒づきながらも、毎年なんとなく惰性で部屋の片付けをしてしまうのが年末である。普段全くと言っていいほど片付けのできない人間なので、1年に1回くらいは片付けをしないとさすがにまずい。

片付けといっても、大抵はいらないものを捨てることである。なんとなく捨てるのは惜しい気がして取っておいたものとか、古くなったバージョンのソフトウェアとかを大分処分する。基本的に中古屋やオークションなどで売る気のない製品の箱は捨ててしまって構わないはずなのだが、箱の中にマニュアルやCDが入っていたりすると今度はそれらをどこに保管するのかという問題が生じるのでなかなかややこしい。

毎回片付けをするたびに悩むのが、古くなった技術書、例えばC++の教科書(入門書)の扱いである。中学生もしくは高校生の頃に買ったり、買ってもらったりしたものだ。これらははっきり言ってもはや必要ない。今後手元に置いておいても参照することはないだろう。しかし、それらの本がその言語を学ぶに当たって初めて手にし、繰り返し読んで育った本だったりすると、今の自分を形成する重要な一部品のような気がしてなかなか捨てられないのである。

これが技術書でなく普通の本なら、古本屋や古本市に流して誰かの役に立つ事を祈る、という方法で自分を納得させることもできよう。しかしながらコンピュータ業界は流行廃りが激しいことは古本屋の旦那でも知っているので、コンピュータ関連の本はまず引き取って貰えない。仮に引き取ってもらえたとしても、そのような古い内容の本(例えば、iostream.hと書いてあったり、templateや例外について書いていなかったり…)を世に流すのは今や害悪であると思うので、それもできない。

というわけで、今年も結局読むでもなく処分するでもない本が何冊か生じてしまうのである。物を大切にするのは美徳の1つだとは思うが、大切にしすぎて自分の生活空間を圧迫するのも考え物だな…。

| | Comments (2) | TrackBack (0)

より以前の記事一覧