谈谈memcpy函数的优化(纯C)

  • Post author:
  • Post category:其他

在使用C语言编程时,我们常用memcpy来复制内存数据,但很少有人会关注到memcpy怎么实现。最简单的memcpy功能实现如下:

void *low_memcpy(void *dst, const void *src, size_t length)
{
    char *srcp = (void*)src;
    char *dstp = (void*)dst;
    char *tail = srcp + length;
    
    while(srcp < tail) *dstp ++ = *srcp ++;
    
    return dst;
}

一.数据对齐

这通常是一个初学者的实现,满足memcpy的功能,但性能非常低,因为while()每一次循环只能复制一个字节。如果要进一步的优化,就需要用到更多的知识,例如CPU位宽、数据对齐、时钟周期等等,学过计算机原理应该知道CPU字长、寄存器位宽等概念。现在常见的CPU通常为32/64位,今天我们以32位CPU来讲解。32位CPU字长为32BIT,即它的每个通用寄存器包含32个位,占4个字节,一个内存访问周期可以完成4个字节的读写,如果按照low_memcpy()函数的实现,每次while()循环只能复制1个字节,会浪费大量的内存访问周期。那我们能否按照32位CPU位宽,即4个字节为单位进行内存复制呢?CPU从内存取数据的过程,了解的人都知道,对齐存放的数据可加快CPU处理的速度,因为在同一个时钟周期内,CPU访问的数据总是按32位对齐访问的。例如CPU寄存器从内存0x20000001开始取32位数据需要两次访问内存:第一次取3字节0x20000001~0x20000003,第二次取1字节0x20000004。但是,如果从0x20000008开始取32位数据则可以一次性全部取出。

参考上图,如果需要按对齐方式将0x20000001到0x2000002C中总共48字节的数据复制到0x20000041、0x20000082,0x200000C3,0x20000104,0x20000145,0x2000019A等几个目标位置,复制过程包括哪些步骤呢?

从0x20000001到0x20000041:先按字节复制前3个字符,需要循环3次,再按4字节对齐复制0x20000004到0x2000002B之间的数据,共需要循环10次,最后一个字节复制1次,共计14次内存访问。

从0x20000001到0x20000082:因为源和目标无法同时对齐,只能按照字节复制,需要访问内存48次,为什么源和目标必须对齐呢?假设复制到0x20000004时源正好对齐到4字节,但是此时该地址的数据将被复制到0x20000085,但目标地址并不对齐。

从0x20000001到0x200000C3:因为源和目标无法同时对齐,只能按照字节复制,需要访问内存48次。

从0x20000001到0x20000100:因为源和目标无法同时对齐,只能按照字节复制,需要访问内存48次。

从0x20000001到0x20000145:先按字节复制前3个字符,需要循环3次,再按4字节对齐复制0x20000004到0x2000002B之间的数据,共需要循环10次,最后一个字节复制1次,共计14次内存访问。

从0x20000001到0x2000019A:因为源和目标无法同时对齐,只能按照字节复制,需要访问内存48次。

通过上述分析,我们发现:

1.如果数据能够对齐,访问内存的次数只有单字节复制的1/3,即性能提升接近3倍。

2.在32位机上源和目标对4取模的结果一致才能对齐。

二.指令流水线

除了数据对齐外,是否能从CPU指令流水线方面作出一些优化呢?指令流水线的作用是将一条指令分割成多个步骤,并由不同的部件顺序完成,在同一时刻,每个部件可以同时执行多个指令的不同步骤,尽可能保证每个时钟周期都能输出一条指令结果。如果你了解指令流水线应该明白,跳转指令将导致控制冒险,C语言中的if{}else{};while();for(;;){};以及switch case都将可能生成跳转指令。那么,如何避免或减少控制冒险呢?增加循环中的代码量可以减少控制冒险。

int a1[ARRAY_COUNT] = { 0xff };
int a2[ARRAY_COUNT] = { 0x00 };

void test1(void)
{
    int i;

    for (i = 0; i < ARRAY_COUNT; i++)
    {
        a2[i] = a1[i];
    }
}

void test2(void)
{
    int i;

    for (i = 0; i < ARRAY_COUNT/8; i+=8)
    {
        a2[i + 0] = a1[i + 0];
        a2[i + 1] = a1[i + 1];
        a2[i + 2] = a1[i + 2];
        a2[i + 3] = a1[i + 3];
        a2[i + 4] = a1[i + 4];
        a2[i + 5] = a1[i + 5];
        a2[i + 6] = a1[i + 6];
        a2[i + 7] = a1[i + 7];
    }
}

例如以上代码,test1和test2的目的都是将a1复制到a2,但是test1会执行64次循环,每次循环都将导致控制冒险,而test2仅有8次循环,控制冒险减少为8次。除此之外,test1执行过程中CPU需要执行的指令数量比test2至少多56条比较和跳转指令,共计112条指令。

3.优化结果

废话少说,直接上代码:

/*
 *    Copyright(C) 2013-2015, Fans-rt development team.
 *
 *    All rights reserved.
 *
 *    This is open source software.
 *    Learning and research can be unrestricted to modification, use and dissemination.
 *    If you need for commercial purposes, you should get the author's permission.
 *
 *    date           author          notes
 *    2014-09-07     JiangYong       new file
 */
#include <config.h>
#include <debug.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <sys/types.h>

void *fast_memcpy(void *dst, const void *src, size_t length)
{
    union{
        char *lpstr;
        uint32_t *lpint;
    }s;
    union{
        char *lpstr;
        uint32_t *lpint;
    }d;
    
    char *suffix = (void*)(((uint32_t)src) + length);
    char *prefix = (void*)(((uint32_t)src) & (~(sizeof(uint32_t)-1)));
    uint32_t *middle = (void*)(((uint32_t)suffix) & (~(sizeof(uint32_t)-1)));

    
    s.lpstr = (void*)src;
    d.lpstr = (void*)dst;
    
    if (prefix != src)
    {
        while(s.lpstr < prefix + sizeof(uint32_t))
        {
            *d.lpstr++ = *s.lpstr ++;
        }
    }

    while(s.lpint < middle - (sizeof(uint32_t) * 8))
    {
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
    }

    while(s.lpint < middle - (sizeof(uint32_t) * 4))
    {
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
    }

    while(s.lpint < middle - (sizeof(uint32_t) * 2))
    {
        *d.lpint++ = *s.lpint ++;
        *d.lpint++ = *s.lpint ++;
    }

    while(s.lpint < middle) *d.lpint++ = *s.lpint ++;
    while(s.lpstr < suffix) *d.lpstr++ = *s.lpstr ++;

    return dst;    
}

void *memcpy(void *dst, const void *src, size_t length)
{
    if ((((uint32_t)src) & (~(sizeof(uint32_t)-1))) != (((uint32_t)dst) & (~(sizeof(uint32_t)-1))))
    {
        char *lpSrc = (void*)src;
        char *lpDst = (void*)dst;
        char *lpTail = lpSrc + length;
        
        while(lpSrc < lpTail) *lpDst ++ = *lpSrc ++;
        
        return dst;
    }
    
    return fast_memcpy(dst, src, length);
}

 

 


版权声明:本文为sevek82原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。