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

Этот вопрос является расширением этого один. Здесь я представляю два возможных решения и хочу знать их осуществимость. Я использую микроархитектуру Haswell с компиляторами GCC/ICC. Я также предполагаю, что память выровнена.

ВАРИАНТ 1. У меня уже есть выделенная позиция в памяти, и я делаю 3 перемещения памяти. (я использую memmove вместо memcpy, чтобы избежать конструктора копирования).

void swap_memory(void *A, void* B, size_t TO_MOVE){

    memmove(aux, B, TO_MOVE);
    memmove(B, A, TO_MOVE);
    memmove(A, aux, TO_MOVE);
}

ВАРИАНТ 2. Используйте загрузку и сохранение AVX или AVX2, используя преимущества выровненной памяти. К этому решению я считаю, что меняю местами int типа данных.

void swap_memory(int *A, int* B, int NUM_ELEMS){

    int i, STOP_VEC = NUM_ELEMS - NUM_ELEMS%8;
    __m256i data_A, data_B;

    for (i=0; i<STOP_VEC; i+=8) {
        data_A = _mm256_load_si256((__m256i*)&A[i]);
        data_B = _mm256_load_si256((__m256i*)&B[i]);

        _mm256_store_si256((__m256i*)&A[i], data_B);
        _mm256_store_si256((__m256i*)&B[i], data_A);
    }

    for (; i<NUM_ELEMS; i++) {
        std::swap(A[i], B[i]);
    }
}

Вариант 2 самый быстрый? Есть ли другая более быстрая реализация, о которой я не упоминаю?


c memory swap avx2
person Hélder Gonçalves    schedule 19.05.2016    source источник
comment
Вы его профилировали?   -  person Steve Lorimer    schedule 19.05.2016
comment
Я бы предположил, что (с включенной оптимизацией) gcc/icc будет векторизовать циклы для вас, а не требовать от вас делать это вручную.   -  person    schedule 19.05.2016
comment
ОП: Я использую memmove вместо memcpy, чтобы избежать конструктора копирования → что? Обе эти функции работают только с необработанными байтами, не используют конструкторы копирования (или перемещения) или операторы присваивания. Однако первый корректно работает с перекрывающимися диапазонами.   -  person Javier Martín    schedule 19.05.2016
comment
Вероятно, это больше проблема дизайна, если вам нужно сделать все это копирование - вы должны просто поменять местами два указателя, верно?   -  person Paul R    schedule 19.05.2016
comment
... зачеркните это -- если бы указатели были помечены __restrict__, я бы ожидал, что gcc/icc векторизует циклы для вас. Без __restrict__ я не уверен, сколько компиляторов в наши дни добавят тесты для непересекающихся диапазонов, чтобы проверить, безопасно ли переупорядочивать операции или нет.   -  person    schedule 19.05.2016
comment
Почему бы не измерить и не убедиться самому? Если вариант 1 не окажется медленным как патока, цвет меня удивит.   -  person n. 1.8e9-where's-my-share m.    schedule 19.05.2016
comment
SteveLorimer, я просто измеряю время. OPT2 быстрее. Пол Р., я не могу просто поменять местами указатели. Приходится менять всю память. Я просто хочу знать, есть ли другой способ сделать это, еще быстрее.   -  person Hélder Gonçalves    schedule 19.05.2016
comment
Если хотите еще быстрее, может _mm512_load_si512? Однако может достичь точки убывающей отдачи. Измерьте также скорость одной копии памяти - вы не сможете получить больше, чем вдвое. В лучшем случае вы могли бы намекнуть на предварительную выборку в каждом из них для небольшого выигрыша, если вы можете сделать что-то еще заранее.   -  person Todd Christensen    schedule 20.05.2016

Ответы (3)


arrow_upward
2
arrow_downward

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

Скорее всего, вариант 2 (или что-то семантически делающее это) может быть быстрее, поскольку указатели не ограничены или что-то в этом роде. Компилятор может не знать, безопасно ли переупорядочивать память или оставлять «aux» нетронутыми.

Кроме того, вариант 2 может быть более потокобезопасным в зависимости от того, как настроен aux.

Было бы неплохо использовать локальное временное и memcpy в/из этого временного в блоках или даже все сразу, так как gcc может векторизовать это. Избегайте использования внешних временных элементов и убедитесь, что все ваши структуры оформлены как выровненные.

person Todd Christensen    schedule 19.05.2016
comment
Я не думаю, что вы можете использовать alignas, чтобы сообщить gcc, что указатель указывает на выровненную память. alignas работает только для выравнивания самих данных (например, alignas(32) foo[32]). Вариант 2 лучше, потому что компилятор почти наверняка не оптимизирует версию memcpy в чередующийся цикл, который не касается aux. Ваш последний абзац, вероятно, приведет к множественным вызовам memcpy с небольшим количеством. - person Peter Cordes; 19.05.2016
comment
Возможно, тогда указатель наalign_storage? Обычно я просто использую атрибуты или определения gcc и т. д. и забыл, что alignas не указывает на память. - person Todd Christensen; 19.05.2016
comment
Специфичный для gcc способ — A = __builtin_assume_align(A, 32). Вы также можете typedef __attribute__((aligned(32))) int align32_int, а затем void foo(align32_int *A) {}. IIRC, это работает, а alignas в том же typedef не работает - person Peter Cordes; 19.05.2016
comment
Правильно, метод typedef — это то, как я обычно это делаю. Стыд alignas не может быть использован таким образом. - person Todd Christensen; 19.05.2016

arrow_upward
0
arrow_downward

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

Вы также можете использовать встроенный AVX _mm256_stream_si256 вместо хранилищ (тогда вам понадобится забор перед повторным чтением памяти).

person GdR    schedule 19.05.2016
comment
Хранилища NT хуже, если буфер маленький, и вы собираетесь его скоро прочитать. Они вытесняют пункт назначения, даже если он был горячим в кеше. - person Peter Cordes; 19.05.2016

arrow_upward
0
arrow_downward

Я бы просто сделал следующее:

unsigned char t; 
unsigned char *da = A, *db = B; 
while(TO_MOVE--) { 
   t = *da; 
   *da++ = *db; 
   *db++ = t; 
}

На том основании, что это очень ясно, и у оптимизатора есть хорошие шансы сделать хорошую работу.

person Wayne Booth    schedule 19.05.2016
comment
Это хорошо с автовекторизацией (-O3), но абсолютный мусор без (-O2). Вы можете использовать -fopenmp и #pragma omp simd даже при -O2, чтобы получить хорошие результаты с gcc. Поскольку у вас есть ints и количество элементов int, глупо приводить его к char. Это делает скалярный цикл очистки хуже. - person Peter Cordes; 19.05.2016