Personal tools
You are here: Home ブログ matsuyama Categories program
Document Actions

program

Up one level

Document Actions

Enjoy 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のある場所が新しいバッファに出力されます。

近いうちに本格的にソースを読んでいきます。

Category(s)
program
linux
The URL to Trackback this entry is:
http://dev.ariel-networks.com/Members/matsuyama/enjoy-source-code-reading/tbping

C++パーサーライブラリ、yapc++

Yapc++

旧名ParseaseであるYapc++ version 0.0.1aをリリースしました。i18nの対応もYapc++の機能に含めてしまおうという話でここ数日開発していたのですが、パフォーマンスを落とすかシンプルさを落とすかあるいは両方落とすかの実装しか浮かばなかったので、結局のところi18n対応はYapc++範疇外ということで今回リリースにいたりました。もちろん拡張セットとしてのi18n対応は考慮されていますし、今後のバージョンアップは主にそれの対応だと思われます。ここに書くべき記事は本家のほうへ書くことにしましたので、ここでは変わってその実装に関しての考えかたやテクを書いていきたいと思います。

Category(s)
c++
program
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しろという方向にベクトルが向いている雰囲気です。時間があるときになんとかしたいと思います。

Category(s)
program
linux
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).

Nihongo unatenakunatta. Koredakara GUI application ha iya nanda.

Category(s)
program
linux
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を使う分のパフォーマンス低下は当然考えられる問題だ。しかしメリットとデメリットを計算したとき、最終的にはやはり符号は+になることだろう。

Category(s)
c++
program
The URL to Trackback this entry is:
http://dev.ariel-networks.com/Members/matsuyama/pimpl30a430a330aa30e030928a9e308b/tbping

Re:pimplイディオムを語る

Posted by valp at 2008-03-19 00:00
auto_ptrではなくてshared_ptr(boostあるいは最近だとstd::tr1)にしないとoperator =はまずいです。標準のauto_ptrは参照カウントなどではないので、現在の規格に合致した処理系ではpimpl_ = rhs.pimpl_;が思った通りにならないはずです。

Re:pimplイディオムを語る

Posted by M太郎 at 2009-04-24 09:57
>思った通りにならないはずです。
pimpl_ = rhs.pimpl_;

delete pimpl_;
pimple_ = rhs.pimple_;
ってことになってOKじゃないですか?

Re:pimplイディオムを語る

Posted by Anonymous User at 2009-05-15 13:48
おそらく、どちらのauto_ptrが最終的にポインタをdeleteするのか?って問題のことをおっしゃってるのでは無いでしょうか?
auto_ptr a;
{
auto_ptr b;
b = a;
//ここでbがデストラクタされる、ポインタ先を解放する
}
//ここの時点で、aはすでに解放された不正なポインタ指してる。

ってな具合で。

Re:pimplイディオムを語る

Posted by Fumi at 2010-01-02 16:06
>思った通りにならないはずです。
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イディオムを語る

Posted by hirose at 2010-01-08 00:29
pimpleイディオムでauto_ptrを使うこと自体が拙いです。
代入してpimpleの所有権が移ってしまうと、元のオブジェクトが持ってたpimpleはどこへ?

boostを使ってよいのなら、pimpleにはboost::scoped_ptr を使うべきです。
#ついでに、pimpleにboost::shared_ptrを使うのも危険です。うっかりしたoperator=を実装すると、複数のオブジェクトで同じpimpleを共有してしまうので。

Re:pimplイディオムを語る

Posted by chanel at 2010-05-27 18:46
nice post .#ついでに、pimpleにboost::shared_ptrを使うのも危険です。うっかりしたoperator=を実装すると、複数のオブジェクトで同じpimpleを共有してしまうので。

Re:pimplイディオムを語る

Posted by valp at 2010-08-30 19:18
ふとしたきっかけで、久々にこのページに出会いました。せっかくなので、自分のコメントに補足を書き足していきます。

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の日記

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として書きたい衝動にかられる。そっちのほうが美しいみたいな。でも実際そうすると逆に問題が難しくなる。いやはやアルゴリズムは奥が深い。

http://www.kmonos.net/wlog/sub/gcj06_q250.py

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さんのと同じになるけど、面倒なのでいいや。

http://www.kmonos.net/wlog/sub/gcj06_q750.py

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を信用して)。再調査します。

Category(s)
program
gcc
The URL to Trackback this entry is:
http://dev.ariel-networks.com/Members/matsuyama/30ed30fc30eb59096570306f90453044/tbping

Re:グローバル変数は遅い?

Posted by inoue at 2006-09-15 01:48
答えは分かりませんが、一応追試。同じくC++版の方が速いです。

AMD Athlon 650MHz
gcc/g++ 3.3.5 (Debian sarge)

CPUが遅い分、数値がはっきり出ます。C版は平均して5.5秒程度、C++版は平均して4秒程度です。

> mov %edx,0x0(,%eax,4)

事実だけ見れば、これ(および類する箇所)が遅い、としか言いようが無さそうです。

Re:グローバル変数は遅い?

Posted by matsuyama at 2006-09-15 11:12
AMDでもなるんですか。んじゃPentiumの特殊な最適化のせいではないってことですね。個人的には局所化の問題なような気がしてならないんですが、ちゃんと証明できないのでまだまだ調査中です。

Re:グローバル変数は遅い?

Posted by Sildenafil at 2010-08-14 18:49
int main() {
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

Copyright(C) 2001 - 2006 Ariel Networks, Inc. All rights reserved.