Оптимизация функции memswap

В обзоре кода следующей реализации memswap():

void util_memswap(size_t psize,
                  void *restrict p1, 
                  void *restrict p2)
{
    unsigned char *a = p1;
    unsigned char *b = p2;
    unsigned char tmp;

    while (psize--) {
        tmp = *a;
        *a++ = *b;
        *b++ = tmp;
    }
}

Я получил следующий совет:

Реализация util_memswap() может быть улучшена для более крупных объекты:

while (psize--) {
    tmp = *a;
    *a++ = *b;
    *b++ = tmp;
} 

Вы обнаружите, что версия memcpy() и/или memmove() в вашей библиотеке, вероятно, смещает более крупные единицы в соответствии с целью. архитектуры платформы, прибегая к побайтовому копированию только на заканчивается (и, возможно, для невыровненных данных). Настроенная реализация swap скорее всего, будет использовать аналогичные оптимизации.

Маловероятно, что оптимизатор вашего компилятора распознает образец здесь и группируйте переводы в более крупные единицы. Я попробовал с последние GCC и Clang - первый разворачивал цикл, но оба по-прежнему генерирую код, который обращается к памяти отдельными блоками, насколько я могу читать. @Тоби Спейт

А затем поискал и нашел примеры реализации memcpy(), которые копируют слова вместо байтов после переинтерпретации void * как long *. Но мне кажется, что это нарушает строгие правила псевдонимов, поскольку void * изначально не мог быть long *. Предполагая, что я правильно понимаю, какой вариант оптимизации описанной выше процедуры мне нужен?

О замене его тремя memcpy() звонками @Peter Cordes говорит в комментариях под этим ответом:

Это, вероятно, помешает некоторым оптимизациям в большинстве компиляторов. Многие неплохо разбираются в таком использовании memcpy, но определенно не идеально. Я настоятельно рекомендую не использовать это, если вас волнует производительность. В лучшем случае это может стать запасным вариантом #ifdef для компиляторов, которые не поддерживают расширения GNU, в частности typeof().


Обновлено: приведенная выше процедура используется следующим образом:

#include <assert.h>
#include <string.h>

/**
 * Like C11's _Static_assert() except that it can be used in an expression.
 *
 * EXPR - The expression to check.
 * MSG  - The string literal of the error message to print only if EXPR evalutes
 *        to false.
 *
 * Always return true. */
#define STATIC_ASSERT_EXPR(EXPR, MSG)   \
    (!!sizeof( struct { static_assert ( (EXPR), MSG ); char c; } ))

/* OP is aware that this would not work for VLAs, or variables that are 
 * declared with the `register` storage class, or identical variables. */
#define SWAP(A, B)                                                         \
    util_memswap((sizeof *(1 ? &(A) : &(B))                                \
        * STATIC_ASSERT_EXPR(sizeof (A) == sizeof (B),                     \
        "Arguments of SWAP() must have same size and compatible types.")), \
        &(A),                                                              \
        &(B))

кажется, что это нарушает строгие правила псевдонимов. Реализация memcpy не связана правилами, установленными стандартом. Ваши собственные функции не освобождаются от ответственности. Ваши варианты: (1) нарушать правила, осознавая риски, или (2) проявлять осторожность и не нарушать правила.

n. m. could be an AI 23.06.2024 10:40

«Я пробовал использовать последние GCC и Clang — первый выполнил некоторое развертывание цикла, но оба по-прежнему генерируют код, который обращается к памяти в отдельных модулях, насколько я могу читать» --- На сегодняшний день это неправда, вы можете смело игнорировать все беседа. Проведите собственное исследование.

n. m. could be an AI 23.06.2024 10:48

При тестировании я рекомендую поменять местами структуры, содержащие переменные с плавающей запятой: float, double и long double. При таком побайтовом копировании довольно легко случайно создать недопустимый шаблон.

Ted Lyngmo 23.06.2024 10:50

@n.m.couldbeanAI Я забыл добавить ссылку, которой поделился Тоби. Теперь у меня есть.

Harith 23.06.2024 10:50

Я понятия не имею, как читать ARM-сборку и оценивать ее эффективность. Я умею читать x86-64 и там четко вижу ходы по 16 байт.

n. m. could be an AI 23.06.2024 10:58

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

Lundin 24.06.2024 12:00

Мне бы хотелось, чтобы в стандартной библиотеке C был определен memswap(), поскольку он был бы очень полезен для реализации общих функций сортировки на месте, аналогичных стандарту qsort().

Ian Abbott 24.06.2024 14:09

@IanAbbott Подумайте о том, чтобы написать предложение :). Возможно, он попадет в C2Y или в следующую версию. Надеюсь, на этот раз будут добавлены хотя бы max() и min().

Harith 24.06.2024 14:27

@n.m.couldbeanAI: Программы, предназначенные для использования с реализациями, настроенными для низкоуровневого программирования, освобождаются от любых ограничений, от которых отказывается реализация. Одной из сильных сторон языка C является то, что он допускает компромисс между переносимостью и производительностью, хотя многие люди предпочитают игнорировать ту часть устава Комитета по стандарту C, которая прямо признает легитимность непереносимых программ на языке C.

supercat 29.07.2024 17:38
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
3
9
125
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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


Вы связали старый ответ со старым комментарием, помните, что такие советы иногда устаревают по мере совершенствования компиляторов.

  1. Питер прав, компиляторы действительно оптимизируют этот случай. Я пробовал gcc, Clang и MSVC на x86-64, только MSVC не удалось оптимизировать: https://godbolt.org/z/E5f4acze9 . Обратите внимание, что vmovups с аргументом ymm использует 256-битные регистры, что больше, чем 32-битные или 64-битные long. Также обратите внимание на отсутствие утечек.

  2. Питер отчасти прав в том, что попытка memcpy использовать более крупный тип помешает лучшей оптимизации. См. https://godbolt.org/z/GMfdPfsYG -- gcc перешел на 64-битные регистры (стало хуже), Clang по-прежнему использует 256-битные регистры.

  3. Если сделать размер элемента постоянным, то он тоже начинает полную оптимизацию в gcc https://godbolt.org/z/jqGcvE6YE (а также начинает компилироваться в MSVC, который не поддерживает VLA, но только с 64- битовые регистры)

  4. Вы также можете увеличить константу размера элемента до размера векторного регистра. Теперь все три упомянутых компилятора его полностью оптимизируют: https://godbolt.org/z/7ooaE7oYE

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


MSVC, как правило, не силен в оптимизации компилятора, а также не ориентирован конкретно на C, в отличие от C++. Для C++ оптимизация алгоритма std::swap_ranges реализована в STL (а не в компиляторе).

Другие вопросы по теме