Микрооптимизация функции сравнения C++

Я думаю, что понял большую часть этого.

Когда я опубликовал сборку для функций в своем OP-редактировании, я заметил, что встроенная версия может отличаться. Я не проверял и не публиковал код синхронизации, потому что он был более сложным, и потому что я думал, что процесс встраивания не изменится независимо от того, происходит ли ветвление в Compare().

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

Compare(): 7.18ns avg
Compare2(): 3.15ns avg

Затем, когда я заменил a[i]=rand()%2 на a[i]=false, я получил следующее:

Compare(): 2.59ns avg
Compare2(): 3.16ns avg

Это демонстрирует выигрыш от предсказания ветвлений. Тот факт, что замена a[i] не дала никаких улучшений, изначально показывает, что встраивание удалило ветвь.

Итак, последняя часть загадки заключается в том, почему встроенный Compare2() превосходит встроенный Compare(). Я полагаю, я мог бы опубликовать сборку кода синхронизации. Кажется вполне правдоподобным, что некоторые особенности встраивания функций могут привести к этому, поэтому я согласен закончить свое расследование на этом. Я заменю Compare() на Compare2() в своем приложении.

Спасибо за множество полезных комментариев.

РЕДАКТИРОВАТЬ: я должен добавить, что вероятная причина того, что Compare2 превосходит все остальные, заключается в том, что процессор может выполнять оба сравнения параллельно. Это была интуиция, которая привела меня к тому, как я написал функцию. Все другие варианты по существу требуют двух логически последовательных операций.

Я написал библиотеку C++ под названием Celero, предназначенную для тестирования именно таких оптимизаций и альтернатив. (Беззастенчивая самореклама: https://github.com/DigitalInBlue/Celero)

Я запустил ваши случаи, используя следующий код:

class StackOverflowFixture : public celero::TestFixture
{
  public:
    StackOverflowFixture()
    {
    }

    inline bool NoOp(bool greater, int p1, int p2) 
    {
      return true;
    }

    inline bool Compare(bool greater, int p1, int p2) 
    {
      if(greater == true)
      {
        return p1>=p2;
      }

      return p1<=p2;
    }

    inline bool Compare2(bool greater, int p1, int p2)
    {
      bool ret[2] = {p1<=p2,p1>=p2};
      return ret[greater];
    }

    inline bool Compare3(bool greater, int p1, int p2) 
    {
      return (!greater != !(p1 <= p2)) | (p1 == p2);
    }

    inline bool Compare4(bool greater, int p1, int p2) 
    {
      return (greater ^ (p1 <= p2)) | (p1 == p2);
    }
};

BASELINE_F(StackOverflow, Baseline, StackOverflowFixture, 100, 5000000)
{
  celero::DoNotOptimizeAway(NoOp(rand()%2, rand(), rand()));
}

BENCHMARK_F(StackOverflow, Compare, StackOverflowFixture, 100, 5000000)
{
  celero::DoNotOptimizeAway(Compare(rand()%2, rand(), rand()));
}

BENCHMARK_F(StackOverflow, Compare2, StackOverflowFixture, 100, 5000000)
{
  celero::DoNotOptimizeAway(Compare2(rand()%2, rand(), rand()));
}

BENCHMARK_F(StackOverflow, Compare3, StackOverflowFixture, 100, 5000000)
{
  celero::DoNotOptimizeAway(Compare3(rand()%2, rand(), rand()));
}

BENCHMARK_F(StackOverflow, Compare4, StackOverflowFixture, 100, 5000000)
{
  celero::DoNotOptimizeAway(Compare4(rand()%2, rand(), rand()));
}

Результаты показаны ниже:

[==========]
[  CELERO  ]
[==========]
[ STAGE    ] Baselining
[==========]
[ RUN      ] StackOverflow.Baseline -- 100 samples, 5000000 calls per run.
[     DONE ] StackOverflow.Baseline  (0.690499 sec) [5000000 calls in 690499 usec] [0.138100 us/call] [7241140.103027 calls/sec]
[==========]
[ STAGE    ] Benchmarking
[==========]
[ RUN      ] StackOverflow.Compare -- 100 samples, 5000000 calls per run.
[     DONE ] StackOverflow.Compare  (0.782818 sec) [5000000 calls in 782818 usec] [0.156564 us/call] [6387180.672902 calls/sec]
[ BASELINE ] StackOverflow.Compare 1.133699
[ RUN      ] StackOverflow.Compare2 -- 100 samples, 5000000 calls per run.
[     DONE ] StackOverflow.Compare2  (0.700767 sec) [5000000 calls in 700767 usec] [0.140153 us/call] [7135039.178500 calls/sec]
[ BASELINE ] StackOverflow.Compare2 1.014870
[ RUN      ] StackOverflow.Compare3 -- 100 samples, 5000000 calls per run.
[     DONE ] StackOverflow.Compare3  (0.709471 sec) [5000000 calls in 709471 usec] [0.141894 us/call] [7047504.408214 calls/sec]
[ BASELINE ] StackOverflow.Compare3 1.027476
[ RUN      ] StackOverflow.Compare4 -- 100 samples, 5000000 calls per run.
[     DONE ] StackOverflow.Compare4  (0.712940 sec) [5000000 calls in 712940 usec] [0.142588 us/call] [7013212.893091 calls/sec]
[ BASELINE ] StackOverflow.Compare4 1.032500
[==========]
[ COMPLETE ]
[==========]

Учитывая этот тест, похоже, что Compare2 — лучший вариант для этой микрооптимизации.

РЕДАКТИРОВАТЬ:

Сборка Compare2 (лучший случай):

cmp r8d, r9d
movzx   eax, dl
setle   BYTE PTR ret$[rsp]
cmp r8d, r9d
setge   BYTE PTR ret$[rsp+1]
movzx   eax, BYTE PTR ret$[rsp+rax]

Compare3 Assembly (следующий лучший случай):

xor r11d, r11d
cmp r8d, r9d
mov r10d, r11d
setg    r10b
test    dl, dl
mov ecx, r11d
sete    cl
mov eax, r11d
cmp ecx, r10d
setne   al
cmp r8d, r9d
sete    r11b
or  eax, r11d

Как насчет этого...

inline bool Compare3(bool greater, int p1, int p2) 
{
  return (!greater != !(p1 <= p2)) | (p1 == p2);
}

or

inline bool Compare4(bool greater, int p1, int p2) 
{
  return (greater ^ (p1 <= p2)) | (p1 == p2);
}