Как оптимизировать эту строку кода C (проверка диапазона)?

Question

Есть ли способ оптимизировать следующую строку кода C (чтобы избежать разветвления)?

if ((i < -threshold) || (i > threshold)) 
{ 
    counter++; 
}

Все переменные представляют собой 16-разрядные целые числа со знаком.Оптимизированная версия должна быть легко переносимой.

Answer 1

Как насчет:

counter += (i < -threshold) | (i > threshold);

Если исходный код действителен, то это также должно работать переносимым способом.Стандарт гласит, что реляционные операторы (<, > и т. Д.) Возвращают int, равный 1 при успехе или 0 при ошибке.

UPDATE

Чтобы ответить на комментарий Шина ниже, следующий код:

int main()
{
    short threshold = 10;
    short i = 20;
    short counter = 0;

    counter += (i < -threshold) | (i > threshold);

    return 0;
}

приводит к следующему дизассемблеру на x86 с использованием GCC без оптимизаций:

  push   %rbp
  mov    %rsp,%rbp
  movw   $0xa,-6(%rbp)
  movw   $0x14,-4(%rbp)
  movw   $0x0,-2(%rbp)
  movswl -4(%rbp),%edx
  movswl -6(%rbp),%eax
  neg    %eax
  cmp    %eax,%edx
  setl   %dl
  movzwl -4(%rbp),%eax
  cmp    -6(%rbp),%ax
  setg   %al
  or     %edx,%eax
  movzbw %al,%dx
  movzwl -2(%rbp),%eax
  lea    (%rdx,%rax,1),%eax
  mov    %ax,-2(%rbp)
  mov    $0x0,%eax
  leaveq 
  retq  

Answer 2

Существует стандартная идиома для проверки диапазона с одной инструкцией сравнения. Это идет как:

(unsigned)x - a <= (unsigned)b - a   /* a <= x <= b */
(unsigned)x - a < (unsigned)b - a    /* a <= x < b */

В качестве распространенного примера (эта версия, если isdigit гарантированно верна по стандарту):

(unsigned)ch - '0' < 10

Если ваш исходный тип больше int (например, long long), вам нужно будет использовать более крупные типы без знака (например, unsigned long long). Если a и b являются константами или уже имеют тип без знака, или если вы знаете, что b-a не будет переполнен, вы можете опустить приведение из b.

Чтобы этот метод работал, естественно, вы должны иметь a<=b, а типы / значения должны быть такими, чтобы исходное выражение (т.е. a <= x && x <= b или подобное) действовало математически правильно. Например, если x было подписано, а b без знака, x<=b может быть оценено как ложное при x=-1 и b=UINT_MAX-1. Пока все ваши исходные типы имеют подпись или меньше, чем тип без знака, к которому вы применяете, это не проблема.

Что касается того, как работает этот "трюк", то после уменьшения по модулю UINT_MAX+1 чисто определяется, лежит ли x-a в диапазоне от 0 до b-a.

В вашем случае, я думаю, что следующее должно работать нормально:

(unsigned)i + threshold > 2U * threshold;

Если threshold не изменяется между итерациями цикла, компилятор, вероятно, может хранить в регистрах threshold и 2U*threshold.

Говоря об оптимизации, хороший компилятор должен оптимизировать исходный тест диапазона для использования арифметики без знака, если он знает, что ограничения выполнены. Я подозреваю, что многие делают это с константами a и b, но, возможно, не с более сложными выражениями. Тем не менее, даже если компилятор может оптимизировать его, идиома (unsigned)x-a<b-a все еще чрезвычайно полезна в макросах, где вы хотите убедиться, что x вычисляется ровно один раз.

Answer 3

О, очень жаль, что на вопрос уже дан ответ.Перефразируя ответ Оли, код

#include <stdint.h>
int main()
{
    int32_t threshold_square = 100;
    int16_t i = 20;
    int16_t counter = 0;

    counter += ( (int32_t) i * i > threshold_square);

    return 0;
}

дает следующий ассемблер x86 с использованием GCC без оптимизации

pushq   %rbp
movq    %rsp, %rbp
movl    $100, -8(%rbp)
movw    $20, -2(%rbp)
movw    $0, -4(%rbp)
movswl  -2(%rbp),%edx
movswl  -2(%rbp),%eax
imull   %edx, %eax
cmpl    -8(%rbp), %eax
setg    %al
movzbl  %al, %edx
movzwl  -4(%rbp), %eax
leal    (%rdx,%rax), %eax
movw    %ax, -4(%rbp)
movl    $0, %eax
leave
ret

, что на четыре инструкции меньше, чем при использовании (i < -threshold) | (i > threshold)

Лучше это или нет, конечно, в зависимости от архитектуры.

(Использование stdint.h для иллюстративных целей, для строгой замены C89 на все, что имеет отношение к целевой системе.)

Answer 4

Этот код не имеет ветки с высокой переносимостью (однако, реализация abs может иметь такую ​​ветку).

#include <stdlib.h>
counter += abs(i) > threshold;

Это простейшее стандартное выражение.

Если ваш компилятор не использует оптимизированный макрос для abs (), вы можете использовать свою собственную макро / встроенную функцию.

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

#define ABS(x) ((x)*(((x)>>15)|1))

#define ABS(x) ((x)-((x)>>15)^((x)>>15))

Также вы можете заменить оператор сравнения следующим выражением:

#define LESS(x, y) (-((x)-(y))>>15))

Результирующий код:

counter -= ((threshold - abs(i)) >> 15);

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

Answer 5

Оли Чарльзуорт, я думаю, имеет правильную идею. Тем не менее, я подозреваю, что его можно оптимизировать (за счет читабельности).

Порог можно нормализовать до нуля, чтобы удалить сравнение.

То есть ...

counter += ((unsigned) (i + threshhold)  < (unsigned) (threshhold + threshhold));

Answer 6

Это основано на битовом хиддинг-хаке , (настоятельно рекомендуется)

#define CHAR_BIT 8

int main()
{
  int i=-3; // example input
  int treshold=2; // example treshold
  int count=0;
  // step 1: find the absolute value of i
  unsigned int r;  // the result goes here 
  int const mask = i >> (sizeof(int) * CHAR_BIT - 1);
  r = (i + mask) ^ mask;
  // step 2: compute the sign of the difference
  // sign becomes 0 (if r<=treshold)
  // sign becomes 1 otherwise
  int sign = 1 ^ ((unsigned int)(r-treshold-1) >> (sizeof(int) * CHAR_BIT - 1));
  count+=sign;
  return count;
}

Это работает для 32-битных целых, адаптация к 16-битным должна быть легкой. Компилируется с использованием g ++.

Скорость зависит от используемого процессора. В конце концов, ветвление может быть быстрее.

Answer 7

Вы можете использовать следующий прием, который сводит ветви к одной ветви:

if (((unsigned) (i + threshold)) > (threshold << 1)) 
{ 
  counter++; 
}

или, для педантичных:

if (((unsigned) i + (unsigned) threshold) > ((unsigned) threshold << 1)) 
{ 
  counter++; 
}

Answer 8

В зависимости от распределения значений 'i' ваш ЦП вполне может кэшировать прогноз ветвления для вас лучше, чем любое изменение кода, которое вы можете сделать.Смотрите http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/ для интересной рецензии.Reddit обсуждение здесь: http://www.reddit.com/r/programming/comments/c7ues/fast_and_slow_ifstatements_branch_prediction_in/

Answer 9

Сравните абсолютное значение обоих

short imask = i >> sizeof(short) * 8 - 1; //compute the sign bit 1 or 0
short tmask = threshold >> sizeof(short) * 8 - 1; //compute the sign bit 1 or 0

short iabsolute = (i + imask) ^ imask; // compute i absolute
short tabsolute = (threshold + tmask) ^ tmask; // compute threshold absolute

counter += iabsolute > tabsolute;

Answer 10

Что не так с оригинальным кодом? Это действительно нуждается в ручной оптимизации?

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