Эффективная проверка, принадлежит ли незначенное целое число. ⇐ C++

[Anonymous]

В различных контекстах я столкнулся с вопросом о определении того, принадлежит ли данное неподтвержденное целочисленное значение ни одному из двух непересекающих интервалов, и не редко эти проверки вводят значительную неэффективность. Моими целями в реализации таких проверок, в порядке уменьшения важности, являются: (1) устранение (зависимых от данных) филиалов; (2) минимизация общего количества операций; (3) уменьшение длины цепочек зависимости. Я понимаю, что цель (3) может быть в конфликте с целями (1) и (2); Это наименее важно для меня, так как я обычно сосредотачиваюсь на пропускной способности, а не на задержку. Но для простоты исследования и экспозиции я подумал, что могу ограничить себя безписанными байтами, в частности тип uint8_t C ++. Я понимаю, что это может быть боковым шагом на некоторых других проблемах, таких как эффективная конструкция целочисленных константов на процессорах RISC. Полагайтесь на применение XOR для преобразования двух интервалов в один интервал (как в случаях 0 и 1). < /p>
, в то время как я обычно могу избавиться от дел вручную, грандиозная схема для такой оптимизации ускользает от меня. Я не знаю, как компиляторы обращаются к этому. Используют ли они специализированные преобразования для оптимизации комбинаций двухсторонних чеков диапазона, или они просто полагаются на общие упрощения с помощью целочисленных преобразований? Я проверил восхищение Хакер Уоррена, 2-е издание. Определяет, возможно ли оптимизировать проверку включения в течение всего интервала с помощью и или XOR-подхода (или, возможно, других операций, например, предполагая, что одно цикл Mul!), И если это так, также предоставляет специфическую последовательность операций и константов для использования.#include
#include
#include

#define CASE (0)

#if (CASE == 0)
bool in_range_1 (uint8_t a)
{
return ((a >= 0x40u) && (a < 0x50u)) || ((a >= 0x54u) && (a < 0x58u));
}
bool in_range_2 (uint8_t a)
{
return ((a ^ 0x44u) < 0x14u);
}
#elif (CASE == 1)
bool in_range_1 (uint8_t a)
{
return ((a >= 0x67u) && (a < 0x70u)) || ((a >= 0x90u) && (a < 0x98u));
}
bool in_range_2 (uint8_t a)
{
return (((a ^ 0x10u) - 0x77u) < 0x11u);
}
#elif (CASE == 2)
bool in_range_1 (uint8_t a)
{
return ((a >= 0x10u) && (a < 0x20u)) || ((a >= 0x30u) && (a < 0x40u));
}
bool in_range_2 (uint8_t a)
{
return ((a & 0xd0u) == 0x10u);
}
#elif (CASE == 3)
bool in_range_1 (uint8_t a)
{
return ((a >= 0x01u) && (a < 0x21u)) || ((a >= 0x41u) && (a < 0x61u));
}
bool in_range_2 (uint8_t a)
{
return (((a & 0xbfu) - 0x01u) < 0x20u);
}
#else
#error no such CASE
#endif // CASE

int main (void)
{
uint8_t a = 0;
do {
bool ref = in_range_1 (a);
bool res = in_range_2 (a);
if (res != ref) {
printf ("error: a=%02x res=%d ref=%d\n", a, res, ref);
return EXIT_FAILURE;
}
a++;
} while (a);
printf ("case %d: test passed\n", CASE);
return EXIT_SUCCESS;
}

Чтобы предоставить пример улучшений, которые можно достичь, я скомпилировал случай 0 для 32-разрядной платформы RISC-V с использованием Clang 20.1 -O3 . Сгенерированный код для двух функций с идентичной функциональностью выглядит так: < /p>
in_range_1(unsigned char):
andi a1, a0, 240
andi a0, a0, 252
addi a1, a1, -64
addi a0, a0, -84
seqz a1, a1
seqz a0, a0
or a0, a0, a1
ret

in_range_2(unsigned char):
xori a0, a0, 68
sltiu a0, a0, 20
ret


Подробнее здесь: https://stackoverflow.com/questions/795 ... wo-compile