memcpy中的内存读写优化问题

memcpy作为一个很简单的库函数,实现了内存的拷贝。不过这个函数功能虽然简单,要实现一个高效的memcpy函数还是很有难度的,这里对其优化问题做一简单讨论。

基本实现

最简单的memcpy函数实现如下:

1
2
3
4
5
6
7
8
9
void * memcpy1(void * dest, const void * src, size_t n) {
char * psrc, * pdest;
psrc = (char *)src; pdest = (char *)dest;
for (size_t i = 0; i < n; i++) {
*pdest = *psrc;
pdest++; psrc++;
}
return dest;
}

memcpy1函数对应的汇编代码如下:(使用gcc 4.8.4 -O1优化级别得到,-O2优化级别得到的代码差不多,-O3优化级别得到的代码会复杂很多,极为难以理解……)

1
2
3
4
5
6
7
8
9
10
11
12
13
memcpy1:
movq %rdi, %rax
testq %rdx, %rdx
je .L2
movl $0, %ecx
.L3:
movzbl (%rsi, %rcx), %r8d
movb %r8b, (%rax, %rcx)
addq $1, %rcx
cmpq %rdx, %rcx
jne .L3
.L2:
ret

从中可以看到,在.L3主循环中,每次使用零扩展传送(MOVZ)从源地址读取一个字节的内容,然后将其写入目的地址。

内存读写优化

memcpy1实现的功能是完全正确的,然而,这段代码效率也是很低效的,其中一个重要原因就是没考虑到实际内存读写过程。目前大部分主流CPU架构中,数据总线的位宽是确定的(大部分是32位或64位),在进行数据传输时,只能以此为基本单位进行传输,且每次读写数据的地址也最好是按照总线位宽对齐的(可能会有其他更严格的对其要求,如x86平台上SSE寄存器要求128位对齐),如果需要的数据不满足此要求时,读写效率会降低,如会进行多次读写等。

根据以上分析,我们可以每次都以数据总线位宽为单位进行读写,以此优化上述代码:

1
2
3
4
5
6
7
8
9
10
void * memcpy2(void * dest, const void * src, size_t n) {
long long * psrc, * pdest;
psrc = (long long *)src; pdest = (long long *)dest;
n /= 8;
for (size_t i = 0; i < n; i++) {
*pdest = *psrc;
pdest++; psrc++;
}
return dest;
}

需要注意的是,以上代码假设n是8的整数倍。对应的汇编代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
memcpy2:
movq %rdi, %rax
testq %rdx, %rdx
je .L2
movl $0, %ecx
.L3:
movq (%rsi, %rcx, 8), %r8
movq %r8, (%rax, %rcx, 8)
addq $1, %rcx
cmpq %rdx, %rcx
jne .L3
.L2:
ret

对比两段反汇编代码可以看到,理论上说后一段代码的执行速度会是前一段的8倍,实际测试表明后一段的确快很多,数据长度不同时加速比不一样,不过没有达到8倍,其原因应该和Cache有关,现代主流CPU中均有Cache,所以第一段代码也不是每次都会去读取内存的,之前读到的数据会存在于Cache中,后续访问的速度会比读取内存快很多。

memcpy2为了说明主要问题,假设n是8的整数倍,然而对于实际使用的函数而言,显然不能做这个假设,此时的处理方法是最后来复制n % 8个字节,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void * memcpy3(void * dest, const void * src, size_t n) {
long long * psrc, *pdest;
psrc = (long long *)src; pdest = (long long *)dest;
n /= 8;
size_t m = n % 8;
for (size_t i = 0; i < n; i++) {
*pdest = *psrc;
pdest++; psrc++;
}
char * psrc2, *pdest2;
psrc2 = (char *)psrc; pdest2 = (char *)pdest;
for (size_t i = 0; i < m; i++) {
*pdest = *psrc;
pdest++; psrc++;
}
return dest;
}

此时的汇编代码类似memcpy1memcpy2的混合体,此处从略。

另一个问题是,之前也提到,内存的读写最好以对齐的方式进行,不过我实际测试了下对于memcpy3来说,srcdest是不是对齐的影响并不大,特别是数据量比较大的时候。这个应该也与Cache机制有关。当然,这是对于x86架构来说的,对于ARM架构而言,地址是强制要求对齐的,好像不对齐的话会出现错误。

更多优化

实际的标准库memcpy函数的实现要复杂的多,主要还要考虑以下一些问题:

  • 使用SIMD指令集,如SSE2,SSSE3,AVX2等;
  • 考虑缓存预取问题(Cache Prefetch);
  • 考虑地址对齐问题;

相关讨论可以参考这个知乎帖子:

怎样写出一个更快的 memset/memcpy?

关于预取(Prefetch)技术的优化技巧,可参考ARM公司的这篇文章:

Using Block Prefetch for Optimized Memory Performance

最后,实际最新版的Glibc 2.26中memcpy的代码是用汇编写的,对于x86_64架构使用了SSSE3指令集优化,代码长达3000余行……列在最后以表达下对技术大佬的膜拜……

memcpy-ssse3.S