Copying 80 bytes as fast as possible

Question

I am running a math-oriented computation that spends a significant amount of its time doing memcpy, always copying 80 bytes from one location to the next, an array of 20 32-bit ints. The total computation takes around 4-5 days using both cores of my i7, so even a 1% speedup results in about an hour saved.

By using the memcpy in this paper by intel, I was able to speed up by about 25%, and also dropping the size argument and simply declaring inside seems to have some small effect. However, I feel I am not utilising the fact that my copying operations are always the same size. That said, I can't come up with a better way. Here's what my code looks like atm:

void *memcpyi80(void* __restrict b, const void* __restrict a){
    size_t n = 80;
    char *s1 = b;
    const char *s2 = a;
    for(; 0<n; --n)*s1++ = *s2++;
    return b;
}

Some other things that may be useful for optimization:

1. I use an Intel Core i7-2620M, based on Sandy Bridge. I don't care about portability at all.

2. I only care about the 16 least significant bits of every int. The other 16 are useless to me and are permanently zeroed out.

3. Even though I copy 20 32-bit ints per memcpy invocation, I only care about the first 17. I have added 3 as it helps with alignment and therefore speed.

4. I use GCC 4.6 on Windows 7.

Any ideas?

UPDATE:

I think this is the assembly output (never done this before, there may be more than you need):

memcpyi80:
    pushq   %r12
    .seh_pushreg    %r12
    pushq   %rbp
    .seh_pushreg    %rbp
    pushq   %rdi
    .seh_pushreg    %rdi
    pushq   %rsi
    .seh_pushreg    %rsi
    pushq   %rbx
    .seh_pushreg    %rbx
    .seh_endprologue
    movq    %rdx, %r9
    movq    %rcx, %rax
    negq    %r9
    andl    $15, %r9d
    je  .L165
    movzbl  (%rdx), %ecx
    leaq    -1(%r9), %r10
    movl    $79, %esi
    andl    $7, %r10d
    cmpq    $1, %r9
    movl    $79, %ebx
    leaq    1(%rdx), %r8
    movl    $1, %r11d
    movb    %cl, (%rax)
    leaq    1(%rax), %rcx
    jbe .L159
    testq   %r10, %r10
    je  .L160
    cmpq    $1, %r10
    je  .L250
    cmpq    $2, %r10
    je  .L251
    cmpq    $3, %r10
    je  .L252
    cmpq    $4, %r10
    je  .L253
    cmpq    $5, %r10
    je  .L254
    cmpq    $6, %r10
    je  .L255
    movzbl  (%r8), %r8d
    movl    $2, %r11d
    movb    %r8b, (%rcx)
    leaq    2(%rax), %rcx
    leaq    2(%rdx), %r8
.L255:
    movzbl  (%r8), %ebx
    addq    $1, %r11
    addq    $1, %r8
    movb    %bl, (%rcx)
    addq    $1, %rcx
.L254:
    movzbl  (%r8), %r10d
    addq    $1, %r11
    addq    $1, %r8
    movb    %r10b, (%rcx)
    addq    $1, %rcx
.L253:
    movzbl  (%r8), %edi
    addq    $1, %r11
    addq    $1, %r8
    movb    %dil, (%rcx)
    addq    $1, %rcx
.L252:
    movzbl  (%r8), %ebp
    addq    $1, %r11
    addq    $1, %r8
    movb    %bpl, (%rcx)
    addq    $1, %rcx
.L251:
    movzbl  (%r8), %r12d
    addq    $1, %r11
    addq    $1, %r8
    movb    %r12b, (%rcx)
    addq    $1, %rcx
.L250:
    movzbl  (%r8), %ebx
    addq    $1, %r8
    movb    %bl, (%rcx)
    movq    %rsi, %rbx
    addq    $1, %rcx
    subq    %r11, %rbx
    addq    $1, %r11
    cmpq    %r11, %r9
    jbe .L159
    .p2align 4,,10
.L160:
    movzbl  (%r8), %r12d
    movb    %r12b, (%rcx)
    movzbl  1(%r8), %ebp
    movb    %bpl, 1(%rcx)
    movzbl  2(%r8), %edi
    movb    %dil, 2(%rcx)
    movzbl  3(%r8), %ebx
    movb    %bl, 3(%rcx)
    leaq    7(%r11), %rbx
    addq    $8, %r11
    movzbl  4(%r8), %r10d
    movb    %r10b, 4(%rcx)
    movq    %rsi, %r10
    movzbl  5(%r8), %r12d
    subq    %rbx, %r10
    movq    %r10, %rbx
    movb    %r12b, 5(%rcx)
    movzbl  6(%r8), %ebp
    movb    %bpl, 6(%rcx)
    movzbl  7(%r8), %edi
    addq    $8, %r8
    movb    %dil, 7(%rcx)
    addq    $8, %rcx
    cmpq    %r11, %r9
    ja  .L160
.L159:
    movl    $80, %r12d
    subq    %r9, %r12
    movq    %r12, %rsi
    shrq    $4, %rsi
    movq    %rsi, %rbp
    salq    $4, %rbp
    testq   %rbp, %rbp
    je  .L161
    leaq    (%rdx,%r9), %r10
    addq    %rax, %r9
    movl    $1, %r11d
    leaq    -1(%rsi), %rdi
    vmovdqa (%r10), %xmm0
    movl    $16, %edx
    andl    $7, %edi
    cmpq    $1, %rsi
    vmovdqu %xmm0, (%r9)
    jbe .L256
    testq   %rdi, %rdi
    je  .L162
    cmpq    $1, %rdi
    je  .L244
    cmpq    $2, %rdi
    je  .L245
    cmpq    $3, %rdi
    je  .L246
    cmpq    $4, %rdi
    je  .L247
    cmpq    $5, %rdi
    je  .L248
    cmpq    $6, %rdi
    je  .L249
    vmovdqa 16(%r10), %xmm3
    movl    $2, %r11d
    movl    $32, %edx
    vmovdqu %xmm3, 16(%r9)
.L249:
    vmovdqa (%r10,%rdx), %xmm4
    addq    $1, %r11
    vmovdqu %xmm4, (%r9,%rdx)
    addq    $16, %rdx
.L248:
    vmovdqa (%r10,%rdx), %xmm5
    addq    $1, %r11
    vmovdqu %xmm5, (%r9,%rdx)
    addq    $16, %rdx
.L247:
    vmovdqa (%r10,%rdx), %xmm0
    addq    $1, %r11
    vmovdqu %xmm0, (%r9,%rdx)
    addq    $16, %rdx
.L246:
    vmovdqa (%r10,%rdx), %xmm1
    addq    $1, %r11
    vmovdqu %xmm1, (%r9,%rdx)
    addq    $16, %rdx
.L245:
    vmovdqa (%r10,%rdx), %xmm2
    addq    $1, %r11
    vmovdqu %xmm2, (%r9,%rdx)
    addq    $16, %rdx
.L244:
    vmovdqa (%r10,%rdx), %xmm3
    addq    $1, %r11
    vmovdqu %xmm3, (%r9,%rdx)
    addq    $16, %rdx
    cmpq    %r11, %rsi
    jbe .L256
    .p2align 4,,10
.L162:
    vmovdqa (%r10,%rdx), %xmm2
    addq    $8, %r11
    vmovdqu %xmm2, (%r9,%rdx)
    vmovdqa 16(%r10,%rdx), %xmm1
    vmovdqu %xmm1, 16(%r9,%rdx)
    vmovdqa 32(%r10,%rdx), %xmm0
    vmovdqu %xmm0, 32(%r9,%rdx)
    vmovdqa 48(%r10,%rdx), %xmm5
    vmovdqu %xmm5, 48(%r9,%rdx)
    vmovdqa 64(%r10,%rdx), %xmm4
    vmovdqu %xmm4, 64(%r9,%rdx)
    vmovdqa 80(%r10,%rdx), %xmm3
    vmovdqu %xmm3, 80(%r9,%rdx)
    vmovdqa 96(%r10,%rdx), %xmm2
    vmovdqu %xmm2, 96(%r9,%rdx)
    vmovdqa 112(%r10,%rdx), %xmm1
    vmovdqu %xmm1, 112(%r9,%rdx)
    subq    $-128, %rdx
    cmpq    %r11, %rsi
    ja  .L162
.L256:
    addq    %rbp, %rcx
    addq    %rbp, %r8
    subq    %rbp, %rbx
    cmpq    %rbp, %r12
    je  .L163
.L161:
    movzbl  (%r8), %edx
    leaq    -1(%rbx), %r9
    andl    $7, %r9d
    movb    %dl, (%rcx)
    movl    $1, %edx
    cmpq    %rbx, %rdx
    je  .L163
    testq   %r9, %r9
    je  .L164
    cmpq    $1, %r9
    je  .L238
    cmpq    $2, %r9
    je  .L239
    cmpq    $3, %r9
    je  .L240
    cmpq    $4, %r9
    je  .L241
    cmpq    $5, %r9
    je  .L242
    cmpq    $6, %r9
    je  .L243
    movzbl  1(%r8), %edx
    movb    %dl, 1(%rcx)
    movl    $2, %edx
.L243:
    movzbl  (%r8,%rdx), %esi
    movb    %sil, (%rcx,%rdx)
    addq    $1, %rdx
.L242:
    movzbl  (%r8,%rdx), %r11d
    movb    %r11b, (%rcx,%rdx)
    addq    $1, %rdx
.L241:
    movzbl  (%r8,%rdx), %r10d
    movb    %r10b, (%rcx,%rdx)
    addq    $1, %rdx
.L240:
    movzbl  (%r8,%rdx), %edi
    movb    %dil, (%rcx,%rdx)
    addq    $1, %rdx
.L239:
    movzbl  (%r8,%rdx), %ebp
    movb    %bpl, (%rcx,%rdx)
    addq    $1, %rdx
.L238:
    movzbl  (%r8,%rdx), %r12d
    movb    %r12b, (%rcx,%rdx)
    addq    $1, %rdx
    cmpq    %rbx, %rdx
    je  .L163
    .p2align 4,,10
.L164:
    movzbl  (%r8,%rdx), %r9d
    movb    %r9b, (%rcx,%rdx)
    movzbl  1(%r8,%rdx), %r12d
    movb    %r12b, 1(%rcx,%rdx)
    movzbl  2(%r8,%rdx), %ebp
    movb    %bpl, 2(%rcx,%rdx)
    movzbl  3(%r8,%rdx), %edi
    movb    %dil, 3(%rcx,%rdx)
    movzbl  4(%r8,%rdx), %r10d
    movb    %r10b, 4(%rcx,%rdx)
    movzbl  5(%r8,%rdx), %r11d
    movb    %r11b, 5(%rcx,%rdx)
    movzbl  6(%r8,%rdx), %esi
    movb    %sil, 6(%rcx,%rdx)
    movzbl  7(%r8,%rdx), %r9d
    movb    %r9b, 7(%rcx,%rdx)
    addq    $8, %rdx
    cmpq    %rbx, %rdx
    jne .L164
.L163:
    popq    %rbx
    popq    %rsi
    popq    %rdi
    popq    %rbp
    popq    %r12
    ret
.L165:
    movq    %rdx, %r8
    movl    $80, %ebx
    jmp .L159
    .seh_endproc
    .p2align 4,,15
    .globl  memcpyi
    .def    memcpyi;    .scl    2;  .type   32; .endef
    .seh_proc   memcpyi

UPDATE:

By building on Peter Alexander's solution and combining it with ideas from around the thread, I have produced this:

void memcpyi80(void* __restrict b, const void* __restrict a){
    __m128 *s1 = b;
    const __m128 *s2 = a;
    *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++; 
}

The speedup is small but measurable (about 1%). Now I guess my next temptation is to find how to use __m256 AVX types so I can do it in 3 steps rather than 5.

UPDATE: The __m256 type requires allignment on the 32-bit barrier, which makes things slower, so it seems __m128 is a sweet spot.

Answer 1

The fastest way to do this would be to align your data on 16-byte boundaries, then the entire copy just becomes 5 copies through XMM registers.

This is over twice as fast as your version on my machine.

Store your data like this:

#include <xmmintrin.h>
struct Data
{
    union
    {
        int i[20];
        __m128 v[5];
    };
};

Then the copy function is just:

void memcpyv5(__m128* __restrict b, const __m128* __restrict a)
{
    __m128 t0 = a[0];
    __m128 t1 = a[1];
    __m128 t2 = a[2];
    __m128 t3 = a[3];
    __m128 t4 = a[4];
    b[0] = t0;
    b[1] = t1;
    b[2] = t2;
    b[3] = t3;
    b[4] = t4;
}

// Example
Data dst, src;
memcpyv5(dst.v, src.v);

Assembly output:

__Z8memcpyv5PU8__vectorfPKS_:
LFB493:
    pushq   %rbp
LCFI2:
    movq    %rsp, %rbp
LCFI3:
    movaps  16(%rsi), %xmm3
    movaps  32(%rsi), %xmm2
    movaps  48(%rsi), %xmm1
    movaps  64(%rsi), %xmm0
    movaps  (%rsi), %xmm4
    movaps  %xmm4, (%rdi)
    movaps  %xmm3, 16(%rdi)
    movaps  %xmm2, 32(%rdi)
    movaps  %xmm1, 48(%rdi)
    movaps  %xmm0, 64(%rdi)
    leave
    ret

Answer 2

Code below is optimized:

void *memcpyi72(void* __restrict b, const void * __restrict a)
{
  return memcpy(b,a, 18*sizeof(int));
}

GCC with -O3 generates the same assembly for this function as for the Pubby8 code. There's no need to use structs.

Answer 3

What is the assembly generated?

I remember finding that using structs can speed things up:

typedef struct {
  int x[17] __attribute__ ((packed));
  int padding __attribute__ ((packed, unused));
} cbytes __attribute__ ((packed));


void *memcpyi80(cbytes* __restrict b, const cbytes* __restrict a){
    size_t n = 80 / sizeof(cbytes);
    cbytes *s1 = b;
    const cbytes *s2 = a;
    for(; 0<n; --n)*s1++ = *s2++;
    return b;
}

Answer 4

You know what the size is, and you know it's ints, so do a little insider-trading:

void myCopy(int* dest, int* src){
    dest[ 0] = src[ 0];
    dest[ 1] = src[ 1];
    dest[ 2] = src[ 2];
    ...
    dest[19] = src[19];
}

Answer 5

If you really need this part as fast as possible, one obvious route would be to write it in assembly language. The assembly language you've posted looks a bit on the insane side for this task (at least to me). Given a fixed size, the obvious route would be something like:

; warning: I haven't written a lot of assembly code recently -- I could have 
; some of the syntax a bit wrong.
;
memcpyi80 proc dest:ptr byte src:ptr byte
    mov esi, src
    mov edi, dest
    mov ecx, 20    ; 80/4
    rep movsd
memcpyi80 endp

That is definitely open to improvement by using (for one example) moves through the SSE registers, but I'll leave that for others to play with. The improvement is pretty small though: recent processors have a special path specifically for memory copies, which this will use, so it's pretty competitive despite its simplicity.

@Mike Dunlavey's comment is good though: most of the time people think they need a faster memory copy, they really need to re-think their code to simply avoid needing it.

Answer 6

Have you try unroll the loop? Do 17 instead of 20? You can also take care of condition 2 at the same time because the values are in the registers already. Int should be 4-byte aligned, copy int instead of char? Save you look at Intel SSE instructions?

Answer 7

The compiler cannot vectorize your version. If you simply change the for loop to be indexed instead of dereferenced, you will see a huge speed improvement. I get >10x speed up for this:

void *memcpyi80(void* __restrict b, const void* __restrict a) {
    size_t n = 80;
    char *s1 = b;
    const char *s2 = a;
    for(; 0 < n; --n) {
      s1[n] = s2[n];
    }
    return b;
}

Answer 8

You are copying byte by byte, so it would be a lot faster copying int by int instead. Also unrolling the loop should help:

void *memcpyi80(void* __restrict b, const void* __restrict a){
  int* s1 = b;
  int* s2 = a;
  *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++;
  *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++;
  *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++;
  *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++;
  *s1++ = *s2++;
  // *s1++ = *s2++; *s1++ = *s2++; *s1++ = *s2++;
  return b;
}

In C# I have found that separating the access and incrementation is faster, so that's worth a try:

void *memcpyi80(void* __restrict b, const void* __restrict a){
  int* s1 = b;
  int* s2 = a;
  *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++;
  *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++;
  *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++;
  *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++;
  *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++;
  *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++;
  // *s1 = *s2; s1++; s2++; *s1 = *s2; s1++; s2++; *s1 = *s2;
  return b;
}

Answer 9

There's no way any solution in c or c++ could be better than assembly (unless of course, it was horribly written). The answer with the assembly language from Jerry Coffin above...

memcpyi80 proc dest:ptr byte src:ptr byte
    mov esi, src   ; load source address
    mov edi, dest  ; load destination address
    mov ecx, 20    ; initialize count register (80/4)
    rep movsd      ; perform transfer
memcpyi80 endp

cannot be improved upon, in my opinion, unless it's possible to use a smaller number larger operands. Naturally the memory addresses need to be aligned properly. The rep movsd instruction is the only part of the code that does any work, automatically incrementing the count register until the operation is complete.

What you might try is to pass the count as a separate parameter and then split the data into as many parts as you have cores, and call the function with a separate thread for each part.