ハッシュ取得処理の速度を調べてみた

コメントを残す

なんかハッシュの計算速度を調べている人がいるらしいので自分で組んだルーチンの速度をちょっと調べてみました。

対象は今現在自分が実装しているハッシュコードの取得ルーチンすべてです。

なお、私のハッシュコードの取得ルーチンはほとんど最適化されていないので、コンパイラの最適化任せになっています。

それを踏まえた上でこの結果を参考にしてみるといいかもしれません。

実行環境はQPC検証時と同じ

です。説明するなら

OS : Windows 7 Ultimate Edition SP1 x64

CPU : Core 2 Quad Q8400 (2.66GHz)

Compiler : Visual Studio 2005

ですね。ちなみに、念のためにWinXP x86でも32bit版の結果をとってみましたがほぼ計測結果が変わらなかったので割愛します。

対象ファイルはFedora15 Live Desktopのイメージファイル(ISOイメージ)です。確認のためのSHA256ハッシュがあるのでルーチンの検証もついでにやっています。

時間測定にはWin7を使うのでQPC問題にかかることはない+どうせ速度といっても絶対時間ではなく処理クロック数を比較するものなのでQPCを使っています。

x86版実行ファイルでの測定結果

filesize : 592445440 bytes. QPC Freq: 2603925 count per second.

CRC32 [ 3837671 count ( 1.47 sec)] : 05ccf59c

MD5 [ 5727820 count ( 2.20 sec)] : 334ad4f894acef758cc1d1e24fa90d13

SHA1 [ 9155363 count ( 3.52 sec)] : f3a3c175b7b1fc60eb90fd1d6f95aad468408821

SHA224 [ 13484459 count ( 5.18 sec)] : ee95a0a87c4ca0991b32e442ec4c75f95e954aa97bab0de7d71fa928

SHA256 [ 13474869 count ( 5.17 sec)] : 73203b15e4d43e72378d522a9d3e0098c8c4403a2f1e0e062b70ca1d4b63af74

SHA384 [ 28754034 count ( 11.04 sec)] : 553def5b076b74ece060f991ed42ec7c766df7823bf7d56172dd63633e598a387acf8be390b3a308c8adfd875b8fad77

SHA512 [ 28755813 count ( 11.04 sec)] : e193ab61a5e1f3cb3d6d2f789831d668d2858d5d541205946889b330e22c773c7d9465086f22ca5691ada86e26214883667cb9760b17edec13d63fd8631ce088

RIPEMD128 [ 11008149 count ( 4.23 sec)] : d8bfc1c96d8087396e0ec86c0ef57689

RIPEMD160 [ 15908033 count ( 6.11 sec)] : 0e7161a192ea3b09b3b404c22886f166e23886b9

RIPEMD256 [ 11887182 count ( 4.57 sec)] : 770dd314bd0d0a6c7e47bf643df6ff9db37b24ce7bbd2b39165c78ed4b773a9a

RIPEMD320 [ 16891965 count ( 6.49 sec)] : 326616fbf8a78e16d271273d581ccd0ffa531a0890644986648986061cc793f5331989c41964b2da

Whirlpool [ 95903986 count ( 36.83 sec)] : 2cac8c0277024915a5eb09a74ae30bcb4359cb169abdf34530f99433a11b071de3ed85682a958fdab4347bd9a936c27682dedff52238b235cc5df506fdb0af93

x64版実行ファイルでの測定結果

filesize : 592445440 bytes. QPC Freq: 2603925 count per second.

CRC32 [ 4215701 count ( 1.62 sec)] : 05ccf59c

MD5 [ 5023232 count ( 1.93 sec)] : 334ad4f894acef758cc1d1e24fa90d13

SHA1 [ 7682911 count ( 2.95 sec)] : f3a3c175b7b1fc60eb90fd1d6f95aad468408821

SHA224 [ 13548376 count ( 5.20 sec)] : ee95a0a87c4ca0991b32e442ec4c75f95e954aa97bab0de7d71fa928

SHA256 [ 13548089 count ( 5.20 sec)] : 73203b15e4d43e72378d522a9d3e0098c8c4403a2f1e0e062b70ca1d4b63af74

SHA384 [ 8358848 count ( 3.21 sec)] : 553def5b076b74ece060f991ed42ec7c766df7823bf7d56172dd63633e598a387acf8be390b3a308c8adfd875b8fad77

SHA512 [ 8354883 count ( 3.21 sec)] : e193ab61a5e1f3cb3d6d2f789831d668d2858d5d541205946889b330e22c773c7d9465086f22ca5691ada86e26214883667cb9760b17edec13d63fd8631ce088

RIPEMD128 [ 7693319 count ( 2.95 sec)] : d8bfc1c96d8087396e0ec86c0ef57689

RIPEMD160 [ 11636038 count ( 4.47 sec)] : 0e7161a192ea3b09b3b404c22886f166e23886b9

RIPEMD256 [ 7742416 count ( 2.97 sec)] : 770dd314bd0d0a6c7e47bf643df6ff9db37b24ce7bbd2b39165c78ed4b773a9a

RIPEMD320 [ 11268493 count ( 4.33 sec)] : 326616fbf8a78e16d271273d581ccd0ffa531a0890644986648986061cc793f5331989c41964b2da

Whirlpool [ 27395845 count ( 10.52 sec)] : 2cac8c0277024915a5eb09a74ae30bcb4359cb169abdf34530f99433a11b071de3ed85682a958fdab4347bd9a936c27682dedff52238b235cc5df506fdb0af93

考察

全般的にx64で実行する方が処理時間としては有利になっていますね。

おそらくレジスタ数の増加によりテンポラリ変数へのアクセスを大幅に減らせることがその原因と思います。

ただ、よく見ると速度が劇的に改善しているものとほとんど変わらないものがあります。それは

劇的に改善(3倍以上):SHA-384/512、Whirlpool

ほぼ変化なし:SHA-224/256 (速度が下がっている:CRC32)

ですね。これは、前者のルーチンは64bit処理に対して最適化されたハッシュルーチンなのに対して後者のルーチンは32bit処理に対して最適化されたハッシュルーチンなので

前者は32bit環境では演算的に不利(64bit単位での加算処理・回転処理などが32bitx2で行わなければならないという点)で、32bit環境で速度が大幅に低下している、

後者は64bit環境でコンパイルしてもコンパイラが最適化を行う部分を見つけられなかった、ということだと思われます。

160bitハッシュで、SHA-1とRIPEMD160の比較では、アルゴリズムをそのまま適応するならちょっとSHA-1の方が速度的には有利っぽい、という感じです。

ただし、RIPEMD系の場合はブロックを二つにして同じような処理を行っている関係上、SIMDにより２つのブロックの同時処理ができればRIPEMDの処理速度は1.5倍くらいには向上できると思いますので

その最適化が入ればRIPEMD系が有利となることもあります。

ちなみに、ちょっとおもしろいのがRIPEMD160とRIPEMD256ではRIPEMD160がハッシュ長は短いに計算に時間がかかっている、という現象も確認できました。

これはRIPEMD256の処理がRIPEMD128の変形であり、ハッシュ計算時のラウンド処理がRIPEMD160系の4/5になっている、ということが効いていると思われます。

もちろん、これは(コード的に)最適化していないルーチンを使っている例

なのが注意点です。FIPSなどで記述されている数式をそのままプログラム化した結果である、ということです。

考察にも記述しましたが、これよりも早くすることはいくらでもできると思われます。たとえば

  • ラウンド関数処理の演算を最適化する(XOR,AND,OR,NOTの演算をもう少しきれいにする)
  • ブロックが並列動作している場合はSIMDの使用を考える(RIPEMD系が特にそれに該当する)
  • x86の実行ファイル上でワード単位が64bitのハッシュ処理を使うときにはSSE2を使うことで直接の64bit処理を行い処理量を少なくする

といったことがあげられます。

まあ、この結果自身は自分の関数がどれくらいの速度で動作できるかを示しているので

自分の書いた処理が遅すぎはしないかどうかを調べる手助けにはなる可能性があると思います。

ついでのソースコード

この測定結果を作り出したソースコードも記述しておきます。

私が持っているゲーム用のライブラリから作っているので一部記述がトリッキーになっていますので注意してください。(defineの置換など)

バッファオーバーランなどは検証目的なので起こらない範囲でバッファを静的に確保しています。

#include <gamecommon.h>
#include <winbase.h>
typedef enum _hashtype{
	HASH_CRC32, HASH_MD5, HASH_SHA1, HASH_SHA224, HASH_SHA256, HASH_SHA384, HASH_SHA512,
	HASH_RIPEMD128, HASH_RIPEMD160, HASH_RIPEMD256, HASH_RIPEMD320, HASH_Whirlpool, HASH_MAX
} HASHTYPE;
#define HASH_CREATE(type)		case HASH_##type: lpHashCode = new CHash##type(); break
#define HASH_NAME(type)			case HASH_##type: lpHashName = #type; break
IHashCode *CreateHashCode(HASHTYPE type)
{
	IHashCode *lpHashCode = NULL;
	switch(type){
	HASH_CREATE(CRC32); HASH_CREATE(MD5); HASH_CREATE(SHA1); HASH_CREATE(SHA224); HASH_CREATE(SHA256); HASH_CREATE(SHA384); HASH_CREATE(SHA512);
	HASH_CREATE(RIPEMD128); HASH_CREATE(RIPEMD160); HASH_CREATE(RIPEMD256); HASH_CREATE(RIPEMD320); HASH_CREATE(Whirlpool);
	}
	return lpHashCode;
}
const char *GetHashCodeName(HASHTYPE type)
{
	const char *lpHashName = "";
	switch(type){
	HASH_NAME(CRC32); HASH_NAME(MD5); HASH_NAME(SHA1); HASH_NAME(SHA224); HASH_NAME(SHA256); HASH_NAME(SHA384); HASH_NAME(SHA512);
	HASH_NAME(RIPEMD128); HASH_NAME(RIPEMD160); HASH_NAME(RIPEMD256); HASH_NAME(RIPEMD320); HASH_NAME(Whirlpool);
	}
	return lpHashName;
}
void HashToString(char *str,const unsigned char *hash,size_t len)
{
	static const char hex[] = "0123456789abcdef";
	while(len > 0){
		*str++ = hex[*hash >> 4];
		*str++ = hex[*hash & 0x0f];
		++hash; len--;
	}
	*str = '
#include <gamecommon.h>
#include <winbase.h>
typedef enum _hashtype{
	HASH_CRC32, HASH_MD5, HASH_SHA1, HASH_SHA224, HASH_SHA256, HASH_SHA384, HASH_SHA512,
	HASH_RIPEMD128, HASH_RIPEMD160, HASH_RIPEMD256, HASH_RIPEMD320, HASH_Whirlpool, HASH_MAX
} HASHTYPE;
#define HASH_CREATE(type)		case HASH_##type: lpHashCode = new CHash##type(); break
#define HASH_NAME(type)			case HASH_##type: lpHashName = #type; break
IHashCode *CreateHashCode(HASHTYPE type)
{
	IHashCode *lpHashCode = NULL;
	switch(type){
	HASH_CREATE(CRC32); HASH_CREATE(MD5); HASH_CREATE(SHA1); HASH_CREATE(SHA224); HASH_CREATE(SHA256); HASH_CREATE(SHA384); HASH_CREATE(SHA512);
	HASH_CREATE(RIPEMD128); HASH_CREATE(RIPEMD160); HASH_CREATE(RIPEMD256); HASH_CREATE(RIPEMD320); HASH_CREATE(Whirlpool);
	}
	return lpHashCode;
}
const char *GetHashCodeName(HASHTYPE type)
{
	const char *lpHashName = "";
	switch(type){
	HASH_NAME(CRC32); HASH_NAME(MD5); HASH_NAME(SHA1); HASH_NAME(SHA224); HASH_NAME(SHA256); HASH_NAME(SHA384); HASH_NAME(SHA512);
	HASH_NAME(RIPEMD128); HASH_NAME(RIPEMD160); HASH_NAME(RIPEMD256); HASH_NAME(RIPEMD320); HASH_NAME(Whirlpool);
	}
	return lpHashName;
}
void HashToString(char *str,const unsigned char *hash,size_t len)
{
	static const char hex[] = "0123456789abcdef";
	while(len > 0){
		*str++ = hex[*hash >> 4];
		*str++ = hex[*hash & 0x0f];
		++hash; len--;
	}
	*str = '\0';
}
int main(void)
{
	FILE *rfp; unsigned char *ptr; size_t length; IHashCode *lpHashCode;
	LARGE_INTEGER liBegin,liEnd,liFreq,liTime; int type; char str[256]; unsigned char hash[64];
	rfp = fopen("hash.dat","rb");
	if(rfp == NULL) return 0;
	_fseeki64(rfp,0,SEEK_END); length = (size_t)_ftelli64(rfp); _fseeki64(rfp,0,SEEK_SET);
	ptr = new unsigned char[length];
	fread(ptr,1,length,rfp); fclose(rfp);
	QueryPerformanceFrequency(&liFreq);
	printf("filesize : %d bytes. QPC Freq: %lld count per second.\n",length,liFreq.QuadPart);
	for(type = HASH_CRC32;type < HASH_MAX;type++){
		lpHashCode = CreateHashCode((HASHTYPE)type);
		QueryPerformanceCounter(&liBegin);
		lpHashCode->Init();
		lpHashCode->Load(ptr,length);
		lpHashCode->Final();
		lpHashCode->GetDigest(hash);
		QueryPerformanceCounter(&liEnd);
		HashToString(str,hash,lpHashCode->GetDigestLength());
		liTime.QuadPart = liEnd.QuadPart - liBegin.QuadPart;
		printf("%10s [%10lld count (%6.2f sec)] : %s\n",GetHashCodeName((HASHTYPE)type),liTime.QuadPart,(double)liTime.QuadPart / (double)liFreq.QuadPart,str);
		delete lpHashCode;
	}
	delete[] ptr;
	return 0;
}

';
}
int main(void)
{
	FILE *rfp; unsigned char *ptr; size_t length; IHashCode *lpHashCode;
	LARGE_INTEGER liBegin,liEnd,liFreq,liTime; int type; char str[256]; unsigned char hash[64];
	rfp = fopen("hash.dat","rb");
	if(rfp == NULL) return 0;
	_fseeki64(rfp,0,SEEK_END); length = (size_t)_ftelli64(rfp); _fseeki64(rfp,0,SEEK_SET);
	ptr = new unsigned char[length];
	fread(ptr,1,length,rfp); fclose(rfp);
	QueryPerformanceFrequency(&liFreq);
	printf("filesize : %d bytes. QPC Freq: %lld count per second.\n",length,liFreq.QuadPart);
	for(type = HASH_CRC32;type < HASH_MAX;type++){
		lpHashCode = CreateHashCode((HASHTYPE)type);
		QueryPerformanceCounter(&liBegin);
		lpHashCode->Init();
		lpHashCode->Load(ptr,length);
		lpHashCode->Final();
		lpHashCode->GetDigest(hash);
		QueryPerformanceCounter(&liEnd);
		HashToString(str,hash,lpHashCode->GetDigestLength());
		liTime.QuadPart = liEnd.QuadPart - liBegin.QuadPart;
		printf("%10s [%10lld count (%6.2f sec)] : %s\n",GetHashCodeName((HASHTYPE)type),liTime.QuadPart,(double)liTime.QuadPart / (double)liFreq.QuadPart,str);
		delete lpHashCode;
	}
	delete[] ptr;
	return 0;
}

関連する記事

  1. スパムコメントは落ち着いたし、いろいろとやるか
  2. MediaFoundationを使う (6) MediaFoundation管理クラス実装その4
  3. C++でAny型もどきを実装してみる 拡張編
  4. C++でAny型もどきを実装してみる
  5. 実行時間を調べる処理 (1) 方法を見てみる

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

この記事のトラックバック用URL