memsetの拡張

C言語の標準ライブラリには、memsetという関数があり、配列のを全てのバイトを同じデータで埋める操作ができる。
gccでは以下のようになっている。

void *memset(void *s, int c, size_t n);
 
s で示されるメモリ領域の先頭から n バイトを c で埋める。
例えば、memset(s,0,n);とすることで配列sの先頭nバイトを0で初期化できる。
しかし、この関数では、複数バイト型の変数を1で初期化することはできない。
memset(s,1,n);では例えば4バイトなら0x01010101になってしまう。
そこで、memsetを多バイトに拡張した関数を作ってみた。

仕様

どんな場合でも使えるように以下のような仕様を満たすように関数を作る。
void *memsetex(void *dst, void *src, size_t nmemb, size_t size);
 
dst で示されるメモリ領域の先頭から size * nmemb バイトを src の示すデータ(大きさは nmemb バイト)で埋める。
※src の示すデータが nmemb バイト未満であった場合の動作は未定義
※dst で示されるメモリ領域のサイズが size * nmemb バイト未満であった場合の動作は未定義
※dst と src の領域が重なっていた場合の動作は未定義

ナイーブな実装(その1)

void *memsetex(void *dst, void *src, size_t nmemb, size_t size)
{
	int i,j;
	char *dstpt = (char*)dst;
	for(i = 0; i < size; i++)
	{
		char *srcpt = (char*)src;
		for(j = 0; j < nmemb; j++)
		{
			*dstpt++ = *srcpt++;
		}
	}
	return dst;
}
 
void * 型を char * 型にキャストして1バイトずつコピー。後で述べるが別に char * 型にキャストしなくても1バイトずつコピーできる。

ナイーブな実装(その2)

C言語の標準ライブラリの memcpy はたいがい爆速で動くようになっているので、 memcpy を使うように変更。
void *memsetex(void *dst, void *data, size_t nmemb, size_t size)
{
	int i;
	for(i = 0; i < size; i++)
	{
		memcpy(dst+i*nmemb, data, nmemb);
	}
	return dst;
}
 

今回の実装

memcpy はデータ列が短いとあまり効果がないので、最大限コピーするデータ列が長くなるように改良。
memcpy の呼び出し回数も size 回からおよそ log_2(size) 回に。関数呼び出しのオーバーヘッドが最小限になるように配慮。
void *memsetex(void *dst, void *src, size_t nmemb, size_t size)
{
	if(size == 0)
	{
		return NULL;
	}
	if(size == 1)
	{
		memcpy(dst, src, nmemb);
	}
	else
	{
		size_t half = size/2;
		memsetex(dst, src, nmemb, half);
		memcpy(dst + half * nmemb, dst, half * nmemb);
		if(size%2)
		{
			memcpy(dst + (size - 1) * nmemb, src, nmemb);
		}
	}
	return dst;
}
 
コピー先の前半分までを再帰的にコピーして、前半分を後ろ半分に一気にコピーする。sizeが奇数だった場合は最後に1個分コピー。
size = 0のときをわざわざ場合分けしているのは無限ループを避けるため。また、普通 size_t 型は非負整数型をtypedefした型なので負数のときの処理は考えていない。
  • void * 型の処理
一般にtype * 型をインクリメントすると、ポインタの値は sizeof(type) バイトずつ増える。
一方で、あまり知られていないが、void * 型をインクリメントするとポインタの値は1ずつ増える。同様に、四則演算も1バイト単位になる。(この辺は処理系依存かもしれない)

実行時間比較

10000要素の配列に同じ値を埋める操作を10000回繰り返すのに要した時間をtime コマンドで求めた(表に記したのはuser time)。小数点第2位以下はあまり信用できない。
環境
OS: Ubuntu 12.04 (precise) 32-bit
CPU: Intel® Atom™ CPU N280 @ 1.66GHz
Memory: 1GB
アルゴリズム int型(4byte) long double型(16byte)
その1 1.564s 4.028s
その2 2.368s 2.808s
今回の実装 0.080s 0.244s
どちらも今回の実装のほうが10倍以上高速である。

まとめ

memcpyはいくら速いとはいえ、呼び出し回数が増えるとそれだけオーバーヘッドが大きいので(とくに、サイズが小さいと直コピーより時間がかかる)、効率的に呼び出すように工夫すべきである。
最終更新:2012年05月16日 15:37