ホーム » スタッフ » 斉藤徹 » ワードアライメントとビットフィールド

2012年11月
« 10月   12月 »
 123
45678910
11121314151617
18192021222324
252627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

ワードアライメントとビットフィールド

先週の構造体の演習が1週2コマでは不足っぽいので、前半座学+後半演習とした。

ワードアライメント

struct FOO {
char a[ 6 ] ;
int  b ;   // sizeof( data ) は (6+4)*10=100byte?
} data[ 10 ] ; // 実際は、(6+2+4)*10=120byte。

このような構造体を作ったら、構造体1件あたりのメモリの使用量は何バイトであろうか? 6+4の10byteと思うかもしれないけど、32bitコンピュータなどであれば、12byte になるのが一般的。

これは、CPUとメモリのデータの速度を比べると、メモリの速度の方が遅い。 このため、CPUがメモリとデータのやり取りをする時は、1ワード(32bit)など まとめて読み書きをするのが一般的。

pack状態      隙間あり
+|0|1|2|3|   +|0|1|2|3|
00|a|a|a|a|  00|a|a|a|a|
04|a|a|b|b|  04|a|a|x|x| packされた状態では、
08|b|b|a|a|  08|b|b|b|b|  data[0].bは、6,7,8,9番地になる。
12|a|a|a|a|  12|a|a|a|a|  するとワード単位の読み出しでは、
16|b|b|b|b|  16|a|a|x|x|  04行と08行の2回に分けて読まれる。

構造体のchar a[6]とint bが隙間なく配置されると、ワード単位の読み書きでは メモリの読み出し回数が増えて、機械語の実行速度が遅くなる。 このため、構造体ではデータがワード単位の区切り(ワードアライメント) をまたがないように、データ間に隙間を入れるのが一般的。

ビットフィールド導入

struct Birthday {
int year ;
int month ;
int day ;
} ;

このような構造体を考えると、1件あたり4×3=12byteを要する。 しかし、年は西暦であれば2047までであれば、11bit で十分であり、 monthは0〜11までの4bitで十分。dayであれば1〜31の5bitで十分。 西暦を4095までの12bitとしても、21bitで1ワードに収まるデータであり、 最初の誕生日構造体はメモリ上無駄がある。

また、この誕生日データでは、年齢の比較をする際にyear,month,dayの比較を 要し、処理的にも煩雑となる。この様な時は、10進数の桁を使って、 以下の様なテクニックもよく使われる。

int ymd( int y , int m , int d ) {
return y * 10000 + m * 100 + d ; // 1999年7月14日は、19990714
}
int month_ymd( int ymd ) {
return (ymd / 100) % 100 ; // 19990714から7を取り出す
}

しかし、この方法では、合成や分解で100といった2進数的に切りの悪い、 乗除算計算の遅い組込系のCPUでは処理が遅くなる。 それに、月を0〜99までの数値として扱いメモリもちょっと無駄。 そこで2進数を使って、year=12bit,month=4bit,day=5bitで扱う方法であれば、 以下のようになるであろう。

int ymd( int y , int m , int d ) {
return (y << 9) | (m << 5) | d ;
}
int month_ymd( int ymd ) {    // YYYYYYYYYYYYMMMMDDDDDから
return (ymd >> 5) & 0xF ; //   MMMMを取り出す。
}