program
Up one levelEnjoy source code reading
Namazuをインストールしてから単なる全文検索エンジンであることに気づき、gonzuiをインストールして使いはじめようと思ったらNotImplementedErrorと怒られ、流行に弱い僕があえてetagsのような古いツールを使うわけもなく、結局GNUに帰してgtagsでソースコードを読むことになりました。
インストール
Gentooのパッケージ管理は結構ちゃんとしてるからうれしい。
emerge global
設定
できるだけかぶらないようなキーバインディングを考えて以下のように設定。
;; gtags mode (autoload 'gtags-mode "gtags" "" t) (setq gtags-mode-hook '(lambda () (local-set-key "\C-xtt" 'gtags-find-tag) (lobal-set-key "\C-xtr" 'gtags-find-rtag) (local-set-key "\C-xts" 'gtags-find-symbol) (local-set-key "\C-xtg" 'gtags-pop-stack) ))
使う
まずはG*ファイルを生成しなければなりません。
% cd ~/src/gcc-4.1.1/gcc % gtags -v % #長い
emacsを開いてcdでG*があるディレクトリへ飛んでからM-x gtags-mode。たとえばここでC-x t t mainと打つとmainのある場所が新しいバッファに出力されます。
近いうちに本格的にソースを読んでいきます。
- The URL to Trackback this entry is:
- http://dev.ariel-networks.com/Members/matsuyama/enjoy-source-code-reading/tbping
C++パーサーライブラリ、yapc++
旧名ParseaseであるYapc++ version 0.0.1aをリリースしました。i18nの対応もYapc++の機能に含めてしまおうという話でここ数日開発していたのですが、パフォーマンスを落とすかシンプルさを落とすかあるいは両方落とすかの実装しか浮かばなかったので、結局のところi18n対応はYapc++範疇外ということで今回リリースにいたりました。もちろん拡張セットとしてのi18n対応は考慮されていますし、今後のバージョンアップは主にそれの対応だと思われます。ここに書くべき記事は本家のほうへ書くことにしましたので、ここでは変わってその実装に関しての考えかたやテクを書いていきたいと思います。
- The URL to Trackback this entry is:
- http://dev.ariel-networks.com/Members/matsuyama/c-30fc30b530fc30e930a430e930ea3001yapc/tbping
globalを実際につかってみた
バグ取りも噛ねて製品のソースコードの構造を理解せよとの命令が出たので、最近覚えたglobalを早速使ってみました。まずはG*ファイルを生成させるために、ソースコードディレクトリのルートで
% gtags -v
としてG*ファイルを生成させます。それで、例えばHogeクラスが定義されてるファイルってどこだろう、ということになれば
% global Hoge path/to/Hoge
で一発で出ますし、それの中身を確認したいということになれば、Emacsからglobalを使うか、以下のようにコマンドします。
% global -x Hoge | less -T-
tでnext tag、Tでprevious tagです。:nと:pで操作するのではないので勘違いしないようにしてください。ただ、この方法だと定義周辺のコンテキストを確認できないようです。対策としては以下のようにファイル全体をlessする方法があります。
% global Hoge | xargs less
伝家の宝刀、xargsです。これはstdinを適当にsplitしてcommandに引き渡します。これによって、lessで:nで次のファイルにいったり:pで前のファイルにいったりすることができるようになるのです。ただこの方法では該当行まで飛んでくれないので、かなり不便です。代替策として以下のように根性をだしてlessする方法があります。
% global -x Hoge | awk '{ print "+"$2"G", $3 }' | xargs -n 2 less
qで次のファイル、C-cで終わりです。前のファイルには戻れませんが、そこそこ代替にはなっています。そうとう無茶していますが(笑
そもそもこの辺の処理はglobalが吸収すべきではないでしょうか。古き良きツールのgrepには-Cというマッチした行の周辺コンテキストを表示するコマンドがありますが、このような機能をglobalにもつけてほしいと思ってしまうのです。lessに丸投げにするにしても、lessのtags対応がいまいちなのでなんとも言えませんし。これはどうも自分で改造patch作ってmailinglistにpostしろという方向にベクトルが向いている雰囲気です。時間があるときになんとかしたいと思います。
- The URL to Trackback this entry is:
- http://dev.ariel-networks.com/Members/matsuyama/coreblogentry.2006-07-20.8963268751/tbping
Linux的SWTプログラミング
gentoo portageのSWTはx86_64で問題がある(org.eclipse.swt.gtk.OS.memmoveがないとおこられる)ようなので http://www.eclipse.org/downloads/ -> Other downloads -> SWT Binary and Source -> Linux (x86_64/GTK-2)をダウンロードして以下のようにインストール。
% su % unzip swt-3.2-gtk-linux-x86_64.zip -d /usr/local/
compile and run a test program.
Test.java:
import org.eclipse.swt.widgets.*; public class Test { public static void main(String[] args) { Display display = new Display(); Shell shell = new Shell(display); shell.setText("Test Shell"); shell.setSize(200, 200); shell.open(); while (!shell.isDisposed()) { if (!display.readAndDispatch()) display.sleep(); } display.dispose(); } }
% export CLASSPATH=$CLASSPATH:/usr/local/swt-M20060629-1905-gtk-linux-x86_64/swt.jar % export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/swt-M20060629-1905-gtk-linux-x86_64/ % javac Test.java % java Test
You may also be happy to read following useful documents (notably org.eclipse.swt.widgets in official).
- http://help.eclipse.org/help31/nftopic/org.eclipse.platform.doc.isv/reference/api/overview-summary.html
- http://amateras.sourceforge.jp/cgi-bin/fswiki/wiki.cgi/swt?page=FrontPage
Nihongo unatenakunatta. Koredakara GUI application ha iya nanda.
- The URL to Trackback this entry is:
- http://dev.ariel-networks.com/Members/matsuyama/linux7684swt30ed30e930df30f3/tbping
pimplイディオムを語る
foo.h:
class foo { ... };
bar.h:
class bar { ... };
があるとして
hoge.h:
#include "foo.h" #include "bar.h" class hoge { private: foo f; bar b; public: hoge(); foo& get_foo(); bar& get_bar(); };
hoge.cpp:
#include "hoge.h" hoge::hoge() {} foo& hoge::get_foo() { return f; } bar& hoge::get_bar() { return b; }
と書くより
hoge.h:
#include <memory> class foo; class bar; class hoge { private: struct impl; std::auto_ptr<impl> pimpl_; public: foo& get_foo(); bar& get_bar(); };
hoge.cpp:
#include "foo.h" #include "bar.h" #include "hoge.h" struct hoge::impl { foo f; bar b; }; hoge::hoge() : pimpl_(new impl) {} foo& hoge::get_foo() { return pimpl_->f; } bar& hoge::get_bar() { return pimpl_->b; }
と書くほうがすばらしいよという話。前者の場合はhoge.hをincludeした時点でfoo.hとbar.hまでincludeされてしまって、おまけにfoo.hやbar.hに変更が加えられてしまった場合にhoge.hはもちろんのことそれをincludeしているヘッダファイルまで変更が波及してしまうことになり、結果としてコンパイルが遅くなる。一方後者の場合はhoge.hの他への依存性はほぼゼロである。前方宣言を使うのは当然のことであるが、ここではそれ以上にpimplイディオムが大活躍している。つまりimplのポインタにfooやbarを格納してしまうことにより、それらのサイズや定義を知る必要がないのだ。ゆえにいくらhoge.hをincludeしているヘッダファイルがあろうともfoo.hやbar.hの変更はそれらに波及しえない。これによって変更に対する耐性が保証され、結果としてコンパイルが速くなる。
しかしpimplイディオムのメリットはそれだけではない。いやpimplの本質上、メリットがコンパイルの高速化だけでとどまること自体がそもそもおかしい。挙げだすと切りがないのだが(要するにstackにおくこととheapにおくこととの差によるメリット)、個人的に非常に興味深いのは例外安全に対する驚くべき能力である。たとえばfoo.hが以下のようなアホなコードだったとしよう。
foo.h:
class foo { public: ... foo& operator =(const foo& rhs) { throw not_implemented_error(); // how stupid I am! } ... };
このアホクラスを使ってテストコードを書く。
hoge a; hoge b; a = b;
このコードをpimplイディオムでないバージョンのhogeでコンパイルすると a = b の部分で例外が発生する。依存したクラスのおかげで自分のクラスまで非例外安全になるなんてなんてすばらしいのでしょう。しかしpimplイディオムの黒魔術にかかればそんな問題も一発。hoge.hとhoge.cppを以下のように改造する。
hoge.h:
#include <memory> class foo; class bar; class hoge { private: struct impl; std::auto_ptr<impl> pimpl_; public: foo& get_foo(); bar& get_bar(); hoge& operator =(const hoge& rhs); // never throw };
hoge.cpp:
#include "foo.h" #include "bar.h" #include "hoge.h" struct hoge::impl { foo f; bar b; }; hoge::hoge() : pimpl_(new impl) {} foo& hoge::get_foo() { return pimpl_->f; } bar& hoge::get_bar() { return pimpl_->b; } hoge& hoge::operator =(const hoge& rhs) { if (this != &rhs) { pimpl_ = rhs.pimpl_; } return *this; }
これで何回 hoge::operator = しようが決して例外が発生することはない。すばらしすぎる。
その他にも new impl_ するタイミングを調整できたり、 struct impl と本来のクラスに実装をわけて構成をわかりやすくしたり、(時と場合によるが)本体のコピーやswapが断然速いなど、pimplにはたくさんのすばらしいメリットがある。ただもちろんそんなにおいしいことばかりでもなく、heapを使う分のパフォーマンス低下は当然考えられる問題だ。しかしメリットとデメリットを計算したとき、最終的にはやはり符号は+になることだろう。
- The URL to Trackback this entry is:
- http://dev.ariel-networks.com/Members/matsuyama/pimpl30a430a330aa30e030928a9e308b/tbping
Google Code Jam 2006 Qualification Setを勝手に解く
練習がてら解いてみる。かなり適当。
Qualification Set 1
1-250pt問題
Nコンタクトをうまくグループ分けしてコンタクトを見つけるまでにかかる時間を最小にしろという問題。nグループに分けた場合、まずグループを捜すのにn秒、そしてそのグループから実際のコンタクトを見つけるのにN/n秒かかる。例えば5コンタクトを2グループに分ける場合、2+ceil(N/2) == 5秒かかる。
groups.py:
from math import ceil class IMGroups: def optimalTime(self, N): res = 1000000 for i in range(1, N): tmp = int(i + ceil(float(N) / i)) if tmp < res: res = tmp return res
1-750pt問題
N queensの変形。正方のチェスボードが与えらえれk個のビショップを置くパターンの数を計算して下4桁の数をかえせという問題。なおいくつかのセルは破壊されていてそこにビショップを置くことができないという制限がついている。僕が自分で解いた方法は総当たりによる方法で、わかりやすく直接的ではあるけど実行時間がかなりぎりぎりなので他の方法を紹介。簡単に説明するとビショップを置くパターンと置かないパターンでなめるようにdiagをスキャンしていくようになっている(たぶん)。memset(memo, -1, sizeof(memo))はなるほどと思った。
bishops.cpp:
#include <iostream> #include <vector> #include <string> #define MOD 10000 using namespace std; int n; int memo[18][1 << 15]; vector<string> b; int go(int k, int d1, int mask) { int& res = memo[d1][mask]; if (res != -1) return res; if (k == 0) return res = 1; if (d1 >= 2 * n - 1) return res = 0; res = go(k, d1 + 1, mask) % MOD; for (int i = 0; i < n; i++) { int j = d1 - i; int d2 = n - 1 + i - j; if (i < 0 || i >= n || j < 0 || j >= n) continue; if (!(mask & (1 << d2)) && b[i][j] == '.') { res += go(k - 1, d1 + 1, mask ^ (1 << d2)); res %= MOD; } } return res; } class Bishops { public: int count(int k, vector<string> board) { n = (int)board.size(); b = board; if (k > 2 * n - 1) return 0; memset(memo, -1, sizeof(memo)); return go(k, 0, 0); } }; #if 0 int main() { vector<string> board; board.push_back("........"); board.push_back("......#."); board.push_back("........"); board.push_back(".#......"); board.push_back("........"); board.push_back(".....#.."); board.push_back("........"); board.push_back("...#...."); Bishops bishops; cout << bishops.count(7, board) << endl; return 0; } #endif
Qualification Set 2
2-250pt問題
シャッフルする種をあたえられ、それを使って1, 2, 3, ..., nなデッキをn回シャッフルしろという問題。
shuffler.py:
class DeckShuffler: def getDeck(self, n, shuffled): res = range(1, len(shuffled) + 1) while n > 0: tmp = res[:] for i, x in enumerate(shuffled): tmp[i] = res[x - 1] res = tmp n -= 1 return res
2-750pt問題
Qualification Set 1の750pt問題と同じ。
Qualification Set 3
3-250pt問題
レフリーの全行動が[YR] MINUTES NAMEという形式であたえられるので、それの間違いを見付けて最も最初に間違った時間をかえせという問題。たとえば二回目のイエローカードなのに同時間にレッドカードがでてないなど。完璧なコードを書くのが結構むずかしい。と、思ってたら以下のようにすれば簡単にかつ完璧にできることが発覚。さすがですk.inabaさん、あとからレッドカードを検索する発想はなかったわ。なんていうかイエローカードのチェックのifの次にelifとして書きたい衝動にかられる。そっちのほうが美しいみたいな。でも実際そうすると逆に問題が難しくなる。いやはやアルゴリズムは奥が深い。
3-750pt問題
Permanentとかいうやつを計算しろという問題。The parmanent of nxn matrix A is equal to the sum of A[1][p[1]] * A[2][p[2]] * ... A[n][p[n]] over all permutations p of set {1, 2, ..., n}. ということらしい。前から思っていたんだけど、set {1, 2, ..., n}のall permutationsってなにかとても簡単な方法で生成できないのかな。結構用途多いわりにいざ作るとなると再帰やらスタックやらで生成しないといけなくて面倒くさい。で、問題は解けたんだけど遅すぎてtestとおらない。c++で書きなおす気もおこらず、上と同じようにk.inabaさんのコードを掲載。僕のpythonのプログラムにmemoizationつければk.inabaさんのと同じになるけど、面倒なのでいいや。
Qualification Set 4
4-250pt問題
(n,m)のボードから最大の正方(含有可能な正方をはぶくという意味)を抽出してその数をかえせという問題。たとえば
AAB AAB BBB
は2x2のAの正方が1個、1x1のBの正方が5個で計6。Constraintsがゆるいのでごりごり処理しても余裕。まあ工夫するとしたらcoloringして四隅のcolorをチェックすることにより含有をチェックするようにするとか。追記、rは最大にしちゃだめだ。修正面倒なのでこのまま。
square.py:
class SquareCounting: def howMany(self, grid): w = len(grid[0]) h = len(grid) sq = {} res = 0 def row(c, l, t, r): while l < r: if grid[t][l] != c: return False l += 1 return True def include(c, l, t, r, b): for s in sq.get(c, []): if s[0] <= l and s[1] <= t and s[2] >= r and s[3] >= b: return True return False for l in range(w): for t in range(h): c = grid[t][l] r = l + 1 while r < w and grid[t][r] == c: r += 1 b = t + 1 while b < h and row(c, l, b, r): b += 1 r = l + min(r - l, b - t) b = t + min(b - t, r - l) if not include(c, l, t, r, b): sq.setdefault(c, []).append([l, t, r, b]) res += 1 return res
4-750pt問題
Qualification Set 3の750pt問題と同じ。
Qualification Set 5
5-250pt問題
y < x < zのf(x)がy, zのfに関してconvexになっている場合その総数をかえせという問題。convexというのはy, zの直線((y, f(y)), (z, f(z))より点(x, f(x))が上にある場合をいうらしい。y, zはつまりx - 1, x + 1ということだと決めつけて?になっていたことは秘密。上にあるかはy, zの傾きa1とx, yの傾きa2の比較でチェックできる。これもかなりごりごりと処理。floatいるかは不明。
convex.py:
class ConvexityIssues: def howMany(self, values): res = 0 n = len(values) for i in range(n - 2): for j in range(i + 2, n): a1 = float(values[j] - values[i]) / (j - i) for k in range(i + 1, j): a2 = float(values[k] - values[i]) / (k - i) if a1 < a2: res += 1 return res
5-750pt問題
Qualification Set 3の750pt問題と同じ。
Bishopsの問題が一番むずかしかった。でも一番収穫があったのもBishops。特にgo(k, ...)とgo(k - 1, ...)の使いわけによって配置パターンをすべて表現してしまうのには感心した。来年もがんばろう。
P.S. reStructured Textは使いにくくてしょうがない。
- The URL to Trackback this entry is:
- http://dev.ariel-networks.com/Members/matsuyama/google-code-jam-2006-qualification-set309252dd624b306b89e3304f/tbping
グローバル変数は遅い?
ふとしたことから以下のような不思議な現象を発見してしまいました。
test.cpp:
#define N (64*500) class wrap { int data[N]; public: wrap() { int i; for (i = N - 1; i >= 0; i--) data[N - i + 1] = i; } void doit() { int i, j, tmp; for (i = 0; i < N - 1; i++) { for (j = i + 1; j < N; j++) { if (data[i] > data[j]) { tmp = data[i]; data[i] = data[j]; data[j] = tmp; } } } } }; int main() { wrap a; a.doit(); }
test.c:
#define N (64*500) int data[N]; void init() { int i; for (i = N - 1; i >= 0; i--) data[N - i + 1] = i; } void doit() { int i, j, tmp; for (i = 0; i < N - 1; i++) { for (j = i + 1; j < N; j++) { if (data[i] > data[j]) { tmp = data[i]; data[i] = data[j]; data[j] = tmp; } } } } int main() { init(); doit(); }
% g++ test.cpp -o test.cpp.out % time ./test.cpp.out ./test.cpp.out 5.01s user 0.00s system 94% cpu 5.311 total % gcc test.c -o test.c.out % time ./test.c.out ./test.c.out 3.84s user 0.00s system 95% cpu 4.048 total
classのオーバーヘッドがあるんでこれは当然なんですが、
% g++ -O3 test.cpp -o test.cpp.out % time ./test.cpp.out ./test.cpp.out 1.14s user 0.00s system 92% cpu 1.233 total % gcc -O3 test.c -o test.c.out % time ./test.c.out ./test.c.out 1.32s user 0.00s system 93% cpu 1.412 total
奇妙ですね。
% g++ -O3 -c test.cpp -o test.cpp.o % objdump -t test.cpp.o SYMBOL TABLE: 00000000 l df *ABS* 00000000 test.cpp 00000000 l d .text 00000000 .text 00000000 l d .data 00000000 .data 00000000 l d .bss 00000000 .bss 00000000 l d .note.GNU-stack 00000000 .note.GNU-stack 00000000 l d .comment 00000000 .comment 00000000 g F .text 00000067 main % gcc -O3 -c test.c -o test.c.o % objdump -t test.c.o 00000000 l df *ABS* 00000000 test.c 00000000 l d .text 00000000 .text 00000000 l d .data 00000000 .data 00000000 l d .bss 00000000 .bss 00000000 l d .note.GNU-stack 00000000 .note.GNU-stack 00000000 l d .comment 00000000 .comment 00000000 g F .text 00000020 init 0001f400 O *COM* 00000020 data 00000020 g F .text 0000004e doit 00000070 g F .text 0000006e main
initとdoitがinlineになってないじゃん。それぞれ一回しか呼ばれていないので全然関係ないのですが、一応inline化しましょう。gccマニュアルによるとスタンドアロンなオブジェクトのインライン展開にはstatic inlineを使わないとだめだよとのことなので以下のように修正します。
test.c:
#define N (64*500) int data[N]; static inline void init() { int i; for (i = N - 1; i >= 0; i--) data[N - i + 1] = i; } static inline void doit() { int i, j, tmp; for (i = 0; i < N - 1; i++) { for (j = i + 1; j < N; j++) { if (data[i] > data[j]) { tmp = data[i]; data[i] = data[j]; data[j] = tmp; } } } } int main() { init(); doit(); }
% gcc -O3 -c test.c -o test.c.o % objdump -t test.c.o SYMBOL TABLE: 00000000 l df *ABS* 00000000 test.c 00000000 l d .text 00000000 .text 00000000 l d .data 00000000 .data 00000000 l d .bss 00000000 .bss 00000000 l d .note.GNU-stack 00000000 .note.GNU-stack 00000000 l d .comment 00000000 .comment 00000000 g F .text 0000006e main 0001f400 O *COM* 00000020 data
おし消えました(一応asmでも確認)。
% gcc -O3 test.c -o test.c.out % time ./test.c.out ./test.c.out 1.33s user 0.00s system 94% cpu 1.411 total
まあ当然の結果です。以下にtest.cpp.outとtest.c.outのdesasmされた.textをのせます(gccの-Sでもいいのですが読みにくいので)。
odjdump -d test.cpp.o:
00000000 <main>: 0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 57 push %edi 4: 56 push %esi 5: 53 push %ebx 6: 81 ec 0c f4 01 00 sub $0x1f40c,%esp c: 83 e4 f0 and $0xfffffff0,%esp f: 83 ec 10 sub $0x10,%esp 12: 8d b5 e8 0b fe ff lea 0xfffe0be8(%ebp),%esi 18: b8 ff 7c 00 00 mov $0x7cff,%eax 1d: 8d 95 f0 0b fe ff lea 0xfffe0bf0(%ebp),%edx 23: 90 nop 24: 89 02 mov %eax,(%edx) 26: 83 c2 04 add $0x4,%edx 29: 48 dec %eax 2a: 79 f8 jns 24 <main+0x24> 2c: 31 db xor %ebx,%ebx 2e: 8d 7b 01 lea 0x1(%ebx),%edi 31: 89 f8 mov %edi,%eax 33: 81 ff ff 7c 00 00 cmp $0x7cff,%edi 39: eb 16 jmp 51 <main+0x51> 3b: 8b 0c 9e mov (%esi,%ebx,4),%ecx 3e: 8b 14 86 mov (%esi,%eax,4),%edx 41: 39 d1 cmp %edx,%ecx 43: 7e 06 jle 4b <main+0x4b> 45: 89 14 9e mov %edx,(%esi,%ebx,4) 48: 89 0c 86 mov %ecx,(%esi,%eax,4) 4b: 40 inc %eax 4c: 3d ff 7c 00 00 cmp $0x7cff,%eax 51: 7e e8 jle 3b <main+0x3b> 53: 81 ff fe 7c 00 00 cmp $0x7cfe,%edi 59: 89 fb mov %edi,%ebx 5b: 7e d1 jle 2e <main+0x2e> 5d: 8d 65 f4 lea 0xfffffff4(%ebp),%esp 60: 5b pop %ebx 61: 5e pop %esi 62: 31 c0 xor %eax,%eax 64: 5f pop %edi 65: c9 leave 66: c3 ret
objdump -d test.c.o:
00000000 <main>: 0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 56 push %esi 4: 53 push %ebx 5: 83 e4 f0 and $0xfffffff0,%esp 8: 83 ec 10 sub $0x10,%esp b: ba ff 7c 00 00 mov $0x7cff,%edx 10: b9 01 7d 00 00 mov $0x7d01,%ecx 15: 8d 76 00 lea 0x0(%esi),%esi 18: 89 c8 mov %ecx,%eax 1a: 29 d0 sub %edx,%eax 1c: 89 14 85 00 00 00 00 mov %edx,0x0(,%eax,4) 23: 4a dec %edx 24: 79 f2 jns 18 <main+0x18> 26: 31 db xor %ebx,%ebx 28: 8d 73 01 lea 0x1(%ebx),%esi 2b: 89 f0 mov %esi,%eax 2d: 81 fe ff 7c 00 00 cmp $0x7cff,%esi 33: eb 26 jmp 5b <main+0x5b> 35: 8b 0c 9d 00 00 00 00 mov 0x0(,%ebx,4),%ecx 3c: 8b 14 85 00 00 00 00 mov 0x0(,%eax,4),%edx 43: 39 d1 cmp %edx,%ecx 45: 7e 0e jle 55 <main+0x55> 47: 89 14 9d 00 00 00 00 mov %edx,0x0(,%ebx,4) 4e: 89 0c 85 00 00 00 00 mov %ecx,0x0(,%eax,4) 55: 40 inc %eax 56: 3d ff 7c 00 00 cmp $0x7cff,%eax 5b: 7e d8 jle 35 <main+0x35> 5d: 81 fe fe 7c 00 00 cmp $0x7cfe,%esi 63: 89 f3 mov %esi,%ebx 65: 7e c1 jle 28 <main+0x28> 67: 8d 65 f8 lea 0xfffffff8(%ebp),%esp 6a: 5b pop %ebx 6b: 5e pop %esi 6c: c9 leave 6d: c3 ret
test.c.oのほうはリンク時にdataのアドレスが0x0にrelocateされるんですが、それを除けば全く同じです。となればネックになっているのはdataのfetchだと考えるのが普通なんですが、ssもdsも速度的には同等であるはずですし、置かれるデータ構造が同じうえ、キャッシュはlinear addressでされるらしいので、どこで遅くなるのか見当もつきません。実効アドレッシングで差がついてるのか、あるいはちゃんとアドレッシングの原理を理解していないのか、COMMONなオブジェクトはなんらかの理由があって遅いのか、はたまた、等々。いまだ未解決。
以下の資料を読みあさっています。
http://www.intel.co.jp/jp/developer/download/index.htm#ia32
わかりしだい追記したいと思います。誰かわかる人いたら教えてください。この辺の知識はかなり疎くてしょうがないですもう。
追記。ValgrindにCachegrindというCPUのキャッシュ機構をシミュレーションしてキャッシュミス数等をプロファイルする機能があることを知ったので試してみました。なお(ちゃんと調べてないですが)、このマシンのL1 Data Cache Sizeは16KBらしいのでtest.cpp、test.cのdataのサイズをそれにあわせました。
% valgrind --tool=cachegrind ./test.cpp.out ==17087== I refs: 1,209,567,234 ==17087== I1 misses: 1,021 ==17087== L2i misses: 584 ==17087== I1 miss rate: 0.00% ==17087== L2i miss rate: 0.00% ==17087== ==17087== D refs: 537,402,348 (268,898,767 rd + 268,503,581 wr) ==17087== D1 misses: 7,818,505 ( 7,817,144 rd + 1,361 wr) ==17087== L2d misses: 6,058 ( 4,759 rd + 1,299 wr) ==17087== D1 miss rate: 1.4% ( 2.9% + 0.0% ) ==17087== L2d miss rate: 0.0% ( 0.0% + 0.0% ) ==17087== ==17087== L2 refs: 7,819,526 ( 7,818,165 rd + 1,361 wr) ==17087== L2 misses: 6,642 ( 5,343 rd + 1,299 wr) ==17087== L2 miss rate: 0.0% ( 0.0% + 0.0% ) % valgrind --tool=cachegrind ./test.c.out ==17094== I refs: 1,208,158,555 ==17094== I1 misses: 934 ==17094== L2i misses: 524 ==17094== I1 miss rate: 0.00% ==17094== L2i miss rate: 0.00% ==17094== ==17094== D refs: 536,850,915 (268,466,100 rd + 268,384,815 wr) ==17094== D1 misses: 7,806,491 ( 7,805,248 rd + 1,243 wr) ==17094== L2d misses: 2,210 ( 997 rd + 1,213 wr) ==17094== D1 miss rate: 1.4% ( 2.9% + 0.0% ) ==17094== L2d miss rate: 0.0% ( 0.0% + 0.0% ) ==17094== ==17094== L2 refs: 7,807,425 ( 7,806,182 rd + 1,243 wr) ==17094== L2 misses: 2,734 ( 1,521 rd + 1,213 wr) ==17094== L2 miss rate: 0.0% ( 0.0% + 0.0% )
この結果を見たかぎりではC版のほうが当然速くなるはずなのですが...どうやらキャッシュミスとかアラインメントの問題でもないようです(cachegrindを信用して)。再調査します。
- The URL to Trackback this entry is:
- http://dev.ariel-networks.com/Members/matsuyama/30ed30fc30eb59096570306f90453044/tbping
Re:グローバル変数は遅い?
AMD Athlon 650MHz
gcc/g++ 3.3.5 (Debian sarge)
CPUが遅い分、数値がはっきり出ます。C版は平均して5.5秒程度、C++版は平均して4秒程度です。
> mov %edx,0x0(,%eax,4)
事実だけ見れば、これ(および類する箇所)が遅い、としか言いようが無さそうです。
Re:グローバル変数は遅い?
Re:グローバル変数は遅い?
wrap a;
a.doit();
}
今回は私の注意!うーん
OOPに基づくGUIプログラミングについて
GUIプログラミングは非常に退屈で冗長でつまらない作業だ。しかしそれぐらいならまだいい。今日のGUIライブラリは一種キチガイじみた設計になっている。これがすばらしきOOPの産物なのかとまことに崇拝したい気分である。なるほど僕にはOOPを自由に操る能力が欠けているのかもしれない、あるいは業務には必要な一種の妥協性というのが足りないのかもしれない、しかしどちらにしても時間をかければ解決できると思っていた。つまりは、OOP的にカプセル化されたコンポーネントをある複雑構造で保持し、それの更新あるいは発信をリスナを使って他のカプセル化されたコンポーネントへ反映させることが、OOPに基づいた設計ならば簡単である、あるいは仮に簡単でないにしろ時間をかければ可能であると。しかしそれは幻想にすぎなかったのだ。もう一度言うがこれは僕の能力の欠如なのかもしれないし、もしそうならばむしろうれしいぐらいなのである。なるほどそれらはOOPに基づいてカプセル化されている、それはまことに圧巻するほどに。しかし見てみよ、実際使うにはカプセルを完全なまでに分解せねばならぬではないか。これではカプセル化の恩恵を受けるどこか、ただのガラクタと化したカプセルの外殻が内部へのアクセスをただ妨げるだけで、むしろその矛盾性に設計者は苦しむのである。さて以下のような場合を考えてみよう。コンポーネントAとコンポーネントBは互いに関与すべき機能性を保持しているのだが、それはOOPによればコンポーネント化によって分離されるべきものである。つまりは第三者であるコンポーネントCのようなものを持ってきてコンポーネントAとコンポーネントBの仲介者にしなければならない。さてここでコンポーネントBがコンポーネントAの更新情報を逐次受け取れるようにリスナを設定したいとする。コンポーネントAとコンポーネントBは分離させるべきものなので、仲介者であるコンポーネントCがその仕事を請け負うのだが、さてあなたが注意深い設計者ならばコンポーネントCにその仕事を委託することにおそらくためらうだろう。なぜならそこに本来OOPによって取り除かれるべき依存性が、以前より複雑さをまして存在しているからである。仲介者であるコンポーネントCは依存方向に加えて依存範囲や依存方法などさまざまな情報を持たなければならない。そしてあなたはそれが依存に依存していることに気づかれるだろう。かくしてすばらしきOOPの概念は依存を増やすにまで達した。ここで僕が言いたいのはOOPを真っ当から否定することではない。むしろ閉鎖的にカプセル化されたコンポーネントによる関係性がOOPの概念に矛盾するということが言いたいのだ。それはとくにGUI(のリスナ)プログラミングにおける設計に顕著に現れる。Treeのあるアイテムをダブルクリックしたらあるボタンがフォーカスされる、さてこのような処理をOOPの概念に矛盾することなく実装するにはどのようにしたらよいのか。なるほどMediatorパターンを使って関係を隠蔽し統括するのか。おそらくTreeItemとButtonがフラット構造に配置されているのならOOPは饒舌になるだろう。しかし実際問題、そのようなケースはまれで、大抵の場合は皮肉なことにかかる構造はOOPに基づき複雑にカプセル化されている。どのカプセルも口をあけたがらない。口をあけさせるためにカプセルに特殊な処置をほどこしてMediatorだけを特別に通れるようにする。そしてMediatorはそのわずかに開いた口の隙間を息苦しそうに通り抜けていくのである。あまりに馬鹿げてやしないだろうか。一体他への関与をも閉ざしてしまうカプセル(プライベートなリスナセットを持っている)の用途はどこにあるのだろうか。もちろんOOPは暗黙的に(あるいは明確に述べているかもしれない)依存は決して悪くはないと述べている。それはカプセルがアトム的でないことが許される点からも容易に解せられる。しかし同時にGoFなるものがカプセル化の優位性をこれでもかと語っている。またライブラリ設計者はきまってカプセル化を美学的にとらえてこよなく愛す。一方利用者は美しきカプセル化が織り成す戦慄すべき醜悪さと矛盾性に苦しむのである。なるほどOOPはプログラミングを容易にし簡潔にし明快にする。このことは誰も否定はできない。また以下のことは将来において願わくは現在においても肯定されるべきである。つまり閉鎖的なカプセルというのは何もなしえないということ、そしてむしろその閉鎖性がゆえに開口性に複雑に依存するということである。
- Category(s)
- program
- The URL to Trackback this entry is:
- http://dev.ariel-networks.com/Members/matsuyama/about_gui_programming_based_on_oop/tbping
Re:pimplイディオムを語る
Re:pimplイディオムを語る
pimpl_ = rhs.pimpl_;
は
delete pimpl_;
pimple_ = rhs.pimple_;
ってことになってOKじゃないですか?
Re:pimplイディオムを語る
auto_ptr
{
auto_ptr
b = a;
//ここでbがデストラクタされる、ポインタ先を解放する
}
//ここの時点で、aはすでに解放された不正なポインタ指してる。
ってな具合で。
Re:pimplイディオムを語る
pimpl_ = rhs.pimpl_;
は
pimpl_.reset(rhs.pimpl_.release());
だから
auto_ptr a(new Hoge());
{
auto_ptr b;
b = a; // ここでaはbに所有権を委譲し,aは0ポインタを指す.
// ここでbのデストラクタが呼び出され,ポインタ先を解放する.
}
// ここの時点で,aは0ポインタ指している.
ってな具合でここの動作に関しては問題ないと思います.
Re:pimplイディオムを語る
代入してpimpleの所有権が移ってしまうと、元のオブジェクトが持ってたpimpleはどこへ?
boostを使ってよいのなら、pimpleにはboost::scoped_ptr を使うべきです。
#ついでに、pimpleにboost::shared_ptrを使うのも危険です。うっかりしたoperator=を実装すると、複数のオブジェクトで同じpimpleを共有してしまうので。
Re:pimplイディオムを語る
Re:pimplイディオムを語る
pimpl_ = rhs.pimpl_;について、2009-05-15 13:48のAnonymous Userさんやhiroseさんのおっしゃっているのと同じことを指摘するつもりで最初にコメントを書きました。曖昧な記述で混乱を招きましたら、申し訳ございませんでした。ただ、今になって気付いたのですが、実際にはrhsがconstのためコンパイルエラーになりますね(代入元がconstだとauto_ptrはエラーになります)。どちらにせよ、「参照カウントではなく所有権の移動という挙動を持っているためauto_ptrでは問題がある」ということに変わりはありません。
さらに、最初にコメントをしたとき私はまだ知りませんでしたが、auto_ptrを使ってはならないもう1つの理由があります。fooやbarのデストラクタ(根本的にはhoge::implのデストラクタ)が呼ばれないのです(こっちのほうがよっぽど深刻!)。pimpl_のデストラクタで、hoge::impl(不完全型)へのポインタに対しdeleteするのがその原因です。なお、boost::scoped_ptrだとこれを検出してコンパイルエラーにしてくれます。
これの対処は次のいずれかで可能です。
1. boost::shared_ptr / std::shared_ptrを使う: 動的削除子 (dynamic deleter) - 意外と知られていない??boost::shared_ptr の側面 ― Cry's Diary
2. hogeに明示的なデストラクタの定義を与える(boost::scoped_ptr / std::auto_ptrで適用可能): pimplイディオムをscoped_ptrを使って実現するときの注意 ― redboltzの日記