2013-5-20[月] stlport 5.2.1 for dmc,Open Watcom今更ながら(現実逃避がてら) stlport 5.2.1 を Open Watcom 1.9 や dmc 8.56 に対応してみてた。ow のほうはそれなりになった気もするが dm のほうはリンカのこともあっていまいちかも。（何か根本的に見逃しているような気もする） 前回 stlport いじってたのが3年前……時間立つのは速いなあ。5.2.1がrelease最新版のままで開発自体は進んでなくもないけれど、vcでさえ面倒臭そうだったのと、watcom への対応を思うと古いコンパイラへの対応が残っているほうが無難そうに思えて結局5.2.1。(追記: 最近の開発版のほうはどうもunix系でc++11対応のg++のみなのかも. vcはおろかmingwもだめそう) 面倒くさいといえば付属のbuild環境も面倒で無視した。手抜きでバッチでコンパイル。ow,dmc以外にコンパイル試したのは vc(7.1,9,11), mingw g++4.7.1tdm版(32bit/64bit), bcc5.5.1。(ああ mingw 64bit対応が一番マトモな作業かもしれない……動作確認不十分だけど） 作業の参考にと pointer_specialization.txt と 「コンフィグレーション マニュアル」 をいつものごとく翻訳サイトの訳を手直ししたりしてみたが……コンフィグは内容古くて実際には結構廃止されてたり追加されてたりするようで少し徒労感有り。
と、ま、モノは stlport521dmow2.zip。
(txt)
2013-5-19[日] optlink のコンパイル仕事が一段落したので放置していた諸々に手をつけねば、だけど、忙しい最中の現実逃避の残滓を先に…とグダグダ。現実逃避で dmc や ow で遊んでたのですが、dmc ってc++としてはowよりよさげだけどリンク時にハングしたり-gでデバッグ付でまともに動かせなかったりと optlink がかなりネック。交代のリンカ探すもデバッグ機能対応してるやつなんてそうそうなく…で灯台下暗し。optlink 自体がオープンソース化されてたようで dm856c よりも新しいソースがコミットされてた。コンパイルして使うとハングとか -g の具合が改善されてる模様。（といっても -g付きでちょっと大きいリンクすると Error 168: >64K Global Types の刑なのは変わりませんが）
とりあえず、コンパイルメモ
コンパイルには dmc と vc(9) が必要。(express版 でいけるかは未確認）。
vc の nmake と ml(マクロアセンブラ) あたりを使っているよう。 dmcとvcのパスを通し(vcvars32.bat 実行後 set path=x:\dm\bin;%path% をするなり）、 imagecfg.exe をパスの通ったところに置いておく.(不精して dm\bin に掘り込んだ)
ダウンロードしたzip を \dm があるドライブの適当なフォルダに解凍。
(gitで取得のほうが普通か？）. 一応 開発者と同じ状態にするならば
その中の ができているので、dm\bin に上書きコピー。
追記 dmd 2.063 (及びそれに対応するdmc.zip)付属のlink.exeは2013/04 の修正が反映されたバージョンになったようで、わざわざコンパイルしなくてもよくなった。
2012-12-14[金] boost::container で俺俺アロケータこれは C++ Advent Calender 2012 14日目 の記事です。 C++11やboostをまだロクに使っていない人間なので、雰囲気を掴むために boost1.52 の boost/container フォルダを一寸覗いてみました。 new,delete等メモリーアロケート のコストを無視できないターゲットを扱うことも多いので、俺俺アロケータを渡してみたいってのもあり。 C++11仕様でアロケータが今までより楽にかけるようだし、scoped_allocator_adaptor も何か使えそうですし. ※いまだvc9をおもに使ってるので(vc12も使いますが)、C++11の記述はさけてます.
boost::containerboost::container ですが、C++11で仕様拡張された vector,list,map,set,deque 等のコンテナの機能を C++03コンパイラでもなるべく使えるようにした互換コンテナ群+α です。 C++11 で増えたコンテナ(array, unorderd_map 等)については すでにboostに実装があるためか(?) boost::container には含まれていません。詳しいことは こちら とか他のサイトにあたってください。 将来的にどんどん変わっていく部分も多々あるでしょうが、とりあえず boost_1_52_0/boost/container/ フォルダで wc してみると、41ファイル 27613 行（detailフォルダ含)。 実際には container 外のboostヘッダをいろいろinclude しているので実質はもっと大きいです（map,set(tree)等は boost::intrusive のものを使っているようです）。 (ちなみに boost_1_52_0/boost/ では 8779ファイル 約172万行、やっぱりデカいです) boost/container/ 直下にあるファイルは
(ptr_container のような)既存のstdコンテナを継承して拡張(メンバー関数追加)とかではないです。 （といっても boost::intrusive 等 boost内の他のライブラリはよく使われています）
次に、いくつかコンテナについて。
vectorざっくりメンバー変数の部分だけ抜き出してみて、
template <class Allocator>
class vector_alloc_holder {
struct members_holder : public Allocator {
pointer m_start;
size_type m_size;
size_type m_capacity;
}
}
template <class T, class Allocator>
class vector : vector_alloc_holder<Allocator>;
(SGI版派生等)他の実装だと全てポインタで管理していることが多いですが、この実装はsize,capacityを個数で持っています（個人的にはデバッグ時にメンバー変数で見れるので好み）。
Allocatorは、(非static)メンバー変数がない場合に実質 0バイトになるよう struct の継承元になっています。 ということで C++11なら
// １回 N個 アロケートするだけの Allocator
template<typename T, unsigned N>
class SampleAllocator1 {
public:
typedef T value_type;
SampleAllocator1() { }
T* allocate(unsigned n) { assert(n == N); return reinterpret_cast<T*>(buf_); }
void deallocate(T*, unsigned) { }
bool operator == (SampleAllocator1 const & ) const { return false; }
bool operator != (SampleAllocator1 const & ) const { return true; }
private:
typedef double buf_t;
buf_t buf_[(N*sizeof(T)+sizeof(buf_t)-1) / sizeof(buf_t)];
};
//typedef std::vector<int, SampleAllocator1<int,1024> > Int1024Vector;
typedef boost::container::vector<int, SampleAllocator1<int,1024> > Int1024Vector;
Int1024Vector g_intVec;
みたいな真似をしても大丈夫のはず...と書いたけど上記はたぶん boost::container に依存しています.
list実装は boost::intrusive の定義も多く面倒なので、かなり端折って (boost::container としてでなく) ありそうな list 実装のメンバーの雰囲気として以下 （すみません、後付で boost::container からめたはいいけど対処しきれず...)
class Node_Base {
Node_Base* next_;
Node_Base* prev_;
};
template<typename T>
class Node : Node_Base {
T value_;
};
template<typename T, class A >
class List : A {
ListNode_Base root_;
size_t size_;
};
かなりいい加減ですが、メモリーの雰囲気がわかれば...
map,multimap, set, multiset
map,set は たいてい赤黒木 実装のようで、boost::container では boost::intrusive を使ってるようです。
class Node_Base {
Node_Base* left_;
Node_Base* right_;
Node_Base* parent_;
bool balance_;
};
template<typename T>
class Node : Node_Base {
T value_;
};
template<typename T >
class Tree : A {
Node_Base root_;
size_t size_;
};
List や Map は 渡された アロケータをそのまま使うのではなくて、allocator のメンバーの
template <class U> struct rebind { typedef allocator<U> other; };
を用いて、 T でなく Node<T> の allocator を使っています。 また、allocator への要求は通常 1個単位になると思います。 ということで、list や map の俺俺アロケータとしては、ノードサイズ固定のメモリーをプールしておく、というのが考えられます。
template<unsigned B, unsigned N>
class SampleAlloc2 {
public:
SampleAlloc2() {
for (unsigned i = 0; i < N-1; ++i)
buf_[i].link = &buf_[i+1];
buf_[N-1].link = NULL;
root_ = &buf_[0];
}
void* allocate(unsigned n) {
assert(n == 1 && root_);
Link* p = root_;
root_ = p->link;
return p;
}
void deallocate(void* t, unsigned n) {
if (t) {
assert(n == 1);
Link* p = reinterpret_cast<Link*>(t);
p->link = root_;
root_ = p;
}
}
private:
union Link {
Link* link;
char b[B];
};
private:
Link* root_;
Link buf_[N];
};
enum { ELM_SIZE = 32 }; // コンテナのノードを含んだ要素のバイト数.
enum { MAX_SIZE = 16 };
template<typename T>
class SampleAllocator2 : public SampleAlloc2<ELM_SIZE,MAX_SIZE> {
typedef SampleAlloc2<ELM_SIZE,MAX_SIZE> base_type;
public:
typedef T value_type;
SampleAllocator2() {BOOST_STATIC_ASSERT(sizeof(T) <= ELM_SIZE);}
T* allocate(unsigned n) { return reinterpret_cast<T*>(base_type::allocate(n)); }
void deallocate(T* t, unsigned n) { base_type::deallocate(t, n); }
bool operator == (SampleAllocator2 const & ) const { return false; }
bool operator != (SampleAllocator2 const & ) const { return true; }
};
// list
typedef SampleAllocator2<int> IntAllocator;
typedef boost::container::list<int, IntAllocator > IntList;
// map
struct cstr_less {
bool operator()(const char* l, const char* r) const { return strcmp(l,r) < 0; }
};
typedef std::pair<char const* const,int> smpPair_t;
typedef SampleAllocator2<smpPair_t> SmpPairAllocator;
typedef boost::container::map<const char*, int, cstr_less, SmpPairAllocator > StrIntMap;
※ 要素(ノード)サイズ(ELM_SIZE)が直うちでみっともないですが、とりあえずは。
deque（実装面倒なのと、ターゲットであまり使わないし... いえ、時間切れ. 後日に何か)
stringstd::stringは(C++03では)ライブラリごとに結構実装がばらけています(EffectiveSTL に載ってるのとか)。 c++11 で縛りがきつくなったので多少にかよってくるかもですが、それでもいろいろできそうです。 最小限としては vector と同様の内容になりそうですが... boost::container::string から端折って抜き出してみると
struct long_t {
size_type is_short : 1;
size_type length : (sizeof(size_type)*CHAR_BIT - 1);
size_type storage;
pointer start;
};
struct short_header {
unsigned char is_short : 1;
unsigned char length : (CHAR_BIT - 1);
};
struct short_t {
short_header h;
value_type data[UnalignedFinalInternalBufferChars];
// UnalignedFinalInternalBufferChars ≒ (sizeof(long_t)-sizeof(short_header))/sizeof(value_type)
};
union repr_t {
long_raw_t r;
short_t s;
};
long_t は長い文字列でアロケータを用いる場合で、sizeof(long_t)-α 以内におさまる短い場合は short_t のようにして領域をバッファとして使い動的確保せずにすませる、という工夫がされています。 64bit CPUだと、vector互換でもsizeof(ポインタ)*3=24bytesになりますし、結構ありがたい実装です。 （最近作ってた 俺俺string がまさにこのタイプだった... もうboostのでよく） ※ メモ: ビットフィールドは エンディアン問わず、先に書かれたものが低アドレスに配置される.
stable_vector, flat_map, flat_set
stl コンテナの代用品でなく、vector 実装をベースにした特化版。
詳しいことは他のサイトにあたってください。
scoped_allocator_adaptor
C++11 で増えた アロケータです。
scoped_allocator_adaptor を用いれば、例えば map<string,int> のようなコンテナで、ローカルなアロケータをstringとmapで共通で使えるようにできます。 アロケータをコンテナのメンバーにするので、当然メモリー使用量も増えます（とくに内側のコンテナは数が多くなりやすく）。 ので、コンテナのメンバーにするアロケータはポインタだけにし、実装はさらにその先に用意、といった感じにすることになると思います。 詳しいことは こちら のサイトとかみてもらったほうがいいです。 正直なところ一見ではよくわからず、試してみてなんとなく納得の状態です。 以下、試してみたソース.
#include <stdio.h>
#include <boost/container/map.hpp>
#include <boost/container/string.hpp>
#include <boost/container/scoped_allocator.hpp>
#include <boost/foreach.hpp>
// mapで解放しないこと前提に、スタックで解放無視の簡易アロケータ.
template<unsigned N>
class SampleAlloc3 {
public:
SampleAlloc3() : size_(0) { }
void* allocate(unsigned n) {
assert(size_+n <= N);
void* p = ptr(size_);
size_ += n;
return p;
}
void deallocate(void*, unsigned) { /*dummy*/ }
private:
typedef double buf_t;
void* ptr(unsigned n=0) { return (char*)buf_ + ((n + sizeof(buf_t)-1) & ~(sizeof(buf_t)-1)); }
private:
unsigned size_;
buf_t buf_[N / sizeof(buf_t)];
};
// map<string,int> のメモリー
template<unsigned SAMPLE_ALLOC3_SIZE>
class Hoge {
public:
Hoge() : strIntMap_(std::less<String>(), MapAllocator(StrIntPairAlloc(&smpAlc3_))) {}
void insert(const char* name, int val) {
//strIntMap_[String(name, &smpAlc3_)] = val;
strIntMap_.emplace( name, val );
}
void printAll() {
BOOST_FOREACH(StrIntPair p , strIntMap_)
printf("%s = %d\n", p.first.c_str(), p.second);
}
private:
typedef SampleAlloc3<SAMPLE_ALLOC3_SIZE> Alloc;
template<typename T>
class SampleAllocator3 {
public:
typedef T value_type;
// SampleAllocator3() : alc_(0) {} // デフォルトコンストラクタは用意しないほうが安全.
SampleAllocator3(Alloc* alc) : alc_(alc) { }
template<typename U> SampleAllocator3(SampleAllocator3<U> const& r) : alc_(r.detail_get_ptr()) { }
T* allocate(unsigned n) { return reinterpret_cast<T*>(alc_->allocate(n*sizeof(T))); }
void deallocate(T* p, unsigned n) { alc_->deallocate(p,n*sizeof(T)); }
bool operator == (SampleAllocator3 const & ) const { return false; }
bool operator != (SampleAllocator3 const & ) const { return true; }
Alloc* detail_get_ptr() const { return alc_; }
private:
Alloc* alc_;
};
typedef boost::container::basic_string<char, std::char_traits<char>, SampleAllocator3<char> > String;
typedef std::pair<const String, int> StrIntPair;
typedef SampleAllocator3<StrIntPair> StrIntPairAlloc;
typedef boost::container::scoped_allocator_adaptor< StrIntPairAlloc > MapAllocator;
typedef boost::container::map<String, int, std::less<String>, MapAllocator > StrIntMap;
private:
SampleAlloc3<SAMPLE_ALLOC3_SIZE> smpAlc3_;
StrIntMap strIntMap_;
};
void sample3()
{
Hoge<1024> hoge;
hoge.insert("xyz", 1);
hoge.insert("abcdefghijklmnopqrstuvwxyz", 2);
hoge.insert("1234567890", 3);
hoge.printAll();
}
emplace, emplace_back、単に(コピー)コンストラクタの頻度さげるだけじゃなくて、今回のような場合まさに必須の類でした。
おわりに
遅刻したうえに、
グダグダな内容ですみません。 例に挙げたソースのとおり allocator の記述に関してはすごく楽でした。 が、boost::contaneier を std:: にかえて vc12 でコンパイルすると全く×だったので boost::contaneier に結構依存していると思います。 時間の余裕なくなってるので、たぶん後日 補足修正書くことになりそうですが... おつきあいいただきありがとうございました。
追記: コンパイル試したときのソース
[コメント]
2012-12-12[水] サイト分割このサイトのプログラミング以外のページをこっちに移した。いろいろ思惑あれど遅々として進まず、けれど年越す前には何かしとこうと... というか、c++ advent calendar に参戦申込(12/14) しちまってたのでその前に多少なりとも、で。（肝心のネタをどうしよう... )
2012-10-27[土] Win8pro インストールWin8の1200円のアップグレード版をダウンロードした勢いで（サブ機だし）Win7引き継ぎでインストールしたはいいけれど不安定になって結局更地で再インストール中。(OSのインストールは楽ちんになっても各アプリ側が面倒この上なく） 引き継ぎインストール、最初はそこそこいい感じに移行できたように思ったけれど、使いだすと引き継げてるもの・引き継げてないものがあってチグハグだった。
特にWindowsエクスペリエンス計測の このコンピューターの評価 がエラーで動かなかったときは唖然... [追記] Win8 設定完了前に メインでつかってる Win7機がお亡くなりになったため win8に強制移住。HDDが生きてたので被害は少ないけれど、元環境のアプリを起動できないのはやっぱり面倒。 [追記2] iPad mini を購入したら一気に win8 熱が冷めてしまった。片手で持ててそこそこ広いってのは思いのほか重要だった模様。寝ころんでpdf読んで寝落ちするのはある種幸せです。
2012-6-3[日] LaVieLight に Win8rp をインストール久しぶりにサブノートPCを持ち歩こうと思いたち、Win8cp を試しに入れて放置しっぱなしだった LaVie Light BL350/D を復活中。 丁度 Win8 Release Preview が公開したてだったので更地にしてインストールすることにした。 マシンのほうは Atom な netbook の範疇だけど、1366x768 ドットある奴なんで一応 Metoro も大丈夫（なので Cp 版インストールできてた。非力な Atom だけど 1.5GHz 2コア(HT x4) だし、メモリは2GBにHDDはSSD120GBに換装済みなので、それなりに使える感じ）
インストール前に、まず、Microsoft アカウント(Live ID）の氏名欄を 英数のみに変更。 Win8 はPCのユーザー設定で MSなクラウドサービスと連動前提の設定と、そうでない（従来タイプの）設定を選べるが、CP 版時に いろいろ試したく 連動のほうを選んだら、Microsoftアカウント情報に登録してある氏名の“名”の文字列でユーザーが作られてしまったのだった。本名を漢字で設定したままだったから c:/users/本名 な漢字フォルダが作られしまい、古いツールを使う機会もあるプログラマとしては腹立たしい状態だったので、今回はアカウント情報のほうを変えておくことで対処。(CP版のときはこの段階でかなり萎えて余り使わず放置） 更地からなので ISOイメージをDVDに焼いて USB-DVD でインストールした。 途中でプロダクトID を聞かれたので、Webインストール版を実行して手順に従って操作している途中で表示されたプロダクトID を用いた。（この方法でよかったのか不明だがとりあえず動いてる）。 当然インストール開始時には以前インストールしたwindowsの情報は引き継がないほうを選んだのだけど、インストール後デスクトップを選んでみれば壁紙無し単色でタスクバーが縦置き状態……これWin8のデフォじゃないよね？ CP版で設定していた己の設定ぽいので、アカウントに紐付された情報が一部あるのかも。
とまOS自体は結構すんなりインストールできたと思う
その他アプリのインストールについては、CP版より更にスタートボタン破棄の方向が強められてる感じ。 CP版のときは、タスクバーに新規ツールバーとして C:\users\(ユーザー名)\AppData\Roming\Microsoft\Windows\Start Menu\Programs を登録すれば簡易なプログラムメニューとして使うことができたけれど、RPではアプリをインストールしても そもそも このフォルダにアプリのショートカット等は作られず、Metoroなスタート画面にドバっとアイコンが現れる状態。元の(start-プログラムメニューでの)フォルダ構成無視なんで一気にスタート画面がゴミ溜めと化す。全くスタート画面を使わなくてすむならそれでもいいけれど、立ち上げ時に必ず来るしね……しかたないので、右クリックで不要なものをマークして一気にピン止めを外した（ちょっと面倒)。 ※ 全部が全部じゃなくて一部(susie)は従来のメニューに現れるものもあった（たぶん START-プログラム・メニューへの登録が今のwinの作法に則っていないのかも）
インストールしたプログラムでまともに動かなかったのは TortoiseSVN(1.7.7)。
チェックアウトしたりTortoiseSVNのメニューが閉じられるときにクラッシュする。
それだけでなく Exproler(タスクバー) が不安定になって ゴミ箱を空にしようとしたり
タスクバーを自動に隠す設定をやめようとしたらハング（即再起動するが）。 とりあえず TortoiseSVNをアンイストールして再起動で元に戻ったけれど、最初 アンイストール後シャットダウンで終了して電源ボタンで起動しなおしたら OS不安定のままだったので結構あせった。2,3回やっても変わらずで。再起動を選んだところ"更新します"みたいなメッセージでて再起動後ゴミ箱空にしてもハングしなかったので一安心だけど。Win8からの高速なブートや終了のための仕組みの影響なんでしょうかね。 追記: またゴミ箱空にしたらハングするようになった。FireFox(12)も終了するたびにクラッシュレポータが表示される。 どうやら今度は Google日本語入力が原因だった模様。設定をMS IMEに切り替えたらゴミ箱空にできたしFireFoxも正常終了、googleIMEに切替るとまたハング...うーシステム拡張的なものは結構引っかかる感じなのかな。
2012-2-29[水] pyukiwiki 0.2.0月末に作業締め日がある場合、さて閏年でよかったと思うべきか... はどうでもよく。 このサイトに使っている pyukiwiki 共同開発版は一時開発が止まってたけどまた再開していたようで v0.2.0p1 が出てたので更新してみた。 wikiプログラムの更新だけでサイト自体のリニューアルというわけではないけれど。でも微妙な修正をちょこちょこ、どうせspamしか書き込まないのだからcommentは無しにしたり(少し寂)、無理にblog風にすることもないなで昔のtop頁に戻したり。 (もう少しいじってからとか思うもその状態で2週間放置だったり。) pyukikwikiの更新のほうは、久しぶりすぎて、いろいろ細かいこと忘れていてすごく手間取った。自分の改造やプラグインの事情が記憶の彼方なのは当然として、使用した環境じゃ CRLF だとcgi(perl)が動いてくれないことに中々気づかなかったり(本来なら年始に移行するつもりが) 0.1.9あたりから utf-8 専用板が用意されてるようなので、utf-8 版にしようと思ったのも一手間。頁等のutf8へのコンバータプラグインが用意されているけれど、さすがに 0.1.7では駄目のようで一旦 euc(従来)版 の0.2.0環境に移行する必要があり... コンバートだけだからと compact 版を使ったところ動かなかったり(full版は動いてくれた) 改造|自前のpluginの辻褄合わせは微妙に面倒だけどしかたなし。editは改造しなくてもよくなってたけど、calender2とか改造に依存したサイトになってるので... 入れ替える時面倒なので結局 改造プラグインは名前を変えて対処したり。 スキンは 0.1.7で使ってたのがほぼ無変更で使えたのでそのまま. うち向きの仕様も増えてるっぽいので ほんとは 0.2.0 のをベースに作りなおしたほうがいいのだろうけど。
と、pyukiwiki共同開発サイト 見に行ったら 0.2.0p2 のアナウンスが出てた模様。 compact版はやっぱり配布内容がおかしかった模様. (p2にしようかと思うもダウンロードは3/1予定... とりあえずp1のままで)
2011-11-11[金] C++11 を忘れたい、３年くらい
ポッキーの日、と言われてすぐになんのことか思え出せなかった虚け者です...いや、覚えていなくてもいいと思うけれど おすそ分けのポッキー食べたんだからちょっとくらいは覚えておこう＞己。で連鎖的に C++11 を思い出す、けど、まともな処理系がでてくる2,3年後までは知らずにすませていたかったというか忘れたい。今 C++ 03 で(ライブラリを)作るものにとっては非常に目の毒です。（と、ま、ただの生存証明）
2011-1-6[木] stlport.orgひさしぶりに www.stlport.org を見に行ったら消失していて焦ってしまう。 といっても sorceforge にも頁があるので… というより http://stlport.sourceforge.net/Home.shtml が公式ということか? 左サイドのメニューをちゃんと認識していなかった。 いまさらながらhistoryやFAQを見てなんとなく納得。 （放置してた旧サイトのドメインが消失したってだけのことでいいのかな） あとFAQみて4.6系はいまいちな状態でv4の最後の綺麗な版が4.5.3だったことを知る。dmc用公式 stlport が4.5.3どまりなのはそのへんもあるのかと連想。 現在の最終の公式リリースは 5.2.1(2008) のままだけど、開発版のソースをみると、メジャーバージョン(#define)は 6 になっていた（6に向けての開発中) C++0xを考慮してるし、あまりに古い仕様のコンパイラは対象外にしていってるよう。 さすがに、メンバー関数テンプレートのサポートは必須扱い、stdint.hも利用してるしで、互換のためにごちゃごちゃしていた記述が省かれたり単純になったりですっきりしてきている。（v4→v5 時ほどではないのだろうけれど）
ライセンスについては LICENSE ファイルが同梱されているので、それを確認、と。
[1/8追記] どうも http://stlport.com/ がある模様。消失じゃなくて移転ということなのか?
2011-1-1[土]あけましておめでとうございます。今年もよろしく。 去年は人生の節目のようなことがあった反面、 総じてグダグダな一年だったので来年はもっと頑張る予定。 いや今年はも少し頑張るです（数え年は気になる）
また、そこそこ環境整い、さて年賀状印刷しようとしたら、今度はプリンタ(Canon MP640)がエラー6C10 で動作できず。検索でみつかるモノを見ると、基本、メーカー修理するしかなさそうだ。年末年始修理受け付けてないようなので後日。しかしまだ半年経ってなくてあまり使ってないのに…いやプリンタは使用頻度が低すぎるのがまずいのだろうけど。ああ6C10で引っかかる頁はMP640以外もあるのでCanonの機種はエラーコードを継続しているのだなあ、と当たり前といえばそうだけれど妙に感心してしまった。
2010-3-21[日] LLVM lli での実行そういや LLVM の VM(lli) ってどれくらいなんだろうか、とちょっと気になったので 3/12のを lli で実行してみた。 llvm-gccでコンパイルして、 llc で生成したネイティブアセンブラソースからexeを作ったもの、と、 lli で実行したもの。 llcからのexe結果は不精して、前回のからコピペ。 今回試した lli はそのときより数日新しいllvmになっていたり 多少測定環境がぶれていたりするけれど、おおざっぱな雰囲気をみる分には...で。 （ソース&exe)
大筋 lliの実行結果は llc でネイティブアセンブラ生成した場合と同様の結果のよう… 仕組みからすれば、lliのほうは測定範囲外の部分で余分に時間かかってる (実行時コンパイルしてる)だろうが、 .bcサイズに対する今時の実行環境のパワーを思えば たいしてペナルティがあるわけでなく、ってとこ、か? （ ロード時に一括コンパイルしているのかな？） ネイティブ実行以外興味なくて、最初にちょろっと試しただけで、以外に速いかも なんて思ってたのだけど、以外に、どころじゃ、なかった。 LLVM関係の記事(appleのopenglな件とか)に書かれていることを思い返せば、 こういうことなんだろうけど、実感してなかった、というか、わかってなかったことを実感です。
2010-3-20[土] LLVMで Cに変換してみるLLVM (llc) には Cソースコードを生成する機能があり、 C++ソースをCソースにすることができる模様。 ただし C++ から C への直接変換するのではなく、 一旦.ll/.bc(llvm用アセンブラソース,ビットコード)にしたものを、 llc.exe で（ターゲットCPU用アセンブラソースのかわりに） Cソースへ変換するというもの。 普通のアセンブラソースをCに変換した場合 オーバーヘッドは当然あり、 全体として問題になることはそうないかもだが (昔アセンブラソースからCに変換しての移植作業を何本かやったときの印象)、 何割(何倍)か遅くなっていてもおかしくない。 が llvmの .ll/.bc は、 普通のアセンブラソース/オブジェファイルでなく、 それより情報の多い中間コードなわけだし、 llvm-gcc & llc でオプティマイズしているため、 Cソースになっても元よりも速くなる可能性もありそう。 ということで、ちょっと、試してみた。 3/12にしたテストの１つ目。 C++でなく Cソースだけど。 (32bit色640x480→1920x1080拡大の50回生成の平均時間を求める奴. 実行環境は前回同様) llvm-gcc で llvm-gcc -S -o tmp.ll -emit-llvm -O2 -DNDEBUG test.c llvm-as -f -o tmp.bc tmp.ll llc -march=c -f -o test_dst.c tmp.bc
として test_dst.c を生成。
ヘッダ込みでコンパイルされた結果を C化してるのだから、
とりあえずstderrやwin-apiを使わないようにして(外部はC標準関数だけにして)回避。 ついでに 一旦 ldでまとめたものを.llに戻してから llc したものも試す。 llvm-gcc -S -o tmp.ll -emit-llvm -O2 -DNDEBUG test.c llvm-as -f -o tmp.ll.bc tmp.ll llvm-ld -o tmp.ll.exe tmp.ll.bc llvm-dis -f -o tmp.2.ll tmp.ll.exe.bc llvm-as -f -o tmp.2.bc tmp.2.ll llc -march=c -f -o test_dst.c tmp.2.bc 変換後のソースは、 これ。 前者の変換後ソースには元の関数を維持しているが、 後者の変換後ソースでは関数はmain()だけになっている。
が失敗したモノもあり、 実行できたものについての結果は以下 (単位：ミリ秒）
測定したタイミングによっては10,20ぐらいの差がでたりするかもで、 ざっくりとした感じに受け止めてもらうとして。 LLVMのツールであるllvm-gccではあまり差はないようだが、 他のコンパイラでの結果は、多少なりとも llc で変換したソースのほうが速くなってる雰囲気。 ただ前者と後者の変換については、モノによって多少違うも、 測定誤差でありえる範囲の差で、あまり違いはなさそうに思う （関数の分割具合の違いによるオプティマイズの トレードオフはあるだろうで、それが微妙に出てる可能性もあるけれど) 他のソースも試すべきたんだろうが、面倒で挫折... 他の例でも速くなるのか遅くなるのかどうかは結局ソースしだいと思うが、 それでも元のソースよりも速くなる例ができたわけだから （元ソースがヘボいのだろう、というのは置いといて）、 他の例でもそう酷く遅くなるようなことはないんじゃないかと期待.
C++ → C
で、 肝心の c++ → c . が、g++(clang)側のライブラリ(.a)に実体がある関数や機能を使った場合は、 コンパイルできても当然リンクが行えない状態。 bad_alloc みたいなライブラリものもそうだけれど、 virtual使ったり 例外を使った場合もそう。その他諸々。 C++らしい組み方をしてるとまずその手のものは使われてるだろうで... 足りてないリンク物の代用品をターゲット環境用にも用意できれば なんとかなるかもだが、大仕事だろう。(あるいはターゲット対応をllcに施すとか... どちらにしろ個人がチョロですむ作業ではなく）
I/Oを含まずtemplateを使ったような処理をベターCの範囲で書いてCに持ってくる、くらいなら...と思うも、やっぱ面倒だなあ.
あと、llc は c だけじゃなく c++ ソースも生成できる。
なんかすごい、というか、目が点になる、というか。
※と、まあ、発展途上のllvmを使っての感想なんで今後どうなっていくか、わからないけれど
他のC++ → C トランスレータついでのメモ。 元祖のC++実装の cfront は、Cソースへのトランスレータとして実装されている。 例外が実装されずに開発は終わっているが、 こちら でR3.0.3等いくつかのバージョンのソースが公開されている模様。 （使えるかどうかはしらない） 現行のC++をサポートしているだろうトランスレータとしては Comeau C/C++。 有料だけど低価格($50)。 面倒がって未購入だけど。 他環境向けのCソース生成ならこちらのほうがよい?(夢見てるかも)... といっても、ターゲット環境ごとの個別対応は必要だろうで、 Comeauのサイトで対応と書かれているのは比較的メジャーな環境のみのよう。
2010-3-15[月] watcom,dmcのテンプレート不具合open watcom 1.9rc1 が出ている模様. が c++ 関係はあまり進展していないのか、 1.8よりちょっとは増えたようだけれどまだ未実装のSTL関係は多そうで (stable_sortなかったり)、 クラステンプレートのメンバー関数テンプレートをクラス外に書くのも まだ未サポートのよう.
template<typename T>
class Bar {
public:
template<typename U> void test(T* t, U bgn, U end);
};
template<typename T>
template<typename U> // この行.
void Bar<T>::test(T* dst, U start, U last) {
while (start != last) *dst++ = *start++;
}
のBar<T>::testの２つ目のtemplateでシンタックスエラー.
template<typename T >
class Foo {
public:
template<typename U> void test(T* t, U bgn, U end) {
while (bgn != end) *t++ = *bgn++;
}
};
のようにクラス内に書くのはok. ついでに、上記は dmd(8.51) でもコンパイルエラー(startが未定義)になる。 こっちは、 テンプレートな引数の名前が Bar::test()宣言と定義で違うのが気に入らないらしい。 定義側の引数 start, last を bgn, end に修正すれば ok。 (テンプレートでない引数は名前が宣言と定義で違っても無問題) 別のコンパイラ(bcc 5.? だったか)でも、
template<typename CharT, class Traits>
class Foo {
のようにクラス定義してメンバー関数を外に
template<typename C, class T>
void Foo<C,T>::hoge(…) {
みたいにテンプレート引数名を変えていたら 某かの不具合がでた覚えがあり(名前を統一したらok) 汎用性を思うならば(古いコンパイラ気にするなら)、 クラステンプレートのメンバー(関数)は、 下手にクラス定義から分離せずに、内部に書いてしまうほうが 余計なバグに出会わずに済むのかも。 (分離する場合は名前を揃える... てか、ひょっとして普通揃えないとダメなのかな?) （ごちゃごちゃする定義はクラス外部に追い出して、 クラス宣言は身軽にしておこう、 なんて考えてたらドツボにハマることもあった、と）
2010-3-14[日] winの LLVM-Clang でコンパイル.
Clangで、なんとか、コンパイルできた。
(前日冒頭のつづき) コンパイル出来た llvm,Clang のソースは llvm rev.98447、clang rev.98448のもの(結構頻繁に更新されてるよう)で、vs2008sp1 にて release の ALL_BUILD して生成. まず、_WIN32等が設定されてたのは まさに Clangのソース内で設定されていた。 win環境なら _WIN32 定義してて、また、VC環境だと VCのinclude等のパス設定するような処理があった. (VCでコンパイルしたから呼ばれるのかVCがinstall済みだからよばれるのかは よくわかってないけど). でもってmingw関係も定義されてる雰囲気だった(mingwやgccを詐称してるよう).
VC関係は邪魔なので -nostdinc 指定してデフォルトのincludeパスを見に行かないようにし、
引数で llvm-gcc-4.2 の環境を流用して設定するようにした。
(別に llvmのでなく普通の(最近のバージョンの)mingwの環境でも大丈夫そう)
といった感じにコンパイル. ＋こまごま修正.
ヘマして何か設定が足りてないだけかもしれないが、まだ、ちょっと面倒な状況かも、で。 テストの実行結果は以下の通り。 (最適化オプションは-O2にしたけど妥当かどうかは未考慮)
他の結果はこっちみて...
追記: やっぱりマ抜けていた。--emit-llvm を指定しないとただのgccかも. --emit-llvm でllvmなコードを一旦はいてからx86向けを作る、みたい. (コンパイル手順はこっちに, 結果はこっちに追記)
で、clang も -emit-llvm 付で生成すれば同様にさらにオプティマイズできるよう。
2010-3-13[土] win標準と衝突するunix系コマンド.こちらでclangのvcでのコンパイルを紹介されてたので、やってみた。出来たコンパイラを使うとincludeでvc側の ヘッダ読み込まれてエラー。 _WIN32が定義されてるし、何か、しなきゃいけない (環境)設定が抜けてるんだろうなあ。 (includeしてないソースのコンパイルでexeやasmはつくれてた) で、そのとき、こちらの GnuWin32 をインストール. cygwinやmsys同様 unix系フォルダ構成を持つ状態のコマンドラインツール群で、 dllや言語ファイルがあるので単体コマンドを流用したい身には一長一短だけど、 コンパイラやスクリプト言語等は含まれていないので、ある意味、身軽で、 通常(常用)の環境変数PATHの最後にGnuWin32/binを追加して使うのでも よいように思えてきた。 unix系ツールと win(dos)標準コマンド名でいくつか衝突するけど、Windows/System32/*.exeとgnuwin32/bin/*.exeを比べると
ぐらいか。
当然他のパスも通るので衝突がありえるけど.
(コンパイラ関係だと link.exe とか)
※と書いたが、別に GnuWin32 でなくmsys でもほぼ同様かもだけど... (cygwinはともかく msys+mingw環境も特殊性があるのかどうか)
2010-3-12[金] ちょっと速度比較前回触った LLVM-gccやpcc,coins (で作ったプログラム)の速度が気になったので、 手持ちのCコンパイラ(vc意外はフリーのもの)で適当に実行速度を計ってみた。
(3/14修正: cygwinの計測が間違って別のmingwでの結果になってました). 試したコンパイラは全てwin環境用で
正直、オプションが、どの適度適切かは不明。
Watcomはつけすぎてるけど、基本はデフォルトに近い状態。 試したテストプログラムは
download:上記のソースのzip
たくさんやるのも面倒なので、これだけ（これだけでも結構しんどく）。 自分が大雑把に雰囲気をつかむため、なので、あまり適切でないサンプルかも。 1core 1threadな簡易な処理だけだし。 Dhrystone,Whetstoneは一応してみたけど、あまりピンときていない (処理内容わかってないからだろうけど).
実行環境は vista64(PhenomIIx4 3G)、通常のデスクトップでDOS窓とエディタ程度だが、サービスや常駐モノはある程度残った状態で実行.(テスト中の 1core がフル稼働で、あとの処理は他のcoreが大筋まかなってるだろうと期待. 以前別の計測にてsafemodeで起動して計測したほうが安定していた感じはあったけれど、酷すぎるほどの差もなかったので楽してる) 実行結果 は (3/14 一部計測し直し. cygwin計測ミス、安易インタプリタのclang対処反映)
たったこれだけだし、
測定(実行)環境はザルで実行毎の誤差からすれば
細かい数値みちゃうとまずいだろう。
特に浮動少数演算関係のオプション設定が適切でないだろうで
設定かえたら(Whetstoneとか)結果変わってきそうな気もする.
(c標準ライブラリも計測範囲で使われてるので
それの影響もどう据えるかにもよるし)。
が、おおざっぱに、vcが1番よさそうで次gcc系、
後は混戦で、ケツがTinyCCって感じか。 vc9sp1 64 の結果は CPUが64bit CPUなので、コンパイラの比較ってよりCPUの比較になるけど、 64ビットOS用にコンパイルするだけで、 結構違いがでる処理もある、という例になってるかも、で（代わり映えしない処理もあるけど）。
バイリニア拡大の結果は、
64ビット整数の利用頻度が少なかろうと
感想としては llvm(-gcc)は(いろいろミスして勘違いしまくりだったけれど)ものによっては非常に速くなったりでびっくりで早く使い易くなってほしく、 Clangはllvmをしなくても(?)これだけの性能あっていろいろ期待、 PCC は速度は思ってたよりはいいかも、だけど(Win版は)思ったより安定してなさそう、 PellesC はそんなもんだろう、 TinyCC は実行時速度じゃなくてコンパイル速度優先で(-benchなんてオプションがあるくらいだし)スクリプト言語的にCソースを扱うような方向があるようなので 実行時速度はこの程度の差ならokなんだろう、 COINSは悪くないのだけど期待しすぎてたため (ひょっとするとあまりx86系向きじゃないのかもだけど) ちょっと哀しい気分、てとこか。
※追記:cygwin-gcc、測定ミスでやりなおしたけど、gcc3.4の範囲なのでたいして値はかわってない（でもWhetstoneは結構ちがうか。浮動小数点はオプション設定しだいだろうでデフォルトがいい状態だったのかも)。 もともとcygwin使ったCOINSの結果と比較するのにmingwのでいいか微妙な気もして追加したものなので(ただの計算だけだとそう違わないだろうけど). あと最初の4つのテストで cygwin-gccとCOINSは win-apiでなくtime.hを用いて計測しているため若干条件が違う、とも. ※追記:安易インタプリタの結果は、clang対策での修正前にくらべ、どれも4,5秒短くなっている. isalphaやtoupperを手抜きなマクロに置き換えただけだが、結構ライブラリのオーバーヘッドがあったということか. テーブル参照より単純比較のほうが速いのかスレッド関係やロケール対策がらみなのかはしらないけれど。
※追記:
llvm-gcc のやり直しにおいて、Bilinear拡大は最適化されすぎて計算がなくなってしまったため、そうならないよう、若干ソースを修正(計測時間外での対処)した.
※追記:llvm-gcc 同様に clangも -emit-llvm で生成すると速くなる模様
(例えばbilinear拡大のは 100.9 に).
コンパイル不具合のメモ
（とかいたけど、coinsはちゃんと環境できていない可能性もあり）
2010-3-9[火] マイナーなCコンパイラをちょっと触るフリーでwin環境用exeが作れる、ちょっとマイナーな Cコンパイラをちょろっと触ってみた、というかインストールしてみた時のメモ. 試したのは LLVM-gcc, PCC, LCC, TinyCC, COINS。 （マイナーというと語弊のあるモノもあるけど win環境用のcコンパイラとしては、で）
LLVM-gcc(※追記:LLVM-gccでllvmを使う場合-emit-llvmオプションとつけないとダメだったよう) LLVM&clang は、 そのvmな仕組みとか、 オプティマイズ等の実力とか、 使用用途(appleの動向)とか、 GPL(v3)より緩いライセンスがらみとか、 いろいろ話題で今後の発展に期待大なコンパイラ(vm)、 だけど、 win環境で試すには、 mingw-msys 環境に追加する方法になっていて、 ちょっとまだ敷居が高い感じ。 また、残念ながら win 環境向けにはまだ clang バイナリは無いようなので、試せるのは gccフロントエンドのモノのみ。 (追記:clangのほうは自分でコンパイルすれば使える..ということでさらに敷居が高い) ただ llvm-gcc側にコンパイル環境として(mingw-gccをベースにした)必要なものは一通り入っているので、mingwコンパイラをインストールしておく必要はない（あってもかまわないけど）。
設定としては、まず msys 環境が必要。
mingw本家や
TDM等から適当なのをインストール。 LLVMのダウンロード頁から以下の２つを取得
ダウンロードしたファイルを適当な場所、たとえば msys込みで、パスを設定。 set "path=x:\llvm-2.6;x:\llvm-gcc-4.2\bin;c:\msys\bin;%path%;" あとは、llvmc 、または、llvm-gcc, llvm-g++ を用いて、 適当なソースをコンパイル、といった感じだろう。 (※簡単にヤッたら間違ってた。追記参照) mingw 環境のコンパイラだけ置き換えた状態のようなんで、 使い方は mingw(gcc)。 win-apiアプリの コンパイルもできるよう。 （簡単な窓を出すだけのhelloプログラムは動いた)。 速度等はろくに調べていないけれど、xorshiftのときのサンプルをコンパイルしてみたところ、inline展開が働いた時のスコアは結構よいほうだった。 ただ、inline 展開をあきらめるのがvcやg++4.4より早いようで、xorshift128あたり から関数呼出になってスコア落ちた。gcc3.4.5同様素直な感じなのかな、と。
追記: llvmとしてコンパイルするにはオプションが必要のよう. でもってコンパイラ環境がうまく設定されていないのか、一度にコンパイルできず.こちら等を参考にして
llvm-gcc -O2 -DNDEBUG --emit-llvm -S test.c llvm-as test.s llc test.s.bc llvm-gcc -o test.exe test.s.s や
llvm-gcc -DNDEBUG -O2 --emit-llvm -S test.c llvm-as -o tmp.bc test.s llvm-ld -o tmp.2.exe tmp.bc llc tmp.2.exe.bc llvm-gcc -o test.exe tmp.2.exe.s
て感じにしてみる(後者のほうが全体に対するオプティマイズが効くかも) ※ llc で -march=x86 を付けるとwin用でなくなるみたいでマズイのだった. ※追記 こっちでLLVM-Clangを使ってみた。
PCC(Portable C Compiler)かって(ANSI-C以前)の Cの標準だったろう Cコンパイラで、 最近はこちらでC99化していってるらしい。 （こちらもGPLv3の影響で脚光を浴びてるかんじ?）
もともと移植性のいいモノなためか、ちゃんとwin32版も用意されている。
こちら から、 pcc-20090818-win32.exe をダウンロード。実行してインストール。
とりあえず通常のプログラムフォルダ c:\Program Files
(win64なら c:\Program Files (x86)) にインストールしたとする.
コマンドプロンプト窓でコンパイラを使う場合は、 set "path=%ProgramFiles%\pcc\bin;%path%" を先に実行。この状態で pcc を用いてコンパイル。 pcc --help でヘルプ表示すると ld の分しか表示されず涙目だけど、 元はunix系のccそのものだろうから、そのあたりを見ればいいのか。 (基本部分はgccが同じにしてるはずだろうからgccのを試せばよいのかも) mingwベースなんで、winプログラムも同様。とりあえず窓helloは、 pcc w_p_smp1.c -l gdi32 でいけた。 なお、出来たexeは mingw 同様 msvcrt.dll に依存している。
PCC コンパイラのコンパイル
当初 win32バイナリの配布に気づかず、ソースにwin32用バッチがあったので
コンパイルしてみてた。
ので、そのメモも。
ソースについては、こちらから
pcc-cvs-100306.tgz、こちら から
pcc-libs-cvs-100306.tgz をダウンロード。
展開してできたフォルダを x:\pcc, x:\pcc-libs とする。
ソース修正は pcc/os/win32/config.h の31行目付近の #if !defined(vsnprintf) #include <stdio.h> //この一行を追加. #define vsnprintf _vsnprintf #endif をコメントのように#include <stdio.h> を追加するだけ。 (あとからstdio.hがincludeされるとvsnprintf置換でバグになるため) 面倒なのは bison や flex を使うのでそれらを用意する必要があること。 幸い猫研パックのmsys に入ってるので、msys環境を用いれば済みそう。
vc2008 でコンパイルする場合は call "%VS90COMNTOOLS%vsvars32.bat" をしておき(2005なら%VS80…,2003なら%VS71…だろう) x:/pcc/os/win32 へカレントディレクトリを移動し、 build /cl /pccsrcdir x:\pcc /pcclibssrcdir x:\pcc-libs を実行。うまくいけば pcc.exe (とmkext.exe) が出来ているハズ。
できたexeを試す場合は、配布バイナリをインストールした環境のpcc.exeと置き換えてみれば、で。
build /pcc /pccsrcdir x:\pcc /pcclibssrcdir x:\pcc-libs を実行. もし pccのインストールディレクトリを c:\program files\pcc 以外にしていた場合は、build オプションとして /pccdir c:\hoge\pcc のようにインストールしたpccフォルダを追加する必要がある。win64の場合 (x86)付なので指定が必要だろう(/pccdir "%ProgramFiles%" かな)。 LCCLCC は、こちら が大本。 コンパイラ作成の教材のような感じで、 配布されているものは、ソースのみでバイナリなし。 ただ、これをベースに使える環境にしたパッケージがいくつかあるようで といったものがある。
※ こちら にlcc対応のデバッガが公開されてる。 LCC-WIN32LCC-WIN32 は結構昔からあって、 昔試した時点で、IDE環境完備でデバッガ等の出来もよく、 言語仕様拡張や生成改善等もされていて で独自発展していたのだけれど、 今、サイトをみると頁はあるけれどコンパイラ等へのリンク等がことごとく切れてる。 一応、去年の秋はまだダウンロードできてたのだけど。 開発会社のトップページを みると権利関係が別の会社に移譲されたようなことが書いてあるようで... 現状フリー配布はなくなったってことなのかな（LCC-WIN32系のサイトをあたれば、FTPからのダウンロードがまだできるかもだけど、リンクしないでおく）。
Pelles CPellesC もLCC-WIN32同様に IDE完備の開発環境になっている。 IDE上でSJIS入力できたり、char文字列中に表やソで\含文字を使っても 実行で文字化けせず表示されてちょっと感動。 デバッガもそこそこいい感じ。ただwatchポイントは貼れず(LCC-WIN32は出来てた)。 プロジェクト設定は DEBUG/RELEASE切り替え等はできないようで、 プロジェクトのオプション設定でコンパイラ頁とリンカ頁のデバッグ設定をそのつど 切り替えないと駄目なよう(たぶん。でも、その程度)。
当然Winアプリ作れる。(ウィザードもあり)
コマンドプロンプトで使用するときは、まず、 set "PATH=%ProgramFiles%\PellesC\bin;%PATH%" を実行。cc を用いて cc hello.c といった感じ。win窓helloなら cc /Ze w_p_smp1.c user32.lib gdi32.lib で、とりあえず。
LCC コンパイラのコンパイル大本のLCCはソースしかないけれど、win32様のコンパイルバッチが入ってたので 試してみた... が、少々修正する必要があった。 のでそのメモ。 試したのは v4.2 のもの。tar.gz, tar.Z, zip の３つの圧縮ファイルがあるけれど、 基本同じものだけど、ソースの改行コードが違うかも。 winなら zip のモノを選ぶのが吉。
win向けにコンパイルするのには、makefile.nt を使う。 使用するコンパイラは vc. ただちょっと古いバージョン(vc6ぽい) 向けみたいでvc2008にはすでにないオプションが使われていたり。 makefile.nt の9行目付近からの CFLAGS=-DWIN32 -Zi -MLd -Fd$(BUILDDIR)^\ LD=cl -nologo LDFLAGS=-Zi -MLd -Fd$(BUILDDIR)^\ の部分を BUILDDIR=. CFLAGS=-Doutp=outP -DWIN32 -Zi -MT -Fd$(BUILDDIR)^\ LD=cl -nologo LDFLAGS=-Zi -MT -Fd$(BUILDDIR)^\
のように修正. あと、etc/win32.c の
win32.c を見ての通り、結構、環境をハードコーディングしているので、
本格的に使うならば、いろいろ修正したほうがよさげな雰囲気。
とりあえず、staticリンクライブラリが使えるエディションならコンパイル可能になったはず。 dllランタイム版でコンパイルする場合は、上記までの修正に対してさらに、
を施す。 で、vc2008を使ってコマンドプロンプトでコンパイル
call "%VS90COMNTOOLS%vsvars32.bat" を実行(2005なら%VS80…,2010なら%VS100…って感じか) 作業場所が x:\lcc42 フォルダだとして、そこに移動して
nmake -f makefile.nt clean nmake -f makefile.nt all を実行. 上手くいけばlcc.exe,cpp.exe等が作られてる(ハズ)。 お試しは
extern int printf(const char* fmt, ...);
int main(int argc, char* argv[]) {
printf("hello world\n");
return 0;
}
を hello.c としてセーブ. lcc hello.c
でコンパイル。
うまくいけば a.exe ができるので、a.exeを実行してhello worldが表示できたらokと。
なお、#include をせずに直接 extern でprintfを宣言してるのは、#include <stdio.h> をすると cpp.exe 実行中に帰ってこなくなったため... 追求するのは面倒なので、お試しとしては、これで終わりにしておく。
TinyCCTinyCC は小さいCコンパイラ。 (コンパイラ本体のc,hソース行数は3万行弱)。 けど、文法は、ほぼフルスペックのC89+α(C99の一部)。 (浮動小数点数も構造体もビットフィールドもあるし long long もある, らしい) とりあえず、サイトからwin用のバイナリを取得して、適当な フォルダに展開。とりあえず、c:\tcc にいれたとする。
set "PATH=c:\tcc;%path%"
でパスを通して、あとは tcc hello.c のようにしてコンパイルするだけ。
winアプリも出来るよう(examples/hello_win.c )
すごく、あっさり使えてしまう代物のよう。
TinyCC コンパイラのコンパイル
mingw-gcc を用いる。 x:\tcc-0.9.??\win32 フォルダに移動して、 build-tcc.bat を実行する。exeができたら吉。
COINSCOINS についてはリンク先の概要をみるなりして。 コンパイラ研究のインフラとしてのCコンパイラが配布されてるよう。 ライセンスはApache Licene Version 2.0。 モノは java で作られていて、また win環境では cygwin を使う ので、予め、それらがインストールされている必要がある。
javaに関しては、コンパイラをコンパイルするのでなければ jdk は必要でなく jre がインストールされていればよさそう。何かの折にjre6がインストール済みなのでそれを利用。
cygwin は gcc等の基本的な開発ツールがインストールされていればよく。
かなり昔にインストール済みなので、新規インストールについては他のサイトを適当にみてもらって。
と自分の環境はしばらく更新してなかったのでsetupで更新...
したら、どうも最新のcygwin環境だとCOINSはちょっと不具合がでるようで対処が必要になる.後述)
COINSコンパイラのインストールや使い方については、こちら やこちら やその他諸々を参考に...
ダウンロードはCOINSのダウンロード頁 から、
こちらのサイトの助言にしたがい 国際(en)版をダウンロード。
(jp版は euc が使われているためツールによっちゃwin環境では不味い場合があるらしい... なおjp版だけならSourceForgeの頁 からもダウンロードできる）。
ダウンロードしたファイルを(jarだけど)zipファイルとして適当なフォルダに解凍。
名前は coins_tc.bat として x:\coins\bin\ にセーブ。
set "PATH=x:\coins\bin;c:\cygwin\bin;%ProgramFiles%\java\jre6\bin;%PATH%"
hello.cとして以下を適当なフォルダに作成しておく.
#include <stdio.h>
int main() {
printf("Hello World!\n");
return 0;
}
先のバッチを使い coins_tc.bat -o hello.exe hello.c のようにコンパイル。出来た hello.exe を実行して、hello world が出力されたらok. cygwin ツールを cygwin 環境以外で使うため、パス関係の警告がいろいろ出るけど無視。 もし cygwin 環境で実行したいならば、この(上記path設定の)状態で bash --login -i
を実行。カレントがhomeに移動してるので、お試しフォルダへ再度移動。
その他
2010-2-13[土] unittestの作成メモD言語の unittest に触発されて、 C++用に真似たものを作ってみたことがある. 使い方はこんな感じ
// テスト例
#include "unittest.h"
class Foo { 略 };
UNITTEST(Foo_Test) {
Foo foo;
assert(foo.hoge() == 1);
略
}
// 起動ルーチン
#include "unittest.h"
int main() {
UNITTEST_RUN_ALL();
略
}
といった感じでヘッダファイル一つですむ. そのヘッダの中身は
#ifndef UNITTEST_H
#define UNITTEST_H
#include <cassert>
#ifndef UNITTEST_MAX
#define UNITTEST_MAX 256 ///< 登録できるテストの数
#endif
#ifndef USE_UNITTEST // テストしないとき.
#define UNITTEST_RUN_ALL()
#define UNITTEST(T) template<typename D> void uniTTesT_dmy##T()
#else // テストするとき.
#define UNITTEST_RUN_ALL() uNITtEST_Mgr<>::runAll()
#define UNITTEST(T) \
class T { \
public: T() {uNITtEST_Mgr<>::add(&test);} \
private: static void test(); \
}; \
static T uNITtEST_vAr_##T; \
void T::test()
template<int N=UNITTEST_MAX>
class uNITtEST_Mgr {
static unsigned tblNum_;
static void* tbl_[N]; //関数ポインタの配列だとvcが落ちたorz.
public:
static void add(void (*fnc)()) {
if (tblNum_ < N)
tbl_[tblNum_++] = (void*)fnc;
else
assert(0 && "too many UNITTEST.");
}
static void runAll() {
for (unsigned i = 0; i < tblNum_; i++)
((void (*)())tbl_[i])();
}
};
template<int N> unsigned uNITtEST_Mgr<N>::tblNum_=0;
template<int N> void* uNITtEST_Mgr<N>::tbl_[N];
#endif // USE_UNITTEST
#endif // UNITTEST_H
テストしないときは、
テストをするときは、 UNITST_TEST()マクロは、ファイルstaticのclass変数を定義にすることで main()実行前にコンストラクタが実行され、 そのコンストラクタ内でテスト関数へのポインタを UnitstMgr::add()で登録している. グローバル変数のコンストラクタの実行順番は不定なので、Mgrの管理する変数はそれらよりも先に初期化されている必要がありstatic変数にしている(ので登録可能なテスト数/配列サイズも固定) そして main()関数の開始時点で、uNITtEST_Mgrにテストがすべて 登録済みなので、UNITST_RUN_ALL ( UnitstMgr::runAll ) を実行すれば、テストが全て実行される.
わりと単純にすむ、というか、すませてる.
まあ、実際に使おうとすると、assertだけでなく、各種チェック用のマクロがそこそこほしくなるし、多少なりとはいえ、経過メッセージをだしたりエラー数カウントしたりしだすと、すぐ1桁以上大きくなってしまったけれど. [これ]
ただ色々付け加えた後に、ひさしぶりに元の(上記の)ソースみると、 蛇足だったかなあ、という気にもなる. ※そういや、グローバルのコンストラクタって処理順保証なしだから マルチスレッドでばらばらに実行される可能性ってあるのかな? (当然そうだと今のままでは破綻)
2010-2-5[金] Win環境でのSTLport 5.2.1のインストールのメモ.
前回の試しで、STLportの結果がよさげだったので VC以外のコンパイラでも試してみたくなり、とりあえず dmc 用を インストールしてみようとしたのだけどハマった。 VC用はググればインストール例あるし configure.bat --help やって、指示通りにすればできるようで一番お手軽だった模様.
まあ付属ドキュメント読まずに適当にやるでは不味かった.
読めば書いてた. でも英語なんで翻訳ソフトでちまちま...
悔しいので適当に気になるところだけ訳ぽくしてみた
(わからないところを雰囲気で適当にしてたりするので、ちゃんと元のを参照のこと)
ようは、mingw,dmc,bcc 用を作る場合は、Msys 環境が必要. またmsys版でなくMingw32版のgnu make が必要そう. →dmc,bccが目的でもmingw入れちまうが吉かも.
て感じか. 以下、作業メモ. ただし、あまりうまくいってません。
mingw,dmc,bcc共通といいつつ基本 dmc しか作業できてないので... configue実行だけど、MSys環境で configure --use-compiler-family=??? な感じで ??? に gcc, dmc, bcc を設定.('='も忘れずに、と). 必要に応じてその他オプションも併記して. configureやったあとに build/lib/ で mingw32-make -f ???.mak clean mingw32-make -f ???.mak depend mingw32-make -f ???.mak ターゲット名
のような感じでメイク. ターゲット名で install を指定すればallコンパイル＆libへのコピーだが、dmcではエラー. また、all は dll(shared)版しかコンパイルしないようなので、結局自分の必要なものを 指定するのが無難そう. (このへんコンパイラごとに事情が違う)
mingw32-make -f ???.mak release-static dbg-static stldbl-static
な感じに、必要なものを列挙してメイク(指定できるものはコンパイラごとに事情が違う).
ctype_facets_test.cpp 430 付近の'で囲まれた文字を'\xE7'に書き換え ておく(怒られたのは vc だっけ) build/test/unit/ に移って mingw32-make -f ???.mak で、STLport-5.2.1/bin/にテストプログラム生成、 できた exeを全て実行、出力でエラーがなければok ...なんだが、 エラーでてるかも. ロケール関係ぽいので、とりあえず、あきらめ.
dmc
dmcは、ビルドする前に、
dm/bin/ にある link.exe, lib.exe をコピーして
また、makefile の修正が若干必要かもで、
release-static : AR += -p256 のようにする. (256は適当にえらんだ. これでもおこられるならさらに大きくか) リンク時に文字化けした警告がでてるのが気になるが、libできてるようなんで 気にしないでおく. ただコンパイル途中で nbytes=65664, ph_maxsize = 65520 Internal error: ph 1854
なんてエラーがでるかもだが... 出たらあきらめ orz stldbg-shared のコンパイルでも出るかもだが、 dll版は興味ないので放置した (先に static 版のコンパイルをしてあると コンパイル通ったかもだが、それでいいのかで)
INCLUDE=c:\STLport-5.2.1\stlport;…元の文字列… LIB=c:\STLport-5.2.1\lib;…元の文字列…
みたいな感じに追記するのも手. あるいは、己は、元のと新規とを使いわけたいので 元のsc.iniでは行末に置かれていた %INCLUDE%と%LIB%を先頭にもってきて INCLUDE=%INCLUDE%;…その他の元の文字列… LIB=%LIB%;…その他の元の文字列… のようにして、コンパイラ環境設定のバッチで INCLUDE,LIBの設定を切り替えるようにしてみた.
mingwとりあえず上記でstatic版のみ作れた. dll版は、 リンクエラーがでたので放置. (使ったmingw環境の設定等があわなかったのか?) test/unitのはコンパイルできて実行できたと思う.
できたlibを使ってのテストは何もしていない状態.
bccbccの場合は bcc32.cfg と ilink32.cfg の -L に psdk のpath(???/lib/psdk とか)が 抜けていたらそれを追加. とりあえずdll版は作成できるけど、tlibで怒られてしまいstatic版は作れてない(未調査) でもって bcc v5.5.1 のせいかテストでコンパイルできず.. 面倒になったので挫折. (readme.bccもちゃんとみてないので)
その他のテキストインストールに関係ないけど、気になった文章の適当訳も. README.utf8, stlport_namespaces.txt,
Academic Free License ("AFL") v. 3.0 なファイル
makefile 弄ってたらふと、ファイル先頭に、ライセンスとして
Academic Free License 3.0 となっていて、検索すると、stlportヘッダフォルダでも
これは c++0xから増えるヘッダで、v5.2.1では、これ単体で, 他の部分では Boost 発祥の type_traits がincludeされているため、 このtype_traitsファイルさえ使わなければ、気にしなくていいのだけど... 最近の STLportの git リポジトリからとってきたものをみると、 他のソースもこの type_traits ファイルinclude するようになっていて 結構影響する状態のよう. 実質が今のライセンスと かわるのかどうか... Wikipedia や v2.0の和訳をみてると、 微妙に面倒くさそうに思える...(読解力無くて読み違えてるかも...)
2010-2-4[木] sprintf,string,stream のメモ．去年だか一昨年ぐらいから、もうそこそこパワーあるのだから、と、 ターゲット環境でc++で string 系を使ってたのだけど、 そのとき不精して、デバッグログでも使い始めたら やたら処理落ちする箇所の原因になってしまったことがある． ログといっても シリアル とか USB とか LAN とか経由しない、 数十KBのメモリに溜め込むだけの処理だったんで、 開発中は release コンパイルでも有効にしていて、 多少重くなるといってもI/Oからまないから大事ないと思って 見過ごしてしまっていたのだった． たしかに想定してた使用量を超えたルートができていたけれど、 それ以上に酷い重さに化けていた． もちろんログをとってることが問題ではなくて、 string系の文字列をつかって記述で楽して
dbgmsg = strFmt("%s (%d) :",fname,line) + msg + '(' + a + ")\n";
のような感じに + 等使って、テンポラリ変数発生、メモリーアロケート発生、 が山ほど起きていたのが敗因． (↑は今適当に書いたので実際のじゃない) 文字列専用にアロケータ用意してフラグメンテーション対策はほどこして いたけど、当然速度的にはよろしいもんじゃなく． わかってみればあたり前だけど、思い込んだら、でなかなか気づけなかった． そのときは、デバッグログからstring系一層してsprintf系で やりすごしたのだけど、 たとえば + でなく += を使えばテンポラリ無くなり アロケート頻度は落ちるし、 キャパシティをある程度コントロールしてアロケート発生させなければ、 書式なしの文字列連結ならsprintfより速くなる 可能性だってあるはず． 文字列連結を一個一個指定することになって記述が面倒だけど ... iostream系の << なんかはやってること的には += と似たようなものの はずなんだよね． などと思うと、stream関係って、実は速度的に 悪いもんじゃないかも、って気がしてきたのだった． て、ことで、例のごとく、ちょっと計測してみた．
test1:
sprintf(buf, "%s(%d) : test> %s", fname, line, msg);
sprintf だとこんな感じになる処理を、ポインタ操作+mem系, str系, std::string, stringstream, strstream, カスタムstream 等で書いて計測．
ということで、phenom2 3GHz環境で、vc9 と mingw g++4.4.0 での結果．
[A][B] は、test_sprintfに与える引数の文字列長の違い． 文字列長が違うと、差のありようもかわるので． (一例の結果だけみて、何倍の差があるとか早とちりしないように:)
やっぱり、ポインタ活用や、strcatを用いたものはそこそこ早く．
アロケートの(ほぼ?)発生しない stringの '+=' やstream系の<<も
まあ早く．
stringstream も、多少気になるかもだが(毎度ローカル変数生成のような)下手な 書き方さえしなければ、悪い速度じゃなさそう． (VCの stream 実装がいまいちぽいが) というか、そもそも printf 系の処理はそんな速いものでもなく...
test2 : 浮動小数点数を使ってみる
sprintf(buf, "%s(%d) : test (%7.5f,%7.5f)%c %s"
, fname, line, d1, d1, ch1, msg);
s_stringstream << fname << '(' << line << ") : test ("
<< d1 << ',' << d1 << ')' << ch1 << ' ' << msg;
double を使ってみた例．
↑で%7.5fにしてるのはstreamでのデフォルトに合わせるため． ソースはこれ で結果( 100000回の平均. 単位:μ秒 )
vc,mingwとも stringstreamがsprintfの倍くらいにばけてる．
test1の結果からすると、必要以上にオーバーヘッドがある気分．
で、STLport版、sprintfと大差なく... なんか速い． 細かいことはあとにして、とりあえず、次．
test3 : 幅指定等
sprintf(buf, "%-24s(%10d) : test %#016llx\n", fname, line, val);
s_stringstream << setw(24) << left << fname << right
<< '(' << setw(10) << line
<< ") : test "
<< setfill('0') << setw(16) << hex << showbase << val
<< '\n';
真打:-)
ソースはこれ で結果(100000回の平均. 単位:μ秒).
stream、記述のゴツさに、つい比例してしまいそうな印象をもってしまうが、 書式解析がコンパイル時の型チェックでまかなわれているため、 sprintfより速くなる、可能性がある ... vc標準は無視、したいなぁ:)
stringstreamは STLport が がんばっている、って、ことだろうけど．
test1改 : アロケート頻度.test1 において、お手軽な範囲で、無理やり、include関係での malloc や new を乗っ取って、使用数を計測してみた． (ソースこれ追加) ライブラリ.lib 部分になっているのは手がだせてないので、不正確すぎて、判断するには危険だが、大雑把な目安にはなるかも、で． といっても、ヘッダのみなんで、vcは値でたけど、mingwはひっかからず． 以下vcでの1回表示のときの、表示部分でのmalloc:freeの呼び出し数．
vc の string 処理は 16バイトまでならstring内にバッファがあるため、 文字列長でアロケート回数が変わる． stringstream の[A](初回)の値が多かったりfree数が合わないのは、 ライブラリ側の処理とか、あと、バッファ以外にも、 stream処理のサブクラス等の初回生成が含まれているためだろうか． 処理順の都合、stringstreamでアロケートされているけど、 CharAryStream, stringstreamの順に計測すると、CharAryStream側の 回数増えたりするので、可能なものは共通化されてるよう．
で、stringと CharAryStream のstatic変数版が 0回になっているので
アロケートを極力回避しようと思えばできる、って感じ．
stringstream は、static版でも アロケートが発生しているので、 vc版の測定結果が遅い原因だろう． 逆にいえば、g++や STLportのものは、メモリーアロケート発生させてない、 ということでよいか．
test1 追加 : WTL::CString, STLportのstd::string, の追試やっぱり STLportのstd::stringが気になったので、test1の追試． ついでに WTL::CString の結果も． (test1書き直し面倒なんで... vc9,mingwの測定値が若干違うのも面倒で) STLportは v5.2.1 (staticリンク), WTLは8.1のもの.
STLport std::string の '+' での結果がこれって、何だ? って感じだ． STLportはメモリー確保関係工夫してるようなことどっかに書いてあったと思うけど、 いいなあ.
static 変数版を試してないのは実装的にメリットないからだけど、
かわりに Format メンバーを使ったものを併記．
結、というか、雑感たったこれだけのお試しで結論するのも不味いという気もなくはないし、 使い慣れてない iostream系は何かぽかってないか不安もあるけど、 とりあえず．
iostream系は、それだけなら速度パフォーマンスのそう悪い仕組みでない、といったところか．
でも、実装は工夫が必要なんだろう． vcやg++のものが工夫が足りてない、というより、 STLport ががんばっているんだろうし． stream よりも string のほうが速度ペナルティが多くなりそうだ． += じゃなくて + で楽したいんだし． 少なくとも string 使ってる奴が速度パフォーマンスを理由に stream系にケチをつけちゃいけないだろう(自戒:) ただ stringstream は 無様に思えてきた．
strstream は完全に捨て去る必要ないよなあ、で．
vc標準の奴の性能があれなんで躊躇しちゃうけど、
速度を気にするならstrstream(かその代用品)使うのも手かも、と.
まあ速くないといっても、この程度の差で困ることは今時まず無いので 気にしないか． (printf系の使用を避けて速度アップを実感できたのは8bit,16bit機時代くらいか)．
今回の結果はまさに50歩100歩といったところだし．
デバッグ処理で極力メモリーアロケートなんて起きて欲しくないわけだし． もちろん、printf系だって全くメモリーアロケートしないかというと 実装しだいだし書式によってはありえるのだけれど． ただ通常極力しないように作られてるし、 デバッグで通常出す程度ならまず起きないし、で．
今回のソース関係のzip : [download]
2010-1-26[火] xorshift乱数のメモXorShift乱数は、こちらとかのように短い関数で紹介されるけれど、たいていシード固定で書かれていて、シードを外部から与えたい場合はどうしたら、と悩んでしまう. もちろん、ちょっとぐぐったらシード設定できるソース載せてるサイトあるし、 おおもとのpaper に all 0でなければよいようなことかいてあるようだけど、 どの程度適当でよいのか不安にもなる. で、今さらながら2chの擬似乱数2 をみたら76に解説&seed設定付ソースがあった. シードは極端な設定をすると不自然な部分列が出力されるからMTのを参考にしたとある. ありがたく、これ流用させていただくことに... と、よくよくみれば、ここの初期化とほぼ同じ(改良版)のよう. その他、検索したときのサイトメモ. mt-liteの実行速度に xorshiftを含む各種乱数の速度比較あり. 良い乱数・悪い乱数に XorShiftと他の乱数との速度比較とかSSE2使ったバージョンとかがある. 同サイトの こちらにもいろいろなコンパイラでの測定比較あり. xorshift.pdf 上記サイトで、"問題があると書かれている" とあったのでみた(翻訳ソフトでわからないなりに). 元のpaperより突っ込んだ性能テストをして、通過しないテストがいくつか(も)あるよう. （XorShiftは３つのシフト数の有効な値の組み合わせがいくつか(も)あるけれど、 組み合わせによって性能にばらつきがあるよう） あと改良版として256ビット版が載ってる. (周期のビット数だけでなく、計算でのシフト数も増やして精度をあげている)
XorShift乱数の速度擬似乱数2の 42 に 周期 32,64,96,128,160,192 ビット版のソースがあったので、 ちょっと速度比較してみた.
結果は以下. 環境は基本Phenom2 3GHz (玄箱HGは PowerPC 266MHz).
下３つは比較用. MT乱数(mt19937ar-cok.c)と 線形合同法を使った乱数とC標準ライブラリのrand()を使ったもの. コンパイラごとに癖はあるけれど、大筋は似た傾向.
paperの例では1.8GHzで4～6ナノ秒とあったので、
3GHzの環境(vcやg++)で 2～4ナノ秒は、そんなものかもしれない.
全体に周期32ビット版は他より遅くなっているのは、たぶん(アウトオブオーダーとかのレベルの)命令の並列化ができないためだろうか. 速度的には、 大筋ビット数が増えれば遅くなるけれど、32-192の範囲では 増える周期(質の改善)に比べ時間の増加はさほどでもないので、 どうせなら128でなく160や192あたりを使うのも手かもしれない. 256ビット版はプログラムが少々複雑になっているせいか 時間増加のよう. 128ビット版にくらべ2～3倍... MTと対して変わらない速度(場合によっては負ける)なので出番はないだろう.
でinline展開で速いのはいいけれど、
ビット数が大きいほど(ささやかとはいえ)コードサイズが膨れやすくなるので、
乱数の質が高くなくていいなら、ビット数少ないのを選ぶのもよいかもしれない. サイズきになるならinlineしない形に書いて160,192あたりを... もっとも、このソースの64,96,160(,192)は使ったパラメータがほんとにこれがいいのかわかっていないので 結局 128 を選んでおくのがベターな気はする.
あと、XorShiftの件とはずれるが、vcやg++でのcライブラリの rand()の速度が遅いのは、 マルチスレッド対応のオーバーヘッドのためだろうか. インライン展開された線形合同法の乱数の10倍前後なのは ペナルティが大きいとも、10数ナノ程度ならば大抵たいしたことないとも、どちらとも. 結局使用量/使用箇所しだい、だけれど、どっちにしろ精度のことを思えば、 とっとと XorShiftなりMTなり用意して用途別にインスタンスを管理したほうが、 楽になれると思う. (参考サイトにある SIMD版のSFMTとかが使える環境なら, そっちのほうがいいだろうな)
追記乱数の精度の評価についてはさっぱりなんですが (自分が使った処理において出目に不都合があるかどうかくらいなら、ともかく)、 同根のtest2をしたときの結果はあまりよいという感じではなかった.(この場合のテストとして適切かどうかもわかってないけど) まあ、たいていの場合の乱数の利用頻度や精度を思うと 普通は MT を選んどくのが無難だと思う.
この程度の速度差(時間差)やプログラムサイズ差が
ネックになるような利用頻度(仕様)やターゲット環境なんて
ゲームでもまずないだろうし.
2010-1-11[月] 安定ソートについてのメモ(sort test その5)しつこくソートネタ．遣り残してた、というか、自分としては本題だった 安定ソート についてのメモ. 安定ソートだと、ソート対象の値が、同じ値だったときに元の順番を維持した状態でソートできる． 安定ソート としては 挿入ソート、 マージソート、 ビン(バケット)ソート、 基数ソート 、 バブルソート 等がある. アルゴリズムとかの詳しいことは wikipediaとか、 このへんとか、 適当に検索するなりして調べて.
今回のテストルーチンは、
マージ、
基数、
quick
(y)、
その他のソート、
テスト本体 で一組.
本題以外のソートも混ざってて、ごちゃごちゃしてるけれど、 本命は、マージソートと基数ソート． マージソートは
基数ソートは
(分割した処理ごとに範囲チェックをしてるので、入力が0～255ですめば1回+αの処理ですみバケットソートに近くなる)
実行結果とりあえず、その実行結果としては、 【phenom2 945 vista64 vc2008:32bit】 【phenom2 945 vista64 mingw】 【vaio-c1 win2k vc2008】 【玄箱HG debian4 gcc4.1.2】
いくつか抜粋してみると、(単位はμ秒） phenom2 945(vista64)+vc2008(32bit)で int 配列をソートした場合．
phenom2 945(vista64)+vc2008(32bit)で double 配列をソートした場合．
玄箱HG(PowerPC 266MHz)+gcc4.1.2で、int配列をソートした場合．
表のstd::stable_sortはコンパイラ付属のstlライブラリを使った場合． たぶんマージソート(with挿入ソート)がベースだろうと思うけれど(追記:実際はも少しいろいろやってるよう)、 実装の違いからか、ちょっと差が現れている模様． (vcのには勝ってるけど、gccのには量が多いと負ける) quick ソートは安定ソートではないけれど、実行速度の比較のために並べている． (※実行ログでは、quick(+挿入) になっているモノ) 基本的にマージソートはクィックソートより遅くなるが、 基数ソートは条件が揃えばクィックソートよりも速くなりえる． だいたい説明サイトの説明にあるとおりの状況、かな． （どの程度の性能差があるかを見てみたかったので今回のテスト） ただ、基数ソートは仕組み上、ソート値のビット数が多い(値の範囲が広い)場合、処理が重くなるので、 int(4bytes)だと飛びぬけて早いのに、double(8bytes)だと微妙な差になっている． また、phenom2(3GHz 2次cache 512KBx4 3次 6MB)環境だと、 テストで使ったデータ数やデータサイズ・CPU(キャッシュ容量)が 基数ソートに有利に働いた面もあるようで、 クィックソートよりも十分早くなれるが、 玄箱HG(PowerPC 266MHz cache:16+16KB)の場合は 1024個,10000個では速そうだけど、 それ以上ではクイックソートのほうが速くなっていて、 基数ソートが必ずしも速いというわけでない模様．
基数ソートは、個数が少ないときは、処理のオーバーヘッドが大きすぎて割にあわない． もっともクィックソートにしろマージソートにしろ、数が少ないときは実質、挿入ソートになっているので、 実際に基数ソートを使う場合も一定数以下はマージソートを使う、のようにするだろう． ただ、他の実行環境(CPU)やソート対象のサイズ等により、効果的な境界値が大きくばらけるので、 汎用的な決めうちは、やりにくい．
基数ソートは条件揃えば倍速以上になるとはいえ、 手間を思うと、よほどのことがないかぎり、 安定ソートはマージソート、 非安定ソートでよければクィックソート、 でいいかな、というのが結論．というか、普通を再確認しただけとも．
upper_boundを用いた vector への insert先の結果のvector insertの行は、vector<Hoge> hoge_vec; でデータを保持しているとき、
hoge_vec.insert(std::upper_bound(hoge_vec.begin(),hoge_vec.end(), val), val); のような感じに安定ソート状態を維持したまま新規の値 val を挿入するもの． テストルーチンでは、他のソートと関数仕様あわせたため、(実使用からすれば) 余分なアロケート時間やコピー時間が混ざっていて、 他のソートと比較するのにはフェアな状態ではない． が、回数に対する時間の増え方からすれば、効率はあまりよくないだろう． これを用いるメリットは、
といったところか． 作業メモリについては、挿入ソートも作業メモリ不要なので、追加回数しだい... どちらにしても、量が多いときの速度ペナルティが大きいので、数があるときは メモリの折り合いつけてマージソートとかを使うほうがよいだろうけど．
しかし、余分に作業メモリ(外部メモリ)が必要になる、というのは、
場合(ターゲット環境)によっては面倒かもしれない． なので、最大数わかってる場合に固定の作業メモリを与えられるマージソート・ルーチンがほしい、というのが、今回のテストルーチン作成の理由のひとつ（実際に使う機会があるかは別として) あと、後述のSmpClassの例からすると登録順番も保持し比較対象にすることでクィックソート(std::sort)を用いるというのも、動的アロケート回避、という意味では有りな選択かもしれない.
※ 基数ソートで、符号無し整数として比較を行っているけど、他のソートは
型どおりに行っている．
Class/Structのソート
テストルーチンで、SmpClass を使ったものについて．
[1] SmpClass1 [2] SmpClass2 [3] SmpClass3
8バイトの構造体. SmpClass3へのポインタ 128バイトの構造体.
class { (4バイト) class {
float key_; ※比較はSmpClass3の float key_;
unsigned no_; ものを使う unsigned no_;
}; unsigned rsv_[30];
};
のようなデータのソートを行ってみる.
class {
float key_;
Hoge* pHoge_;
};
のようなソートキーと実体へのポインタの組み合わせ、を想定している．
また、quickソートにおいて、登録順も比較対象にすることで[1]と同様の安定ソートを実現するため
[4] SmpClass4
12バイトの構造体
class {
flaot key_; // 比較対象
unsigned no_; // 比較対象
unsigned rsv_[1]; // Hoge* pHoge;のようなのを想定.
};
も用意． 10000個の場合 (単位:μ秒)
100000個の場合 (単位:μ秒)
のような感じ． [1]の場合はソート対象のコピー量は増えるけれど比較コストは増えない. [2]のようにポインタだけの場合はコピー量は最小になるけれど メモリにあるポインタを経由して比較用のキーにアクセスするため 比較時間(コスト)が増加する. で、CPUキャッシュ等の都合から、今時の環境だと[1]のほうが有利なことが多そう.
なので、[1]のようにできるならば、そうしたほうが構造体等のソートは
速くなると思われる.
で、どうせ、ソート用のテーブルを作るならば、登録順番も控えることで クィックソートを使えるようにするのも一考. ソート対象が8バイトから12バイトに増えるが、 マージソートや基数ソートは 余分に外部メモリを必要とするので、 メモリ使用量的には同等か有利ということになる. (マージソートだと総数の半分、基数ソートだと総数分) 今回の例では、基数ソートに対しては全くだけれど、マージソートと比べるとよい結果となっている． もっとも[4]はIEEEなfloatの正数であることを前提にキーと登録順を合わせた64bit整数にして 比較を軽くしているので、このように出来ず比較コストが上がると、また違う結果になるだろう．
バケット(ビン)ソート
基数ソート以上に利用条件厳しいけれど、条件があえばバケット(ビン)ソートのほうが当然速い．
で、一応、用意してみた(これ)
基数ソートのようにgetkeyを与えられるようにすればいいのだけれど、 ただ、基数ソート・ルーチンは、 入力の値がすべて0～255までなら1回+αで処理打ち切ることになりビンソートに近い状態になるので (多少オーバーヘッドが多いけれど)、 その結果をみれば大体の雰囲気はつかめると思う．
ということで、乱数の値を0～255にして試した結果は、コレ．
抜粋すると、
のような感じ．場合によっちゃ、やっぱりバケットソート専用も意味あるかな．
その他諸々
当然、それなりに測定誤差がある.
前回以降にCPUを換装してしまい、今回分と前回分を単純に比較できなくなってしまったので、
テストでは、安定ソートだけでなく、前回試した他のソートもいくつか試している.
前回のテストでは、quick_sortのtemplate版が内部でイテレータのアドレス比較してて
実質、配列のソートにしか対応してなかった． で、オフセット値を用いて修正してみると、
Bidi版と大差なくなってしまった．
厳密にはBidi版のほうがまだ1変数多くなるので、比較処理によっては差がありえるけど、
これくらいなら利便のほう優先して、今回のテストのquickソートは前回のBidi版をベースにした．
前回の結論に基づき、quickソート内部の挿入ソートを Bidirectional Iterator を
受け付ける形でやねう版にしてみたはいいけど、性能出なかった．
よくよく考えれば、
やねう版挿入ソートは、無駄な代入を減らせる可能性が高まる代わりに、比較回数が1回増えてる．
比較処理がコピーよりも十分にコストが安いことが前提なわけで、
比較のコストが高くなる場合は当然不利だ．
ただ、元のソースは、ループで1回無駄に比較をしている状態でもあるので、その1回分の比較を
回避することで改善した...が、ソースが結構酷い状態に.
基数ソートルーチンは、実は dmc でコンパイルすると int 版の結果が不正になってしまっていた． こちらのバグかもしれないけれど、深く追求せず． 他にも玄箱でTYPE_SMPCLASS=4でコンパイルするといくつかのソートで実行結果が不正になるが、これも放置. このテストのクィックソート等再帰を用いた処理は当たり所が悪いとスタック溢れがあるよう. (乱数を0～255にしたら駄目なモノがあった... 個数減らして回避. 追記:下記に修正版) open watcom c++ (v1.8)の場合、std::stable_sort, std::upper_bound が未実装だった. 辻褄あわせして通したけれど、他にもテンプレートの特殊化ができなかったり、と、 まだ使うにはつらい感じ． 今回linux環境で使ったタイマーはwinに比べての精度がよくなさそう(4ミリ秒単位くらい?)． ただ、他のプロセスの時間を含まない値なので、そういう面では楽かも．
追記
実際のstl(stlport)のものをみると std::sortやstd::stable_sortはも少しいろいろ工夫してるよう.
(std::sortは、イントロソート等工夫してるらしく)
このテストのquick sort は、中間値のコピーをローカル変数にとるため値のサイズが大きいと再帰中のスタック消費がはげしくなってしまっていた.
2009-12-24[木] mg.exe LFN対応
今更ながら mg.exe を LFN対応してみた.(これ) が、msdos player はLFN未対応だったらしく..orz
vtdosのほうは、動いてくれた.
command.com は、PC DOS J7.0/V のCD発掘できたので、それを利用.
しかし、ドキュメントを読む分には素でも動きそうなのだが. ドキュメントやCOMSPECを見ると vtdcmd.exe というものを実行していそうだが、 配布物の中にそのexeファイルはなく. 仮想名かもと思うが、動かないとこみると、やっぱり必要なのかも? ...が、とりあえず command.com 入れて動いたのでよしとしておこう.
(追記)
といっても、ax=71a7h; int 21h (win32なファイル時間をdosファイル時間に変換するLFN用システムコール)を実行してみて、エラーがax=0x7100になるかどうかを
見てるだけ.
あっと、lfnのシステムコールは こちらを参考にしてます.
2009-12-20[日] 古PC復活メモ(遅延書込) 最近、古い5インチFDDや3.5インチMOをサルベージしたく バラしたままだった古PCを１台復活させたが、 この手のことはやってるときは楽しく、 つい他の古PCの復活もやってしまったのだった.
pen3 800MHz前後まずは、NetVista6842(pen3 866MHz i810E mem512MB hdd:120GB) とか NetVista6881(celeron 700MHz i810 256MB 80GB)とか Mate MA07H(pen3 800MHz 810 256MB 80GB)とか (昔中古で安いからと買いすぎた代物). NetVistaは家用サーバーで使っていたのを引退させたものだから、 いまさらそんなモノにするのもつまらなく、 デスクトップな linux ディストリビューションを 試すことにした. あと、PCI付のNetVistaにはPCIのRivaTNT(やG400)が残っていたので、 それをつけてみた. 結論から言えば、このスペック程度でデスクトップ利用するのに 一番いいOSは、やっぱり Win2K、だろうというのが実感.
最新のwin7(rcだけど)をNetVista6842 に入れたら、
linux等フリーosも、グラフィックアクセラレータ対応ドライバーの有無がネックだろうか.
nVidiaの古いチップは、オープン(あるいは解析済)というわけでは ない模様. メーカー製ドライバは古いxに対応のものは存在しているが、 最近のXorgには未対応のよう. このために古いディストリ入れるのも楽しくないので、 また810は多少はアクセラレーション効くのかAGPx2なのがPCIよりも有利に 働くのかマシな状況だったため、結局TNT(PCI) はお払い箱にした. ちなみに ATIのだと、数年前に情報オープンになってて最近 よくなってきているらしく、 Radeon9600gtをつけた別のマシンで試しに ubuntu(gnome) いれたときは、アクセラレーション有効になるとまずまずの感じだった （それでも検索するとメーカー製ドライバのほうがよいような記述も みかけたが、インストールの面倒を思うとフリー版でよいかと） と思っていたら こちらの記事からすると、 Kernel 2.6.33 あたりでnVidiaの古いチップ対応がマージされるらしい? ということはもう数ヶ月まてばマシになるのかもしれない. というか、Fedoraだと今、対応済みってことなのだろうか？ 気力ができたら試そう （debian系に慣れたため、他を弄る気が薄く...) ただ、グラフィックドライバーの問題を抜きにしても ubuntuは pen3 866MHz 512MB程度のスペックで使うには重かった. (不要なプロセスも多少殺したが、いまいち) メモリ256MBのほうに, debian+lxde や u-lite(ubuntu+lxde) を 入れたときは結構よく思えたので、 じゃあとgnome版を試したのだが、レベルが違った. あきらめたほうがよさそうだ. 日本語対応を思うと ubuntuは魅力的なんだが... u-liteになると結局日本語関係いまいちな感じになるので、ううむ. その他 ReactOSは、うまくインストールできず. 他にもLiveCDモノもいくつか..でpuppyは結構よい感じだった(後述). 日本語整備されたものをみちゃうと、堕落してしまう ただ結局のところ、512MBのPCはdebian入れてサーバー的にLAN接続、 他はpuppyとか入れっぱなしで放置という結果になった (放置分だれか引き取ってくれないかしらん)
puppy linux軽いといううわさの Puppy Linux も HDDにFULLモードで入れてみたが、たしかに軽いようだ. 先のlxdeな環境に比べても、頭一つ抜き出ている印象をうける. jwmというのも軽いのだろうが、全体で上手く調整されているのだろうな. (窓移動で中身表示せず枠だけってのは遅いマシンでは嬉しい. みっともない窓描画みせられるよりか、ずいぶん印象がよくなる)
なにより日本語対応が思いのほか行われていたのがうれしい.
ただ個人的には標準のファイラが好みでなかったのが痛かった. パッケージシステムも、 基本的に1CD起動、RAMディスク運営のシステムとして 調整されているものだから、 そもそもdebianやubuntuと比べるのはお門違いなのだが、 なまじまとまったシステムのせいか(まあ面倒だし）、 ソース落としてきてまでインストールという気にもなれず. RAMディスクベース用にロードモジュールを用意するのは、 os-9のロードモジュールを連想してある意味楽しいそうなんだが.
x,gtk+?ubuntu(9.10)の外観の設定、では視覚効果の指定で３つの状態が選べるが、 radeon9600gtを入れたPCで試していると、 効果無しを選ぶとアクセラレーションが効いていないようにみえる. 逆に通常効果(追加効果)を指定したほうがきびきび動いてるようだ (810だと通常効果を選べなかった). あとdebianで、ためしにmac4linを入れたのだが(窓まわりはそれらしくなったけどドック関係は失敗)、非常に激重になった. 使い物にならないのでアンインストールしたが、元どおりにならず、マシになったとはいえ描画が非常に重い状態. よくみると、窓に半透明影が残っている...非力でないPCでubuntu動かした ときはmac4linいれるまでもなく影付きなので、元々の機能でon/offできるのか? こちらをみてて
> gconftool-2 --type boolean --set /apps/metacity/general/compositing_manager FALSE でoffできた. offできると今度はインストール前よりも速いような?気も. (アクセラレーションがきいた? わからない) xとかgtk+,gnomeの設定がちゃんとしてあげられたら 非力なマシンでももっとよくなるのかな？ このへんのところ調べたほうがよいのだろうが...疲れた.
DynaBook GT475
msdos playerとかに触発されたこともあって、
調子乗って、十数年前の win95 なnote機 DynaBook GT475(486 75MHz 24MB)
も弄ってしまった.
linux等でコンソールのみだとしても、よほど古いディストリ等でないかぎり 辛いサイズに思う(一度入れたが日本語使えないのはやっぱり嫌で)
もちろん dos/v 入れる分にはそこそこ十分だ.
HDDは元の500MBのものから、余ってた30GBのモノに付け替えた. マシンのばらし方はこちらのサイトがまだあったのでありがたく. E-IDE と表示されてるので 8G までいけるとおもいきや BIOS的には 500MBまでなのか、GT475につなげて fdisk等すると 誤った容量が表示されそのまま作業すると不味い状態.
まあBIOS で大容量HDDをちゃんと認識できなくても、
起動したosがサポートしていれば通常で利用できることが多いので、
あらかじめ 別PC で freedosにて fdisk＆format
(念のため起動ドライブは8GB以内の4GBに設定)
してから GT475につなげたところ 4GB,24GB にアクセスはできて一安心.
折角だからとパーティションきってlinux等もいれようとしてみたけれど、 biosが想定外なのか grubやliloを使っても2つ目以降のパーティションからの起動が 無理のよう. ブートできないシリンダだとおこられる. 2つ目のパーティションが500MB以内にくるように 1つ目のパーティションを100MBにした状態でも駄目. なので複数インストールはあきらめて一つだけにした.
で、結局いれたのは、Win98...orz FreeDOS関係でなんとかしたい、と思ったが、 lfnのサポート具合のこともあるし、 ネット関係を思うと、 LANカードのドライバー等はなんとかなるにしても、 LAN内の他のPCとのやり取りの利便を考えれば 結局win機がベターなのだった. (ただwin95無印はfat32無しだしその他ドライバーが見つからず... win98で自動認識されてインストールというのが吉だった) また、せめてtelenet端末として、と思う場合も、 utf8が使えるdos/v用の端末ソフトがあるや否や、 で、移植や改造が頭によぎりバカらしくなり.
とりあえずwin98ならば teraterm 動作ということでok.
*まあ、使えないマシンを復活させるのは楽しくここ2週間ほどちまちま弄ってたけど、 ふと我に代えると非常にむなしいもので…… 次またやってしまう率を減らすためにメモといったところ. 思い返すと古PCは osお試しインストールすることこそが 目的なのかもしれないと思えてくるが... 最近は、 メモリもCPU速度もありisoイメージ直インストールできる メインマシン上の VirtualBox での作業するほうが吉だものな.
2009-12-18[金] 夢にみたソフトxp64で64ビットwinに移行して以来、自宅メインPCでは 16ビットdos用の exeが使えなくなっていて、 それもあって win7bisのxp付はちょっと魅力的だったりしたのですが. （いやイザとなればサブPCはw2kだし、virtualpcでwin9xという手もあるけれど)
最近ごそごそ別件で検索してたら なるMSDOSコンソールなエミュレータが２つも開発されていた模様. 双方公開されて日が浅く... というかwin7(64)で16bit exe使えず 不便だからと作られたもののよう. ハードのエミュレートじゃなく、dos(+α)部分のみで 入出力が仮想ドライブじゃなくて通常のドライブ(環境)のままで、 まさに、かって欲しかった(作れなかった)ソフトそのもの. MSDOS Playerのほうは msdos.exe hoge.exe files のように単発実行できるもの. lccコンパイラ使うためってことらしく他の32ビットツールとの連携もやすそう. VTDOSのほうはv-text環境込みのdos窓(shellコンソール)みたいなもののよう. v-text(dos/v)版のvzやfdも使えるらしい. こちらも16ビットexeだけでなく32ビットexeも呼び出せる模様. (それもあってか設定がちょっと面倒そう...己は上手くいってませんorz)
で、まあ、双方のサンプルに mg.exeって記述があって思わず笑ってしまったのでした。 (今でも触って下さってる方がいるなんてありがとうございますです)
ただ、喜んだのはいいのですが、すっかり16ビットdosツールとは 疎遠になってしまっていて、これを機に16ビットツール環境復活...したいけど,どこにバックアップしまったやら. （試すためにこのサイトの16bit-dosツールからmg.exe落としたりとちょっと間抜け）
で、折角だからfreedosからとってきたcommand.comと、こちらのos9/6809 L1 エミュレータ(v1.1)とを組み合わせて
C:\Users\myname\OS9>msdos command.com /c echo hello | os9l1 place \* world hello world world
て具合に msdos(8086) と OS-9/6809 の夢の競演をさせてみました.
2009-12-17[木] CPU換装→AMDLLD64青画面どうもPC組立やパーツ差替のたびにトラブルってるような... ソフマップの特価につられつい CPUを PhenomII945に換装したら、 vista起動ログイン直後に必ずブルースクリーンになってしまうのでした. (前回は9月頃MBのBIOS更新に失敗してMB交換. でもそもそも BIOS更新した理由はMBで不具合のでるGカードを買ったせい) いやsafeモードだと問題なく.メモリテストも問題なく. BIOSはちょっと古かったので更新かけたけど変わりなく. 青画面のメッセージには amdlld64.sys(AMD Low Level Device Driver) の中のアドレスが表示されていて、こいつが犯人ぽい. ググッたところ日本のサイトでは見つからなかったけれど、海外にちらほら. 初っ端に見つかる こち ら が正解のよう.
MBの種類は違うけれど、症状は同じ.
対処は、
AMDLLD64.SYSがなくていいのかは
わからないけれど、起動できないよりは、で
(?別のドライバに置き換わってるのかも?).
2009-12-15[火] ソートについて２
test1 補足
やねう版の結果がちょっと気になったので、手元ですぐ動くvc以外の
コンパイラでも試してみた。
プログラムのほうも時間計測の関数変えたり結果出力編集するの面倒だったので若干修正.
実行環境は athron64x2 5200+ 8GB(Vista64)環境.
(だいたい似たようなもんだけれど、それなりに誤差があるので雰囲気見るために)
さらに quick sort の一部として使った場合の結果は、微妙.
でもまあ、基本どんぐりの背比べ、だけどよくなるコンパイラもある、んだから、汎用的に書く場合は やねう版 でいいかも、と。 （下手な書き方してでっかい要素をそのままソートする場合にはやねう版のほうが有利な気もするし）
※ と結論にしたけれど、後のtest2～は test1補足を試す前に調査してたのでやねう版になってません
ついでに std::sort。 gccやwatcomだと他の結果がいまいちのことがあっても 付属stlのstd::sortは速いので、 基本的には付属のを使うのが吉のよう. vcのは若干、bccのは結構、遅いけれど... bccについては使ったのは数年前のもので最新じゃないし、 borlandのc++はその時々に付属するstl(の元)が変わったりするので… てみたらdinkumwareだった(VCと同じ元ネタ)...orz ※追記: std::sortの実装は単純なquick+挿入なだけじゃなくスタック溢れ対策?もあるよう.
※追記: vcのコンパイルオプションが不味く、スタック等のチェックルーチンが結構生成されていた. (関数分割や分岐が多いと不利だった模様). チェックを生成しない設定でコンパイルしたら、 結論がかわるほどの大きな違いはなかったけれど、 std::sort等ややねう版の結果も心持よくなったような気も.
test2 引数の数の違いの影響関数呼び出しオーバーヘッドが性能に影響する、状況だろうから、 じゃあ、2引数版(<専用) と 3引数版（比較ファンクタ指定） でどれくらいの差がでるか、と思い、試した.（引数の数というより、ループの最内側で使われる引数で渡された'比較'が、ちゃんインライン展開されているや否や） cでなくc++のテンプレートで実装. std::sortに引数をあわせている. また quick sort とかいているけど実際には挿入ソートを使ったバージョン. (以後単にquick sortと書いていても同様) vcでの結果(単位:μ秒)
他のコンパイラもだいたい同様の傾向.
引数が2個か3個かの違いは、(ちゃんとオプティマイズされてたら)気になるような
差は見受けられず.
てことで、実体つくるなら3引数版をつくってそれを呼び出す2引数版を作る、で よいのだろう.
test3 std::listのソート(追記: マージソート失念して間抜けなことしてます..orz)
std::list のソートのテスト. 比較のため、
してみた。
SmpClass版(mallocポインタやstd::vectorを持つ適当なクラス) (単位:μ秒)
std::string版
int版
基本的には SmpClass版の結果が、実使用に近いものだと思う.
で、みてのとおり、std::list でソートしたくなったら、
std::list のメンバーの sort() を使う
という当たり前の結論. intやdoubleのような小さい要素で少量のときは逆転してるけど、 そもそも個数がn個程度と限定されているならばlistでなくvectorあたりでよく. 無理に bidirectional iterator を受け取れる quick sort 作ってまで やることじゃない、と. あと、そのものstd::list自体のソートが必要なく、 途中の処理として整列された順番でデータ舐めたいだけならば、 ４つ目のように、 要素へのポインタを集めてそれをソートして使うのが吉かも.
test4 大きめのオブジェクトのソート、スマートポインタのソート
普通は、大きめのオブジェクトの実体を直接ソートしない。しないですむように作る。
もっとも、大きめのオブジェクトはポインタなりハンドルなりで扱い そのまま管理/やりとりすることはないだろうで、 c++だとスマートポインタの類による管理も増えている.
じゃあスマートポインタのソートはどう？ってことで、試した.
以下 SmpClass (mallocポインタ,std::vectorメンバー有り)の結果(単位μ秒) vc2008版(64バイト)
mingw32-gcc(4.4.0)版(56バイト)
上から順に.
shared_ptrはいろいろ便利だけれど、やっぱりその分実行時コストがかかってしまう。 それが気にならない箇所ならいいけれど、 ソートのような場合は考えたほうがよさそう. intrusive_ptrは、ポイント先になるクラス側に参照カウンタ処理が必要となり、 shared_ptrより使い勝手は落ちるけれど、 参照カウンタの処理自体は shared_ptr よりも素直な状態なので、 実行時コストは小さい. で intrusive_ptr のほうは、ソート済の生ポインタをも一度intrusive_ptrに することができる(もちろん、このへん、操作をあやまると参照カウンタ管理を 破綻しかねないので注意深く...)が、 shared_ptrは生ポインタ化してソートした結果を元のshared_ptrに戻す方法が なさそう. (shared_ptrの指す先でなくshared_ptr自体のアドレスでソートすればだが不本意)
追記:比較条件が単純でソートキーが値一つですむようならば、 ポインタのみの配列でなくソートキーとポインタのペアの配列を ソートしたほうが速くなりやすいと思われる(test5)
ソース＆実行ファイルとりあえず、今回のソース等を固めたもの.
2009-12-12[土] ソートはPGの基礎知識...昔(もう20年ほど前か)、os-9/6809を使っていたときアセンブラで dirコマンドを自作してソート機能をつけたことがある。 このとき最初 単純にかける(O(n^^2^^)系の)ソートで 実装していたのだけど、 公開してみたら、遅いからクィックソートにしてみたら、 と言われたのだった。 実際、差し替えたところ、 十数秒かかっていたのが3秒ぐらいになって、非常に驚いた覚えがある。 アセンブラでカリカリに書いてるから速いつもりだったんだよ。 でもそれ以上にアルゴリズムの性能が段違いにモノをいう、 ってのを身をもって教えられたのでした。 まあ、ものわかりの悪い奴なんで、 実際に経験しないと気づけないという... 本に速いと書かれているのみてても、その性能差を汲み取れてないのよね. その後、情報処理専門でない理系の大学のプログラムの授業で ソートを習ったりしたので、PGならソートくらいは知ってて当然の つもりだったのだけど... 数年前、作るものの仕様に整列をする部分があって、 やたら見積もり時間がおおかったり難色しめしたりする子がいて、 聞いてみるとソートを知らないという。 ゲーム専門学校とはいえプログラマ・コースだったから てっきり知っていると思ったら習ったことない、と。 初めてコレ聞いたときはかなりがっくりきた。 その後ゲ専出の何人か聞いた範囲ではほとんどが習ってなかった。 習っていた子もいたけれど、 バブルソートを自分で書いたことがある程度で、 でもって、ちゃっかりそのルーチンを仕事の実機で書いてくれて、 非常に残念な気分を味わえたのだった。(己と同じ過ちを...) これが酷いのか普通なのかはよくわからないけれど... ソートに関しては、 簡単だけれど性能の出ないルーチンを下手に作らせるよりも (PGは自分が書いたルーチンを使いたがるものだから)、 アルゴリズムの違いの性能差をとっとと見せ付けておくほうが、 そして、標準ライブラリにはそれらを使ったstd::sort(なりqsortなり)が あることを知ってもらっているほうが、いいだろうと思う.
ソート時間を測定してみる.ということで、かるくソート時間を計測してみとく. 実行環境は Athron64 X2 5600+ 8GB(Vista64) と Crusoe TM5400(600MHz) 256M(Win2k) なマシン. テストしてみたルーチンはコレ. 元ネタはwikipediaやその他検索ひっかかった所から.(面倒なんでクィックソートとか単純なまま) バブル,選択,挿入, コム, クィック, クィック+挿入(閾値32), std::sort, qsort の時間をチェック. (std::sortを呼ぶためC++でコンパイルしてるけれど他はCでの記述状態)
適当な個数のソートを何回か繰り返した平均を出している。 テスト環境は普段使っているPCのまま。 なるべく他のソフト立ち上げていないけれど、エディタやファイラは 多少残してたり常駐ソフトも残ってるしで、厳密さはなし。 時間計測も単純にC関数のclock()に任せてるので精度とかは微妙かもだし。 測定しなおすと、細かい数字は結構かわるし、たまに当たり所が悪いと余計に時間 食っていることもありそうだし。
それでも、大雑把な傾向は出てると思う.
Crusoe TM5400(600MHz) 256M(Win2k)環境でのint値のソート時間.(単位:μ秒)
Athron64X2 5200+(2.6GHz) 8GB(Vista64)環境でのint値のソート時間.(単位:μ秒)
上から３つが Ｏ(ｎ^^2^^)、次の２つがＯ(ｎlogｎ)。 10,20個程度だと、大差ない雰囲気があるけれど、 1000個とか10000個のソートになってくると Ｏ(ｎ^^2^^)ものとＯ(ｎlogｎ)モノとで1～3桁 時間が違ってきてる。 （当然それ以上だとさらに差は拡大するわけで） 数が少ないときは比較的似通っているといっても、 挿入ソートは目だって速く、 上記結果だと、TM5400では int 50個程度までなら、Athron64X2では int 100個程度 までなら、コムソートやクィックソートより速い結果になっている. (もちろんCPU等環境の違いで個数は大きく変わる)
で、クイックソートは、一定個数以下になったら挿入ソートに切り替えることが
可能で、それによって速度を上げることができる. std::sort()も実はだいたい同様でクィック＋挿入(少なくともvcのはだったはず.)。 若干遅い結果なのは汎用性等の書き方で多少オーバーヘッドがあるのか. この差が問題になるかどうかは、用途しだいだけど、 普段気にするようなレベルではないだろう. ※追記>std::sort()の実装は(普通?は) 再帰が深くなるとヒープソートに切替えるらしい. (イントロソートらしい?)
ただ、Cライブラリの qsortもアルゴリズム自体は同様と思われるが、 こちらはCプログラムでの汎用性のため (とくにintなんていう単純なデータのソートとしては) オーバーヘッドが大きくなってしまっている模様。 quick+挿入に対して、1桁違うことはないだろうが、 下手すると数倍の時間がかかったりして、結構大きい。 C言語の場合は、性能のためにあえてqsortを使わず、 自前で(コムやクィック)ソート・ルーチン用意するのは、 ありの選択. （が、性能と手間を思うと、C++環境にできるなら とっととC++に移行してしまうのが吉かも） ※クィックソートから挿入ソートへの切替個数は、 コンパイラ付属のものにあわせて 32個にしている。 アルゴリズムの本(20年位前にかかれたもの)をみると、 CPU性能やコンパイラ性能等でかわってくるが だいたい 10～20 位、って値が示されているのだが、 最近のCPUの性能がいいのかより大きい値のほうが速いようだった.
ついでに他のソート時間を測定してみる.ついでに、wikipediaのコムソートの説明にあったcomb sort 11 と、 数日前に流行?っていたやねうらお氏の挿入ソートも試してみた。 (ちょっとはしょりすぎて100～1000の精度がいまいち...) Crusoe TM5400(600MHz) 256M(Win2k)環境でのint値のソート時間.(単位:μ秒)
Athron64X2 5200+(2.6GHz) 8GB(Vista64)環境でのint値のソート時間.(単位:μ秒)
Athron64X2 5200+(2.6GHz) 8GB(Vista64)環境でのdouble値のソート時間.(単位:μ秒)
comb sort11については、個数が多いときには効果あるようだけど、逆に個数が 少ないときは増えた if 文のペナルティが出るのか、遅くなってしまっている。 その効果もささいな感じなので、無理に使う必要はなさそう. やねうらお氏の挿入ソートだけど、説明読んだときは効きそうに思ったのだけど、 結果は、よくなったり悪くなったり、で、ちょっと残念な結果でした。 いや、なんか、自分がポカやってる可能性は多いにあるのですが。 (TM5400の50個の列の値は、当たり所悪く他の処理時間が混ざったパターンぽく) やなう版は、最内側のループの外側とはいえ、外のループの内側に if文が増えているので、そのへんが影響して、 コンパイラの最適化やCPUのキャッシュ具合、分岐予測 等、 何かバランス的にくづれて、メモリー代入のペナルティと同等か それ以上のペナルティになってしまっているのかな？ 追記:こっちを書くまで気づいてなかったけど、 比較回数が1回増えてるので、コピーしないですました時間より 比較時間が増えるのが無視できないということかも. (元記事の前提と違う状態で使ってしまったとも)
その他
しらべていないけれど、 (己がかいた)クィック＋挿入は、一見性能よさそうにみえるけど、 個数がある数(以上?)だと、急激に時間がふえてしまったりしていた. ちょっと困った. あとソースをコンパイルしたexeや使ったバッチ等
2009-12-10[木] C標準ライブラリのマルチスレッド対応のメモグローバル変数や関数内部のstatic変数、あるいはそれらにアクセスする関数は、 複数のスレッドから同時に読み書きが行われると破綻する(バグになる). C標準ライブラリで(特にマルチスレッドセーフに作っていない場合)そのようなものは
等結構ある.(malloc関係はちょっと別枠だけど)
マルチスレッド対応の方法としては、たとえば元が
static unsigned long rand_seed = 1;
int rand(void) {
rand_seed = rand_seed * 1103515245L + 12345;
return (rand_seed >> 16) & 0x7fff;
}
て感じだとすると, 雰囲気として
struct ThreadLocalVar { // この構造体は適当
long rand_seed; // rand,srand
char* strtok_ptr; // strtok
char tmpnam_buf[_MAX_PATH]; // tmpnam
int errno_wk; // errno
:
(その他標準ライブラリが使う変数全部)
:
};
ThreadLocalVar* get_threadLocalVar() {
return 現在のスレッドのThreadLocalへのポインタを返す;
}
int rand(void) {
ThreadLocalVar* p = get_threadLocalVar();
p->rand_seed = p->rand_seed * 1103515245L + 12345;
return (p->rand_seed >> 16) & 0x7fff;
}
といった感じに、ライブラリが内部で使う変数すべてを収めた構造体を用意してスレッド別にそのメモリを持つ. スレッドごとに独立して処理するため、他スレッドの影響が起きないようになる.
当然、スレッドの開始時にはこの構造体の初期化が必要になる.
あと、上記では、適当にget_threadLocalVar()の名で中身はしょってるけど、
vcだと_getptd()、 ようは、スレッド別のメモリのポインタの取得は、 グローバル変数アクセスごとにmutex等で制御したりするのに比べれば まま軽いだろう(そこまで非効率な実装にはなってなかったよと).
ただ strtok のような本来十分に軽い処理からすれば
（そうであることを前提に利用頻度が高い場合）、
スレッド別のメモリのポインタの取得は気になるかもで、
可能なら使わずにすます形にしていったほうがよいだろう.
C++0xではスレッドローカル記憶域(TLS)が追加されるかもらしい.
そういやD言語ver2もサポートしてる. D2の場合は特に指定のないグローバル変数はスレッドローカルになる.
2009-12-9[水] ググれるようになった
自分のサイト/ページがググって出てくるのってやっぱ嬉しいな.
|