龙芯版memcpy 的实现

comcat

memcpy 是为最常用之函数，对其性能优化很有意义。

1. 概述

memcpy 所做的操作是把内存中的一块数据复制到内存的另一个地方，也就是内存到
内存的数据拷贝，这个过程需要CPU的参与，即：先从内存取数据到CPU的寄存器，然
后再从寄存器写到内存中。可以用类似如下C 代码实现：

char *dest = (char *)to;
char *src = (char *)from;
int i = size -1;

while(i >= 0)
{
        *(dest + i) = *(src + i);
        i--;
}

这个在size 比较小时，性能尚可。倘若size 很大，这种每次取一个字节的方式，远
没有充分发挥CPU的数据带宽。作为一种改进方式，我们可以每次取4个字节进行写入，
不足4字节的部分，依然每次取一个字节写入：

int *dest = (int *)to;
int *src = (int *)from;

int word_num = size/4 - 1;

int slice = size%4 - 1;

while(word_num >= 0)
{
        *dest= *src;
        dest += 4;
        src += 4;
        word_num--;
}

while(slice >= 0)
{
        *((char *)dest + slice) = *((char *)src + slice);
        slice--;
}

上面这个就是 memcpy 优化的基本思想。

龙芯2E因为是64位，可以使用ld指令，每次取8个字节写入目标地址。

上面的例子，为了说明问题的方便，没有考虑指针的是否对齐。因为不对齐访问会触发
异常，所以使用汇编码写高性能 memcpy 时，对指针是否对齐要分情况予以周密的处理。
        

2. glibc 对memcpy的优化分析

先看看glibc 对memcpy的实现。


     1        #include <endian.h>
     2        #include <sys/asm.h>
     3        #include "regdef.h"


     4        /* void *memcpy(void *dest, const void *src, size_t n);
     5           a0 <--- dest;  a1 <--- src;  a2 <--- n        
     6         */


     7                .global        memcpy
     8                .ent        memcpy

     9        memcpy:
    10                .set        noreorder
    11                .set        mips3

    12                slti        t0, a2, 16                        # 小于16字节，则跳转到last16处，由其进行处理
    13                bne                t0, zero, last16
    14                move        v0, a0                         # 目标指针作为返回值写入v0，注意此指令位于延迟槽中

    15                xor                t0, a1, a0               # 都对齐，或者都不对齐（低3位相同）
    16                andi        t0, 0x7
    17                bne                t0, zero, shift        # 低3位不相同，则跳转。则肯定有一个不对齐，或者都不对齐（低3位不同）
    18                subu        t1, zero, a1

    19                                                                   # 都对齐，或者都不对齐（低3位相同）
    20                andi        t1, 0x7                          # t1 的值实际上为 8 - (a1 & 0x7)，即a1 加上 t1 就对齐了。
    21                beq                t1, zero, chk8w     # a1 aligned, then branch

    22                subu        a2, t1                                
                                                               # 不跳转则 a1 不对齐，此时 a0 肯定不对齐，而且他们的低3位相同
    23                ldr                t0, 0(a1)                   # 把低 t1 个字节，使用非对齐访问指令特别照顾
    24                addu        a1, t1                            # 指针前移，a1 对齐矣        
    25                sdr                t0, 0(a0)                  # 把低 t1 个字节，写到 a0 开始处的 t1 字节的空间里
    26                addu        a0, t1                            # 指针前移，a0 对齐矣

    27        chk8w:
    28                andi        t0, a2, 0x3f                    # t0 = a2 % 64
    29                beq                t0, a2, chk1w          # 小于 64 字节则跳转到chk1w
    30                subu        a3, a2, t0                      # a3 = a2 / 64
    31                addu        a3, a1                            # a3 = end address of loop
    32                move        a2, t0                           # a2 = what will be left after loop，是为不足64字节部分
    33        lop8w:        
    34                ld                t0, 0(a1)                     # 每次循环处理64个字节
    35                ld                t1, 8(a1)
    36                ld                t2, 16(a1)
    37                ld                t3, 24(a1)
    38                ld                ta0, 32(a1)
    39                ld                ta1, 40(a1)
    40                ld                ta2, 48(a1)
    41                ld                ta3, 56(a1)
    42                addiu        a0, 64                                # 指针前移 64 字节
    43                addiu        a1, 64                                # 同上
    44                sd                t0, -64(a0)
    45                sd                t1, -56(a0)
    46                sd                t2, -48(a0)
    47                sd                t3, -40(a0)
    48                sd                ta0, -32(a0)
    49                sd                ta1, -24(a0)
    50                sd                ta2, -16(a0)
    51                bne                a1, a3, lop8w
    52                sd                ta3, -8(a0)

    53        chk1w:
    54                andi        t0, a2, 0x7                            # 8 or more bytes left?
    55                beq                t0, a2, last16                 # less than 8 bytes, then jump to last16
    56                subu        a3, a2, t0                             # Yes, handle them one dword at a time
    57                addu        a3, a1                                  # a3 again end address
    58                move        a2, t0
    59        lop1w:
    60                ld                t0, 0(a1)
    61                addiu        a0, 8
    62                addiu        a1, 8
    63                bne                a1, a3, lop1w
    64                sd                t0, -8(a0)

    65        last16:                                                           # 可改进
    66                blez        a2, lst16e                                # Handle last 16 bytes, one at a time
    67                addu        a3, a2, a1                              # a3 为终止标志
    68        lst16l:
    69                lb                t0, 0(a1)
    70                addiu        a0, 1
    71                addiu        a1, 1
    72                bne                a1, a3, lst16l
    73                sb                t0, -1(a0)
    74        lst16e:
    75                jr        ra                                                  # Bye, bye
    76                nop

    77        shift:                                                               
    78                subu        a3, zero, a0                            # a1 不对齐，a0 可能对齐，可能不对齐
    79                andi        a3, 0x7                                    #  (unoptimized case...)
    80                beq                a3, zero, shft1                  # a0 对齐，a1 不对齐，则跳转到shft1处

    81                                                                               # 此时 a0不对齐，a1 未知，且低3位不同
    82                subu        a2, a3                                      # a2 = bytes left
    83                ldr                t0, 0(a1)                              # Take care of first odd part
    84                ldl                t0, 7(a1)
    85                addu        a1, a3
    86                sdr                t0, 0(a0)
    87                addu        a0, a3                                       # 到这里，a0 对齐了，a1 反正也不想使其对齐

    88        shft1:                                                               # 此种情况亦可添加 64 字节为单位的处理块
    89                andi        t0, a2, 0x7
    90                subu        a3, a2, t0                                  # a3 为8的倍数
    91                addu        a3, a1                                       # a3 = end address of loop
    92        shfth:
    93                ldr                t1, 0(a1)                               # Limp through, dword by dword
    94                ldl                t1, 7(a1)
    95                addiu        a0, 8
    96                addiu        a1, 8
    97                bne                a1, a3, shfth
    98                sd                t1, -8(a0)
    99                b                last16                                     # Handle anything which may be left
   100                move        a2, t0

   101                .set        reorder
   102                .end        memcpy


下面详细分析之：

1. 12-14行，首先对要复制的数据大小进行判断，小于 16 字节的直接跳转到 last16 处进行处理。

2. 15-17行，在于区分 dest 与 src 指针对齐的情况。两者低 3 位相同（异或为0），则要么都对齐，
   要么都不对齐，这两种情况可以合并起来处理。若两者低 3 位不同（异或不为0），则肯定有一个
   不对齐，或者都不对齐，这种情况要跳转到 shift 处去处理。

3. 18-21行，对 dest 和 src 都对齐或都不对齐的情况予以区分，因为二者对齐情况相同，故而只判断
   a1 的情况即可。如果 a1 对齐，则直接跳转到 chk8w 处，先以 8 字节为单位，取数据写入之。
   注意 18 行执行完了，t1 中是 -a1 的补码，等价于 ~a1 + 1，只有 a1 低 3 位都为 0 时，t1 的低
   3 位才都为 0。

4. 22-26行，处理 dest 和 src 都不对齐的情况。注意此时 dest 与 src 的低 3 位是相同的。直接使用
   非对齐访问指令，获取 t1 个字节，写入目的地。则 dest 与 src 就可以跨到第一个对齐地址处(dest
   +t1, src+t1)，此后的处理方式就和对齐的指针一样了。

5. 27-52行，处理数据块大于64字节的情况，每次循环写入 64 字节的数据。a0，a1，a2 同步移动，该
   程序块运行后，不足64字节部分交由 chk1w 处理。

6. 53-64行，处理数据块小于64字节的情况，每次循环写入 8字节。a0，a1，a2 同步移动。经其处理后，
   不足8字节部分，则交由 last16 开始的程序块处理。

7. 65-76行，以字节为单位写入数据。负责处理最后的16字节。可以将循环展开，优化之。

8. 78-80行，判断 a0 是否对齐，对齐则跳转到 shft1 处执行。

9. 81-87行，使a0对齐。

10. 88-100行，以8字节为单位，处理 a0 对齐，a1不对齐的情况。不足 8 字节的部分，交由 last16 处理。

注意 77-100 行这一块，是对a0，a1低3位不同的情况进行的处理。当a0，a1低3位不同时，可能有以下几
种情况：

I. a0 对齐，a1 不对齐
II. a0 不对齐，a1 不对齐（低3位不同）
III. a0 不对齐，a1 对齐

特别留意一下，其对第三种情况的处理，是首先将其转化为第一种情况，然后再对其进行处理的。

对第二种情况的处理也是这样的。



3. 针对龙芯的改进

A. 短循环展开

该改进的思想来源于前段时间的代码分析，参见《龙芯汇编语言的艺术》

65-73 行负责处理小于16字节的部分，可以展开成如下代码：

        last16:
                blez        a2, 2f
                addiu        a2, a2, -1
                sll                a2, a2, 2                                        # a2 <-- a2 * 4

                la                a3, 1f
                subu        a3, a3, a2

                lb                $15, 0(a1)

                jr                a3
                  addiu a3, 2f-1f
               
                lb                $16, 15(a1)
                lb                $17, 14(a1)
                lb                $18, 13(a1)
                lb                $19, 12(a1)
                lb                $20, 11(a1)
                lb                $21, 10(a1)
                lb                $22, 9(a1)
                lb                $23, 8(a1)
                lb                $8, 7(a1)
                lb                $9, 6(a1)
                lb                $10, 5(a1)
                lb                $11, 4(a1)
                lb                $12, 3(a1)
                lb                $13, 2(a1)
                lb                $14, 1(a1)
        1:        jr                a3
                  sw    $15, 0(a0)
               
                sb                $16, 15(a0)
                sb                $17, 14(a0)
                sb                $18, 13(a0)
                sb                $19, 12(a0)
                sb                $20, 11(a0)
                sb                $21, 10(a0)
                sb                $22, 9(a0)
                sb                $23, 8(a0)
                sb                $8, 7(a0)
                sb                $9, 6(a0)
                sb                $10, 5(a0)
                sb                $11, 4(a0)
                sb                $12, 3(a0)
                sb                $13, 2(a0)
                sb                $14, 1(a0)
        2:  jr                ra
                nop

注意：16~23 号寄存器，使用前需保存，完了要恢复。


B. 细化各种情况

81行处，当a0不对齐，a1对齐时，可直接对a1使用对齐访问，a0使用不对齐访问

这样会减少82-87行的6条指令，多一条分支判断语句。

这样，取数据使用对齐访问指令，写数据使用非对齐访问指令对，效率应该和取数据使用非对齐访问指令对(93,
94 行)，写数据使用对齐访问指令相当(97 行)。

这个改进的效率提升估计不会明显，需要大量测试确认


C. 提升不对齐时大块数据复制的效率

原有实现当检测到a0、a1都不对齐时（低3位不同），将a0整对齐后，直接以8字节为单位，复制数据（见92-98行）
这个应该亦可以引入先以64字节为单位复制数据，然后再进入以8字节为单位的处理流程，这个应该可以提升大快数据复制时的效率，
目前这个也是猜想，需要进一步的大量测试。


注： 这个算手稿，目前只测试了last16处短循环展开的改进，功能正确，效率尚未评测。测试程序见附件，2个文件 godson_memcpy.S
mem_test.c ，如下命令编译之：

gcc godson_memcpy.S mem_test.c -o mtest

./mtest 看输出是否正确



[ 本帖最后由 comcat 于 2007-5-9 06:55 PM 编辑 ]

comcat

逻辑关系有点复杂，过段时间加张图吧

冲天飞豹

不知道修改进glibc能导致多少性能的提高

comcat

这个我过几天测试看看

胶林探索

program MOVE_TST;
const
  s_length = 60;
//  s1: string[s_length] = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
//  s2: string[s_length] = '12345678902234567890323456789042345678905234567890';
  s1: array[0..s_length] of char = '4abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'#0;
  s2: array[0..s_length] of char = '212345678902234567890323456789042345678905234567890'#0;

var
  s3: string[s_length];
  i: integer;

procedure Move(const source;var dest;count:longint);assembler;
  asm
    # count <= 0 ?
    ble $6,$0,.Lmoveexit
    nop

    # source = dest ?
    beq $4,$5,.Lmoveexit
    nop

    # possible overlap?
    bgt $4,$5,.Lnopossibleoverlap
    nop
    # source < dest ....
    add $7,$6,$4
    # overlap?
    # source+count < dest ?
    blt $7,$5,.Lnopossibleoverlap
    nop

  .Lcopybackward:
    # check alignment of source and dest
    or $2,$4,$5

    # move src and dest to the end of the blocks
    # assuming 16 byte block size
    addiu $3,$6,-1
    add $4,$4,$3
    add $5,$5,$3

    b .Lmovebytewise
    li $3,-1

.Lnopossibleoverlap:

    # check alignment of source and dest
    or $2,$4,$5

    # everything 16 byte aligned ?
    andi $13,$2,15

    beq $13,$0,.Lmovetwordwise
    # load direction in delay slot
    li $3,16


    andi $13,$2,7
    beq $13,$0,.Lmoveqwordwise
    li $3,8

    andi $13,$2,3
    beq $13,$0,.Lmovedwordwise
    li $3,4

    andi $13,$2,1
    beq $13,$0,.Lmovewordwise
    li $3,2
    b .Lmovebytewise
    li $3,1

.Lmovetwordwise:
    srl $13,$6,4
    sll $14,$13,4
    beq $14,$0,.Lmoveqwordwise_shift
    nop

.Lmovetwordwise_loop:
    lw $9,0($4)
    lw $10,4($4)
    addiu $13,$13,-1
    lw $11,8($4)
    lw $12,12($4)
    addu $4,$4,$3
    sw $9,0($5)
    sw $10,4($5)
    sw $11,8($5)
    sw $12,12($5)
    addu $5,$5,$3
    bne $13,$0,.Lmovetwordwise_loop
    nop
    subu $6,$6,$14
    beq $6,$0,.Lmoveexit
    nop

.Lmoveqwordwise_shift:
    sra $3,$3,1

.Lmoveqwordwise:
    srl $13,$6,3
    sll $14,$13,3
    beq $14,$0,.Lmovedwordwise_shift
    nop

  .Lmoveqwordwise_loop:
    lw $9,0($4)
    lw $10,4($4)
    addiu $13,$13,-1
    add $4,$3,$4
    sw $9,0($5)
    sw $10,4($5)
    add $5,$3,$5
    bne $13,0,.Lmoveqwordwise_loop
    nop

    subu $6,$6,$14
    beq $6,$0,.Lmoveexit
    nop

  .Lmovedwordwise_shift:
    sra $3,$3,1

  .Lmovedwordwise:
    srl $13,$6,2
    sll $14,$13,2
    beq $14,$0,.Lmovewordwise_shift
    nop

  .Lmovedwordwise_loop:
    lw $9,0($4)
    addiu $13,$13,-1
    addu $4,$4,$3
    sw $9,0($5)
    addu $5,$5,$3
    bne $13,$0,.Lmovedwordwise_loop
    nop

    subu $6,$6,$14
    beq $6,$0,.Lmoveexit
    nop

  .Lmovewordwise_shift:
    sra $3,$3,1
  .Lmovewordwise:
    srl $13,$6,1
    sll $14,$13,1
    beq $14,$0, .Lmovebytewise_shift
    nop

  .Lmovewordwise_loop:
    lhu $9,0($4)
    addiu $13,$13,-1
    add $4,$4,$3
    sh $9,0($5)
    add $5,$5,$3
    bne $13,$0,.Lmovewordwise_loop
    nop

    subu $6,$6,$14
    beq $6,$0, .Lmoveexit
    nop

  .Lmovebytewise_shift:
    sra $3,$3,1
  .Lmovebytewise:
    beq $6,$0, .Lmoveexit
    nop

    lbu $9,0($4)
    addiu $6,$6,-1
    add $4,$4,$3
    sb $9,0($5)
    add $5,$5,$3
    bne $6,$0,.Lmovebytewise
    nop
  .Lmoveexit:
end;

胶林探索

上面是我参考FPC库写的。

冲天飞豹

原帖由 comcat 于 2007-5-9 06:56 PM 发表
这个我过几天测试看看

这样好，期待结果

我很支持把glibc中的常用函数为龙芯优化，这样系统性能的提高应该是能体会出来的。

胶林探索

我将把宝压在FPC上，反正优化后是不可移植的，将会为FPC写一个后端优化程序。
FPC pk GCC

jamesr

我当时写MMI_memcpy时就理解了好久！觉得楼主的memcpy的效率要更高，实际比较也是这样。结果如下：
200000000 packs in total, doing test below:
npackcopy: 20 packs each time:1.776941  900423818.235946 bytes/sec
godson2e_memcpy: 20 packs each time:1.435169     1114851282.322848 bytes/sec
npackcopy: 20000 packs each time:2.323451       688630834.048146 bytes/sec
godson2e_memcpy: 20000 packs each time:2.307875  693278448.789471 bytes/sec
尚不知如何把空间分配到不对齐的地方，所以以上的测试都是8字节对齐的情况下得到。第二个测试结果十分接近，我的比较慢的原因是多一次函数调用的开销（npackcopy调用我的MMI_memcpy）。第一个测试比较慢的原因大概就是楼主的优化吧！当然以上结果都比原来系统自带的memcpy快20％到50％。

以下是我的MMI_memcpy和系统自带的比较：
200000000 packs in total, doing test below:
npackcopy: 20 packs each time:1.772236  902814297.870035 bytes/sec
memcpy: 20 packs each time:1.994866     802058885.158201 bytes/sec
npackcopy: 20000 packs each time:1.787341       895184522.707195 bytes/sec
memcpy: 20000 packs each time:2.549109  627670295.777858 bytes/sec

[ 本帖最后由 jamesr 于 2007-5-9 07:32 PM 编辑 ]

jamesr

测试结果有偶然性，但两性能差距是相同的，多次测试结果显示：性能都是godson2e_memcpy>MMI_memcpy>memcpy