C - самый быстрый способ поменять два блока памяти одинакового размера? - PullRequest
Новая
       45

C - самый быстрый способ поменять два блока памяти одинакового размера?

11 голосов
/ 17 ноября 2011

Какой самый быстрый способ поменять местами две непересекающиеся области памяти одинакового размера? Скажем, мне нужно поменять (t_Some *a) на (t_Some *b). Учитывая компромисс между пространством и временем, увеличит ли временное пространство скорость? Например, (char *tmp) против (int *tmp)? Я ищу портативное решение.

Прототип: 

void swap_elements_of_array(void* base, size_t size_of_element, int a, int b);

Ответы [ 8 ]

5 голосов
/ 16 февраля 2018

Самый быстрый способ переместить блок памяти будет memcpy() из <string.h>. Если вы memcpy() от a до temp, memmove() от b до a, затем memcpy() от temp до b, у вас будет своп, который использует оптимизированную библиотеку подпрограммы, которые компилятор, вероятно, встроен Вам не захочется копировать весь блок сразу, но кусками векторного размера.

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

Однако, что вы действительно хотите сделать, так это упростить работу оптимизатора. Возьми эту программу: 

#include <stddef.h>

void swap_blocks_with_loop( void* const a, void* const b, const size_t n )
{
  unsigned char* p;
  unsigned char* q;
  unsigned char* const sentry = (unsigned char*)a + n;

  for ( p = a, q = b; p < sentry; ++p, ++q ) {
     const unsigned char t = *p;
     *p = *q;
     *q = t;
  }
}

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

В clang 5.0.1 с -std=c11 -O3 он создает (частично) следующий внутренний цикл на x86_64: 

.LBB0_7:                                # =>This Inner Loop Header: Depth=1
        movups  (%rcx,%rax), %xmm0
        movups  16(%rcx,%rax), %xmm1
        movups  (%rdx,%rax), %xmm2
        movups  16(%rdx,%rax), %xmm3
        movups  %xmm2, (%rcx,%rax)
        movups  %xmm3, 16(%rcx,%rax)
        movups  %xmm0, (%rdx,%rax)
        movups  %xmm1, 16(%rdx,%rax)
        movups  32(%rcx,%rax), %xmm0
        movups  48(%rcx,%rax), %xmm1
        movups  32(%rdx,%rax), %xmm2
        movups  48(%rdx,%rax), %xmm3
        movups  %xmm2, 32(%rcx,%rax)
        movups  %xmm3, 48(%rcx,%rax)
        movups  %xmm0, 32(%rdx,%rax)
        movups  %xmm1, 48(%rdx,%rax)
        addq    $64, %rax
        addq    $2, %rsi
        jne     .LBB0_7

Принимая во внимание, что gcc 7.2.0 с теми же флагами также векторизуется, меньше разворачивая цикл: 

.L7:
        movdqa  (%rcx,%rax), %xmm0
        addq    $1, %r9
        movdqu  (%rdx,%rax), %xmm1
        movaps  %xmm1, (%rcx,%rax)
        movups  %xmm0, (%rdx,%rax)
        addq    $16, %rax
        cmpq    %r9, %rbx
        ja      .L7

Убедить компилятор создавать инструкции, работающие с одним словом за раз, вместо векторизации цикла, - это противоположность того, что вы хотите!

4 голосов
/ 17 ноября 2011

Лучше всего максимизировать использование регистров, чтобы при чтении временного хранилища у вас не было дополнительных (вероятно, кэшированных) обращений к памяти. Количество регистров будет зависеть от системы, а распределение регистров (логика, которая отображает ваши переменные в реальных регистрах) будет зависеть от компилятора. Поэтому я считаю, что вам лучше всего ожидать только одного регистра и ожидать, что его размер будет таким же, как указатель. Что сводится к простому циклу for, работающему с блоками, интерпретируемыми как массивы size_t.

2 голосов
/ 23 февраля 2016

Word пишет будет самым быстрым.Однако необходимо учитывать как размер блока, так и выравнивание.На практике вещи обычно выровнены разумно, но вы не должны на это рассчитывать.memcpy() безопасно обрабатывает все и может быть специализированным (встроенным) для постоянных размеров в разумных пределах.

Вот портативное решение, которое в большинстве случаев работает достаточно хорошо . 

static void swap_byte(void* a, void* b, size_t count)
{
    char* x = (char*) a;
    char* y = (char*) b;

    while (count--) {
        char t = *x; *x = *y; *y = t;
        x += 1;
        y += 1;
    }
}

static void swap_word(void* a, void* b, size_t count)
{
    char* x = (char*) a;
    char* y = (char*) b;
    long t[1];

    while (count--) {
        memcpy(t, x, sizeof(long));
        memcpy(x, y, sizeof(long));
        memcpy(y, t, sizeof(long));
        x += sizeof(long);
        y += sizeof(long);
    }
}

void memswap(void* a, void* b, size_t size)
{
    size_t words = size / sizeof(long);
    size_t bytes = size % sizeof(long);
    swap_word(a, b, words);
    a = (char*) a + words * sizeof(long);
    b = (char*) b + words * sizeof(long);
    swap_byte(a, b, bytes);
}
1 голос
/ 16 февраля 2018

Если 2 области памяти велики и занимают целое число страниц памяти, то вы можете поменять местами их записи в таблице страниц, чтобы поменять их содержимое без использования memcpy () или XOR.

Теоретически, для двух больших страниц размером 2 МБ вам нужно написать только 16 байтов структур подкачки, чтобы поменять их отображение в виртуальном адресном пространстве ... и, следовательно, их содержимое тоже.

Страницы 1 ГБ возможны на процессорах x86-64 в 64-битном режиме, и содержимое 2 таких блоков памяти 1 ГБ также можно поменять местами с записью только нескольких байтов структур подкачки.

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

С недавними исправлениями Meltdown (KPTI) переход в режим ядра из режима пользователя стал намного дороже. Возможно, это слишком дорого, чтобы сделать подкачки страниц памяти объемом 4 КБ конкурентоспособными с memcpy () ... но если у вас есть 2 МБ или более блоков памяти для замены, то замена их структур подкачки происходит быстрее.

0 голосов
/ 17 ноября 2011

Очевидно, что вы должны скопировать A в Temp, скопировать B в A, а затем скопировать Temp в B. Вы можете сделать это все сразу, для небольшой области, или сделать это в разделах для большей области, где вы надеваетене хочу выделять такое большое значение Temp.Выбор размера раздела остается за вами, хотя для больших и частых перемещений важно учитывать вопросы выравнивания и кэширования, подходящие для аппаратного обеспечения.

(Ну, на самом деле есть другой способ, который не требуетлюбое временное пространство: XOR A с B, затем XOR B с A, затем XOR A с B. Уловка старого программиста на ассемблере.)

0 голосов
/ 17 ноября 2011 
#include <string.h>
#include <stdio.h>

static void swap_elements_of_array(void* base, size_t size_of_element, int a, int b);
static void swap_elements_of_array(void* base, size_t size_of_element, int a, int b)
{
union {
    int i; /* force alignment */
    char zzz[size_of_element] ; /* VLA */
    } swap;
memcpy (swap.zzz, (char*)base + a * size_of_element,size_of_element);
memcpy ((char*)base + a * size_of_element,(char*)base + b * size_of_element,size_of_element);
memcpy ((char*)base + b * size_of_element, swap.zzz, size_of_element);
}

int main (void)
{
unsigned idx,array[] = {0,1,2,3,4,5,6,7,8,9};

swap_elements_of_array(array, sizeof array[0], 2, 5);

for (idx=0; idx < 10; idx++) {
    printf( "%u%c", array[idx], (idx==9) ? '\n' : ' ' );
    }
return 0;
}

Цель этого фрагмента состоит в том, чтобы позволить высокооптимизированным libc-версиям memcpy (или встроенным компилятором) взять всю необходимую им свободу.Выравнивание имеет решающее значение.Если VLA недоступны (до C99), макрос может быть скомпонован, используя прикольное занятие.

0 голосов
/ 17 ноября 2011

Вы можете использовать логику, описанную здесь . Таким образом, вы можете сохранить третий буфер. 

#include <stddef.h>
#include <stdint.h>
void swap(uint8_t *a, uint8_t *b, size_t length) {
    size_t i;
    for (i=0; i<length; i++) {
        uint8_t aa = a[i];
        aa^=b[i];
        b[i]^=aa;
        aa^=b[i];
        a[i] = aa;
    }
}

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

Но если вы используете такую ​​временную переменную, вы также можете сделать 

#include <stddef.h>
#include <stdint.h>
void swap(uint8_t *a, uint8_t *b, size_t length) {
    size_t i;
    for (i=0; i<length; i++) {
        uint8_t aa = a[i];
        a[i] = b[i];
        b[i] = aa;
    }
}

На первый взгляд, они оба выглядят дорогими из-за большого количества обращений к массиву (в 1-м случае) и обработки только одного байта за цикл, но если вы позволите вашему компилятору оптимизировать это, все должно быть в порядке, поскольку (по крайней мере, gcc) достаточно умен, чтобы всегда объединять 4 шага (в x64: даже 16 шагов) в один цикл.

Обратите внимание, что ваш компилятор может не оптимизировать так агрессивно, поэтому вам, возможно, придется выполнить указанное разбиение самостоятельно. В этом случае позаботьтесь о выравнивании.

0 голосов
/ 17 ноября 2011

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

Лично я предпочел бы создать блок памяти, равный по размеру одному из массивов; используйте memcpy для обмена содержимым, используя вновь созданный блок памяти в качестве пространства подкачки.

Теперь размер блока памяти будет влиять на скорость работы (опять-таки, зависит от платформы), и поэтому вы можете обнаружить, что для очень больших массивов обмен меньшими объемами данных назад и вперед происходит быстрее, чем каждый большой массив. время.

редактировать

В свете комментария позвольте мне объяснить мой последний комментарий о замене меньшего количества данных.

Ваша цель - передать данные a в b и данные b в a с использованием временного пространства подкачки tmp.

Размер tmp равен или меньше размера a или b, и число итераций обмена данными увеличивается с уменьшением размера tmp, например. если tmp является десятым из a, то потребуется 10 итераций.

Теперь, чтобы повысить скорость memcpy, лучше всего убедиться, что массивам (a, b и tmp) выделено выровненное пространство памяти.

...