Какой самый быстрый способ поменять значения в C?

Question

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

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

Или версия xor, которую, я уверен, большинство людей видели:

void swap(int* a, int* b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

Кажется, что первый использует дополнительный регистр, но второй выполняет три загрузки и сохраняет, в то время как первый делает только два из каждого. Может кто-нибудь сказать мне, что быстрее и почему? Почему важнее.

Answer 1

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

С учетом сказанного, вам лучше иметь чертовски вескую причину, чтобы выбрать № 2 вместо # 1. Код в # 1 гораздо более читабелен и поэтому всегда должен быть выбран первым. Переключайтесь на # 2 только в том случае, если вы можете доказать, что вам нужно , чтобы внести это изменение, и если вы это сделаете - прокомментировать, чтобы объяснить, что происходит и почему вы сделали это неочевидным способом.

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

Answer 2

Для современных архитектур ЦП способ 1 будет быстрее, также с более высокой читабельностью, чем метод 2.

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

---

Редактировать: Метод 2 - это способ обмен на месте (т.е. без использования дополнительных переменных). Чтобы завершить этот вопрос, я добавлю еще один обмен на месте с помощью +/-.

void swap(int* a, int* b)
{
    if (a != b) // important to handle a/b share the same reference
    {
        *a = *a+*b;
        *b = *a-*b;
        *a = *a-*b;
    }
}

Answer 3

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

Answer 4

х = х + у- (у = х);

float x; cout << "X:"; cin >> x;
float y; cout << "Y:" ; cin >> y;

cout << "---------------------" << endl;
cout << "X=" << x << ", Y=" << y << endl;
x=x+y-(y=x);
cout << "X=" << x << ", Y=" << y << endl;

Answer 5

По моему мнению, подобные локальные оптимизации следует рассматривать только в тесной связи с платформой. Это имеет огромное значение, если вы компилируете это на 16-битном компиляторе uC или на gcc с x64 в качестве цели.

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

Answer 6

Ниже кусок кода будет делать то же самое. Этот фрагмент оптимизирован для программирования, так как не использует третью переменную.

  x = x ^ y;
  y = x ^ y;
  x = x ^ y;

Answer 7

Еще один прекрасный способ.

#define Swap( a, b ) (a)^=(b)^=(a)^=(b)

Advantage

Нет необходимости в вызове функции и удобстве.

Минус:

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

Answer 8

void swap(int* a, int* b)
{
    *a = (*b - *a) + (*b = *a);
}

// Мой C немного ржавый, так что, надеюсь, я понял * правильно:)

Answer 9

Если ваш компилятор поддерживает встроенный ассемблер и ваша цель - 32-разрядная версия x86, то, вероятно, наилучшим способом сделать это является инструкция XCHG ... если вы действительно заботитесь о производительности.

Вот метод, который работает с MSVC ++:

#include <stdio.h>

#define exchange(a,b)   __asm mov eax, a \
                        __asm xchg eax, b \
                        __asm mov a, eax               

int main(int arg, char** argv)
{
    int a = 1, b = 2;
    printf("%d %d --> ", a, b);
    exchange(a,b)
    printf("%d %d\r\n", a, b);
    return 0;
}

Answer 10

Если вы можете использовать встроенный ассемблер и сделать следующее (псевдо ассемблер):

PUSH A
A=B
POP B

Вы сэкономите много передаваемых параметров, исправите код и т. Д.