Безразклонени условия за цели числа — бързо, но могат ли да бъдат направени по-бързи?

Експериментирах със следното и забелязах, че дефинираното тук безразклонено „ако“ (сега с &-!! заместващо *!!) може да ускори определен код с тесни места с до (почти) 2 пъти на 64-битови цели на Intel с clang:

// Produces x if f is true, else 0 if f is false.
#define  BRANCHLESS_IF(f,x)          ((x) & -((typeof(x))!!(f)))

// Produces x if f is true, else y if f is false.
#define  BRANCHLESS_IF_ELSE(f,x,y)  (((x) & -((typeof(x))!!(f))) | \
                                     ((y) & -((typeof(y)) !(f))))

Имайте предвид, че f трябва да бъде разумно прост израз без странични ефекти, така че компилаторът да може да направи най-добрите си оптимизации.

Производителността силно зависи от процесора и компилатора. Представянето на „ако“ без разклонения е отлично със звън; Все още не съм намерил случаи, в които „if/else“ без разклонения е по-бърз.

Въпросът ми е: те безопасни и преносими ли са, както е написано (което означава, че гарантирано дават правилни резултати за всички цели) и могат ли да бъдат направени по-бързи?

Примерно използване на безразклонен if/else

Те изчисляват 64-битов минимум и максимум.

inline uint64_t uint64_min(uint64_t a, uint64_t b)
{
  return BRANCHLESS_IF_ELSE((a <= b), a, b);
}

inline uint64_t uint64_max(uint64_t a, uint64_t b)
{
  return BRANCHLESS_IF_ELSE((a >= b), a, b);
}

Примерно използване на безразклонно ако

Това е 64-битово модулно допълнение — то изчислява (a + b) % n. Версията с разклоняване (не е показана) страда ужасно от неуспешно предсказване на разклонения, но версията без разклонения е много бърза (поне с clang).

inline uint64_t uint64_add_mod(uint64_t a, uint64_t b, uint64_t n)
{
  assert(n > 1); assert(a < n); assert(b < n);

  uint64_t c = a + b - BRANCHLESS_IF((a >= n - b), n);

  assert(c < n);
  return c;
}

Актуализация: Пълен конкретен работещ пример за if без разклонения

По-долу е напълно работеща C11 програма, която демонстрира разликата в скоростта между разклонени и безразклонени версии на просто условно if, ако искате да го изпробвате на вашата система. Програмата изчислява модулно степенуване, което е (a ** b) % n, за изключително големи стойности.

За да компилирате, използвайте следното в командния ред:

• -O3 (или каквото и да е високо ниво на оптимизация, което предпочитате)
• -DNDEBUG (за деактивиране на твърдения, за скорост)
• Или -DBRANCHLESS=0, или -DBRANCHLESS=1, за да укажете съответно разклонено или безразклонено поведение

В моята система ето какво се случва:

$ cc -DBRANCHLESS=0 -DNDEBUG -O3 -o powmod powmod.c && ./powmod
BRANCHLESS = 0
CPU time:  21.83 seconds
foo = 10585369126512366091

$ cc -DBRANCHLESS=1 -DNDEBUG -O3 -o powmod powmod.c && ./powmod
BRANCHLESS = 1
CPU time:  11.76 seconds
foo = 10585369126512366091

$ cc --version
Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin14.1.0
Thread model: posix

И така, безразклонната версия е почти два пъти по-бърза от разклонената версия на моята система (3,4 GHz. Intel Core i7).

// SPEED TEST OF MODULAR MULTIPLICATION WITH BRANCHLESS CONDITIONALS

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>
#include <assert.h>

typedef  uint64_t  uint64;

//------------------------------------------------------------------------------
#if BRANCHLESS
  // Actually branchless.
  #define  BRANCHLESS_IF(f,x)          ((x) & -((typeof(x))!!(f)))
  #define  BRANCHLESS_IF_ELSE(f,x,y)  (((x) & -((typeof(x))!!(f))) | \
                                       ((y) & -((typeof(y)) !(f))))
#else
  // Not actually branchless, but used for comparison.
  #define  BRANCHLESS_IF(f,x)          ((f)? (x) : 0)
  #define  BRANCHLESS_IF_ELSE(f,x,y)   ((f)? (x) : (y))
#endif

//------------------------------------------------------------------------------
// 64-bit modular multiplication.  Computes (a * b) % n without division.

static uint64 uint64_mul_mod(uint64 a, uint64 b, const uint64 n)
{
  assert(n > 1); assert(a < n); assert(b < n);

  if (a < b) { uint64 t = a; a = b; b = t; }  // Ensure that b <= a.

  uint64 c = 0;
  for (; b != 0; b /= 2)
  {
    // This computes c = (c + a) % n if (b & 1).
    c += BRANCHLESS_IF((b & 1), a - BRANCHLESS_IF((c >= n - a), n));
    assert(c < n);

    // This computes a = (a + a) % n.
    a += a - BRANCHLESS_IF((a >= n - a), n);
    assert(a < n);
  }

  assert(c < n);
  return c;
}

//------------------------------------------------------------------------------
// 64-bit modular exponentiation.  Computes (a ** b) % n using modular
// multiplication.

static
uint64 uint64_pow_mod(uint64 a, uint64 b, const uint64 n)
{
  assert(n > 1); assert(a < n);

  uint64 c = 1;

  for (; b > 0; b /= 2)
  {
    if (b & 1)
      c = uint64_mul_mod(c, a, n);

    a = uint64_mul_mod(a, a, n);
  }

  assert(c < n);
  return c;
}

//------------------------------------------------------------------------------
int main(const int argc, const char *const argv[const])
{
  printf("BRANCHLESS = %d\n", BRANCHLESS);

  clock_t clock_start = clock();

  #define SHOW_RESULTS 0

  uint64 foo = 0;  // Used in forcing compiler not to throw away results.

  uint64 n = 3, a = 1, b = 1;
  const uint64 iterations = 1000000;
  for (uint64 iteration = 0; iteration < iterations; iteration++)
  {
    uint64 c = uint64_pow_mod(a%n, b, n);

    if (SHOW_RESULTS)
    {
      printf("(%"PRIu64" ** %"PRIu64") %% %"PRIu64" = %"PRIu64"\n",
             a%n, b, n, c);
    }
    else
    {
      foo ^= c;
    }

    n = n * 3 + 1;
    a = a * 5 + 3;
    b = b * 7 + 5;
  }

  clock_t clock_end = clock();
  double elapsed = (double)(clock_end - clock_start) / CLOCKS_PER_SEC;
  printf("CPU time:  %.2f seconds\n", elapsed);

  printf("foo = %"PRIu64"\n", foo);

  return 0;
}

Втора актуализация: Intel срещу ARM производителност

• Тестването на 32-битови ARM цели (iPhone 3GS/4S, iPad 1/2/3/4, както е компилирано от Xcode 6.1 с clang) разкрива, че безразклоненото „ако“ тук всъщност е около 2–3 пъти по-бавно< /em> отколкото троичния ?: за модулния код за степенуване в тези случаи. Така че изглежда, че тези безклонови макроси не са добра идея, ако е необходима максимална скорост, въпреки че могат да бъдат полезни в редки случаи, когато е необходима постоянна скорост.
• На 64-битови ARM цели (iPhone 6+, iPad 5) безразклоненият „if“ работи със същата скорост като троичния ?: — отново както е компилиран от Xcode 6.1 с clang.
• Както за Intel, така и за ARM (както е компилирано от clang), безразклоненият „if/else“ беше около два пъти по-бавен от троичния ?: за изчисляване на min/max.