[techaday:0002] C言語での構造体とアライメントについて

[techaday:0002] C言語での構造体とアライメントについて

はじめに

「1日1技シリーズ」第2回は,構造体とアライメントについてです.
構造体は複数のデータをひとまとめにして扱えるため,みなさんも様々なプログラムで多用しているかと思います.
また,マイコンプログラミングではメモリが数kB〜数十kBと制約がシビアになるため,1bitで済むフラグや値が小さいことがわかっている変数を,構造体の拡張機能であるビットフィールドを使って複数固めて使用することがあります.
しかし,使い方によってはかえってメモリを食いつぶしてしまう場合があります.今回はそれと回避方法について書いていきます.
この手の話について大変詳しく知っているわけではないので誤りが含まれているかもしれません.その場合は躊躇なさらずご指摘ください.

前提知識

  • C言語の構造体・共用体が使える

効能

  • ビットフィールドや構造体を使うときに気をつけるようになる
  • どうしても使いたい時の容量節約方法が分かる

動機

マイクロマウスのプログラムを書いていて,方向を扱うフラグを以下のように宣言していました.

typedef union {
uint8_t half:4;
struct {
unsigned NORTH:1;
unsigned EAST:1;
unsigned SOUTH:1;
unsigned WEST:1;
} bits;
} Direction;

このようにすることで各方向へのビットアクセスと,4ビットまとめたビット列へのアクセスができて便利だからです.
これを配列にすると迷路データを管理することができるので嬉々として実装してみたところ,迷路データが予想以上にメモリを食ってしまい,迷路を解こうとしたのに開発が迷宮入りしてしまいました.
さて,この Direction のサイズはどうなっているのでしょうか?実際に見てみると,こちらのように4バイトになります.
当初の狙いとしては1バイトで収まってくれると考えていたのですが,そうではないようです.さて,これはなぜでしょうか?

アライメント

この現象の理由は,CPUが命令を実行する際の単位に変数を落としこむためのアライメント(バイトアライメント)処理にあります.
一般的な 32bit CPU の場合は,計算を行う単位は 32bit と 16bit と 8bit つまり 4,2,1バイト です.
変数の種類(アクセスする単位)と変数の開始アドレスの間には決まり(というかこう配置すると遠回りせずに計算できますという位置関係)があります.
その決まりに則ったお行儀の良い並びに整えるのがアライメントの役割です.
アライメントに関わる規則の多くはハードウェアの仕様によって規定されるので,これは皆さん大好きな処理系依存な振る舞いになります.

詳細は他の記事に譲るとして,この処理が理由で(中略)今回の場合構造体は4バイト(32bit)の倍数の大きさになります.

サイズ増加の回避方法

上記の構造を崩さずに実装をしてしまいたかったため,仕方なく GCC 拡張の packed アトリビュートをつけることによって,通常のアライメントルールではない規則でパックすることにしました.
Common Type Attributes - Using the GNU Compiler Collection (GCC)

This attribute, attached to struct or union type definition, specifies that each member (other than zero-width bit-fields) of the structure or union is placed to minimize the memory required. When attached to an enum definition, it indicates that the smallest integral type should be used.

要するに structunion のメモリ上のサイズを最小化するようにメンバ変数を配置するということです.
つまり,メンバの順序を変えることでサイズを縮めることができる場合は,中身の順番が変わっても文句は言えません(たぶん).

変更後のコードはこのようになります.

typedef union __attribute__ ((__packed__)) {
uint8_t half:4;
struct __attribute__ ((__packed__)) {
unsigned NORTH:1;
unsigned EAST:1;
unsigned SOUTH:1;
unsigned WEST:1;
} bits;
} Direction;

こうすることで,Direction のサイズは1バイトになりました(ideone).
私はこれを1000個ほど配列にしていたので,データがかなり膨れていたわけですね.そりゃ変に見えるわけです.

この方法はデータのサイズを圧縮できる代わりに詰め方がぐちゃぐちゃになるので,計算のために前処理と後処理が必要になり,パフォーマンスは落ちます.

まとめ

  • アライメントには気をつけましょう

参考

補足

  • ところで,アライメントを取得するには sizeof は厳密には使えません.GCCなら __alignof__ 演算子を使うみたいです.