Копирование 80 байт как можно быстрее


Я бегу по математике, ориентированных на вычисление, которое тратит значительное количество своего времени делают функции memcpy, всегда копировал 80 байт из одного места к следующему, массив 20 32-битный инты. Общее вычисление занимает около 4-5 дней, используя оба ядра моего i7 процессор, так что даже 1% приводит к ускорению примерно через час спас.

С помощью функции memcpy в данном документе от Intel, я смог ускорить примерно на 25%, а также снижается размер аргумента и просто объявив внутри, кажется, есть какой-то небольшой эффект. Тем не менее, я чувствую, что я не используя тот факт, что мои операции копирования всегда одинакового размера. Что сказал, Я не могу придумать лучшего способа.

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;
}

Некоторые другие вещи, которые могут быть полезны для оптимизации:

  1. Я использую процессор Intel сердечника i7-2620M, на основе песчаного моста. Я не забочусь о переносимости вообще.

  2. Меня интересует только 16 младших бит каждого инт. Остальные 16 бесполезны для меня и постоянно обнуляться.

  3. Хотя я копия 20 32-разрядный Ints на вызов функции memcpy, меня интересует только первая 17. Я добавил 3 как это помогает с выравниванием и поэтому скорость.

  4. Я использовать GCC 4.6 на Windows 7.

Любые идеи?

Обновление:

Я думаю, что это выход сборки (никогда раньше этого не делал, причин может быть больше, чем нужно):

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

Обновление:

Опираясь на решения Петр Александра и сочетая его с идеями со всего потока, я произвел этот:

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++; 
}

Ускорение небольшое, но измеримое (около 1%). Теперь я думаю, мой следующий соблазн найти, как использовать __М256 с AVX видах так что я могу сделать в 3 шага, а не 5.

Обновление:

В __тип М256 требует выравнивания на 32-битный барьер, который делает вещи медленнее, так кажется __м128 микроконтроллеров-это сладкое место.



10724
36
задан 22 октября 2011 в 09:10 Источник Поделиться
Комментарии
8 ответов

Самый быстрый способ сделать это, чтобы выровнять ваши данные на 16-байтовых границах, то вся копия просто будет 5 копий через регистров XMM.

Это более чем в два раза быстрее , как ваша версия на моей машине.

Хранить такие данные:

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

Тогда функция копирования-это просто:

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);

Вывод собрания:

__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

27
ответ дан 22 октября 2011 в 09:10 Источник Поделиться

Если вам действительно нужна эта часть как можно быстрее, одним из очевидных путей будет писать на ассемблере. На ассемблере ты написал выглядит немного безумную сторону для этой задачи (по крайней мере для меня). Учитывая фиксированный размер, очевидное маршрута будет нечто вроде:

; 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

Что это наверняка открыта для улучшения с помощью (например) движется по ЕГЭ регистры, но я оставлю это для других, чтобы играть. Улучшение довольно маленький, но все же: последние процессоры имеют специальные пути непосредственно по памяти копии, которые это будет использовать, так что это довольно низким, несмотря на свою простоту.

Комментарий @Майк Данлейви это хорошо хотя: большую часть времени люди думают, что им нужно быстрее скопировать памяти, они действительно должны переосмыслить свой код просто не нужен.

2
ответ дан 22 октября 2011 в 02:10 Источник Поделиться

Ниже код оптимизирован:

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

GCC с -O3 не создает той же сборке для этой функции, как для Pubby8 код. Нет необходимости использовать структуры.

1
ответ дан 22 октября 2011 в 07:10 Источник Поделиться

Что такое сборки?

Я помню, как нашла, что использование структуры могут ускорить процесс:

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;
}

0
ответ дан 22 октября 2011 в 10:10 Источник Поделиться

Вы знаете, что размер, и вы знаете, что это ИНЦ, так что немного инсайдерской торговли:

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

0
ответ дан 22 октября 2011 в 02:10 Источник Поделиться

Компилятор не может векторизовать свои версии. Если вы просто измените цикл for, чтобы быть проиндексированы вместо разыменования, вы увидите огромное улучшение скорости. Я получаю >10х скорость это:

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;
}

0
ответ дан 22 октября 2011 в 03:10 Источник Поделиться

Вы копируете байт за байтом, так было бы намного быстрее, копируя инт на Инт вместо. Также разворачивая петли должны помочь:

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;
}

В C# я нашел, что разделение доступа и приращения быстрее, так что стоит попробовать:

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;
}

0
ответ дан 22 октября 2011 в 06:10 Источник Поделиться

Нет никакого способа, любое решение в C или C++ может быть лучше, чем сборка (если, конечно, это было ужасно написано). Ответ с языка ассемблера Джерри гроб выше...

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

не может быть улучшена, на мой взгляд, если это возможно, чтобы использовать меньшее количество больших операндов. Естественно, что адреса памяти должны быть выровнены. В рэп movsd инструкция-это только часть кода, которая делает любую работу, автоматически увеличивая счетчик зарегистрировать до завершения операции.

Что вы могли бы попробовать это, чтобы передать графу как отдельный параметр, а затем разделить данные на несколько частей, сколько у вас ядер, и вызвать функцию с отдельным потоком для каждой части.

-1
ответ дан 23 октября 2011 в 09:10 Источник Поделиться