Как преобразовать серию цепочек отношений if / else if / else if / в код с линейным циклом

Question

Как преобразовать серию цепочек отношений if / else if / else if / в код с линейным циклом

У меня есть ядро алгоритма, который я хочу преобразовать, по сути, из серии if / else if / else if / else i / chain примерно на 20 глубин в цикл, который можно сделать линейным способом. Условия просты с одной из 4 возможностей (A [i] < B [j]), (A [i] <= B [j]), (A [i]> B [j]), (A [i]> = B [j]). Как я могу конвертировать их всех в один условный. Например, цепь может быть примерно такой.

if (A[i+0] <  B[j+0]) break
if (A[i+1] <= B[j+1]) break
if (A[i+2] >  B[j+2]) break
if (A[i+3] >= B[j+3]) break
if (A[i+4] >= B[j+4]) break
....

Каждое условие может быть 1 из 4 возможных, но я хочу преобразовать их все в один набор шагов без регистра, чтобы это можно было выполнить в цикле (или, возможно, параллельно с векторными встроенными функциями)

// Given a list R[n] of 4 possible relations loop over all the data
int result = 1;
for (i = 0; i < num_relations && result; ++i) {
// How do I convert this to linear code which does the equivalent of
// (the value of R[n] and what relation it maps is flexible, this is an example)
case (R[n]) {
0 : result = A[i] <  B[i]; break;
1 : result = A[i] <= B[i]; break;
2 : result = A[i] >  B[i]; break;
3 : result = A[i] >= B[i]; break;
}
}

Некоторые свойства (числа без знака), которые могут быть использованы:

(A > B) ^ 1 === (A <= B) ^ 0

Можно ли оптимизировать вышесказанное для чего-то лучшего, чем

result = 1;
for (i = 0; i < num_relations && result; ++i) {
result = ((A[i] <  B[i]) && (R[i] == 0)) ||
((A[i] <= B[i]) && (R[i] == 1)) ||
((A[i] >  B[i]) && (R[i] == 2)) ||
((A[i] >= B[i]) && (R[i] == 3));
}

1

boolean-expression boolean-logic boolean-operations c++vectorization

Решение

Другие решения

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

bool (*)(int A, int B);

bool isLess(int A, int B) { return A < B; }
bool isLessOrEqual(int A, int B) { return A <= B; }
bool isGreater(int A, int B) { return A > B; }
bool isGreaterOrEqual(int A, int B) { return A >= B; }

Поместите их в массив.

typedef bool (*CompareFunction)(int A, int B);
CompareFunction functions[] = {isLess, isLessOrEqual, isGreater, isGreaterOrEqual};

Используйте массив функций в цикле.

for (i = 0; i < num_relations && result; ++i) {
result = functions[i](A[i], B[i]);
}

0

Вы могли бы использовать побитовое AND:

result = 1;
for (i = 0; i < num_relations && result; ++i) {
delta = A[i] - B[i];

//  R[i] & 1 is true for 1 and 3
//  R[i] & 2 is true for 2 and 3
if (delta == 0) {
result = (R[i] & 1);
}
else  {
//  exclusive or
result = (delta < 0) ^ (R[i] & 2);
}
}

Хитрость заключается в том, чтобы объединить случаи и, таким образом, уменьшить количество реляционных операций.

0

Источник

Accepted Answer

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

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

int signs[] = {1, 1, -1, -1, -1, ...};
int equals[] = {0, 1, 0, 1, 1, ...};
if (A[i+0] <  signs[0]*B[j+0] + equals[0]) break;
if (A[i+1] <  signs[1]*B[j+1] + equals[1]) break;
if (A[i+2] <  signs[2]*B[j+2] + equals[2]) break;
if (A[i+3] <  signs[3]*B[j+3] + equals[3]) break;
if (A[i+4] <  signs[4]*B[j+4] + equals[4]) break;
...

Однако векторизация этого кода должна завершиться неудачей, поскольку компилятор не должен загружаться A[i+1] из памяти до того, как первое условие будет оценено и показано, что оно не выполнено. Таким образом, вы должны сделать оценку состояния независимой друг от друга:

int signs[] = {1, 1, -1, -1, -1, ...};
int equals[] = {0, 1, 0, 1, 1, ...};
int doBreak = 0;
doBreak |= (A[i+0] <  signs[0]*B[j+0] + equals[0]);
doBreak |= (A[i+1] <  signs[1]*B[j+1] + equals[1]);
doBreak |= (A[i+2] <  signs[2]*B[j+2] + equals[2]);
doBreak |= (A[i+3] <  signs[3]*B[j+3] + equals[3]);
doBreak |= (A[i+4] <  signs[4]*B[j+4] + equals[4]);
...
if(doBreak) break;

Теперь вы можете сделать из этого петлю.

1