Эффективность сравнений в C ++? (abs (X)> 1 против abs (x)! = 0) - PullRequest
4 голосов
/ 09 июля 2009

знаю - преждевременная оптимизация.
Но у меня есть код, который должен выяснить, изменилась ли позиция по сравнению с кэшированной позицией.

Текущий код:

if(abs(newpos-oldpos) > 1){
    .....
}

Более эффективно использовать следующее?

if(abs(newpos-oldpos) != 0){
    ....
}

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

Ответы [ 12 ]

13 голосов
/ 09 июля 2009

Основная причина не менять

(abs(newpos-oldpos) > 1)

до

(abs(newpos-oldpos) != 0)

в том, что они семантически разные.

Когда abs(newpos-oldpos) == 1, вы получите разные результаты. Это пример того, почему вы должны неохотно менять вещи «просто потому, что» - за исключением того факта, что в любом случае не будет ощутимой разницы в производительности (и, вероятно, также нет реальной разницы).

13 голосов
/ 09 июля 2009

Почему не это?

if (newpos != oldpos) {
    ...
}

Более эффективен, чем оба из-за отсутствия abs(), и понятнее для загрузки.

4 голосов
/ 09 июля 2009

Второй более эффективен, если вы удалите ненужный abs (). Если вы сравниваете с нулем, не имеет значения, положительная или отрицательная разница. Кроме того, я думаю, что это более читабельно. Однако эти два условия не кажутся эквивалентными; что произойдет, если abs (newpos-oldpos) == 1?

3 голосов
/ 09 июля 2009

Если я что-то упустил, они не делают то же самое. x> 1 не совпадает с x! = 0.

3 голосов
/ 09 июля 2009

На большинстве архитектур не должно быть никакой разницы. Сравнения, как правило, выполняются внутри ЦП путем вычитания и установки ALU кодов условий. Разветвление выполняется путем тестирования кодов условий (т. Е. Переход на неравных проверяет нулевой бит в регистре кодов условий, переход на большее обычно проверяет флаги обнуления, отрицания и переполнения).

2 голосов
/ 09 июля 2009

Не пытайтесь оптимизировать операторы сравнения для равных операторов; они должны иметь одинаковое время и иметь одинаковое значение для целых чисел.

Если вы вообще собираетесь оптимизировать, попробуйте

if ((newpos - oldpos > 1) || (oldpos - newpos > 1))

, который все еще читается. (а также постоянно корректно для плавающих pt #s)

редактирование: Ack! Не берите в голову, если вы хотите узнать, изменилась ли позиция какой-то минимальной дельтой (я изначально прочитал ваш вопрос кода буквально без просмотра общей цели, которую вы пытаетесь достичь), используйте это:

if ((newpos - oldpos > delta) || (oldpos - newpos > delta))

для дельты> 0, или это (как предложил Ной М)

if (newpos != oldpos)

для дельта = 0

1 голос
/ 10 июля 2009

Поскольку ответ будет зависеть от вашей архитектуры, давайте взглянем на сгенерированный код на x86-64 (с gcc -O3):

#include <math.h>

int t_gt(int x) { // note! not equivalent to the others
    return abs(x) > 1;
}

int t_ge(int x) {
    return abs(x) >= 1;
}

int t_ne(int x) {
    return abs(x) != 1;
}

становится:

Disassembly of section .text:

0000000000000000 <t_gt>:
#include <math.h>

int t_gt(int x) {
   0:   89 f8                   mov    %edi,%eax
   2:   c1 f8 1f                sar    $0x1f,%eax
   5:   31 c7                   xor    %eax,%edi
   7:   29 c7                   sub    %eax,%edi
   9:   31 c0                   xor    %eax,%eax
   b:   83 ff 01                cmp    $0x1,%edi
   e:   0f 9f c0                setg   %al
    return abs(x) > 1;
}
  11:   c3                      retq   
  12:   66 66 66 66 66 2e 0f    nopw   %cs:0x0(%rax,%rax,1)
  19:   1f 84 00 00 00 00 00 

0000000000000020 <t_ge>:

int t_ge(int x) {
  20:   89 f8                   mov    %edi,%eax
  22:   c1 f8 1f                sar    $0x1f,%eax
  25:   31 c7                   xor    %eax,%edi
  27:   29 c7                   sub    %eax,%edi
  29:   31 c0                   xor    %eax,%eax
  2b:   85 ff                   test   %edi,%edi
  2d:   0f 9f c0                setg   %al
    return abs(x) >= 1;
}
  30:   c3                      retq   
  31:   66 66 66 66 66 66 2e    nopw   %cs:0x0(%rax,%rax,1)
  38:   0f 1f 84 00 00 00 00 
  3f:   00 

0000000000000040 <t_ne>:

int t_ne(int x) {
  40:   89 f8                   mov    %edi,%eax
  42:   c1 f8 1f                sar    $0x1f,%eax
  45:   31 c7                   xor    %eax,%edi
  47:   29 c7                   sub    %eax,%edi
  49:   31 c0                   xor    %eax,%eax
  4b:   83 ff 01                cmp    $0x1,%edi
  4e:   0f 95 c0                setne  %al
    return abs(x) != 1;
}
  51:   c3                      retq   

Как видите, есть два различия:

  • Коды условий в установленных * операциях отличаются. Это скорее всего не повлияет на скорость.
  • Для t_ge используется двухбайтовый регистровый тест (AND), в то время как два других используют cmp (вычитание) и буквенный однобайтовый операнд для сравнения.

Хотя разница между различными вариантами set * и test и cmp, вероятно, равна нулю, дополнительный однобайтовый операнд для cmp может снизить производительность на неизмеримо малую величину.

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

0000000000000060 <t_ne2>:

int t_ne2(int x) {
  60:   31 c0                   xor    %eax,%eax
  62:   85 ff                   test   %edi,%edi
  64:   0f 95 c0                setne  %al
    return (x != 0);
}
  67:   c3                      retq   

Имейте в виду, что эти выводы могут не относиться к другим архитектурам; однако потеря пресса наверняка будет быстрее где угодно.

1 голос
/ 09 июля 2009

Игнорируя тот факт, что они не являются эквивалентными операциями, в x86 вы можете сохранить цикл или около того.

abs (new-pos)> 1

будет

  1. Вычитание
  2. Abs
  3. Сравнить с 1
  4. Jmp

abs (newpos-oldpos)! = 0

будет

  1. Вычитание
  2. Abs
  3. Jmp - Если abs встроен и последняя операция соответствующим образом устанавливает нулевой флаг.

Я был бы удивлен, если бы это оказало какое-либо измеримое влияние на вашу программу - Вы определенно заслуживаете похвалы, если ваш код уже работает настолько невероятно напряженно.

0 голосов
/ 10 июля 2009

По крайней мере на компиляторе, который я сейчас использую (gcc 4.2), код сборки, который он генерирует для вашего первого выражения, использует описанный трюк здесь . Затем он уменьшает результат и использует код условия, чтобы решить, как выполнить переход.

Во-вторых, он переписывает его на что-то вроде newpos != oldpos

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

Кстати, если вы имели в виду abs(newpos - oldpos) >= 1 для первого теста, он все равно генерирует последовательность абсолютных значений. Это, вероятно, из-за возможности переполнения в вычитании, предполагая систему дополнения до двух. На моей машине, например, abs(-2147483648 - 2147483647) дает 1, что провалило бы ваш тест, если вы искали, скажем, дельту, 2 или более, даже если они явно совершенно разные. Оптимизатор компилятора должен соблюдать осторожность, чтобы сохранить такое поведение даже в крайних случаях.

0 голосов
/ 09 июля 2009

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

Если код должен сравнивать два числа с плавающей запятой, то на большинстве машин невозможна оптимизация, но важно то, что речь идет не о преждевременной оптимизации, а о рефакторинге кода, который вы не совсем понимаете.

...