ボトルネック

最近8coreのワークステーションを使う機会があったのですが、そのCPUのパワーを引き出すことの難しさを身をもって経験しました。大量のデータを処理したかったのですが、HDDがボトルネックになって、全然CPUが活躍させられないのです。

これからの時代、より大量のデータを処理する局面が増えてくると思うのですが、いかにデータをCPUに流してやるかが重要なんですね。SSDとかだともっとましになるだろうし、または分散ファイルシステムにしてMapReduce的なことをするのも向いてるのかなあという印象です。

以前までのやってた研究だと、データはほんの少しでほとんどがいかに計算を速くするかを問題にしていたので、新鮮な経験でした。

Fedora12のevinceで日本語表示

最近UbuntuだけでなくFedoraも使うようになったが、FedoraはUbuntuに比べると日本語対応が弱いようで結構苦労する。標準では日本語のPDFも見られないし、日本語のLaTeXもレポジトリにないし。

今日はFedora 12上のevinceで日本語を表示する方法が判明したのでメモとして書いておく。

1. evinceのインストール: 多分標準で入る
2. popplerのサイトからpoppler-data-x.y.z.tar.gzの最新版をダウンロード
3. poppler-dataを展開
4. Makefileのprefixを/usrに変更

"prefix = /usr/local" => "prefix = /usr"

5.  (rootで) make install
   

これで日本語フォントの埋め込まれたPDFは読めるようになった。ただ埋め込まれていないPDFに対応するにはさらに設定が必要な気がする。手元にそんなPDFファイルがなかったので確認していないけど。

ひさしぶりに

前回の投稿から結構経ってしまいました。この間に就職活動でさんざん苦労したものの、無職確定寸前でなんとか就職が決まって、その後関東に引越したりしました。

すっかりブログのことは忘れていましたが、先日研究室の後輩と飲んだときに、なぜか教えていなかったこのブログのことを知っているという話になって驚きました。そんなこんなで、読者がいるならまたボチボチ再開しようかなあという気がしてきました。

ただ、ネタをどうしようかなあという感じです。

C++によるrubyの拡張

現在研究中のプログラムをライブラリ化して簡単に使えるように ruby の binding がうまくいくかを試してみようと思った。README.EXT.ja や Programming Rubyを参考に簡単なものを作ってみたが予想外に苦労するはめになった。それは、クラスにメソッドを登録するところで、以下のようなコードでもエラーが出るのだ。

VALUE initialize(VALUE self){
return Qnil;
}
...
void Init_something(void){
....
rb_define_method(klass, "initialize", initialize, 0);
....
}

エラーメッセージ

error: invalid conversion from ‘VALUE (*)(VALUE)’ to ‘VALUE (*)(...)’

これは rb_define_method の引数の型が合わないことが原因で、reinterpret_cast を使って対処することにした。この方法が分かるまで本当に面倒だった。

#define RB_FUNC(f) reinterpret_cast<VALUE (*)(...)>(f)

void Init_something(void){
....
rb_define_method(klass, "initialize", RB_FUNC(initialize), 0);
....
}

C++の前方宣言

C++には前方宣言というのがあって、うまく使うとヘッダファイルのインクルード関係を整理できる。なんとなく使っていたが、今日一つはまった点をメモ。

下に例を載せているが、クラス定義の中で前方宣言したクラスの変数を定義する際は、ポインタやテンプレート変数ならばいいけれども、そのまま使うことはできない。vectorのテンプレート変数にする分には問題ない。

ここらへんはごまかして勉強したのでダメですね。

// case1: OK

class A; // 前方宣言

class B{
    A *a;
};

// case2: OK

class A;

class B{
    std::vector<A> a;
};

// case3: OK

class A;

template<class T=A>
class B{
    T a;
};

// case4: NG

class A;

class B{
    A a;
};

FreeBSDでsincos

glibcではsincosを使うことができるが, FreeBSD上ではlibcに入っていないので使うことができない. 以下のようなインクルードファイルを作ってやれば一応使える. 以前どこかのページで見て使っていたのだが, どこのページだったかは失念してしまった.

inline void sincos(double t, double *s, double *c){
        asm("fsincos;" : "=t" (*c), "=u" (*s) : "0" (t) : "st(7)");
        // *s = sin(t); *c = cos(t)
}

FreeBSD上でのCPUの使用率の計測方法

FreeBSDでCPUの使用率をチェックするために, fluxboxのドック用の自作アプリを使っているのだが, 最近 7-stable のソースの更新をしたところ, そのアプリが動かなくなった. 元々, xosview のソースを流用していて, それでは kvm を使って使用率を取得していたが, どうも仕様が変更になったらしい. 試しに, xosview を入れてみるとやはり動かなかった.

そこで, powerd.c のソースを参考にして, sysctl を使ってCPUの使用率を取るように変更した. 簡単に解説すると, まず, 前処理として, Management Information Base (MIB) を取得しておき, 使用率を取る際はその MIB を使って sysctl(3) を使う. プログラムの一部だけだが, 以下のようになった.

#include <sys/resource.h>
#include <sys/types.h>
#include <sys/sysctl.h>

static int cp_time_mib[2];

/* 前処理. 1回だけ行う. */
void preprocess(void){
    int len = 2;
    if (sysctlnametomib("kern.cp_time", cp_time_mib, &len))
    {
        perror("lookup kern.cp_time");
        exit(1);
    }
}

/* CPUの使用率を百分率で返す */
double cpu_getusage(void) 
{
    long cpu, nice, system, idle, used, total;
    long cpu_time[CPUSTATES];
    size_t cpu_time_len;

    cpu_time_len = sizeof(cpu_time);
    if (sysctl(cp_time_mib, 2, cpu_time, &cpu_time_len, NULL, 0))
    {
        perror("sysctl error");
        exit(1);
    }

    cpu = cpu_time[CP_USER];
    nice = cpu_time[CP_NICE];
    system = cpu_time[CP_SYS];
    idle = cpu_time[CP_IDLE];

    used = cpu + nice + system;
    total = used + idle;
    return 100.0 * used / (double) total;
}

tabular の列間の調節

今 LaTeX で論文を書いていて, ある表の横幅が長くなりすぎて困っていた. その表は列間の空白が比較的多くて, ここをうまく縮めればいいのになあと思ったので, 対処法を調べてみた.

tabular の代わりに tabular* を使って,

\begin{tabular*}{??pt}{@{\extracolsep{\fill}}c|rr}
...
\end{tabular*}

のようにしてやればよいことが分かった. \fill のところは好きなサイズを入れることも可能. 特に列間を縮めたければ, -5pt とか入れるとかなり縮まる.

参考:
http://www.comb.kokushikan.ac.jp/inlab/LaTeX/node26.html
http://www.tex.ac.uk/cgi-bin/texfaq2html?label=fixwidtab
http://www-h.eng.cam.ac.uk/help/tpl/textprocessing/teTeX/latex/latex2e-html/ltx-68.html

xvidcap のコンパイル

ここ最近 FreeBSD 7-stable で sysutils/xvidcap をコンパイルしようとすると, 最後のリンクで失敗する状況が続いていた. 特にすぐ xvidcap を使うことはなかったので, そのうち直るだろうと放っておいたが, portupgrade -a するたびにエラーが報告されるのがだんだん気になってきたので, ちょっと調べてみた.

libtheora と libx264 がリンクするファイルのリストに載っていなかったのが原因だと分かった. ports/sysutils/xvidcap/work/xvidcap-1.1.4p1/src/Makefile の PACKAGE_LIBS の部分を赤字のように変更すると無事コンパイルできるようになった.

PACKAGE_LIBS = -pthread -L/usr/local/lib -lglade-2.0 -lgtk-x11-2.0 -lxml2 -lgdk-x11-2.0 -latk-1.0 -lgdk_pixbuf-2.0 -lpangocairo-1.0 -lXext -lXrender -lXinerama -lXi -lXrandr -lXcursor -lXcomposite -lXdamage -lcairo -lpangoft2-1.0 -lpango-1.0 -lm -lfreetype -lz -lfontconfig -lX11 -lXfixes -lgobject-2.0 -lgmodule-2.0 -lgthread-2.0 -lglib-2.0 -liconv -ltheora -lx264

マウスの真ん中のボタンとFirefox

Firefox でマウスの真ん中のボタンをリンクの上で押すと, そのリンクを新しいタブにロードしてくれて便利に使っている. しかし, ボタンを押したときにリンクからはずれていると, そのときにコピーしていた文字列を URL にしてアクセスして少し困っていた. ただ, どうしたらその機能を停止できるかは分からなかったので, 今まで我慢して使っていた.

そして, 今日なんとなく about:config を何となく見ていたら, その解消法が分かった.

middlemouse.contentLoadURL

を false にすればいいようだ. これでますます快適になる.

そろそろ Firefox 3 も試したいなあ.

vector にはまる

STL の vector を使っていて, vector の要素へのポインタを使っていた所, そのポインタの指す先が勝手に破壊される自体に遭遇して悩んだ. 結果的には vector に push_back した際に vector が自動的に resize して, ポインタの指す先が解放されていたのが原因だと判明. とりあえずは, vector::reserve で自動的な resize を抑制することで解決した. 根本的な問題の解決のためにデザインを考え直さなければ. vector のもっとも便利な自動 resize でつまづくことになるとは...

zsh と FDclone

zsh を使うようになってから, なぜか FDclone が使えなくなった. "malloc(): Cannot allocate memory" というメッセージが出て FDclone が死んでしまったのだ. その原因を調べてみたところ, zshrc に HISTFILE と HISTSIZE というのを書いていて, ここで zsh の履歴の設定をしているのだが, この環境変数が FDclone も使っていることが原因だったと分かった.

zsh のために "export HISTSIZE = 100000" と設定していたが, これを FDclone も読み込み, しかも, FDclone 内部では HISTSIZE を short型で取っていたため, 100000 があふれて -31072 になってしまっていた. そのせいで, malloc(-31072) というのを実行して死んだのだ.

解決法としては, FD_HISTFILE と FD_HISTSIZE という環境変数を設定してやればOK.

valarrayのconstructorとresize

valarrayの各要素に同じ値を入れる方法として constructor を使う方法と resize を使う方法があるが, そのインターフェースの違いに戸惑ったのでメモ.

• valarray(const T& v, size_t num)
  
• valarray.resize(size_t num, const T v = T())
  

このように, 引数の順番が逆になっているのに気づいていなかった. T と size_t が異なればコンパイル時にエラーが出るが, そうでない場合はそのままバグになるので気をつけないと.

例:

01: #include<valarray>
02: #include<iostream>
03:
04: using namespace std;
05:
06: int main(void){
07:     valarray<char> v('a', 5);
08:     for(int i = 0; i < v.size(); ++i) cout << v[i]; cout << endl;
09:
10:     v.resize(5,'b');
11:     for(int i = 0; i < v.size(); ++i) cout << v[i]; cout << endl;
12:
13:     return 0;
14: }

C++のテンプレートに悩む

C++のテンプレートにはまった. 下のようにテンプレートの片方のパラメータの特殊化しようとしたが, コンパイルが通らない... C++難しいなあ.


(a.cpp)

01: #include <iostream>
02:
03: using namespace std;
04:
05: template<typename T, int N>
06: struct A{
07:     int val() const;
08: };
09:
10: template<>
11: template<typename T>
12: int A<T,1>::val() const{
13:     return 1;
14: }
15:
16: int main(void){
17:     A<int,1> a;
18:     cout << a.val() << endl;
19:     return 0;
20: }

環境: gcc version 4.2.1 20070719 [FreeBSD]

a.cpp:12: error: invalid use of incomplete type 'struct A'
a.cpp:6: error: declaration of 'struct A'
*** Error code 1

Windows XP SP3

Windows XP SP3 を入れようとしたが, インストールの途中でブルースクリーンが出て失敗. うーん, どうしたものか. 情報を集めないと.

追記(5/11):
PCは ThinkPad X40 なのだが, SP3 を入れる前にソフトウェア導入支援を起動してみたら, Windows のパッチが「重要」として挙がっていたので, それをまず入れてみた. すると SP3 が無事にインストールできた. 普通のWindowsのパッチは「KB???」の形式の名前がついているが, 今回のパッチはThinkPad専用とのことで「Q???」の形式の名前だった. これが効いたのだろうか?

Left-Leaning Red-Black Tree part2

前回の Left-Leaning Red-Black (LLRB) Tree の Haskell のコードがきちんと動くことを大体確認した. HaskellのData.Setと比べた特徴は以下の通り.

• insert と member は LLRB の方が早い.
  
• delete は Data.Set の方が早い.
  

今後の課題としては, Data.Set にある集合演算を LLRB で実装するのも面白いかも.

LLRB の delete を Data.Set よりも早くしようと試行錯誤したがうまくいかなかった. Haskell のチューニングの難しさを実感した. なかなか直感通りにいかなくて大変だ.

Left-Leaning Red-Black Tree

Left-Leaning Red-Black Tree [PDF] というのを見つけて, 実装が簡単だと書いてあったので, 最近練習中のHaskellで書いてみた. PDF に所々ミスがあるし, Haskell に慣れてないのもあって, あんまり簡単ではなかった. まだきちんと検証もしていないがさらしてみる. とりあえず, delete が member でない要素を与えられたときにエラーを返すのは仕様. deleteはPDFに載っているのとは少し変える必要があった上に, 書き直しにかなり悩んだので間違っているかも.

module Main where

data Color = Red | Black deriving (Show, Eq)
data LLRB a = Null | Branch !Color !(LLRB a) a !(LLRB a) deriving (Show)

member :: Ord a => a -> LLRB a -> Bool
member _ Null = False
member x (Branch c l y r) =
    case compare x y of
 LT -> member x l
 GT -> member x r
 EQ -> True

null :: LLRB a -> Bool
null Null = True
null _   = False

empty :: LLRB a
empty = Null

singleton :: a -> LLRB a
singleton x = Branch Red Null x Null

insert :: Ord a => a -> LLRB a -> LLRB a
insert x root = make_black $ insert' x root

insert' :: Ord a => a -> LLRB a -> LLRB a
insert' x Null = singleton x
insert' x h@(Branch _ (Branch Red _ _ _) _ (Branch Red _ _ _)) = insert' x $ colorFlip h
insert' x h@(Branch c l y r) =
    f2 $ f1 $ case compare x y of
 LT -> Branch c (insert' x l) y r
 GT -> Branch c l y (insert' x r)
 EQ -> h
    where 
    f1 t@(Branch _ _ _ (Branch Red _ _ _)) = rotateL t
    f1 t = t
    f2 t@(Branch _ (Branch Red (Branch Red _ _ _) _ _) _ _) = rotateR t
    f2 t = t

findMin :: LLRB a -> a
findMin (Branch _ Null x r) = x
findMin (Branch _ l x r) = findMin l
findMin Null = error "LLRB.findMin: empty tree has no minimal element"

findMax :: LLRB a -> a
findMax (Branch _ l x Null) = x
findMax (Branch _ l x r) = findMax r
findMax Null = error "LLRB.findMax: empty tree has no minimal element"

deleteMax :: LLRB a -> LLRB a
deleteMax root = make_black $ deleteMax' root where

deleteMax' :: LLRB a -> LLRB a
deleteMax' h = let t' = apply_rotR h in
    if isRightNull t' then Null else (fixUp . f . apply_mRR) t' where
    f (Branch c l x r) = Branch c l x (deleteMax' r)

deleteMin :: LLRB a -> LLRB a
deleteMin root = make_black $ deleteMin' root where

deleteMin' :: LLRB a -> LLRB a
deleteMin' (Branch _ Null _ _) = Null
deleteMin' h = (fixUp . f . apply_mRL) h
    where
    f (Branch c l x r) = Branch c (deleteMin' l) x r

delete :: Ord a => a -> LLRB a -> LLRB a
delete x root = make_black $ delete' x root

data NodeCond = NLeft | NRight | NBottom

delete' :: Ord a => a -> LLRB a -> LLRB a
delete' _ Null = error "LLRB.delete: element is not the member"
delete' x h@(Branch c l y r) =
    fixUp $ case compare x y of
 LT -> (f . apply_mRL) h
     where
     f (Branch c l y r) = Branch c (delete' x l) y r
 GT -> (f . apply_mRR . apply_rotR) h
     where
     f (Branch c l y r) = Branch c l y (delete' x r)
 EQ -> case nodecond h of
     NBottom -> Null
     NLeft -> let z = apply_mRL h in
  if eq x z then delleft z else delete' x z
     NRight -> let z = (apply_mRR . apply_rotR) h in
  if eq x z then delright z else delete' x z
     where
     eq a (Branch _ _ b _) = a == b
     nodecond (Branch _ Null _ Null) = NBottom
     nodecond (Branch _ (Branch _ _ _ _) _ _) = NLeft
     nodecond (Branch _ _ _ (Branch _ _ _ _)) = NRight
     delleft  (Branch c' l' x' r') = Branch c' (deleteMax' l') (findMax l') r'
     delright (Branch c' l' x' r') = Branch c' l' (findMin r') (deleteMin' r')

--
-- Helper
--
apply_mRL t@(Branch _ (Branch Red _ _ _) _ _) = t
apply_mRL t@(Branch _ (Branch _ (Branch Red _ _ _) _ _) _ _) = t
apply_mRL t = moveRedLeft t

apply_mRR t@(Branch _ _ _ (Branch Red _ _ _)) = t
apply_mRR t@(Branch _ _ _ (Branch _ (Branch Red _ _ _) _ _)) = t
apply_mRR t = moveRedRight t

apply_rotR t@(Branch _ (Branch Red _ _ _) _ _) = rotateR t
apply_rotR t = t

isRightNull t@(Branch _ _ _ Null) = True
isRightNull t = False

make_black :: LLRB a -> LLRB a
make_black (Branch _ l x r) = Branch Black l x r
make_black Null = Null

fixUp :: LLRB a -> LLRB a
fixUp = f3 . f2 . f1 where
    f1 t@(Branch _ _ _ (Branch Red _ _ _)) = rotateL t
    f1 t = t
    f2 t@(Branch _ (Branch Red (Branch Red _ _ _) _ _) _ _) = rotateR t
    f2 t = t
    f3 t@(Branch _ (Branch Red _ _ _) _ (Branch Red _ _ _)) = colorFlip t
    f3 t = t

moveRedRight :: LLRB a -> LLRB a
moveRedRight h = f $ colorFlip h where
    f t@(Branch _ (Branch _ (Branch Red _ _ _) _ _) _ _) = colorFlip $ rotateR t
    f t = t

moveRedLeft :: LLRB a -> LLRB a
moveRedLeft h = f $ colorFlip h where
    f (Branch c l x r@(Branch _ (Branch Red _ _ _) _ _)) = colorFlip $ rotateL $ Branch c l x (rotateR r)
    f t = t

colorFlip :: LLRB a -> LLRB a
colorFlip (Branch c (Branch c1 l1 x1 r1) x (Branch c2 l2 x2 r2)) =
    Branch (fl c) (Branch (fl c1) l1 x1 r1) x (Branch (fl c2) l2 x2 r2)
    where
    fl Red = Black
    fl Black = Red
colorFlip _ = error "LLRB.colorFlip: tree must have 3 nodes at least"

rotateL :: LLRB a -> LLRB a
rotateL (Branch c l x (Branch c' l' x' r')) =
    Branch c (Branch Red l x l') x' r'
rotateL _ = error "LLRB.rotateL: tree must have 2 nodes at least"

rotateR :: LLRB a -> LLRB a
rotateR (Branch c (Branch c' l' x' r') x r) =
    Branch c l' x' (Branch Red r' x r)
rotateR _ = error "LLRB.rotateR: tree must have 2 nodes at least"

     
-- 
-- test 
--

tree :: Int -> LLRB Int
tree 0 = empty
tree (n+1) = insert (n+1) (tree n)

main :: IO ()
main = do
    print $ member 1 $ (iterate deleteMax (tree 100000)) !! 100000

Firefoxの反応が遅い

最近, 研究室用のマシンの FreeBSD 7-stable 上の linux-firefox の反応が遅くなった. Ctrl-T で新しいタブを作成しようとしても, キーを押してからタブができるまでに数秒のタイムラグが発生するのだ. ちょっとしたら, どこかで修正されるかなと思って我慢していたけど, 改善されないので, 諦めて 6-stable に戻った. 6-stable 上ならキビキビ動く. ちなみに, 後輩の Debian 上の Firefox でも同様の現象が起きていた. Linux用の Firefox 特有の問題なのだろうか.

あと, 後輩にC言語のコールグラフを生成する方法を聞かれたので, 調べてみたら gprof2dot というのを見つけた. なかなか便利そうだ.

Graphvizのフォント

プログラムのプロファイリングに最近 Google CPU Profilerを使うようになった. 特にコンパイルしなおさなくても, LD_PRELOAD で libprofiler.so を渡すだけでなので楽だ.

また, pprof --pdf とかで出力されるコールグラフも見やすくていい. ただ,

Error: Could not find/open font

というのが無数に出力されるのが気になったので調べてみた. pprof の問題ではなく, 内部で使っている Graphviz の問題のようだ. "times.ttf" というファイルを /usr/local/lib/X11/fonts/ で探すのだが, それが見つからないために出力されていた.

# cd /usr/local/X11/fonts/
# ln -fs TTF/luxisr.ttf times.ttf

とかで適当にリンクを張ってごまかしたら, エラーメッセージが消えた.

VPython を FreeBSD にインストール

研究でデータの可視化に利用している VPython を FreeBSD にインストールしなおしたのでメモ. ports/graphics/py-visual はバージョンが古いので, 自分で visual-4.beta26.tar.bz2 を入れた.

1. VPython が依存するパッケージのインストール
   

   # portinstall -RP boost-python py25-numpy libglademm24 gtkglextmm

   
   
2. ソースの修正
   src/python/cvisualmodule.cpp, src/python/vector_array.cpp の一行目に

   #include <iostream>

   を追加する
   
3. configure & make