Memcpy优化

出自龙芯梦兰知识库

跳转到: 导航, 搜索

memcpy是常用热点C函数之一,下面我们通过一个memcpy优化实例,展示loongson 3A平台上的优化过程。

目录

What we have

loongson 3A
一个4核CPU,指令集兼容mips64r2,并加入了龙芯指令扩展。本优化就是围绕着龙芯扩展的16字节load/store指令 -- gslq/gssq
memcpy
函数原型为void *memcpy(void *dest, const void *src, size_t size),其中总是返回dest,并其n可以取值为0。

The plan

对于mips而言,一次处理宽数据的指令,通常对齐情况也必须是同等的要求。例如:

对于地址非对齐状况,则借助单字节load/store指令或者非对齐访存指令,此时效率较差:


对于memcpy而言,其工作模型为每次拷贝x字节,循环拷贝完全部数据:

如此,memcpy的效率与destsrc的对齐情况相关。然而这种相关性可以减弱从而提升效率 —— 先拷贝部分数据后,提高destsrc的对齐情况,从而可以使用高位宽的访存指令。

例如:dest=0x5f0004,src=0x5f0c14,两个地址均是4字节对齐的,据前述只能使用4字节宽度的对齐访存指令。然而,通过先拷贝12字节数据,此时dest和src“前进”到了0x5f0010与0x5f0c20,变成了16字节对齐的两地址,可以使用16字节宽度的访问指令。

通过数学推导可知,对于任意两地址,其除16得余数a,b,假设a = MAX(a,b)且b != 0,则a对应的地址可以“升级”到16字节对齐,而余数差“a-b”中2因子个数则决定另一地址升级后的对齐情况。


于是,优化后的模块结构如下图所示:

Memcpy-from-patent-file.jpg

Prepare

开发前准备工作:

为了便于应用和调试,这里我们将优化代码单独编译成一个库,并使用preload机制来加载:

上述方法的限制是:

memcpy.S

memcpy.S: git


memcpy函数原型在MIPS ABI规范中对应如下:

void * memcpy( void *dest, const void *src, size_t n )
v0 a0 a1 a2

入口

memcpy:
    /* if less then 0x36 bytes */
    sltiu   t2, a2, 0x36
    addiu   t8, jp, _memcpy_less_0_base-memcpy
    bnez    t2, _memcpy_less
    or      v0, a0, zero

首先,memcpy的三个参数,依照MIPS ABI,分别在寄存器a0(dest)、a1(src)和a2(size),返回值存于v0寄存器。

入口代码首先判断memcpy的长度是否满足临界值54字节,如太少则转入_memcpy_less。 留意两处:

模块A:非对齐拷贝模块

非对齐拷贝模块,用于拷贝少量字节。最简单的实现是使用单字节访存指令lb/sb。此处我们进一步优化,使用8字节非对齐访存指令ldl/ldr、sdl/sdr。

由于此处拷贝长度限制为54字节,因此我们可以把指令全部写出来。注意,每组访存搬运8字节数据,而实际拷贝的字节数可能不是8字节的整数倍。因此我们将拷贝长度按照除8的余数,分成若干个代码块,用于处理各种余数情形。

下图展示了拷贝9个字节的过程:在除8余1的代码块base上,计算合适的偏移,最终分解为一个8字节的非对齐拷贝 + 1字节拷贝。

图:9字节拷贝示意 Unaligned copy.png

如何使用模块A? _memcpy_less例子

_memcpy_less分支在拷贝字节数较少进入。目的是忽略多余计算,直接用模块A来完成拷贝。

模块A的“接口”如下表:

模块 模块入口 拷贝长度 拷贝完后dest的位置 拷贝完后src的位置 拷贝完后跳转的位置
非对齐拷贝(模块A 多个入口 由入口决定! a0 a1 ta3

下面主要进行上述参数的计算,其中模块A的入口地址存在t0寄存器中:

_memcpy_less:
    /* t0 = a2 % 8,长度除8的余数 */
    andi    t0, a2, 0x7

    /* a0 += a2, a0是拷贝完成后,dest所前进到的位置 */
    addu    a0, a0, a2

    /* 处理各种余数的代码块长度故意统一128字节 */
    /* t1 = t0 * 128 即是当前余数对应代码块的偏移量 */
    sll     t1, t0, 0x7

    /* t2 = 拷贝长度减掉余数,等效的C代码为“t2 = (a2 / 8) * 8” */
    subu    t2, a2, t0

    /* a1 += a2,a1是拷贝完成后,src所前进到的位置 */
    addu    a1, a1, a2

    /* t2 = t2 * 2,完成一次8字节搬运,需要4条指令,即4 * 4B = 16B。
     * 即拷贝t2长度的数据,需要2 * t2长度的指令流,用于计算代码块内的偏移
     */
    sll     t2, t2, 0x1

    /* 此处t8是老早在memcpy入口处计算的_memcpy_less_0_base内存地址
     * t8 + t1 = 对应余数的代码块“入口” —— _memcpy_less_N_base,详见下图
     */
    addu    t0, t8, t1

    /* _memcpy_less_N_base指示了m次8字节拷贝的结束
     * 由此向前偏移t2字节,则是m次8字节拷贝的入口地址
     * 参见前述9字节拷贝的示意图
     */
    subu    t0, t0, t2
    jr      t0
    or      ta3, ra, zero  /* 延时槽:将函数返回地址放到ta3寄存器中,
                            * ta3寄存器即o32下的t3寄存器;n32/n64下的a7寄存器。
                            */

图:处理各个余数的代码块的布局 Memcpy-unaligned-blocks.png

非对齐拷贝

以余数为1的代码情形为例:

_memcpy_less_1:
    ...
    ldl     ta2, -0x0a(a1)
    ldr     ta2, -0x11(a1)
    sdl     ta2, -0x0a(a0)
    sdr     ta2, -0x11(a0)
    gsldlc1 $f4, -0x02(a1)
    gsldrc1 $f4, -0x09(a1)
    gssdlc1 $f4, -0x02(a0)
    gssdrc1 $f4, -0x09(a0)
_memcpy_less_1_base:
    lbu     ta0, -0x01(a1)
    jr      ta3
    sb      ta0, -0x01(a0)

    _MEMCPY_ALIGN_SPACE(1, 2)
_memcpy_less_2:

注意到使用了两条访存通路,实测此方式能够戏剧般地改善访存。

最后,_MEMCPY_ALIGN_SPACE(1,2)这个宏主要是确保相邻的两个_memcpy_less_N_base间距为128字节,这通过在代码块结尾填充0来实现的。

模块B:升级中各参数计算模块

该模块的一个主要工作是计算出“升级”后的对齐状况。对于访存宽度最大为16字节的处理器而言,按照dest_src形式列出“升级”后的对齐状况:16_1、16_2、16_4、16_8、16_16、1_16、2_16、4_16、8_16

其中对于16_1对齐状况,既可以用lb + gslq,也可以用ldl/ldr + gslq;具体取舍要参考性能上的表现。

经过测试,我们将16_1与16_2合并为16_1_2;将1_16、2_16和4_16合并成4_2_1_16。

在具体实现上,我们将dest_src编码成一个索引数。而对应的各个入口地址则放入一张表中。通过索引数来访问表项,从而得到对应代码块的入口。

dest_src到索引数的编码规则为:[ 高1位: x_16还是16_x形式] + [ 低3位: log2 x ]


在memcpy中,对齐多字节拷贝各个代码块的入口表如下:

    .type   _memcpy_loop_entries, @object
    .size   _memcpy_loop_entries, 52  /* 4*(10 + 3)Bytes */
_memcpy_loop_entries:
    .word   _memcpy_16_1_2   /* 16_1 */
    .word   _memcpy_16_1_2   /* 16_2 */
    .word   _memcpy_16_4
    .word   _memcpy_16_8
    .word   _memcpy_16_16
    .space  12               /* padding 12B space */
    .word   _memcpy_4_2_1_16 /* 1_16 */
    .word   _memcpy_4_2_1_16 /* 2_16 */
    .word   _memcpy_4_2_1_16 /* 4_16 */
    .word   _memcpy_8_16
    .word   _memcpy_16_16

注意到该表在代码段而不是数据段中。这样作对表的访问只需通过代码段内的偏移,若放到数据段,对PIC代码而言需要借助GOT表。有关更多信息,参见 How To Write Shared Libraries, Ulrich Drepper

计算dest_src对齐状况,及其对应的对齐多字节拷贝代码入口地址

    andi    t0, a0, 0xf     /* dest: 取除16的余数 */
    andi    t1, a1, 0xf     /* src: 取除16的余数 */
    /* index (bit 2-0) */
    subu    t2, t0, t1      /* 余数差 */
    ori     t2, t2, 0x10    /* 处理余数差为0的情况,确保尾部连续零的个数不超过4 */

    /* 余数差中2因子的个数,实际上就是二进制形式下尾部(低位)连续的零的个数
     * 因此,如果有计数结尾连续零的指令(例如X86下的bsr指令)则一条指令完成
     * 然而,在龙芯3A上并没有如此指令,因此用一组指令来完成。主要是借助clz(counting leading zeros)指令。
     * clz计数开头(高位)连续零,其换算公式为:
     * ctz(x) = reg_width - 1 - clz(x & (-x))
     */
    subu    ta1, zero, t2   /* 取相反数 */
    and     t2, t2, ta1     /* 余数差与之相反数进行按位与运算,产生形如
                             * "00000000000000000000000000001000"的二进制数,
                             * 之后用clz计算开头连续零个数,并用总位宽-1 减去即得
                             * 尾部连续零的个数
                             */
    ori     ta1, zero, 0x1f /* 总位宽-1:31 */
    clz     t2, t2
    /* 插入两条酱油指令:为了快速处理任一余数为0情形(即跳过“升级”步骤) */
    /* 余数t0和t1中任一为0,则t3等于t0(此时,t3要么是t0移了0位,要么t0就是0)*/
    sll     t3, t0, t1      
    beq     t3, t0, _memcpy_have_16
    subu    ta3, ta1, t2

    /* 余数差中2因子的个数在上面被计算完毕,作为索引数的低3位
     * 下面是计算索引数的最高一位的
     */
    sltu    ta0, t0, t1

    /* 以下合成索引数 [ ta0最低1位 ] + [ ta3最低3位 ]
     * 用到了mip64r2中的位插入指令,在ta3第3位插入ta0的1位
     */
    .set    arch=mips64r2
    ins     ta3, ta0, 0x3, 0x1
    .set    arch=loongson3a

    sll     ta2, ta3, 2     /* 计算调入口表项的偏移,表项长度为4字节 */
    addiu   t2, jp, _memcpy_loop_entries-memcpy /* PIC代码: jp寄存器记录当前函数地址 */
    /* 龙芯特有的“两地址 + 偏移"装载指令,装载地址为“t2 + ta2 + 0” */
    gsldx   ta3, 0x0(t2, ta2)

至此,ta3寄存器即是对齐多字节拷贝代码块的入口。

其他升级参数的计算

计算升级过程中需要拷贝的字节数,以及其他一些升级参数。

升级过程中需要拷贝的字节数等于“16 - 余数中间较大者“,即16 - max(t1, t0)。代码如下:

    /* 条件复制:t1 = ta0 == 0 ? t0 : t1 */
    movz    t1, t0, ta0
    /* 注意到mips的精简,用与0寄存器的或操作完成立即数装载 */
    ori     t3, zero, 0x10
    subu    t3, t3, t1

此时t3即是升级拷贝过程中需要拷贝的字节数。

下面计算一些边界参数。

    /* 令a0为升级后dest“前进”到的位置 */
    addu    a0, a0, t3
    /* 令a1为升级后src“前进”到的位置 */
    addu    a1, a1, t3
    /* 令t2为升级后剩余待拷贝的字节数 */
    subu    t2, a2, t3

    /* 对齐多字节拷贝(一轮拷16字节),此处计算不足一轮的剩余字节数,存在 a2
     * 这部分将再交由非对齐拷贝模块来完成。
     */
    andi    a2, t2, 0xf
    /* 减去a2后,t2成了对齐多字节拷贝模块需要拷贝的字节数 */
    subu    t2, t2, a2
    /* 令a3为 "升级" + "对齐多字节拷贝“后,src”前进“到的位置 */
    addu    a3, a1, t2

以下计算两次用到模块A的两入口

    /* 计算 升级中,模块A的参数
     * 参见_memcpy_less分支。
     */
    andi    t0, t3, 0x7
    sll     t1, t0, 0x7
    subu    t2, t3, t0
    sll     t2, t2, 0x1
    addu    t0, t8, t1
    subu    ta0, t0, t2

    /* 计算 模块C拷贝后,用模块A拷贝剩余字节所需参数
     * 参见_memcpy_less分支。
     */
    andi    t0, a2, 0x7
    sll     t1, t0, 0x7
    subu    t2, a2, t0
    sll     t2, t2, 0x1
    addu    t0, t8, t1
    /* 跳转到升级中的模块A入口,注意到下一条指令在延时槽中,无条件执行 */
    jr      ta0
    subu    t8, t0, t2

至此,完整拷贝过程中三阶段的模块所需参数计算完毕,如下表:

模块 模块入口 拷贝长度 拷贝后dest的位置 拷贝后src的位置
非对齐拷贝(模块A,升级) ta0 由入口决定! a0 a1
对齐多字节拷贝(模块C) ta3 a3
非对齐拷贝(模块A,剩余拷贝) t8 由入口决定!(a2)

模块C:对齐多字节拷贝模块

模块C的“接口”如下表:

模块 模块入口 拷贝完后剩余字节数 拷贝完前dest的位置 拷贝完后dest的位置 拷贝完前src的位置 拷贝完后src的位置 拷贝完后跳转的位置
对齐拷贝多字节拷贝(模块C 多个入口 a2 a0 a0 + (a3 - a1) a1 a3 t8

以下以“_memcpy_4_2_1_16”情形为例。

在对齐多字节拷贝中,进一步应用了循环展开的优化方式。即在循环中的一轮,进行多次16字节拷贝,这样有助于减少循环涉及的计数指令和分支指令数目。

在我们的实验中,循环中的一轮进行两次16字节拷贝时,效果提升明显。例如,在模块C进行80字节拷贝中:

  1. 计算后并跳转到一轮中的第二次16字节拷贝。即先拷贝16字节。
  2. 剩下的64字节,刚好跑两轮完整的循环。

计算循环展开后的入口

_memcpy_4_2_1_16:
    /* t0为模块C需要拷贝的字节数 */
    subu t0, a3, a1
    /* t0 = t0 % 32,即不满展开后的一轮的余数 */
    andi t0, t0, 0x1f

    /* 余数字节拷贝完成时dest前进到的位置 */
    addu a0, a0, t0

    /* 如果余数不为0, 则直接跳到一轮中的第二次16字节拷贝 */
    bnez t0, _memcpy_4_2_1_16_
    /* 余数字节拷贝完成时src前进到的位置 */
    addu a1, a1, t0

    /* 余数为0,一开始就进行满轮拷贝,此处先读取16字节 */
    gslq    t0, t1, 0x0(a1)

对齐多字节拷贝

_memcpy_4_2_1_16_loop:
    /* 计算一轮32字节拷贝完后,dest和src前进到的位置 */
    /* 此处两条加法指令恰好处于16字节数据装载和存储的中间
     * 因为存储指令依赖装载的寄存器,故在等待间隙加入加法操作
     */
    addiu   a0, a0, 0x20
    addiu   a1, a1, 0x20

    /* 将16字节数据,用两对8字节非对齐存储指令,复制到内存中去 */
    /* 注意:寄存器t0和t1中数据已在入口处或是后面延时槽中读取了 */
    sdl     t0, -0x11(a0)
    sdr     t0, -0x18(a0)
    sdl     t1, -0x19(a0)
    sdr     t1, -0x20(a0)
_memcpy_4_2_1_16_:
    /* 第二次16字节拷贝,此处使用fpu的数据通路,实测有明显提升 */
    /* 16字节读取到fpu的寄存器中 */
    gslqc1  $f4, $f6, -0x10(a1)
    /* 两对8字节的非对齐存储指令,fpu通路 */
    gssdlc1 $f4, -0x01(a0)
    gssdrc1 $f4, -0x08(a0)
    gssdlc1 $f6, -0x09(a0)
    gssdrc1 $f6, -0x10(a0)

    /* 判断拷贝是否结束,这里用到了branch likely类型的指令
     * 这类跳转指令只有在条件成立时才执行延时槽中的指令
     * 注意:此类指令被MIPS标记为即将作废,不赞成使用。此处使用是因为剧情需要。
     */
    bnel    a1, a3, _memcpy_4_2_1_16_loop
    gslq    t0, t1, 0x0(a1)

    /* 为模块A准备处理剩余字节的参数 */
    addu    a0, a0, a2
    addu    a1, a1, a2
    jr      t8
    or      ta3, ra, zero
个人工具
名字空间
变换
动作
导航
工具箱