技術系備忘録​/C++​/最適化小手先テクニック​/ビットフィールドを活用すべし(メモリ節約編) のソース :: シンクリッジ

• 差分^[1] を表示
• 技術系備忘録/C++/最適化小手先テクニック/ビットフィールドを活用すべし(メモリ節約編)^[2] へ行く。

例えば、文庫本を管理するソフトウェアを作るとします。
各文庫本にはジャンル情報があり、ジャンルは複数個持つことが可能とします。

何も考えずに組むと List1 のようなクラスになると思います。

-List1
#prettify{{
class CBook // 文庫本クラス
{
public:
	string  m_sTitle;		// タイトル
							// ジャンルフラグ
	int m_nGenreScienceFiction;	// SF (true or false)
	int m_nGenreLoveStory;		// 恋愛 (true or false)
	int m_nGenreMystery;		// ミステリー (true or false)
	int m_nGenreHorror;			// ホラー (true or false)
	int m_nGenreComedy;			// コメディ (true or false)
	int m_nGenreShort;			// 短編 (true or false )
};
}}

/*
Windowsプログラムでは"int"を使わずに"BOOL"と書くことがあると思いますが、
"BOOL"は"int"の別名と定義されてますので、ここでは同じ意味と思って下さい。
*/
ここでは、タイトル(m_sTitle)は置いといて、ジャンル情報に着目します。

ジャンル情報を見ると、各項目はフラグ(true or false)として使用するのですが、型はintを使っています。
それが６種類あるので、使用するメモリは、4Byte×6で24Byteです。
文庫本が数冊であれば問題ない量ですが、数十万冊などもあり得えることを考慮すると、なるべく無駄遣いは避けたいとこです。
少し工夫して、int ではなく bool を使うようにしたものが List2 です。 

-List2
#prettify{{
class CBook	// 文庫本クラス
{
public:
	string  m_sTitle;			// タイトル
								// ジャンルフラグ
	bool	m_bGenreScienceFiction;	// SF (true or false)
	bool	m_bGenreLoveStory;		// 恋愛 (true or false)
	bool	m_bGenreMystery;		// ミステリー (true or false)
	bool	m_bGenreHorror;			// ホラー (true or false)
	bool	m_bGenreComedy;			// コメディ (true or false)
	bool	m_bGenreShort;			// 短編 (true or false)
};
}}

こうすることで、24Byteだったのが 6Byte に収まりました。(boolは1byteとしています）
これで十分かもしれませんが、もっと節約したい場合もあると思います。
ビットフィールドを使うと以下のようになります。 

-List3
#prettify{{
class CBook // 文庫本クラス
{
public:
	string  m_sTitle;			// タイトル
	union{						// ジャンルフラグ
		struct{
			char	bScienceFiction	: 1;	// SF (true or false)
			char	bLoveStory		: 1;	// 恋愛 (true or false)
			char	bMystery		: 1;	// ミステリー (true or false)
			char	bHorror			: 1;	// ホラー (true or false)
			char	bComedy			: 1;	// コメディ (true or false)
			char	bShort			: 1;	// 短編 (true or false)
		};
		char	All;
	}m_Genre;
};
}}

こうするとジャンル情報は1byteで収まります。
さらに、例では6ジャンルしか定義してませんが、8ジャンルまでなら1byteで済みます。

以上、ビットフィールドの活用方法としては一番単純な例ですが、メモリ節約の面からの効果が期待出来ます。


なお、C(C++)言語の通説として、「コンピュータにとってはintが一番扱いやすく処理も軽い」とありますが、これはCPUの内部処理のことです。この例で int を使うことで軽くなるのは、ビット処理がint処理で済むその瞬間のみです。
実際の運用では、この場合はCBookを構築、比較、コピーなどの処理を考慮すると、少ないメモリ処理量で済ませられる効果が大きいと思います。
特に昨今のコンピュータは、メモリはCPUより遅いクロックで動作しており、メモリアクセスを少なくすること（=メモリを節約すること）が、CPUの待ち時間を減らし、キャッシュヒット率を上げることに貢献します（と聞いています）。

/*
余談ですが、Pentium3とかが出始めた頃、ちょっと時間のかかる計算式を、リアルタイムに計算するのではなく、計算結果を予めメモリに用意しておき、テーブル参照だけで答えが出るような処理にしたら逆に遅くなってしまったことがあり、メモリ参照というのは思った以上に重い処理になりつつあるというのを実感しました。
*/

ちなみに、ビットフィールドを使用しないで同じことをやる例として、List4 のようなものがあります。 

-list4
#prettify{{
#define SCIENCEFICTION	0x1		// SF
#define LOVESTORY		0x2		// 恋愛
#define MYSTERY			0x4		// ミステリー
#define HORROR			0x8		// ホラー
#define COMEDY			0x10	// コメディ
#define SHORT			0x20	// 短編 

class CBook // 文庫本クラス
{
public:
	string  m_sTitle;		// タイトル
	char	m_cGenre;		// ジャンルフラグ
};
}}

このような記述は古いソフトウェアで良く見かけます。
数値型変数のビット管理をプログラマが自分で行うやり方です。

自分の場合（この例では）ビットフィールドを使うと思いますが、最適化の観点からみると、この記述で非効率となる要因は特に思いつきません。
逆に、コンパイラ任せにしないという意味から言えば、効率的な記述と言えるのかもしれません。



なお、ビットフィールドは 1BIT 単位でしか使えないものではありません。

例えば、CBook クラスに、本のサイズという項目を設けた場合は List5 のように記述出来ます。
-List5
#prettify{{
class CBook // 文庫本クラス
{
public:
	string  m_sTitle;				// タイトル
	union{							// フラグ
		struct{
			// ジャンルフラグ
			char	bScienceFiction	: 1;	// SF (true or false)
			char	bLoveStory		: 1;	// 恋愛 (true or false)
			char	bMystery		: 1;	// ミステリー (true or false)
			char	bHorror			: 1;	// ホラー (true or false)
			char	bComedy			: 1;	// コメディ (true or false)
			char	bShort			: 1;	// 短編 (true or false)
			// 本のサイズ
			char	nSize			: 2;	// 0=A3以上 1=A4 2=A5 3=A6
		};
		char	All;
	}m_Property;
};
}}

このように、記述することが可能です。
面倒なビット演算はコンパイラが面倒みてくれますので、nSize は普通の変数のように扱えます。

-
#prettify{{
if( m_Book.m_Property.nSize == 2 ){   // A5サイズなら
}}

みたいな記述も可能です。
（ただ、内部的にはビット演算処理を行うコードが出力されてますので、処理速度について注意が必要です。）
こうなると List4 にある #define を使って自前で処理をコーディングすることはかなり面倒になりますので、ビットフィールドのメリットが現れてきます。


以上、今回のネタはメモリ節約という最適化の一つのネタとして挙げてみました。
ただ、メモリ節約と処理速度との関係は難しく、メモリ節約することで動作が遅くなることもあれば早くなることもあり得ますので、一概にこうしたほうが良いとは言えません。
クラスの実装の際、そのクラスの使われ方を考慮しコーディングする必要があると思います。

• 技術系備忘録/C++/最適化小手先テクニック/ビットフィールドを活用すべし(メモリ節約編) のバックアップソース(No. All)
  • 現: 2016-04-01 (金) 13:36:22 takatsuka^[3]