Какой самый быстрый способ поменять значения в 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 часто называют «умным» способом сделать это. На самом деле это, скорее всего, медленнее, поскольку затеняет явную цель программиста - поменять местами две переменные. Это означает, что компилятор не может оптимизировать его для использования реальных операций ассемблера для замены. Он также предполагает возможность делать побитовый xor для объектов.

Придерживайтесь номера 1, это самый общий и самый понятный своп, который можно легко шаблонизировать / обобщать.

Этот раздел Википедии объясняет проблемы довольно хорошо: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice

Answer 2

Метод XOR не выполняется, если a и b указывают на один и тот же адрес. Первый XOR очистит все биты по адресу памяти, указанному обеими переменными, поэтому, как только функция вернется (* a == * b == 0), независимо от начального значения.

Больше информации на вики-странице: Алгоритм обмена XOR

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

Answer 3

На современном процессоре вы можете использовать следующее при сортировке больших массивов и не видеть разницы в скорости:

void swap (int *a, int *b)
{
  for (int i = 1 ; i ; i <<= 1)
  {
    if ((*a & i) != (*b & i))
    {
      *a ^= i;
      *b ^= i;
    }
  }
}

Действительно важной частью вашего вопроса является «почему?» часть. Теперь, если вернуться через 20 лет к 8086 дням, то вышеприведенное было бы реальным убийством производительности, но на последнем Pentium это будет совпадение по скорости с теми, что вы опубликовали.

Причина заключается только в памяти и не имеет ничего общего с процессором.

Скорость процессора по сравнению со скоростью памяти астрономически возросла. Доступ к памяти стал основным узким местом в производительности приложений. Все алгоритмы обмена будут тратить большую часть своего времени на ожидание извлечения данных из памяти. Современные ОС могут иметь до 5 уровней памяти:

• Уровень кэша 1 - работает с той же скоростью, что и процессор, имеет незначительное время доступа, но мало
• Уровень кэша 2 - работает немного медленнее, чем L1, но он больше и имеет большие накладные расходы для доступа (обычно данные сначала нужно перенести на L1)
• Кэш 3-го уровня - (не всегда присутствует) Часто внешний по отношению к ЦП, медленнее и больше, чем L2
• RAM - основная системная память, обычно реализующая конвейер, поэтому в запросах на чтение есть задержка (CPU запрашивает данные, сообщение отправляется в RAM, RAM получает данные, RAM отправляет данные в CPU)
• Жесткий диск - когда недостаточно ОЗУ, данные выгружаются на HD, что очень медленно, и не контролируется ЦП как таковым.

Алгоритмы сортировки ухудшат доступ к памяти, поскольку они обычно обращаются к памяти неупорядоченным образом, что приводит к неэффективным затратам на извлечение данных из L2, RAM или HD.

Таким образом, оптимизация метода подкачки действительно бессмысленна - если он вызывается только несколько раз, любая неэффективность скрывается из-за небольшого количества вызовов, если он вызывается много, то любая неэффективность скрывается из-за количества пропусков кэша (где ЦП требуется получить данные из L2 (1-й цикл), L3 (10-й цикл), RAM (100-й цикл), HD (!)).

Что вам действительно нужно сделать, так это взглянуть на алгоритм, который вызывает метод swap. Это не тривиальное упражнение. Хотя нотация Big-O полезна, O (n) может быть значительно быстрее, чем O (log n) для малых n. (Я уверен, что об этом есть статья CodingHorror.) Кроме того, многие алгоритмы имеют вырожденные случаи, когда код делает больше, чем необходимо (использование qsort для почти упорядоченных данных может быть медленнее, чем сортировка по пузырькам с ранней проверкой). Итак, вам нужно проанализировать ваш алгоритм и данные, которые он использует.

Что приводит к тому, как анализировать код. Профилировщики полезны, но вам нужно знать, как интерпретировать результаты. Никогда не используйте один прогон для сбора результатов, всегда усредняйте результаты по многим выполнениям - потому что ваше тестовое приложение могло быть перенесено на жесткий диск ОС на полпути. Всегда выпуск профиля, оптимизированные сборки, профилирование кода отладки бессмысленно.

Что касается первоначального вопроса - что быстрее? - это все равно, что пытаться выяснить, быстрее ли Ferrari, чем Lambourgini, взглянув на размер и форму зеркала крыла.

Answer 4

Первое быстрее, потому что побитовые операции, такие как xor, обычно очень трудно визуализировать для читателя.

Быстрее понять, конечно, что является наиболее важной частью;)

Answer 5

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

Никогда не используйте функции в качестве макросов по следующим причинам:

1. Тип безопасности. Здесь ничего нет. Следующее генерирует предупреждение только при компиляции, но не во время выполнения:

   float a=1.5f,b=4.2f;
   swap (a,b);
   

   Шаблонная функция всегда будет правильного типа (и почему вы не рассматриваете предупреждения как ошибки?).

   РЕДАКТИРОВАТЬ: Поскольку в C нет шаблонов, вам нужно написать отдельный своп для каждого типа или использовать хакерский доступ к памяти.

2. Это текстовая подстановка. Следующие ошибки во время выполнения (на этот раз без предупреждений компилятора):

   int a=1,temp=3;
   swap (a,temp);
   

3. Это не функция. Поэтому его нельзя использовать в качестве аргумента для чего-то вроде qsort.

4. Компиляторы умны. Я имею в виду действительно умный. Сделано действительно умными людьми. Они могут делать встраивание функций. Даже во время ссылки (что еще умнее). Не забывайте, что встраивание увеличивает размер кода. Большой код означает больше шансов пропустить кеш при получении инструкций, что означает более медленный код.

5. Побочные эффекты. Макросы имеют побочные эффекты! Рассмотрим:

   int &f1 ();
   int &f2 ();
   void func ()
   {
     swap (f1 (), f2 ());
   }
   

   Здесь f1 и f2 будут вызываться дважды.

   РЕДАКТИРОВАТЬ: версия C с неприятными побочными эффектами:

   int a[10], b[10], i=0, j=0;
   swap (a[i++], b[j++]);
   

Макросы: Просто скажите нет!

РЕДАКТИРОВАТЬ: Вот почему я предпочитаю определять имена макросов в UPPERCASE, чтобы они выделялись в коде как предупреждение, чтобы использовать с осторожностью.

РЕДАКТИРОВАТЬ2: Чтобы ответить на комментарий Леана Новаша:

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

bytes = C(p) + C(f)

где C () - количество произведенных байтов, C (f) - байты для функции, а C (p) - байты для кода «служебного обслуживания», преамбула и пост-переменная, которые компилятор добавляет к функция (создание и уничтожение стекового фрейма функции и т. д.). Теперь для вызова функции f требуется C (c) байтов. Если функция вызывается n раз, тогда общий размер кода составляет:

size = C(p) + C(f) + n.C(c)

Теперь давайте встроим функцию. C (p), «домашнее хозяйство» функции, становится равным нулю, поскольку функция может использовать кадр стека вызывающей стороны. C (c) также равен нулю, так как теперь нет кода операции вызова. Но, f копируется везде, где был звонок. Итак, общий размер кода теперь:

size = n.C(f)

Теперь, если C (f) меньше, чем C (c), общий размер исполняемого файла будет уменьшен. Но если C (f) больше, чем C (c), тогда размер кода будет увеличиваться. Если C (f) и C (c) схожи, то вам также необходимо учитывать C (p).

Итак, сколько байтов составляют C (f) и C (c). Ну, самая простая функция C ++ была бы геттером:

void GetValue () { return m_value; }

, который, вероятно, сгенерирует четырехбайтовую инструкцию:

mov eax,[ecx + offsetof (m_value)]

что составляет четыре байта. Инстукция вызова составляет пять байтов. Таким образом, общий размер экономии. Если функция более сложна, скажем, индексатор («return m_value [index];») или вычисление («return m_value_a + m_value_b;»), тогда код будет больше.

Answer 6

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

#define swap(a, b)   \
do {                 \
    int temp = a;    \
    a = b;           \
    b = temp;        \
} while(0)

Answer 7

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

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

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

Answer 8

Никогда не понимал ненависти к макросам. При правильном использовании они могут сделать код более компактным и читабельным. Я полагаю, что большинство программистов знают, что макросы следует использовать с осторожностью, и важно понять, что конкретный вызов - это макрос, а не вызов функции (все заглавные буквы). Если SWAP(a++, b++); является постоянным источником проблем, возможно, программирование не для вас.

По общему признанию, уловка xor - это аккуратные первые 5000 раз, когда вы ее видите, но все, что она действительно делает, - это экономит одно временное устройство за счет надежности. Глядя на сборку, сгенерированную выше, она сохраняет регистр, но создает зависимости. Также я бы не рекомендовал xchg, поскольку он имеет префикс подразумеваемой блокировки.

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

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

void swap(size_t esize, void* a, void* b)
{
    char* x = (char*) a;
    char* y = (char*) b;
    char* z = x + esize;

    for ( ; x < z; x++, y++ )
        SWAP(char, *x, *y);
}

Answer 9

Все ответы с самым высоким рейтингом на самом деле не являются окончательными "фактами" ... это люди, которые спекулируют!

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

Вот код c, который я скомпилировал с флагами "gcc -std = c99 -S -O3 lookingAtAsmOutput.c":

#include <stdio.h>
#include <stdlib.h>

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

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

int main() {
    int a = 5;
    int b = 6;
    swap_traditional(&a,&b);
    swap_xor(&a,&b);
}

Вывод ASM для swap_traditional () требует >>> 11 <<< инструкций (не включая «уйти», «ret», «размер»): </p>

.globl swap_traditional
    .type   swap_traditional, @function
swap_traditional:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %ecx
    pushl   %ebx
    movl    (%edx), %ebx
    movl    (%ecx), %eax
    movl    %ebx, (%ecx)
    movl    %eax, (%edx)
    popl    %ebx
    popl    %ebp
    ret
    .size   swap_traditional, .-swap_traditional
    .p2align 4,,15

ASM-вывод для swap_xor () занимает >>> 11 <<< инструкции, не включающие в себя «уход» и «ret»: </p>

.globl swap_xor
    .type   swap_xor, @function
swap_xor:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %ecx
    movl    12(%ebp), %edx
    movl    (%ecx), %eax
    xorl    (%edx), %eax
    movl    %eax, (%ecx)
    xorl    (%edx), %eax
    xorl    %eax, (%ecx)
    movl    %eax, (%edx)
    popl    %ebp
    ret
    .size   swap_xor, .-swap_xor
    .p2align 4,,15

Сводка выходных данных сборки:
swap_traditional () занимает 11 инструкций
swap_xor () занимает 11 инструкций

Вывод:
Оба метода используют одинаковое количество инструкций для выполнения и поэтому имеют примерно одинаковую скорость на этой аппаратной платформе.

Извлеченный урок:
Когда у вас есть небольшие фрагменты кода, просмотр вывода asm полезен для быстрой итерации вашего кода и получения самого быстрого кода (т.е. с наименьшим количеством инструкций). И вы можете сэкономить время, даже если вам не нужно запускать программу для каждого изменения кода. Вам нужно только запустить изменение кода в конце с помощью профилировщика, чтобы показать, что изменения кода происходят быстрее.

Я часто использую этот метод для тяжелого кода DSP, которому нужна скорость.

Answer 10

Я бы не стал делать это с указателями, если бы вам не пришлось. Компилятор не может оптимизировать их очень хорошо из-за возможности псевдонима указателя (хотя, если вы можете ГАРАНТИРОВАТЬ, что указатели указывают на непересекающиеся местоположения, GCC по крайней мере имеет расширения для оптимизации этого).

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

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

Примерно так:

#define swap(a,b) \
  do { \
    typeof(a) temp; \
    temp = a; \
    a = b; \
    b = temp; \
  } while (0)

...    
{
  int a, b;
  swap(a, b);
  unsigned char x, y;
  swap(x, y);                 /* works with any type */
}

С другими компиляторами или если вам требуется строгое соответствие стандарту C89 / 99, вам придется создавать отдельный макрос для каждого типа.

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