Логический/Relational Expression Optimization

Question

мне нужно оптимизировать выражение вида:

(a > b) || (a > c) 

Я попробовал несколько оптимизированных форм, одна из которых заключается в следующем:

(a * 2) > (b + c) 

Оптимизация не из точка компилятора. Я хотел бы уменьшить два> s до одного.

Это основано на предположении, что 1 < = (а, Ь, с) < = 26

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

Answer 1

Лучшее, что я могу придумать это

char a, b, c; 
std::cin >> a >> b >> c; 

if (((b-a) | (c-a)) & 0x80) { 
    // a > b || a > c 
} 

С gcc -O2 это генерирует только один условный переход

40072e:  29 c8     sub %ecx,%eax 
400730:  29 ca     sub %ecx,%edx 
400732:  09 d0     or  %edx,%eax 
400734:  a8 80     test $0x80,%al 
400736:  74 17     je  40074f <main+0x3f> 

Это оптимизирует использование ограничений входных значений, так как значения не может быть больше чем 26, то вычитание a из b даст вам отрицательное значение, когда a > b, в дополнении 2 вы знаете, что бит 7 будет установлен в этом случае - то же самое относится к c. I затем ИЛИ оба так, что бит 7 указывает, a > b || a > c, наконец мы проверим бит 7 на И с 0x80 и веткой на этом.

Обновление: Из любопытства Я приурочил 4 разных способа кодирования. Для генерации тестовых данных я использовал простой линейный конгруэнтный генератор псевдослучайных чисел. Я приурочил его к циклу для 100 миллионов итераций.Я предположил для простоты, что если условие истинно, мы хотим добавить 5 к счетчику, ничего не делать. Я приурочил его, используя g++ (GCC) 4.6.3 20120306 (Red Hat 4.6.3-2) на Intel Xeon X5570 @ 2.93GHz, используя -O2 уровень оптимизации.

Вот код (закомментируйте все, но один из условных вариантов):

#include <iostream> 
unsigned myrand() { 
    static unsigned x = 1; 
    return (x = x * 1664525 + 1013904223); 
} 

int main() { 
    size_t count = 0; 
    for(size_t i=0; i<100000000; ++i) { 
     int a = 1 + myrand() % 26; 
     int b = 1 + myrand() % 26; 
     int c = 1 + myrand() % 26; 

     count += 5 & (((b-a) | (c-a)) >> 31);  // 0.635 sec 
     //if (((b-a) | (c-a)) & 0x80) count += 5;  // 0.660 sec 
     //if (a > std::max(b,c)) count += 5;   // 0.677 sec 
     //if (a > b || a > c) count += 5;   // 1.164 sec 
    } 
    std::cout << count << std::endl; 
    return 0; 
} 

Самый быстрый является модификацией по предложению в моем ответе, где мы используем знаковое для создания маски, которая либо 32 1s или 32 0s в зависимости от того, является ли условие истинным для false, и используйте это для маскировки добавляемого 5, чтобы он либо добавлял 5, либо 0. В этом варианте нет ветвей. Время в комментариях к каждой строке. Наиболее медленным было исходное выражение (a > b || a > c).

Answer 2

Ответ, вероятно: вы не хотите оптимизировать это. Более того, я сомневаюсь, что есть способ написать это более эффективно. Если вы говорите, что a, b и c - значения от 1 до 26, вы не должны использовать целые числа (вам не нужна эта точность), если вы хотите быть оптимальными (по размеру) в любом случае.

Если a> b, выражение a> c не будет выполнено в любом случае. Таким образом, у вас есть максимум 2 (и как минимум 1) условных операций, что действительно не стоит оптимизировать.

Answer 3

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

a > b || a > c 

будет вычисляться:

compare a b 
jump not greater 
compare a c 
jump not greater 

где

a * 2 > b + c 

дает:

shift a left 1 (in temp1) 
add b to c (in temp2) 
compare temp1 temp2 
jump if not greater 

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