速度テスト

Nehalem 最適化

せっかくPCを新調したのでどれくらい速いのか見てみたいと思う。とりあえずCPUで実行する処理を適当にでっちあげてなんとなく最適化してどれくらいの速度になるのか見てみたい。


お題が満たすべき条件は

  • 最適化しやすい(マルチメディア系処理が良い？)
  • そこそこ重い(CPUで素のまま動かすにはちょっとだけ重い)

あたりかな。

とりあえず適当に

  • 16x32画素の32ビット画像の重ね合わせ処理
  • 重ね合わせはマスク画像をもとにする
  • 1フレームあたり85枚の画像を60フレーム/秒で処理する

って感じで、１秒間に約10MBのデータを処理するって感じで。


この程度ならGPUじゃなくて、CPUで処理するのが順当だろうしちょっとだけ最適化で遊んでみたくなる感じないかなぁ。まぁ実際にはこの程度なら最適化不要かもしれないけどそこはとりあえずのお題ってことで。


アルゴリズムは

  • (画像１ AND マスク) OR (画像２ AND 反転マスク)

で。これならなんかSSEとかで最適化しやすそう。


ざざっと書いてみたＣ言語の処理部はこれ。C言語とはいえ、そこそこ速くなるように64ビットずつ処理する。

#include <stddef.h>
void *masked_memcpyC(void *dest, const void *src, const void *mask, size_t n)
{
	unsigned long		*d8;
	const unsigned long	*s8, *m8;
	size_t			i8;
	unsigned char		*d1;
	const unsigned char	*s1, *m1;
	size_t			i1;


	if(dest == NULL){
		return dest;
	}
	if(src == NULL){
		return dest;
	}
	if(mask == NULL){
		return dest;
	}

	/* 8byte ずつ処理 */
	d8 = (unsigned long *)dest;
	s8 = (const unsigned long *)src;
	m8 = (const unsigned long *)mask;
	for(i8 = 0 ; i8 < (n / sizeof(unsigned long)) ; i8++,d8++,s8++,m8++){
		*d8 = (*d8 & *m8) | (*s8 & (~*m8));		/* 画像1 AND マスク + 画像2 AND 反転マスク */
	}

	/* 1byte ずつ処理 */
	d1 = (unsigned char *)d8;
	s1 = (const unsigned char *)s8;
	m1 = (const unsigned char *)m8;
	for(i1 = 0 ; i1 < (n % sizeof(unsigned long)) ; i1++,d1++,s1++,m1++){
		*d1 = (*d1 & *m1) | (*s1 & (~*m1));
	}

	return dest;
}

それからmain部。
速度計測はRDTSC命令で所要クロック数を計測する感じで。
せっかくなのでＣ言語版、アセンブラ版、関係ないけど比較用にglibcのmemcpyの３つで計測。

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>

__attribute__((always_inline)) __attribute__((fastcall)) static unsigned long long get_clock_register(void)
{
	unsigned int	eax;
	unsigned int	edx;

	__asm__ volatile ("rdtsc" : "=a"(eax), "=d"(edx));

	return ((unsigned long long)edx << 32) | eax;
}


extern void *masked_memcpyC(void *dest, const void *src, const void *mask, size_t n);
extern void *masked_memcpy(void *dest, const void *src, const void *mask, size_t n);


int main(int argc, char *argv[])
{
	unsigned char	*src;
	unsigned char	*dest;
	unsigned char	*mask;
	unsigned long	size;
	unsigned long	repetition;

	unsigned long long	clock;
	size_t		n;
	unsigned long	c;


	if(argc != 3){
		printf("Usage:\n\t> %s size repetition\n", argv[0]);
		return -1;
	}


	size = strtoul(argv[1], NULL, 0);
	if(size == 0){
		size = 16 * 32 * 4;
	}
	repetition = strtoul(argv[2], NULL, 0);
	if(repetition == 0){
		repetition = 85 * 60;
	}
	n = size * repetition;

	src = (unsigned char *)malloc(n);
	dest = (unsigned char *)malloc(n);
	mask = (unsigned char *)malloc(size);

	{
		int	i;
		for(i=0;i<n;i++){
			src[i] = rand() >> 8;
		}
		for(i=0;i<n;i++){
			dest[i] = rand() >> 8;
		}
		for(i=0;i<size;i++){
			mask[i] = rand() >> 8;
		}
	}


	clock = get_clock_register();
	for(c=0;c<repetition;c++){
		masked_memcpyC(dest+size*c, src+size*c, mask, size);
	}
	printf("C   -> %d\n", (int)(get_clock_register() - clock));
	clock = get_clock_register();
	for(c=0;c<repetition;c++){
		masked_memcpy(dest+size*c, src+size*c, mask, size);
	}
	printf("ASM -> %d\n", (int)(get_clock_register() - clock));
	clock = get_clock_register();
	for(c=0;c<repetition;c++){
		memcpy(dest+size*c, src+size*c, size);
	}
	printf("cpy -> %d\n", (int)(get_clock_register() - clock));


	free(src);
	free(dest);
	free(mask);

	return 0;
}

最後にSSEで最適化もどき。128ビットずつ処理。
「Intel64 and IA-32 Architectures Software Developer's Manual Volume1: Basic Architecture」のChapter10 「Programming with Streaming SIMD Extensions(SSE)」からChapter12「Programming with SSE3, SSSE3, AND SSE4」あたりを眼を皿のようにして使えそうな命令を探しつつ、同「Optimization Reference Manual」のAppendix C C.3.1に書いてあるTable C-x達と見比べつつChapter3「General Optimization Guidelines」あたりを参考にしながら書いてみた。

#void *masked_memcpy(dest, src, mask, n)
#eax   masked_memcpy(rdi,  rsi, rdx,  rcx)
#{
	.text

.globl masked_memcpy
	.type   masked_memcpy, @function

masked_memcpy:
	movq	%rdi, %r8		# backup
	movq	%rdx, %r9		# backup
	movq	%rbx, %r10	# backup

	cmpq	$0,   %r8		# ぬるぽ
	je	Lend		# ｶﾞｯ!
	cmpq	$0,   %r9		# ぬるぽ
	je	Lend		# ｶﾞｯ!
	cmpq	$0,   %rsi	# ぬるぽ
	je	Lend		# ｶﾞｯ!

	/*
	*	for(i=0;i<(n/16);i++){
	*		16バイトずつ処理;
	*	}
	*/
	testq	%rcx, %rcx		# rcx : n
	je	Lend
	movq	%rcx,  %rax
	shrq	$4,    %rax		# rax : i
	je	Lremain

	.p2align 4,,15			# 2^4 align max 15 bytes pad
Loop16:
	movupd	(%rdi),%xmm0		# *dest
	movupd	(%rdx),%xmm1		# mask
	movupd	(%rsi),%xmm2		# src
	andpd	%xmm1, %xmm0		# dest = dest & mask
	andnpd	%xmm2, %xmm1		# mask = ~mask & src
	orpd	%xmm1, %xmm0		# dest = dest | mask
	movupd	%xmm0, (%rdi)		# *dest

	addq	$16,   %rdi		# dest++
	addq	$16,   %rdx		# mask++
	addq	$16,   %rsi		# src++
	subq	$1,    %rax		# i++
#	cmpq	$0,    %rax		# i < (n/16)
	jne	Loop16


Lremain:
	/*
	*	for(i=0;i<(n%16);i++){
	*		1バイトずつ処理;
	*	}
	*/
	movq	%rcx,  %r11		# r11 : i
	andq	$15,   %r11
	je		Lend

	.p2align 3,,7			# 2^3 align max 7 bytes pad
Loop01:
	movzbl	(%rdx),%eax		# eax = *m
	movzbl	(%rdi),%ebx		# ebx = *d
	subq	$1,    %r11		# i++
	addq	$1,    %rdx		# m++
	andl	%eax,  %ebx		# *d & *m  -> xxx
	notl	%eax			# ~*m
	andb	(%rsi),%al		# *s & ~*m -> yyy
	addq	$1,    %rsi		# s++
	orl	%eax,  %ebx		# ebx = xxx | yyy
	movb	%bl,   (%rdi)		# *d = ebx
	addq	$1,    %rdi		# d++
	cmpq	$0,    %r11		# i < (n%16)
	jne     Loop01

Lend:
	movq	%r8,   %rdi		# restore
	movq	%r9,   %rdx		# restore
	movq	%r10,  %rbx		# restore
	movq	%rdi,  %rax		# return dest
	retq
#}

測定結果がこれ。

所要クロック数 2.66GHz換算(ms)
C 6852069 2.58
ASM 6021533 2.26
memcpy 5477978 2.06

てか、アセンブラあんまり速くない...orz 予定では２倍速くらい出てほしかったのに。どこかがボトルネックになってるのか、最適化の余地が残ってるのか。まぁ、ループアンロールすらしてないけど。
う〜ん。思っている以上に最適化って奥が深いかもしれない。Intelのマニュアルにもいろいろ書いてあったしなぁ。後で実験してみようかな。
ちなみになんでmemcpyが遅いんだろ？？？１バイトずつ転送してるのかな。やってることは単純なのでC言語版の数倍速でても良いハズなんだけど。