2010-04-25-01-昨日の続き - project-enigma

2010-04-25-01-昨日の続き

>> Site top >> weblog >> 月別アーカイブ >> 2010年04月のlog >> 2010-04-25-01-昨日の続き

最終更新日付:2014/01/02 00:00:00


昨日の続き

2010 年 04 月 25 日

さて、本題に入るとしよう。テンプレートを使用したメタプログラミングでエンディアンを操作するやつだ。

使い方から先に書くと、以下のような感じになる。

int n = LittleEndian::ConvertTo<BigEndian>( 0x12345678 );

このことからわかるのは、クラス LittleEndian にクラススコープのメンバ関数テンプレートがあり、テンプレート引数に BigEndian を渡してエンディアン変換をしているということだ。実際には、LittleEndian および BigEndian は typedef であり、以下のように定義されている。

typedef Endian<__LITTLE_ENDIAN> LittleEndian;
typedef Endian<__BIG_ENDIAN>    BigEndian;

つまり、Endian というクラステンプレートがあり、その内部にメンバ関数テンプレートとして ConvertTo() があるわけだ。で、この __LITTLE_ENDIAN と __BIG_ENDIAN とはなにか。これは、endian.h にある数値で、バイトオーダーを表現している。

#define __BIG_ENDIAN    4321
#define __LITTLE_ENDIAN 1234

ちなみに、endian.h ではマシンのバイトオーダーを __BYTE_ORDER として定義しているので、以下の定義によりマシンのエンディアンを取得できる。

typedef Endian<__BYTE_ORDER> MachineEndian;

ここまでで、Endian クラステンプレートの定義が見えてくる。以下のような感じだ。

template<int BYTEORDER>
struct Endian {
    static const int byte_order = BYTEORDER;
    template<typename ENDIAN>
    static inline int ConvertTo( int n );
};

static const int byte_order がここでのキモだ。これをコンパイラが定数として扱うことで、コンパイル時点でできる計算をかなり増やすことができる。

ここで少し脱線すると、こいつは little endian と big endian だけでなく、他のバイトオーダーも扱うことができる。例えば以下のように。

typedef Endian<3412> PDPEndian;

で、問題はメンバ関数テンプレートである ConvertTo の実装だ。これは、以下のようになる。

template<int BYTEORDER>
template<typename ENDIAN>
inline int Endian<BYTEORDER>::ConvertTo( int n ) {
    return __ConvertEndian( n, Endian<BYTEORDER>(), ENDIAN() );
};

これは、変換元と変換先の Endian クラスをタグディスパッチに使うことで、__ConvertEndian() の関数オーバーロードを使用して処理を振り分けている。このオーバーロードによって LittleEndian、BigEndian、それ以外の相互変換を個別に実装しているのだ。最初はメンバ関数テンプレート ConvertTo() 自体を特殊化しまくって対処しようと考えていたのだが、いかんせんメンバ関数自体のパラメータは int だけなので断念したような次第。

例えば、little to big の変換では、以下のような __ConvertEndian() になる。これは一番素直な変換だ。

inline int __ConvertEndian( int val, LittleEndian, BigEndian ) {
  return ( ( val & 0xFF000000 ) >> 24 ) |
         ( ( val & 0x00FF0000 ) >>  8 ) |
         ( ( val & 0x0000FF00 ) <<  8 ) |
         ( ( val & 0x000000FF ) << 24 );
};

ちなみに、変換元と変換先のバイトオーダーが等しい場合、なにもしないようにオーバーロードされている。だから例えば、MachineEndian が LittleEndian に等しいことに気付いていなくても、以下のコールは安全だ。

int n = MachineEndian::ConvertTo<LittleEndian>( 0x12345678 );

そして、もうひとつだけ例をあげておこう。little endian から little でも big でもないエンディアンに変換する場合のオーバーロードだ。

template<typename TO>
inline int __ConvertEndian( int val, LittleEndian, TO ) {
    union { int val; char ch[4]; } wk;
    wk.ch[3] = ((char*)&val)[( TO::byte_order      %10)-1];
    wk.ch[2] = ((char*)&val)[((TO::byte_order/  10)%10)-1];
    wk.ch[1] = ((char*)&val)[((TO::byte_order/ 100)%10)-1];
    wk.ch[0] = ((char*)&val)[((TO::byte_order/1000)%10)-1];
    return wk.val;
};

なんだか複雑そうに見えるが、重要なのは変換対象である val 以外は全て定数ということだ。つまり、これは計算のほとんどをコンパイル時点でやってしまえる。昨日試した限りでは、配列解釈による転置よりもビットシフトで実装する方が速いが、このような変換でも同じように実装することが可能だろう。

ひとまずこんなところだが、冷静に考えるとまだまだ改善の余地があるような気がしてくる。全てをビットシフトでなんとかでき、計算の多くをコンパイル時点にやってしまえるなら、ConvertTo からタグディスパッチを使って __ConvertEndian のたくさんのオーバーロードの中から処理を選ぶ必要などないのかもしれない。そこのところを上手く書くことができれば、同じ効率でも実装はもっと短くなる。

 

コメント

いなあも - 04/25/2010 09:25:46 PM

凄いですね。

たった1日で色々なアイデアが…!!

昨日の速度計測結果は非常に興味深い内容でした。

僕が話した「メモリアクセスよりもレジスタアクセスが高速」と言う話は、僕がアセンブラを使っていた20年くらい前の話でしたが、今でも変わらないんでしょうね。

アセンブラの場合、変数も定数も全てメモリに展開されますが、ここで言う「メモリアクセス」は変数(Cで言うところのポインタ変数)と考えて結構です。

例えばアセンブラの定数は実行コードの中に埋め込まれるのでCPUはコードをフェッチするだけで値を読み込むことが出来ますが、変数はフェッチして得られるのは格納先のアドレスなので、CPUはそこで格納先のデータを読み込みに行かねばなりません。

つまり、CPU的にはアドレスバスをコードのフェッチ先からデータ格納先に切り替えが発生します。ここに遅延が発生します。

最近はCPUもパイプラインを使ったベクトル処理が主流ですから、このような遅延は隠蔽されるのかなと思ったのですが、そうでもないみたいですね。

kagelow - 04/25/2010 09:42:03 PM

> いなあもさん

「メモリアクセスよりもレジスタアクセスが高速」というのは、頭では分かっているのですが、コードを見てもどの部分がレジスタアクセスで済むのか、がわからないのが難点です。おそらく、C/C++ の世界ではコンパイラ任せでしょうからアセンブリリストを見る必要があるのでしょうが、それが読めないので個人的にはお手上げ。

単純に考えて、使用する変数が少ないほどそれがレジスタ上で使用される、という可能性は高いですよね。あとは register 指定子でできるだけ可能性を上げてやるくらいしかC/C++ のレベルでできることは無いのかな? あとは実測してみるのが一番ということでしょうかね。アセンブラを勉強しようという気持ちになれれば話は別なんですが...

いなあも - 04/26/2010 02:06:59 AM

コンパイラによって細かい仕様は変わるでしょうが、基本は変数を使えば全てメモリアクセスになると思って良いと思います。

陰郎さんが今回試行錯誤したように全て定数で済ませるのが高速になるのは、命令フェッチ以外のメモリアクセスが発生しない(=レジスタアクセス)と考えて間違いないんじゃないかな?

いや偉そうに断言してしまいましたが、本当はコンパイラの味付け次第なんですけどね。

sinray - 04/29/2010 09:47:44 PM

HP、Palmを12億ドルで買収

http://japan.cnet.com/news/biz/story/0,2000056020,20412889,00.htm

びっくりしました。

このページにコメントする

 

このページのタグ

Page tag : 開発

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.