Безотраслевая версия замены x на y, если x> y?

Question

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

if (x < y) {
    std::swap(x, y);
}

Я могу сразу подумать о решении с использованием c = x < y, а затем назначить x до c * x + (1 - c) * y и т. д., но этот подход выдает инструкции умножения, которых я хотел бы избежать.Есть ли способ сделать это с одной лишь битой?

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

Answer 1

Я не уверен, что это ускорит ваш код, но это решение без ответвлений:

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

int main(int argc, char **argv) {
  int a = atoi(argv[1]);
  int b = atoi(argv[2]);
  int c = a - b;
  c &= c >> 31; // SXT for signed int
  a -= c;
  b += c;
  printf("Result: %d %d\n", a, b);
}

Answer 2

В случае, если x и y записываются в память после этой операции, вы можете использовать запись в динамическую ячейку памяти вместо условного перехода. Например, сортировать a[0], a[1]:

int x = a[0];
int y = a[1];
a[x >= y] = x;
a[y > x] = y;

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

Answer 3

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

Например, компилятор может преобразоватьэто:

if (x < y) {
    std::swap(x, y);
}
do_something(x, y);
return x;

.. в это:

if (x < y) {
    // Names of "x" and "y" swapped in subsequent code
    do_something(y, x);
    return y;
} else {
    do_something(x, y);
    return x;
}

Конечно, поменять имена и не поменять местами данные часто бесплатно (для производительности), потому что вы на самом деле ничего не меняете,

Современные процессоры делают точно такой же трюк.

В частности;ЦП имеет регистры, а регистры - это имена, связанные с данными.Для такой инструкции, как xchg eax,ebx (на 80x86), ЦП просто поменяет имена регистров и не будет перемещать данные.Это означает, что ЦП может выполнять обмен, когда данные в любом регистре еще не известны (например, потому что они все еще вычисляются или выбираются предыдущей инструкцией).

Другими словами;самый быстрый способ реализовать std::swap(x, y); - убедиться, что для CPU сгенерирована правильная инструкция (например, так, чтобы CPU получил xchg eax,ebx на 80x86, который не имеет ветвей и не должен ждать, пока значенияизвестно).

Answer 4

Как предлагают другие, вы можете попробовать переписать свой код в терминах std::min() и std::max().

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

О единственном другом решении, отличном от C ++, которое я могу предложить, будет встроенная сборка, в которой вы сможете написать именно те инструкции, которые вам нужны. Однако использование встроенной сборки влияет на то, что компилятор делает с кодом вокруг него, и может иметь негативные последствия (например, неэффективное использование регистров, разливов регистров и т. Д.), Которые могут компенсировать или сводить на нет любые ожидаемые выгоды.