memcpy代替案

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
kamiko
記事: 2
登録日時: 5年前

memcpy代替案

#1

投稿記事 by kamiko » 5年前

こんにちは

質問です。

memcpyを使わずに、memcpyより処理速度の速い関数を作りたいと思っています。

1日知恵を絞った結果、某サイトに載っているコードが出来ました。。。
この他に、何か案はあるのでしょうか?知恵を貸していただきたいです。。。お願いします。。。
以下、コード

コード:

void *memset(void *s, int c, size_t n)
{
    const unsigned char uc = c;
    unsigned char       *p = (unsigned char *)s;

    while (n-- > 0)
        *p++ = uc;

    return (s);
}

kamiko
記事: 2
登録日時: 5年前

Re: memcpy代替案

#2

投稿記事 by kamiko » 5年前

何故かmemsetのコードを乗っけていることに気づいた…

コード:

void *memcpy(void *s1, const void *s2, size_t n)
{
    char        *p1 = (char *)s1;
    const char  *p2 = (const char *)s2;

    while (n-- > 0) {
        *p1 = *p2;
        p1++;
        p2++;
    }
    return (s1);
}
こちらが正解です。。。

かずま

Re: memcpy代替案

#3

投稿記事 by かずま » 5年前

大きなサイズの場合に速くしたいのであれば、
バイト単位ではなく、4バイトずつコピーするなどすれば
ループ回数が減るので速くなります。
ただし、コピー元もコピー先も 4の倍数のアドレスにあるか
どうか考慮しないといけないでしょう。

コード:

#include <stdio.h>

#define SIZE 16  // or 32

void *m_copy(void *s1, const void *s2, size_t n)
{
	char *p1 = (char *)s1;
	const char *p2 = (const char *)s2;

	if (n < SIZE) {
		while (n--) *p1++ = *p2++;
		return s1;
	}
	long a1 = (long)p1, a2 = (long)p2;
	const int mask = sizeof(long) - 1;
	int b1 = a1 & mask, b2 = a2 & mask;
	if (b1 != b2) {
		while (n--) *p1++ = *p2++;
		return s1;
	}
	while (b1--) *p1++ = *p2++;
	long *q1 = (long *)p1, *q2 = (long *)p2;
	for (n -= b2; n >= sizeof(long); n -= sizeof(long)) *q1++ = *q2++;
	p1 = (char *)q1, p2 = (const char *)q2;
	while (n--) *p1++ = *p2++;
	return s1;
}

int main(void)
{
	char a[32] = "abcdefghijklmnopqrstuvwxyz";
	char b[32];
	m_copy(b, a, 32);
	puts(b);
	m_copy(b, a + 3, 29);
	puts(b);
	m_copy(b + 5, a + 3, 29);
	puts(b);
}
さらに、ループアンローリングを行うと高速になります。
詳細は自分でググって、解説をお願いします。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: memcpy代替案

#4

投稿記事 by みけCAT » 5年前

環境やコピーするサイズにもよりますが、並列化すると速くなるかもしれません。

これまでの関数もまとめてテストコードを作ってみました。
なぜか(アドレスの範囲だけ確保した場所が使われるにあたって実際のRAMを割り当てる処理の分?)
最初のコピーは他より時間がかかるようなので、それぞれ2回実行し、
かつ最初に実行する関数を選べるようにしてみました。

copy_test.c

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

double get_time(void) {
	struct timeval tv;
	if (gettimeofday(&tv, NULL) == 0) {
		return tv.tv_sec + tv.tv_usec * 1e-6;
	} else {
		perror("gettimeofday");
		return 0;
	}
}

void *kamiko_memcpy(void *s1, const void *s2, size_t n)
{
	char        *p1 = (char *)s1;
	const char  *p2 = (const char *)s2;

	while (n-- > 0) {
		*p1 = *p2;
		p1++;
		p2++;
	}
	return (s1);
}

#define SIZE 16  // or 32

void *m_copy(void *s1, const void *s2, size_t n)
{
	char *p1 = (char *)s1;
	const char *p2 = (const char *)s2;

	if (n < SIZE) {
		while (n--) *p1++ = *p2++;
		return s1;
	}
	long a1 = (long)p1, a2 = (long)p2;
	const int mask = sizeof(long) - 1;
	int b1 = a1 & mask, b2 = a2 & mask;
	if (b1 != b2) {
		while (n--) *p1++ = *p2++;
		return s1;
	}
	while (b1--) *p1++ = *p2++;
	long *q1 = (long *)p1, *q2 = (long *)p2;
	for (n -= b2; n >= sizeof(long); n -= sizeof(long)) *q1++ = *q2++;
	p1 = (char *)q1, p2 = (const char *)q2;
	while (n--) *p1++ = *p2++;
	return s1;
}

void *parallel_memcpy(void* dst, const void* src, size_t n)
{
	char* dst_c = (char*)dst;
	const char* src_c = (const char*)src;
	size_t i;

	#pragma omp parallel for
	for (i = 0; i < n; i++) {
		dst_c[i] = src_c[i];
	}
	return dst;
}

#define TEST_NUM 4

int main(int argc, char* argv[]) {
	size_t size = 1000000000;
	char *src, *dest;
	double start_time, end_time;
	int i, j, offset = 0;
	void* (*func[TEST_NUM])(void*, const void*, size_t) = {
		memcpy, kamiko_memcpy, m_copy, parallel_memcpy
	};
	const char *name[TEST_NUM] = {
		"memcpy", "kamiko_memcpy", "m_copy", "parallel_memcpy"
	};
	if (argc >= 2) {
		size = 0;
		for (i = 0; argv[1][i] != '\0'; i++) {
			int d = argv[1][i] - '0';
			size_t size_bak = size;
			if (d < 0 || 9 < d) {
				fputs("invalid size\n", stderr);
				return 1;
			}
			size = size * 10 + d;
			if (size < size_bak) {
				fputs("size overflow\n", stderr);
				return 1;
			}
		}
	}
	if (argc >= 3) {
		offset = atoi(argv[2]);
		if (offset < 0 || TEST_NUM <= offset) offset = 0;
	}
	printf("test with %zu bytes\n", size);
	if ((src = calloc(1, size)) == NULL) {
		perror("calloc");
		return 1;
	}
	if ((dest = malloc(size)) == NULL) {
		perror("malloc");
		free(src);
		return 1;
	}

	for (i = 0; i < 2; i++) {
		for (j = 0; j < TEST_NUM; j++) {
			int idx = (j + offset) % TEST_NUM;
			start_time = get_time();
			func[idx](dest, src, size);
			end_time = get_time();
			printf("%s(): %fs\n", name[idx], end_time - start_time);
		}
	}

	free(src);
	free(dest);
	return 0;
}
測定結果例

コード:

YUKI.N>gcc -O3 -march=native -fopenmp -std=c99 -o copy_test copy_test.c
YUKI.N>icc -O3 -march=native -qopenmp -std=c99 -o copy_test_i copy_test.c
YUKI.N>./copy_test 100000000000 0
test with 100000000000 bytes
memcpy(): 46.692896s
kamiko_memcpy(): 14.339785s
m_copy(): 14.335661s
parallel_memcpy(): 4.705481s
memcpy(): 7.627874s
kamiko_memcpy(): 14.336197s
m_copy(): 14.337643s
parallel_memcpy(): 4.664744s
YUKI.N>./copy_test_i 100000000000 0
test with 100000000000 bytes
memcpy(): 68.312313s
kamiko_memcpy(): 10.672402s
m_copy(): 21.783252s
parallel_memcpy(): 3.669785s
memcpy(): 14.826188s
kamiko_memcpy(): 14.554980s
m_copy(): 23.390514s
parallel_memcpy(): 3.785170s
YUKI.N>./copy_test 100000000000 3
test with 100000000000 bytes
parallel_memcpy(): 3.242945s
memcpy(): 7.648677s
kamiko_memcpy(): 16.415280s
m_copy(): 16.412930s
parallel_memcpy(): 2.611474s
memcpy(): 7.648535s
kamiko_memcpy(): 16.413523s
m_copy(): 16.412830s
YUKI.N>./copy_test_i 100000000000 3
test with 100000000000 bytes
parallel_memcpy(): 5.122000s
memcpy(): 12.433303s
kamiko_memcpy(): 10.631792s
m_copy(): 21.404856s
parallel_memcpy(): 3.932546s
memcpy(): 12.294414s
kamiko_memcpy(): 10.633808s
m_copy(): 21.410336s
今回実験を行った環境とサイズでは、parallel_memcpy()が一番速いようです。
また、コンパイラによっては複雑なことをしているm_copy()より、
シンプルで最適化しやすいkamiko_memcpy()の方が速くなることがあるようです。
オフトピック
かずま さんが書きました:
5年前

コード:

	m_copy(b + 5, a + 3, 29);
bの範囲を超えて書き込んでしまい、よくないですね。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

かずま

Re: memcpy代替案

#5

投稿記事 by かずま » 5年前

みけCAT さんが書きました:
5年前
オフトピック
かずま さんが書きました:
5年前

コード:

	m_copy(b + 5, a + 3, 29);
bの範囲を超えて書き込んでしまい、よくないですね。
すみません。m_copy(b + 3, a + 3, 29); のつもりでした。

次の場合のテストです。
 m_copy(b, a, 32); // a も b も 4バイト境界
 m_copy(b, a + 3, 29); // a と b の境界が異なる
 m_copy(b + 3, a + 3, 29); // a も b も 4バイト境界ではないが long コピー可能

kamiko_memcpy のコンパイル結果を逆アセンブルしてみると、
gcc の最適化のすごさがわかりますね。

かずま

Re: memcpy代替案

#6

投稿記事 by かずま » 5年前

size が約1GBなので、VC++ の 64ビット版で試してみました。

コード:

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

void *kamiko_memcpy(void *s1, const void *s2, size_t n)
{
	char        *p1 = (char *)s1;
	const char  *p2 = (const char *)s2;

	while (n-- > 0) {
		*p1 = *p2;
		p1++;
		p2++;
	}
	return (s1);
}

#define SIZE 16

void *m_copy(void *s1, const void *s2, size_t n)
{
	char *p1 = (char *)s1;
	const char *p2 = (const char *)s2;

	if (n < SIZE) {
		while (n--) *p1++ = *p2++;
		return s1;
	}
	long long a1 = (long long)p1, a2 = (long long)p2;
	const int mask = sizeof(long long) - 1;
	int b1 = a1 & mask, b2 = a2 & mask;
	if (b1 != b2) {
		while (n--) *p1++ = *p2++;
		return s1;
	}
	while (b1--) *p1++ = *p2++;
	long long *q1 = (long long *)p1, *q2 = (long long *)p2;
	for (n -= b2; n >= sizeof(long long); n -= sizeof(long long)) *q1++ = *q2++;
	p1 = (char *)q1, p2 = (const char *)q2;
	while (n--) *p1++ = *p2++;
	return s1;
}

void *parallel_memcpy(void* dst, const void* src, size_t n)
{
	char* dst_c = (char*)dst;
	const char* src_c = (const char*)src;
	size_t i;

	#pragma omp parallel for
	for (i = 0; i < n; i++) {
		dst_c[i] = src_c[i];
	}
	return dst;
}

#define TEST_NUM 4

int main(int argc, char* argv[]) {
	size_t size = 1000000000;
	char *src, *dest;
	double start_time, end_time;
	int i, j, offset = 0;
	void* (*func[TEST_NUM])(void*, const void*, size_t) = {
		memcpy, kamiko_memcpy, m_copy, parallel_memcpy
	};
	const char *name[TEST_NUM] = {
		"memcpy", "kamiko_memcpy", "m_copy", "parallel_memcpy"
	};
	if (argc >= 2) {
		size = 0;
		for (i = 0; argv[1][i] != '\0'; i++) {
			int d = argv[1][i] - '0';
			size_t size_bak = size;
			if (d < 0 || 9 < d) {
				fputs("invalid size\n", stderr);
				return 1;
			}
			size = size * 10 + d;
			if (size < size_bak) {
				fputs("size overflow\n", stderr);
				return 1;
			}
		}
	}
	if (argc >= 3) {
		offset = atoi(argv[2]);
		if (offset < 0 || TEST_NUM <= offset) offset = 0;
	}
	printf("test with %zu bytes\n", size);
	if ((src = calloc(1, size)) == NULL) {
		perror("calloc");
		return 1;
	}
	if ((dest = malloc(size)) == NULL) {
		perror("malloc");
		free(src);
		return 1;
	}

	for (i = 0; i < 2; i++) {
		for (j = 0; j < TEST_NUM; j++) {
			int idx = (j + offset) % TEST_NUM;
			start_time = clock();
			func[idx](dest, src, size);
			end_time = clock();
			printf("%fs: %s()\n",
				((double)end_time - start_time)/CLOCKS_PER_SEC, name[idx]);
		}
	}

	free(src);
	free(dest);
	return 0;
}
最適化なしの実行結果

コード:

test with 1000000000 bytes
0.808000s: memcpy()
2.361000s: kamiko_memcpy()
0.309000s: m_copy()
2.113000s: parallel_memcpy()
0.172000s: memcpy()
2.355000s: kamiko_memcpy()
0.321000s: m_copy()
2.036000s: parallel_memcpy()
-O2 オプションで最適化

コード:

test with 1000000000 bytes
0.704000s: memcpy()
0.355000s: kamiko_memcpy()
0.207000s: m_copy()
0.406000s: parallel_memcpy()
0.183000s: memcpy()
0.380000s: kamiko_memcpy()
0.199000s: m_copy()
0.411000s: parallel_memcpy()
memcpy は、もともとかなり高性能です。
kamiko_memcpy や parallel_memcpy から分かるように
VC++ の最適化も優秀です。

YuO
記事: 947
登録日時: 13年前
住所: 東京都世田谷区

Re: memcpy代替案

#7

投稿記事 by YuO » 5年前

かずま さんが書きました:
5年前
memcpy は、もともとかなり高性能です。
VC++に関して,memcpyの直接の呼び出しは/Oi コンパイラオプションを使うと (REP MOVSBに) インライン展開されます。
ref) intrinsic | Microsoft Docs

このため,/O2 (/Og/Oi/Ot/Oy/Ob2/Gs/GF/Gy) を使う場合,関数ポインタ経由ではなく直接呼び出すと時間が大きく違う可能性があります。
オフトピック
GCCでも-fno-builtin-memcpy等を付けずに直接呼び出しをするとインライン化される模様。

かずま

Re: memcpy代替案

#8

投稿記事 by かずま » 5年前

kamiko さんが書きました:
5年前
この他に、何か案はあるのでしょうか?知恵を貸していただきたいです。。。お願いします。。。
知恵を貸しているのに、放置ですか?

C++ になりますが、<algorithm> の std::copy も
memcpy に匹敵する性能を持っているようです。

コード:

void *std_copy(void* dst, const void* src, size_t n)
{
	const char *s = (const char *)src;
	std::copy(s, s + n, (char *)dst);
	return dst;
}

返信

“C言語何でも質問掲示板” へ戻る