main.c++

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstdlib>

#ifndef __has_attribute
#define __has_attribute(x) (0)
#endif /* __has_attribute */

#ifndef __has_builtin
#define __has_builtin(x) (0)
#endif /* __has_builtin */

#ifndef __fallthrough
#if __has_attribute(__fallthrough__)
#define __fallthrough __attribute__((__fallthrough__))
#else
#define __fallthrough
#endif
#endif /* __fallthrough */

#if defined(__INTEL_COMPILER)
#define __builtin_expect_with_probability(expr, value, prob) (expr)
#endif

#if !defined(__builtin_expect_with_probability) &&                             \
    !__has_builtin(__builtin_expect_with_probability) &&                       \
    (!defined(__GNUC__) || __GNUC__ < 9 || defined(__INTEL_COMPILER))
#define __builtin_expect_with_probability(expr, value, prob) (expr)
#endif /* __builtin_expect_with_probability */

#if !defined(__clang__)
#define CLANG_X86CMOV_NOTICE "not a CLANG/LLVM compiler"
#elif !(defined(i386) || defined(__386) || defined(__i386) ||                  \
        defined(__i386__) || defined(i486) || defined(__i486) ||               \
        defined(__i486__) || defined(i586) | defined(__i586) ||                \
        defined(__i586__) || defined(i686) || defined(__i686) ||               \
        defined(__i686__) || defined(_M_IX86) || defined(_X86_) ||             \
        defined(__THW_INTEL__) || defined(__I86__) || defined(__INTEL__) ||    \
        defined(__x86_64) || defined(__x86_64__) || defined(__amd64__) ||      \
        defined(__amd64) || defined(_M_X64) || defined(_M_AMD64) ||            \
        defined(__IA32__) || defined(__INTEL__))
#define CLANG_X86CMOV_NOTICE "not a x86/IA32 target"
#elif __clang_major__ < 5
#define CLANG_X86CMOV_NOTICE "none needed for CLANG < 5"
#elif defined(CLANG_X86CMOV_CRUTCH)
#define CLANG_X86CMOV_NOTICE CLANG_X86CMOV_CRUTCH
#else
#define CLANG_X86CMOV_NOTICE "__asm() workaround"
#define CLANG_X86CMOV_WORKAROUND(size, flag)                                   \
  do                                                                           \
    __asm __volatile(""                                                        \
                     : "+r"(size)                                              \
                     : "r" /* the `b` constraint is more suitable here, but    \
                              cause CLANG to allocate and push/pop an one more \
                              register, so using the `r` which avoids this. */ \
                     (flag));                                                  \
  while (0)
#endif

#ifndef CLANG_X86CMOV_WORKAROUND
#define CLANG_X86CMOV_WORKAROUND(size, flag)                                   \
  do                                                                           \
    /* nope for non-clang or non-x86 */;                                       \
  while (0)
#endif /* CLANG_X86CMOV_WORKAROUND */

/* Адаптивно-упрощенный шаг двоичного поиска:
 *  - без переходов при наличии cmov или аналога;
 *  - допускает лишние итерации;
 *  - но ищет пока size > 2, что требует дозавершения поиска
 *    среди остающихся 0-1-2 элементов. */
#define BINARY_SEARCH_STEP                                                     \
  do {                                                                         \
    const TYPE *const middle = it + (size >> 1);                               \
    size = (size + 1) >> 1;                                                    \
    const bool flag = CMP(*middle, key);                                       \
    CLANG_X86CMOV_WORKAROUND(size, flag);                                      \
    it = flag ? middle : it;                                                   \
  } while (0)

#if 0
/* Компромиссный вариант для альтернативно-одаренного оптимизатора clang.
 *
 * Основное отличие в том, что при "не равно" (true от компаратора) переход
 * делается на 1 ближе к концу массива. Алгоритмически это верно и обеспечивает
 * чуть-чуть более быструю сходимость, но зато требует больше вычислений.
 * Поэтому в целом это более медленно в сравнении с базовым вариантом,
 * а также ВАЖНО(!) не допускается спекулятивное выполнение при size == 0.
 *
 * Однако, двойная зависимость от flag (видимо из-за ошибки в оптимизаторе)
 * подталкивает clang >= 5 к использованию cmov вместо условных переходов. */
#define BINARY_SEARCH_STEP                                                     \
  do {                                                                         \
    const TYPE *const middle = it + (size >> 1);                               \
    const bool flag = CMP(*middle, key);                                       \
    size = ((size + 1) >> 1) - flag;                                           \
    it = flag ? middle + 1 : it;                                               \
  } while (0)

#endif /* #if 0 */

#define TYPE int
#define CMP(a, b) __builtin_expect_with_probability((a) < (b), 0, 0.5)
typedef const TYPE *(*SEARCH)(const TYPE *, size_t, const TYPE);

//------------------------------------------------------------------------------

const TYPE *linear_scan(const TYPE *it, size_t size, const TYPE key) {
  const TYPE *end = it + size;
  while (it < end && CMP(*it, key))
    it += 1;
  return it;
}

//------------------------------------------------------------------------------

/* ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING
 * Paul-Virak Khuong and Pat Morin, March 14, 2017
 * https://arxiv.org/pdf/1509.05053.pdf */
const TYPE *lb_PVKaPM(const TYPE *it, size_t size, const TYPE key) {
  /* template <typename T, typename I>
      I sorted_array<T, I>::_branchfree_search(T x) const {
        const T *base = a;
        I n = this->n;
        while (n > 1) {
          const I half = n / 2;
          base = (base[half] < x) ? &base[half] : base;
          n -= half;
        }
        return (*base < x) + base - a;
      } */
  while (size > 1) {
    intptr_t half = size / 2;
    it = (it[half] < key) ? it + half : it;
    size -= half;
  }
  /* LY: the fix added to the original code */ it += size > 0 && CMP(*it, key);
  return it;
}

//------------------------------------------------------------------------------

#include <bit>

#if !defined(__cpp_lib_int_pow2) || __cpp_lib_int_pow2 < 202002L
namespace std {
inline size_t bit_floor(size_t i) {
  constexpr int num_bits = sizeof(i) * 8;
  return size_t(1) << (num_bits - std::countl_zero(i) - 1);
}
inline size_t bit_ceil(size_t i) {
  constexpr int num_bits = sizeof(i) * 8;
  return size_t(1) << (num_bits - std::countl_zero(i - 1));
}
} // namespace std
#endif /* __cpp_lib_int_pow2 < 202002L */

/* Malte_Skarupke's branchless lower_bound()
 * https://probablydance.com/2023/04/27/beautiful-branchless-binary-search/ */
static const TYPE *lb_MalteSkarupke(const TYPE *it, size_t size,
                                    const TYPE key) {
  const auto end = it + size;
  if (size == 0)
    return end;
  size_t step = std::bit_floor(size);
  if (step != size && CMP(it[step], key)) {
    size -= step + 1;
    if (size == 0)
      return end;
    step = std::bit_ceil(size);
    it = end - step;
  }
  for (step /= 2; step != 0; step /= 2) {
    if (CMP(it[step], key))
      it += step;
  }
  return it + CMP(*it, key);
}

//------------------------------------------------------------------------------

/* Минималистичный вариант с предусловием:
 *  - без обращений за границы при size == 0;
 *  - "совместим" с багом clang;
 *  - сходимость 2:1 на итерацию цикла;
 *  - поиск среди до 4 элементов включительно без повторов цикла. */
const TYPE *ly_bl_mini0(const TYPE *it, size_t size, const TYPE key) {
  while (size > 2)
    BINARY_SEARCH_STEP;
  it += size > 1 && CMP(*it, key);
  it += size > 0 && CMP(*it, key);
  return it;
}

/* Минималистичный вариант с постусловием:
 *  - компилятор/процессор имеют возможность заранее готовиться к переходу;
 *  - сходимость 2:1 на итерацию цикла;
 *  - поиск среди до 4 элементов включительно без повторов цикла;
 *  - в худшем случае один лишний BINARY_SEARCH_STEP. */
const TYPE *ly_bl_mini1(const TYPE *it, size_t size, const TYPE key) {
  do {
    BINARY_SEARCH_STEP;
  } while (size > 2);
  it += size > 1 && CMP(*it, key);
  it += size > 0 && CMP(*it, key);
  return it;
}

/* Минималистичный вариант с хорошим балансом:
 *  - компилятор/процессор имеют возможность заранее готовиться к переходу;
 *  - сходимость 4:1 на итерацию цикла;
 *  - поиск среди до 8 элементов включительно без повторов цикла;
 *  - в худшем случае два лишних BINARY_SEARCH_STEP. */
const TYPE *ly_bl_mini2(const TYPE *it, size_t size, const TYPE key) {
  do {
    BINARY_SEARCH_STEP;
    BINARY_SEARCH_STEP;
  } while (size > 2);
  it += size > 1 && CMP(*it, key);
  it += size > 0 && CMP(*it, key);
  return it;
}

/* Жадный минималистичный вариант с хорошим балансом:
 *  - компилятор/процессор имеют возможность заранее готовиться к переходу;
 *  - сходимость 8:1 на итерацию цикла;
 *  - поиск среди до 16 элементов включительно без повторов цикла;
 *  - в худшем случае три лишних BINARY_SEARCH_STEP. */
const TYPE *ly_bl_mini3(const TYPE *it, size_t size, const TYPE key) {
  do {
    BINARY_SEARCH_STEP;
    BINARY_SEARCH_STEP;
    BINARY_SEARCH_STEP;
  } while (size > 2);
  it += size > 1 && CMP(*it, key);
  it += size > 0 && CMP(*it, key);
  return it;
}

/* Расширенный вариант, с расчётом на использование компилятором таблицы
 * переходов для реализации оператора switch. Если же компилятор поступает
 * как-то иначе, то этот вариант быстро теряет преимущества перед
 * минималистичным. В том числе поэтому, для стимулирования использования
 * таблицы переходов, добавлена обработка значений 5-6-7-8.
 *  - компилятор/процессор имеют возможность заранее готовиться к переходу;
 *  - сходимость 4:1 на итерацию цикла;
 *  - цикл и выход всегда через косвенный переход;
 *  - поиск среди до 16 элементов включительно без повторов цикла;
 *  - в худшем случае один лишний BINARY_SEARCH_STEP. */
const TYPE *ly_bl_switch1(const TYPE *it, size_t size, const TYPE key) {
  while (1) {
    BINARY_SEARCH_STEP;
    switch (size) {
    default:
      BINARY_SEARCH_STEP;
      continue;
    case 8:
    case 7:
    case 6:
    case 5:
      BINARY_SEARCH_STEP;
      __fallthrough /* fall through */;
    case 4:
    case 3:
      BINARY_SEARCH_STEP;
      __fallthrough /* fall through */;
    case 2:
      it += CMP(*it, key);
      __fallthrough /* fall through */;
    case 1:
      it += CMP(*it, key);
      __fallthrough /* fall through */;
    case 0:
      return it;
    }
  }
}

/* Расширенный вариант, с расчётом на использование компилятором таблицы
 * переходов для реализации оператора switch. Если же компилятор поступает
 * как-то иначе, то этот вариант быстро теряет преимущества перед
 * минималистичным. В том числе поэтому, для стимулирования использования
 * таблицы переходов, добавлена обработка значений 5-6-7-8.
 *  - компилятор/процессор имеют возможность заранее готовиться к переходу;
 *  - сходимость 16:1 на итерацию цикла;
 *  - цикл и выход всегда через косвенный переход;
 *  - поиск среди до 32 элементов включительно без повторов цикла;
 *  - в худшем случае два лишних BINARY_SEARCH_STEP;
 *  - можно убрать по-одному BINARY_SEARCH_STEP или добавить еще несколько. */
const TYPE *ly_bl_switch2(const TYPE *it, size_t size, const TYPE key) {
  while (1) {
    BINARY_SEARCH_STEP;
    BINARY_SEARCH_STEP;
    switch (size) {
    default:
      BINARY_SEARCH_STEP;
      BINARY_SEARCH_STEP;
      continue;
    case 8:
    case 7:
    case 6:
    case 5:
      BINARY_SEARCH_STEP;
      __fallthrough /* fall through */;
    case 4:
    case 3:
      BINARY_SEARCH_STEP;
      __fallthrough /* fall through */;
    case 2:
      it += CMP(*it, key);
      __fallthrough /* fall through */;
    case 1:
      it += CMP(*it, key);
      __fallthrough /* fall through */;
    case 0:
      return it;
    }
  }
}

#ifdef __GNUC__

/* Расширенный вариант с явной таблицей переходов.
 *  - компилятор/процессор имеют возможность заранее готовиться к переходу;
 *  - сходимость 4:1 на итерацию цикла;
 *  - цикл и выход всегда через косвенный переход;
 *  - поиск среди до 16 элементов включительно без повторов цикла;
 *  - в худшем случае один лишний BINARY_SEARCH_STEP. */
const TYPE *ly_bl_goto1(const TYPE *it, size_t size, const TYPE key) {
  static const void *addr4jmp[] = {&&case_0,   &&case_1,   &&case_2,
                                   &&case_3_4, &&case_3_4, &&case_5_8,
                                   &&case_5_8, &&case_5_8, &&case_5_8};
  while (1) {
    const char will_jump = size < 17;
    const void *target = addr4jmp[((size + 1) >> 1) & 15];
    BINARY_SEARCH_STEP;
    if (will_jump)
      goto *target;
    BINARY_SEARCH_STEP;
  }
case_5_8:
  BINARY_SEARCH_STEP;
case_3_4:
  BINARY_SEARCH_STEP;
case_2:
  it += CMP(*it, key);
case_1:
  it += CMP(*it, key);
case_0:
  return it;
}

/* Расширенный вариант с явной таблицей переходов.
 *  - компилятор/процессор имеют возможность заранее готовиться к переходу;
 *  - сходимость 16:1 на итерацию цикла;
 *  - цикл и выход всегда через косвенный переход;
 *  - поиск среди до 32 элементов включительно без повторов цикла;
 *  - в худшем случае два лишних BINARY_SEARCH_STEP;
 *  - можно убрать по-одному BINARY_SEARCH_STEP или добавить еще несколько. */
const TYPE *ly_bl_goto2(const TYPE *it, size_t size, const TYPE key) {
  static const void *addr4jmp[] = {&&case_0,   &&case_1,   &&case_2,
                                   &&case_3_4, &&case_3_4, &&case_5_8,
                                   &&case_5_8, &&case_5_8, &&case_5_8};
  while (1) {
    // const char will_jump = size < 33;
    // const void *target = addr4jmp[((size + 3) >> 2) & 15];
    BINARY_SEARCH_STEP;
    const char will_jump = size < 17;
    const void *target = addr4jmp[((size + 1) >> 1) & 15];
    BINARY_SEARCH_STEP;
    if (will_jump)
      goto *target;
    BINARY_SEARCH_STEP;
    BINARY_SEARCH_STEP;
  }
case_5_8:
  BINARY_SEARCH_STEP;
case_3_4:
  BINARY_SEARCH_STEP;
case_2:
  it += CMP(*it, key);
case_1:
  it += CMP(*it, key);
case_0:
  return it;
}

#endif /* __GNUC__ */

/*----------------------------------------------------------------------------*/

#ifdef __GNUC__

template <typename T> inline unsigned clz(T v) noexcept;

template <> inline unsigned clz<unsigned>(unsigned v) noexcept {
  return __builtin_clz(v);
}
template <> inline unsigned clz<unsigned long>(unsigned long v) noexcept {
  return __builtin_clzl(v);
}
template <>
inline unsigned clz<unsigned long long>(unsigned long long v) noexcept {
  return __builtin_clzll(v);
}

inline unsigned nbits(size_t v) noexcept {
  return v ? sizeof(v) * __CHAR_BIT__ - clz(v) : 0;
}

const TYPE *ly_bl_clz_switch(const TYPE *it, size_t size, const TYPE key) {
  switch (nbits(size)) {
  default:
    abort();
  case 31:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 30:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 29:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 28:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 27:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 26:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 25:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 24:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 23:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 22:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 21:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 20:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 19:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 18:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 17:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 16:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;

  case 15:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 14:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 13:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 12:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 11:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 10:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 9:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 8:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 7:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 6:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 5:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 4:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 3:
    BINARY_SEARCH_STEP;
    __fallthrough /* fall through */;
  case 2:
    BINARY_SEARCH_STEP;
    it += size > 1 && CMP(*it, key);
    __fallthrough /* fall through */;
  case 1:
    it += CMP(*it, key);
    __fallthrough /* fall through */;
  case 0:
    return it;
  }
}

const TYPE *ly_bl_clz_goto(const TYPE *it, size_t size, const TYPE key) {
#define BITS 64
  static const void *addr4jmp[BITS] = {
#if BITS > 32
      &&oops,    &&oops,    &&oops,    &&oops,    &&oops,    &&oops,
      &&oops,    &&oops,    &&oops,    &&oops,    &&oops,    &&oops,
      &&oops,    &&oops,    &&oops,    &&oops,    &&oops,    &&oops,
      &&oops,    &&oops,    &&oops,    &&oops,    &&oops,    &&oops,
      &&oops,    &&oops,    &&oops,    &&oops,    &&oops,    &&oops,
      &&oops,    &&oops,
#endif
      &&oops,    &&case_31, &&case_30, &&case_29, &&case_28, &&case_27,
      &&case_26, &&case_25, &&case_24, &&case_23, &&case_22, &&case_21,
      &&case_20, &&case_19, &&case_18, &&case_17, &&case_16, &&case_15,
      &&case_14, &&case_13, &&case_12, &&case_11, &&case_10, &&case_9,
      &&case_8,  &&case_7,  &&case_6,  &&case_5,  &&case_4,  &&case_3,
      &&case_2,  &&case_1};

  size_t lz = clz(size);
  if (size)
    goto *addr4jmp[lz];
  return it;

oops:
  abort();
case_31:
  BINARY_SEARCH_STEP;
case_30:
  BINARY_SEARCH_STEP;
case_29:
  BINARY_SEARCH_STEP;
case_28:
  BINARY_SEARCH_STEP;
case_27:
  BINARY_SEARCH_STEP;
case_26:
  BINARY_SEARCH_STEP;
case_25:
  BINARY_SEARCH_STEP;
case_24:
  BINARY_SEARCH_STEP;
case_23:
  BINARY_SEARCH_STEP;
case_22:
  BINARY_SEARCH_STEP;
case_21:
  BINARY_SEARCH_STEP;
case_20:
  BINARY_SEARCH_STEP;
case_19:
  BINARY_SEARCH_STEP;
case_18:
  BINARY_SEARCH_STEP;
case_17:
  BINARY_SEARCH_STEP;
case_16:
  BINARY_SEARCH_STEP;
case_15:
  BINARY_SEARCH_STEP;
case_14:
  BINARY_SEARCH_STEP;
case_13:
  BINARY_SEARCH_STEP;
case_12:
  BINARY_SEARCH_STEP;
case_11:
  BINARY_SEARCH_STEP;
case_10:
  BINARY_SEARCH_STEP;
case_9:
  BINARY_SEARCH_STEP;
case_8:
  BINARY_SEARCH_STEP;
case_7:
  BINARY_SEARCH_STEP;
case_6:
  BINARY_SEARCH_STEP;
case_5:
  BINARY_SEARCH_STEP;
case_4:
  BINARY_SEARCH_STEP;
case_3:
  BINARY_SEARCH_STEP;
case_2:
  BINARY_SEARCH_STEP;
  it += size > 1 && CMP(*it, key);
case_1:
  it += CMP(*it, key);
  return it;
}

#endif /* __GNUC__ */

/*----------------------------------------------------------------------------*/

/* Поиск из старых (уже не актуальных) версий libmdbx, который уже заменен
 * на одну из приведенных здесь реализаций. */
const TYPE *old_libmdbx(const TYPE *it, size_t size, const TYPE key) {
  while (size > 3) {
    const unsigned whole = size;
    size >>= 1;
    const TYPE *const middle = it + size;
    const unsigned left = whole - size - 1;
    const bool cmp = CMP(*middle, key);
    size = cmp ? left : size;
    it = cmp ? middle + 1 : it;
  }

  switch (size) {
  case 3:
    if (!CMP(*it, key))
      break;
    ++it;
    __fallthrough /* fall through */;
  case 2:
    if (!CMP(*it, key))
      break;
    ++it;
    __fallthrough /* fall through */;
  case 1:
    if (!CMP(*it, key))
      break;
    ++it;
    __fallthrough /* fall through */;
  case 0:
    break;
  default:
    __builtin_unreachable();
  }

  return it;
}

/*----------------------------------------------------------------------------*/
/* Тест */

#include <cstdio>
#include <vector>

#if !defined(__builtin_expect) && !__has_builtin(__builtin_expect) &&          \
    !defined(__GNUC__)
#define __builtin_expect(expr, value) (expr)
#endif /* __builtin_expect */

unsigned test_flank_size = 111, test_equal_plato = 42;

bool test(SEARCH search, const char *name, const bool bsearch_stdlib = false) {
  std::vector<TYPE> array;
  array.reserve(test_flank_size + test_equal_plato + test_flank_size);

  /* возрастающая последовательность в начале */
  while (array.size() < test_flank_size)
    array.push_back(
        /* чтобы иметь возможность получать от каждого элемента уникальные
           значения посредством +-1 */
        array.size() * 3 + 1);
  /* плато одинаковых элементов */
  while (array.size() < test_flank_size + test_equal_plato)
    array.push_back(array.back());
  /* возрастающая последовательность в конце */
  while (array.size() < test_flank_size + test_equal_plato + test_flank_size)
    array.push_back(
        /* чтобы иметь возможность получать от каждого элемента уникальные
           значения посредством +-1 */
        array.size() * 3 + 1);

  /* проверяем что порядок элементов соответствует компаратору */
  for (unsigned i = 1; i < array.size(); ++i)
    assert(!CMP(array[i], array[i - 1]));

  printf("Verify %-16s...", name);
  fflush(nullptr);
  for (unsigned begin = 1; begin < array.size(); ++begin) {
    for (unsigned size = 0; size < array.size() - begin; ++size) {
      const TYPE *const first = array.data() + begin;
      const TYPE *const after = first + size;
      for (TYPE key = *first - 1; key < *after + 1; ++key) {
        const TYPE *s = search(first, size, key);
        const intptr_t i = s - array.data();
        if (__builtin_expect(s < first, 0) || __builtin_expect(s > after, 0)) {
          if (!s && bsearch_stdlib)
            continue;
          printf("Wrong search-result %zi, for begin %u size %u, key %i\n", i,
                 begin, size, key);
          return false;
        }
        if (size && ((s > first && __builtin_expect(!CMP(s[-1], key), 0) &&
                      (s[-1] != key || !bsearch_stdlib)) ||
                     __builtin_expect(CMP(s[0], key), 0))) {
          printf("Wrong search-result %zi(%i), for begin %u size %u, key "
                 "%i\n",
                 i, *s, begin, size, key);
          return false;
        }
      }
    }
  }

  printf(" done\n");
  fflush(nullptr);
  return true;
}

/*----------------------------------------------------------------------------*/
/* bsearch из stdlib */

static inline int compare(const void *ptr_a, const void *ptr_b) {
  const auto &a = *(static_cast<const TYPE *>(ptr_a));
  const auto &b = *(static_cast<const TYPE *>(ptr_b));
  return (a < b) ? -1 : (a > b) ? +1 : 0;
}

const TYPE *bsearch_stdlib(const TYPE *it, size_t size, const TYPE key) {
  return static_cast<const TYPE *>(
      ::bsearch(&key, it, size, sizeof(TYPE), compare));
}

/*----------------------------------------------------------------------------*/
/* bsearch() from Linux Kernel */

static inline void *
__inline_bsearch_linux(const void *key, const void *base, size_t num,
                       size_t size, int (*cmp)(const void *, const void *)) {
  const char *pivot;
  int result;

  while (num > 0) {
    pivot = (const char *)base + (num >> 1) * size;
    result = cmp(key, pivot);

    if (result == 0)
      return (void *)pivot;

    if (result > 0) {
      base = pivot + size;
      num--;
    }
    num >>= 1;
  }

  return nullptr;
}

const TYPE *bsearch_linux(const TYPE *it, size_t size, const TYPE key) {
  return static_cast<const TYPE *>(
      __inline_bsearch_linux(&key, it, size, sizeof(TYPE), compare));
}

/*----------------------------------------------------------------------------*/
/* std::lower_bound<> */

#include <algorithm>

const TYPE *std_lowerbound(const TYPE *it, size_t size, const TYPE key) {
  return std::lower_bound(
      it, it + size, key,
      [](const TYPE &a, const TYPE &b) -> bool { return CMP(a, b); });
}

/*----------------------------------------------------------------------------*/
/* Бенчмарк */

bool debug_test, debug_bench, dump, skew2first, skew2last;
unsigned bench_size_min,
    bench_size_max = 99999, bench_size_nsteps = 111, bench_size_repeat = 9,
    bench_nprobes = 999999, bench_loops_limit = 999, bench_enough_stable = 5,
    bench_stable_threshold_ppm = 999, uniq_factor = 2, bench_seed = 42,
    skew_factor = 1;

const TYPE *bsearch_debug(const TYPE *it, size_t size, const TYPE key) {
  static size_t nn;
  auto r = std_lowerbound(it, size, key);
  printf("%zu) size %zu, key %li => position %zu\n", ++nn, size, long(key),
         r - it);
  return r;
}

#include <chrono>
#include <random>
const TYPE *nonestub(const TYPE *it, size_t size, const TYPE key) { return it; }

std::mt19937 std_prng;

uint64_t prng_seed, pass_seed;
unsigned prng() {
  prng_seed = prng_seed * UINT64_C(6364136223846793005) + 1;
  auto r = uint32_t(prng_seed >> 32);
  r = /* reducing the probability of correlation */
      ((r << 5) | (r >> 27)) ^ UINT32_C(1727376517);
  return r;
}

struct bench_step {
  unsigned size;
  bench_step(const bench_step &) = default;
  bench_step(unsigned size) : size(size) {}

  /* генерируем равномерно-распределенное псевдо-случайное значение для
   * наполнения массива, так чтобы потом удобно генерировать значения для
   * поиска, которые будут равномерно-распределены по заданной начальной части
   * массива. */
  static TYPE value4vector(unsigned size) {
    return 2 + make_value<false, false>(size);
  }

  enum : unsigned {
    max_uniq_factor = 9,
    max_size =
        (std::numeric_limits<unsigned>::max() - 3) >> (1 + max_uniq_factor)
  };

  typedef TYPE (bench_step::*value4probe)() const;
  static value4probe get_value4probe() {
    if (skew2first)
      return &bench_step::make_value4probe<true, false>;
    else if (skew2last)
      return &bench_step::make_value4probe<false, true>;
    else
      return &bench_step::make_value4probe<false, false>;
  }

protected:
  /* генерируем равномерно-распределенное псевдо-случайное значение для поиска,
   * которое более-менее НЕ выходит за регион поиска соответствующего size,
   * но включает ближайшие значения за его границами. */
  template <bool skew2low, bool skew2high> TYPE make_value4probe() const {
    return 1 + make_value<skew2low, skew2high>(size + 1);
  }
  template <bool skew2low, bool skew2high>
  static TYPE make_value(unsigned limit) {
    static_assert(!skew2low || !skew2high, "WTF?");
    unsigned r = prng() % (limit <<= uniq_factor);
    if (skew2low | skew2high) {
      const auto skew = (uint32_t(prng_seed) >> 28) + skew_factor;
      r = skew2low ? r >> skew : limit - (r >> skew);
    }
    return r << 1;
  }
};

std::vector<bench_step> bench_steps;
static void add_size_step(unsigned size) {
  if (size >= bench_size_min && size <= bench_size_max &&
      bench_steps.size() < bench_size_nsteps)
    bench_steps.push_back(size);
}

std::vector<TYPE> bench_vector;

struct result {
  double duration;
  double position_average;
  double position_min;
  double position_max;
};

#ifdef __GNUC__
__attribute__((__noinline__))
#endif
static result
pass(SEARCH search) {
  const auto data = bench_vector.data();
  const auto begin = bench_steps.cbegin();
  const auto end = bench_steps.cend();

  prng_seed = pass_seed;
  const auto start = std::chrono::steady_clock::now();
  auto step = begin;
  unsigned nprobes = 0, nstep_repeat = 0;
  double position_average = 0;
  double position_min = std::numeric_limits<double>::max();
  double position_max = 0;
  const auto value4probe = bench_step::get_value4probe();
  do {
    step = (step == end) ? begin : step;
    const double reciprocal = step->size ? 1.0 / step->size : 1.0;
    const auto ptr = search(data, step->size, ((*step).*value4probe)());
    if (ptr) {
      const double pp = (ptr - data) * reciprocal;
      position_min = std::min(position_min, pp);
      position_max = std::max(position_max, pp);
      position_average += pp;
    }
    nstep_repeat = (nstep_repeat < bench_size_repeat) ? nstep_repeat + 1 : 0;
    step += nstep_repeat == 0;
  } while (++nprobes < bench_nprobes);

  const auto fihish = std::chrono::steady_clock::now();
  return {std::chrono::duration_cast<std::chrono::nanoseconds>(fihish - start)
                  .count() *
              1e-9,
          position_average / nprobes, position_min, position_max};
}

struct score {
  double value;
  const char *name;
  score(const score &) = default;
  score(double value, const char *name) : value(value), name(name) {}
  friend bool operator<(const score &a, const score &b) {
    return a.value < b.value;
  }
};

std::vector<score> scores;
double reference_score, reference_average_position;

double bench(SEARCH search, const char *name, const double nullbaseline) {
  if (bench_vector.empty()) {
    printf("Preparing test array...");
    bench_vector.reserve(bench_size_max);
    /* наполняем случайными четными значениями от 2 до N - 1.
     * поэтому точно знаем что в данных нет 0, N и нечетных значений */
    while (bench_vector.size() < bench_size_max)
      bench_vector.push_back(bench_step::value4vector(bench_size_max));
    /* сортируем */
    printf(" sorting...");
    fflush(nullptr);
    std::sort(bench_vector.begin(), bench_vector.end(),
              [](const TYPE &a, const TYPE &b) -> bool { return CMP(a, b); });
    printf(" done\n");
    fflush(nullptr);

    /* проверяем соответствие порядока элементов компаратору и считаем дубли */
    unsigned duplicates = 0;
    for (unsigned i = 1; i < bench_vector.size(); ++i) {
      assert(!CMP(bench_vector[i], bench_vector[i - 1]));
      duplicates += bench_vector[i] == bench_vector[i - 1];
    }

    double avg = 0, log2_avg = 0;
    for (const auto &value : bench_vector) {
      avg += value;
      log2_avg += std::log2(value);
    }
    printf("Array of %zu values: min %li, max %li, average %.1f, ∑(lg2/N) "
           "%.2f, 2ⁿ %.1f, %u duplicates (%.1f%%)\n",
           bench_vector.size(), long(bench_vector.front()),
           long(bench_vector.back()), avg / bench_vector.size(),
           log2_avg / bench_vector.size(),
           std::pow(2, log2_avg / bench_vector.size()), duplicates,
           duplicates * 100.0 / bench_vector.size());

    if (dump) {
      printf("dump %zu values:", bench_vector.size());
      for (const auto &value : bench_vector)
        printf(" %li", long(value));
      printf("\n");
    }
    pass_seed = prng_seed;
  }

  if (bench_steps.empty()) {
    printf("Preparing size-steps...");
    fflush(nullptr);
    bench_steps.reserve(256);
    /* наполняем массив длин числами а-ля Фибоначчи
     * от bench_size_min до bench_size_max */
    for (unsigned a = 1, b = 2; a < bench_size_max;) {
      add_size_step(a);
      a += b;
      std::swap(a, b);
    }
    for (unsigned a = 1, b = 2; a < bench_size_max;) {
      add_size_step(a - 1);
      a += b;
      std::swap(a, b);
    }
    for (unsigned a = 1, b = 2; a < bench_size_max;) {
      add_size_step((a + b) / 2 + 1);
      a += b;
      std::swap(a, b);
    }
    const auto Fibonacci_nsteps = bench_steps.size();
    add_size_step(bench_size_max);

    /* дополняем случайными */
    while (bench_steps.size() < bench_size_nsteps)
      add_size_step(bench_size_min +
                    prng() % (bench_size_max - bench_size_min + 1));
    printf(" done\n");
    fflush(nullptr);

    double avg = 0, log2_avg = 0;
    for (const auto &step : bench_steps) {
      avg += step.size;
      log2_avg += step.size ? std::log2(step.size) + 1.0 : 1.0;
    }
    avg /= bench_steps.size();
    log2_avg = (log2_avg - bench_steps.size()) / bench_steps.size();

    if (Fibonacci_nsteps)
      printf("Use %zu Fibonacci-like sizes %u..%u of whole %zu steps: average "
             "%.1f, ∑(lg2/N) %.1f, 2ⁿ %.1f\n",
             Fibonacci_nsteps, bench_steps.front().size,
             bench_steps.at(Fibonacci_nsteps - 1).size, bench_steps.size(), avg,
             log2_avg, std::pow(2, log2_avg));
    else
      printf("Use %zu random steps of size: average "
             "%.1f, ∑(lg2/N) %.1f, 2ⁿ %.1f\n",
             bench_steps.size(), avg, log2_avg, std::pow(2, log2_avg));

    /* перемешиваем */
    std::shuffle(bench_steps.begin(), bench_steps.end(), std_prng);
    if (dump) {
      printf("dump %zu size-steps:", bench_steps.size());
      for (const auto &step : bench_steps)
        printf(" %u", step.size);
      printf("\n");
    }
    pass_seed = prng_seed;
  }

  printf("Benching %-16s...", name);
  fflush(nullptr);

  /* проверяем что порядок элементов соответствует компаратору */
  for (unsigned i = 1; i < bench_vector.size(); ++i)
    assert(!CMP(bench_vector[i], bench_vector[i - 1]));

  const auto first = pass(search);
  double best_duration = first.duration;
  double rms_diff_ppm = 0;
  unsigned loop = 0, stable = 0, rms_count = 0;
  do {
    const auto result = pass(search);
    assert(first.position_average == result.position_average);
    assert(first.position_min == result.position_min);
    assert(first.position_max == result.position_max);

    if (best_duration > result.duration) {
      best_duration = result.duration;
      stable = 0;
      rms_count = 0;
      rms_diff_ppm = 0;
    } else {
      const double diff_ppm = std::abs(best_duration - result.duration) * 1e6 /
                              (best_duration + result.duration);
      if (diff_ppm <= bench_stable_threshold_ppm) {
        if (!stable) {
          rms_count = 0;
          rms_diff_ppm = 0;
        }
        rms_diff_ppm += diff_ppm * diff_ppm;
        rms_count += 1;
        if (++stable == bench_enough_stable)
          break;
      } else if (!stable) {
        rms_diff_ppm += diff_ppm * diff_ppm;
        rms_count += 1;
      }
    }
  } while (++loop < bench_loops_limit || !rms_count);
  assert(rms_count == stable || !stable);

  const auto result = best_duration - nullbaseline;
  printf(" %.6f, %2u loops, rms diff %.1f ppm of %s %u passes", result, loop,
         std::sqrt(rms_diff_ppm) / rms_count, stable ? "stable" : "unstable",
         rms_count);
  bool ok = true;
  if (nullbaseline) {
    if (first.position_average) {
      printf("\n%45s ", "average position");
      if (!reference_average_position) {
        reference_score = result;
        reference_average_position = first.position_average;
        printf("%.2f%%", first.position_average * 100);
      } else
        printf("%s", (reference_average_position == first.position_average)
                         ? "match"
                         : (ok = false, "MISMATCH!"));

      printf(", range is %s",
             ((first.position_min == 0 || skew2last) &&
              (first.position_max == 1.0 || skew2first))
                 ? ((first.position_max - first.position_min == 1.0)
                        ? "fully covered"
                        : "half covered")
                 : (ok = false, "UNCOVERED!"));
    }
    if (ok)
      scores.emplace_back(result, name);
    printf(", %s\n", ok ? "Ok" : "SOMETHING WRONG!");
  }
  fflush(nullptr);
  return result;
}

/*----------------------------------------------------------------------------*/

#include <cstring>

bool get_unsigned(int &n, int argc, const char *argv[], unsigned &target,
                  const unsigned min = 1,
                  const unsigned max = std::numeric_limits<unsigned>::max()) {
  if (n + 1 == argc) {
    fprintf(stderr, "expect integer value after the %s\n", argv[n]);
    return false;
  }
  char *bad = nullptr;
  auto value = strtoul(argv[n + 1], &bad, 0);
  if ((bad && *bad) || value < min || value > max) {
    fprintf(stderr, "invalid integer value for %s\n", argv[n]);
    return false;
  }
  n += 1;
  target = unsigned(value);
  return true;
}

int main(int argc, const char *argv[]) {
  bool exit_failure = false;
  for (int n = 1; n < argc; n++) {
    if (strcmp(argv[n], "--dump") == 0) {
      if (n == 1) {
        bench_size_nsteps = 9;
        bench_size_max = 42;
      }
      dump = true;
    } else if (strcmp(argv[n], "--debug-bench") == 0) {
      debug_bench = true;
      if (n == 1 + dump) {
        bench_size_repeat = 1;
        bench_nprobes = 99;
      }
    } else if (strcmp(argv[n], "--debug-test") == 0) {
      debug_test = true;
    } else if (strcmp(argv[n], "--skew2first") == 0) {
      skew2first = true;
      skew2last = false;
    } else if (strcmp(argv[n], "--skew2last") == 0) {
      skew2first = false;
      skew2last = true;
    } else if (strcmp(argv[n], "--skew-factor") == 0) {
      if (!get_unsigned(n, argc, argv, skew_factor, 0, 9))
        exit_failure = true;
      else if (!(skew2first | skew2last))
        skew2first = true;
    } else if (strcmp(argv[n], "--min") == 0) {
      if (!get_unsigned(n, argc, argv, bench_size_min, 0, bench_step::max_size))
        exit_failure = true;
      else if (bench_size_max < bench_size_min)
        bench_size_max = bench_size_min;
    } else if (strcmp(argv[n], "--max") == 0) {
      if (!get_unsigned(n, argc, argv, bench_size_max, 1, bench_step::max_size))
        exit_failure = true;
      else if (bench_size_min > bench_size_max)
        bench_size_min = bench_size_max;
    } else if (strcmp(argv[n], "--steps") == 0) {
      if (!get_unsigned(n, argc, argv, bench_size_nsteps))
        exit_failure = true;
    } else if (strcmp(argv[n], "--repeat") == 0) {
      if (!get_unsigned(n, argc, argv, bench_size_repeat))
        exit_failure = true;
    } else if (strcmp(argv[n], "--probes") == 0) {
      if (!get_unsigned(n, argc, argv, bench_nprobes))
        exit_failure = true;
    } else if (strcmp(argv[n], "--seed") == 0) {
      if (!get_unsigned(n, argc, argv, bench_seed, 0))
        exit_failure = true;
    } else if (strcmp(argv[n], "--threshold-ppm") == 0) {
      if (!get_unsigned(n, argc, argv, bench_stable_threshold_ppm, 1,
                        1000000 / 12))
        exit_failure = true;
    } else if (strcmp(argv[n], "--enough-stable") == 0) {
      if (!get_unsigned(n, argc, argv, bench_enough_stable, 1, 99))
        exit_failure = true;
    } else if (strcmp(argv[n], "--loops-limit") == 0) {
      if (!get_unsigned(n, argc, argv, bench_loops_limit, 3,
                        std::numeric_limits<unsigned>::max()))
        exit_failure = true;
    } else if (strcmp(argv[n], "--uniq-factor") == 0) {
      if (!get_unsigned(n, argc, argv, uniq_factor, 0,
                        bench_step::max_uniq_factor))
        exit_failure = true;
    } else if (strcmp(argv[n], "--help") == 0 || strcmp(argv[n], "-h") == 0) {
      printf("  --%-24s%s,\n%32s%u by default.\n", "min SIZE",
             "The minimum size of the array where a search is performed", "",
             bench_size_min);
      printf("  --%-24s%s,\n%32s%u by default.\n", "max SIZE",
             "The maximal size of the array where a search is performed", "",
             bench_size_max);
      printf("  --%-24s%s,\n%32s%u by default.\n", "steps NUMBER",
             "The number of bench steps with a permanent size of where a "
             "search is performed",
             "", bench_size_nsteps);
      printf("  --%-24s%s,\n%32s%u by default.\n", "repeat NUMBER",
             "The number of sequentially passes with the each size of an array",
             "", bench_size_repeat);
      printf("  --%-24s%s,\n%32s%u by default.\n", "probes NUMBER",
             "The whole number of search probes for each implementation", "",
             bench_nprobes);
      printf("  --%-24s%s,\n%32s%u by default.\n", "seed NUMBER",
             "Initial seed for PRNG (linear congruential)", "", bench_seed);
      printf(
          "  --%-24s%s,\n%32s%u by default.\n", "loops-limit NUMBER",
          "The limit of evaluation attempts for benchmark each implementation",
          "", bench_loops_limit);
      printf("  --%-24s%s,\n%32s%u by default.\n", "enough-stable NUMBER",
             "The number of stable evaluations to be enough", "",
             bench_enough_stable);
      printf(
          "  --%-24s%s,\n%32s%u by default.\n", "threshold-ppm NUMBER",
          "The threshold value of the difference in ppm so that an evaluation "
          "is considered stable",
          "", bench_stable_threshold_ppm);
      printf("  --%-24s%s,\n%32s%u by default.\n", "uniq-factor NUMBER",
             "The uniqueness factor for filling test array (duplicates: 0→⅜, "
             "..., 9→1‰)",
             "", uniq_factor);
      printf("  --%-24s%s,\n%32s%s by default.\n", "skew2first",
             "Forces the statistical skew of a searched values to the begin",
             "", skew2first ? "Yes" : "No");
      printf("  --%-24s%s,\n%32s%s by default.\n", "skew2last",
             "Forces the statistical skew of a searched values to the end", "",
             skew2last ? "Yes" : "No");
      printf("  --%-24s%s,\n%32s%u by default.\n", "skew-factor NUMBER",
             "Skew intensity factor for --skew2first and --skew2last", "",
             skew_factor);
      printf("  --%-24s%s,\n%32s%s by default.\n", "dump",
             "Print test vectors of values and size-steps", "",
             dump ? "Yes" : "No");
      printf("  --%-24s%s,\n%32s%s by default.\n", "debug-bench", "FIXME", "",
             debug_bench ? "Yes" : "No");
      printf("  --%-24s%s,\n%32s%s by default.\n", "debug-test", "FIXME", "",
             debug_test ? "Yes" : "No");
      return EXIT_SUCCESS;
    } else {
      fprintf(stderr, "unknown option `%s`, try --help\n", argv[n]);
      return EXIT_FAILURE;
    }
  }

  if (!exit_failure) {
    printf("Verification parameters:\n");
    printf("  flank size %u (2ⁿ%.2f)\n", test_flank_size,
           std::log2(test_flank_size));
    printf("  equal plato %u (2ⁿ%.2f)\n", test_equal_plato,
           std::log2(test_equal_plato));
    printf("  whole vector %u (2ⁿ%.2f)\n",
           test_flank_size + test_equal_plato + test_flank_size,
           std::log2(test_flank_size + test_equal_plato + test_flank_size));
    printf("  debug %s\n", debug_test ? "Yes" : "No");

    if (debug_test)
      exit_failure |= !test(bsearch_debug, "debug");
    exit_failure |= !test(bsearch_stdlib, "bsearch_stdlib", true);
    exit_failure |= !test(bsearch_linux, "bsearch_linux", true);
    exit_failure |= !test(std_lowerbound, "std::lower_bound");
    exit_failure |= !test(old_libmdbx, "old_libmdbx");
    exit_failure |= !test(ly_bl_mini0, "ly_bl_mini0");
    exit_failure |= !test(ly_bl_mini1, "ly_bl_mini1");
    exit_failure |= !test(ly_bl_mini2, "ly_bl_mini2");
    exit_failure |= !test(ly_bl_mini3, "ly_bl_mini3");
    exit_failure |= !test(ly_bl_switch1, "ly_bl_switch1");
    exit_failure |= !test(ly_bl_switch2, "ly_bl_switch2");
#ifdef __GNUC__
    exit_failure |= !test(ly_bl_goto1, "ly_bl_goto1");
    exit_failure |= !test(ly_bl_goto2, "ly_bl_goto2");
    exit_failure |= !test(ly_bl_clz_switch, "ly_bl_clz_switch");
    exit_failure |= !test(ly_bl_clz_goto, "ly_bl_clz_goto");
#endif
    exit_failure |= !test(lb_PVKaPM, "PVKaPM");
    exit_failure |= !test(lb_MalteSkarupke, "Malte_Skarupke");
    exit_failure |= !test(linear_scan, "linear_scan");

    printf("\nBenchmark parameters:\n");
    printf("  min size %u (2ⁿ%.2f)\n", bench_size_min,
           std::log2(bench_size_min));
    printf("  max size %u (2ⁿ%.2f)\n", bench_size_max,
           std::log2(bench_size_max));
    printf("  size steps %u\n", bench_size_nsteps);
    printf("  step repetitions %u\n", bench_size_repeat);
    printf("  number of probes %u\n", bench_nprobes);
    printf("  prng seed %u\n", bench_seed);
    printf("  stable threshold %u ppm (%.4f%%)\n", bench_stable_threshold_ppm,
           1e-6 * bench_stable_threshold_ppm * 100.0);
    printf("  enough stable %u\n", bench_enough_stable);
    printf("  loops limit %u\n", bench_loops_limit);
    const double gold_ratio = (std::sqrt(5) - 1) / 2;
    printf("  uniqueness factor %u (≈%.1f%% duplicates)\n", uniq_factor,
           100.0 / (uniq_factor ? ((2 << uniq_factor) + gold_ratio) : M_E));
    printf("  skew %s", skew2first ? "to First" : skew2last ? "to Last" : "No");
    if (skew2first | skew2last)
      printf(" (factor %u)", skew_factor);
    printf("\n  debug %s\n", debug_bench ? "Yes" : "No");
    prng_seed = bench_seed;

    if (debug_bench)
      bench(bsearch_debug, "debug", 0);

    const double nullbaseline = bench(nonestub, "the overhead", 0);
    printf("\n\n");
    fflush(nullptr);

    bench(std_lowerbound, "std::lower_bound", nullbaseline);
    bench(old_libmdbx, "old_libmdbx", nullbaseline);
    bench(ly_bl_mini0, "ly_bl_mini0", nullbaseline);
    bench(ly_bl_mini1, "ly_bl_mini1", nullbaseline);
    bench(ly_bl_mini2, "ly_bl_mini2", nullbaseline);
    bench(ly_bl_mini3, "ly_bl_mini3", nullbaseline);
    bench(ly_bl_switch1, "ly_bl_switch1", nullbaseline);
    bench(ly_bl_switch2, "ly_bl_switch2", nullbaseline);
#ifdef __GNUC__
    bench(ly_bl_goto1, "ly_bl_goto1", nullbaseline);
    bench(ly_bl_goto2, "ly_bl_goto2", nullbaseline);
    bench(ly_bl_clz_switch, "ly_bl_clz_switch", nullbaseline);
    bench(ly_bl_clz_goto, "ly_bl_clz_goto", nullbaseline);
#endif
    bench(bsearch_stdlib, "bsearch_stdlib", nullbaseline);
    bench(bsearch_linux, "bsearch_linux", nullbaseline);
    bench(lb_PVKaPM, "PVKaPM", nullbaseline);
    bench(lb_MalteSkarupke, "Malte_Skarupke", nullbaseline);
    if (bench_size_max < 1025)
      bench(linear_scan, "linear_scan", nullbaseline);

    std::sort(scores.begin(), scores.end());
    printf("\n");
    printf("| Function         |   Time    |  Diff    | Ratio |\n");
    printf("|:-----------------|----------:|---------:|------:|\n");
    for (const auto &record : scores) {
      printf("| %-16s | %9.6f | %+7.2f%% | %5.2f |\n", record.name,
             record.value,
             (record.value - reference_score) * 100.0 / reference_score,
             reference_score / record.value);
    }
#ifdef CLANG_X86CMOV_NOTICE
    printf("\nStatus of CLANG/LLVM workaround for x86 CMOV: %s\n",
           CLANG_X86CMOV_NOTICE);
#endif
  }
  return exit_failure ? EXIT_FAILURE : EXIT_SUCCESS;
}