こんにちは
質問です。
memcpyを使わずに、memcpyより処理速度の速い関数を作りたいと思っています。
1日知恵を絞った結果、某サイトに載っているコードが出来ました。。。
この他に、何か案はあるのでしょうか?知恵を貸していただきたいです。。。お願いします。。。
以下、コード
memcpy代替案
Re: memcpy代替案
大きなサイズの場合に速くしたいのであれば、
バイト単位ではなく、4バイトずつコピーするなどすれば
ループ回数が減るので速くなります。
ただし、コピー元もコピー先も 4の倍数のアドレスにあるか
どうか考慮しないといけないでしょう。
さらに、ループアンローリングを行うと高速になります。
詳細は自分でググって、解説をお願いします。
バイト単位ではなく、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);
}
詳細は自分でググって、解説をお願いします。
Re: memcpy代替案
環境やコピーするサイズにもよりますが、並列化すると速くなるかもしれません。
これまでの関数もまとめてテストコードを作ってみました。
なぜか(アドレスの範囲だけ確保した場所が使われるにあたって実際のRAMを割り当てる処理の分?)
最初のコピーは他より時間がかかるようなので、それぞれ2回実行し、
かつ最初に実行する関数を選べるようにしてみました。
copy_test.c
測定結果例
今回実験を行った環境とサイズでは、parallel_memcpy()が一番速いようです。
また、コンパイラによっては複雑なことをしているm_copy()より、
シンプルで最適化しやすいkamiko_memcpy()の方が速くなることがあるようです。
これまでの関数もまとめてテストコードを作ってみました。
なぜか(アドレスの範囲だけ確保した場所が使われるにあたって実際の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
また、コンパイラによっては複雑なことをしているm_copy()より、
シンプルで最適化しやすいkamiko_memcpy()の方が速くなることがあるようです。
オフトピック
bの範囲を超えて書き込んでしまい、よくないですね。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: memcpy代替案
すみません。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代替案
size が約1GBなので、VC++ の 64ビット版で試してみました。
最適化なしの実行結果
-O2 オプションで最適化
memcpy は、もともとかなり高性能です。
kamiko_memcpy や parallel_memcpy から分かるように
VC++ の最適化も優秀です。
#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()
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()
kamiko_memcpy や parallel_memcpy から分かるように
VC++ の最適化も優秀です。
Re: memcpy代替案
VC++に関して,memcpyの直接の呼び出しは/Oi コンパイラオプションを使うと (REP MOVSBに) インライン展開されます。
ref) intrinsic | Microsoft Docs
このため,/O2 (/Og/Oi/Ot/Oy/Ob2/Gs/GF/Gy) を使う場合,関数ポインタ経由ではなく直接呼び出すと時間が大きく違う可能性があります。
オフトピック
GCCでも-fno-builtin-memcpy等を付けずに直接呼び出しをするとインライン化される模様。