README.md

Экстремально-быстрая “одно-переходная” реализация двоичного поиска для случаев дешевых сравнений:

  • В сравнении с std::lower_bound<>:
    • до 4-х раз быстрее на последних x86_64 при использовании GCC/CLANG/MSVC;
    • более 2-х раз быстрее на Apple M1;
    • как правило, ускорение составляет около 30%.
  • Может служить примером обхода ошибки оптимизатора CLANG≥5 на x86, приводящей к использованию условных переходов вместо CMOV-инструкций.
  • Прекрасно подходит для E2K/Эльбрусов. Разработано для libmdbx и Positive Technologies.

Extremmely fast “single-branch” implementation of binary search for cheap-comparison cases:

  • In comparison with std::lower_bound<>:
    • up to 4 times faster on modern x86_64 with GCC/CLANG/MSVC;
    • more than 2 times faster on Apple M1;
    • usually the speedup is about 30%.
  • Сan serve as an example of workaround for the CLANG≥5 optimizer “eternal” bug on x86, leading to emit the conditional jumps instead of a CMOV-instructions.
  • Perfect for VLIW E2K/Elbrus. Designed for libmdbx & Positive Technologies.

How to…

$ git clone https://gitflic.ru/project/erthink/bsearch-try.git
$ cd bsearch-try
$ make bench

Для более точных замеров (может потребовать много времени) / For more accurate measurements (may take a long time):

$ make all
$ ./bsearch-bench-native --enough-stable 9 --threshold-ppm 99

Для прочих экспериментов / For deep digging:

$ ./bsearch-bench --help
  --min SIZE                The minimum size of the array where a search is performed,
                                0 by default.
  --max SIZE                The maximal size of the array where a search is performed,
                                99999 by default.
  --steps NUMBER            The number of bench steps with a permanent size of where a search is performed,
                                111 by default.
  --repeat NUMBER           The number of sequentially passes with the each size of an array,
                                9 by default.
  --probes NUMBER           The whole number of search probes for each implementation,
                                999999 by default.
  --seed NUMBER             Initial seed for PRNG (linear congruential),
                                42 by default.
  --loops-limit NUMBER      The limit of evaluation attempts for benchmark each implementation,
                                999 by default.
  --enough-stable NUMBER    The number of stable evaluations to be enough,
                                5 by default.
  --threshold-ppm NUMBER    The threshold value of the difference in ppm so that an evaluation is considered stable,
                                999 by default.
  --uniq-factor NUMBER      The uniqueness factor for filling test array (duplicates: 0→⅜, ..., 9→1‰),
                                2 by default.
  --skew2first              Forces the statistical skew of a searched values to the begin,
                                No by default.
  --skew2last               Forces the statistical skew of a searched values to the end,
                                No by default.
  --skew-factor NUMBER      Skew intensity factor for --skew2first and --skew2last,
                                1 by default.
  --dump                    Print test vectors of values and size-steps,
                                No by default.
  --debug-bench             FIXME,
                                No by default.
  --debug-test              FIXME,
                                No by default.

Технически оптимизация концентрируется на минимизации количества условных переходов, что в целом может снижать задержки в итерациях сужения поискового интервала. Стоит отметить несколько моментов, которые могут ускользнуть от внимания:

  • При поиске в больших массивах (больше размера кэша ЦПУ) основную задержку будет вносить чтение данных, поэтому экономия на условных переходах становится менее заметной.
  • При статистическом сдвиге (поиск всегда блике к началу, либо к концу) использование условных переходов может оказаться выгоднее, даже при отсутствии предсказателя переходов.
  • На платформах/процессорах со спекулятивным выполнением использование условных переходов будет/должно провоцировать спекулятивное чтение из памяти. Что может как положительно сказываться на производительности, так и приводить к деградации из-за загрузки каналов к памяти чтением ненужных данных, к засорению кэша.

С точки зрения алгоритма/математики тут ничего нового. Напротив всё тривиально — только убрать лишнее, как говаривал Буонаротти. Соответственно, всё “чудо” оптимизации сводится в основном к шагу двоичного поиска: сравнению и делению отрезка пополам, с сохранением возможности использования инструкций условных пересылок, aka CMOV, вместо условных переходов.

В частности, поэтому в коде нет “арифметического CMOV” (распространение знака, and + xor с маской и т.п.), так как: с одной стороны, это мешает компилятору использовать CMOV там где они доступны, а с другой стороны, компилятор (или программист) сам может решить когда это выгоднее.

В практической же плоскости ещё нужно убедить компилятор ничего не испортить. После небольшой магии с LCC, MSVC и GCC всё оказалось прекрасно со всеми версиями, а CLANG≥5 упрямо портит код — пришлось добавить костыль:

По всей видимости в оптимизаторе CLANG для x86 явно какая-то глупая ошибка, наподобие пропущенного ! в условии. Упрощенно:

  • Если внутри цикла две зависимости от результата сравнения. то CLANG использует две CMOV-инструкции.
  • Если же зависимость одна, то вместо одной CMOV используются переходы.

Эта логика явно ошибочная, ибо:

  • Если одна CMOV дороже переходов, то две точно ещё дороже,
  • А если же CMOV не дороже переходов, то вообще тут незачем использовать переходы (ибо загрязнение стека предсказателя).

Проблема существует с 2017 года, её много раз начинали обсуждать, возможно когда-то исправят. В качестве обходного пути, как правило, используются ассемблерные вставки с нужными CMOV-инструкциями. Сложность в том, что при таком подходе требуется спускать сравнение также внутрь ассемблерных вставок, а это уже сказывается на производительности, так как между CMP и CMOV уже ничего не ставить.

Поэтому вместо ассемблерных вставок с CMOV-инструкциями я решил подсунуть CLANG вторую зависимость, которая подталкивает оптимизатор к отказу от ненужных условных переходов. Это выглядит более рациональным решением, ибо накладные расходы сводятся к одной инструкции наподобие setl cl без исходящих зависимостей по данным. При этом такая ассемблерная вставка не требует обслуживания и не мешает компилятору, а бенчмарк подтверждает ликвидацию отставания от GCC.

На всякий — большинство тестируемых реализаций не предполагает поиск при нулевом размере. Точнее говоря, при нулевом размере происходит чтение одного элемента, т.е. за концом вектора нулевого размера. В моих целевых сценариях это не принципиально. Все остальные подробности в исходном коде.


Benchmark results

Good news

LCC 1.126.12, -Ofast, VLIW E2K/Эльбрус-8СВ:
Function Time Diff Ratio
ly_bsearch_mini1() 0.064143 -29.02% 1.41
ly_bsearch_goto1() 0.066118 -26.83% 1.37
ly_bsearch_mini2() 0.066420 -26.50% 1.36
ly_bsearch_goto2() 0.066601 -26.30% 1.36
ly_bsearch_mini3() 0.068115 -24.62% 1.33
ly_bsearch_switch2() 0.075379 -16.58% 1.20
bsearch_libmdbx() 0.082808 -8.36% 1.09
ly_bsearch_switch1() 0.086666 -4.09% 1.04
std::lower_bound<> 0.090362 +0.00% 1.00
bsearch_linux() 0.112418 +24.41% 0.80
bsearch_stdlib() 0.127668 +41.29% 0.71
GCC 12.1, -Ofast, Intel(R) Xeon(R) Gold 5317:
Function Time Diff Ratio
ly_bsearch_mini1() 0.017126 -75.30% 4.05
ly_bsearch_goto1() 0.017127 -75.29% 4.05
ly_bsearch_mini2() 0.017187 -75.21% 4.03
ly_bsearch_mini3() 0.017458 -74.82% 3.97
ly_bsearch_goto2() 0.017469 -74.80% 3.97
ly_bsearch_switch2() 0.024436 -64.75% 2.84
ly_bsearch_switch1() 0.028880 -58.34% 2.40
std::lower_bound<> 0.069323 +0.00% 1.00
bsearch_linux() 0.070008 +0.99% 0.99
bsearch_libmdbx() 0.070788 +2.11% 0.98
bsearch_stdlib() 0.071515 +3.16% 0.97
GCC 11.3, -Ofast, 11th Gen Intel(R) Core(TM) i7-11700T:
Function Time Diff Ratio
ly_bsearch_goto2() 0.011185 -76.93% 4.33
ly_bsearch_mini1() 0.011245 -76.80% 4.31
ly_bsearch_goto1() 0.011282 -76.73% 4.30
ly_bsearch_mini3() 0.011473 -76.33% 4.23
ly_bsearch_mini2() 0.011670 -75.93% 4.15
ly_bsearch_switch2() 0.016084 -66.82% 3.01
ly_bsearch_switch1() 0.019346 -60.09% 2.51
bsearch_libmdbx() 0.047679 -1.64% 1.02
bsearch_stdlib() 0.047912 -1.16% 1.01
bsearch_linux() 0.048079 -0.81% 1.01
std::lower_bound<> 0.048474 +0.00% 1.00
Apple clang version 13.1.6, -Ofast, Apple M1 MAX:
Function Time Diff Ratio
ly_bsearch_goto1() 0.011080 -58.47% 2.41
ly_bsearch_goto2() 0.011185 -58.07% 2.39
ly_bsearch_switch1() 0.011389 -57.31% 2.34
ly_bsearch_switch2() 0.011449 -57.08% 2.33
ly_bsearch_mini2() 0.011563 -56.66% 2.31
ly_bsearch_mini3() 0.011642 -56.36% 2.29
ly_bsearch_mini1() 0.011893 -55.42% 2.24
std::lower_bound<> 0.026678 +0.00% 1.00
bsearch_linux() 0.031111 +16.62% 0.86
bsearch_libmdbx() 0.034313 +28.62% 0.78
bsearch_stdlib() 0.050448 +89.10% 0.53

Bad news

clang 14, -Ofast, the same 11th Gen Intel(R) Core(TM) i7-11700T:
Function Time Diff Ratio
std::lower_bound<> 0.022907 +0.00% 1.00
bsearch_libmdbx() 0.027637 +20.65% 0.83
bsearch_linux() 0.030347 +32.48% 0.75
ly_bsearch_goto2() 0.038270 +67.07% 0.60
ly_bsearch_goto1() 0.038385 +67.57% 0.60
ly_bsearch_switch1() 0.039737 +73.47% 0.58
ly_bsearch_switch2() 0.042357 +84.91% 0.54
ly_bsearch_mini1() 0.044515 +94.33% 0.51
ly_bsearch_mini2() 0.045908 +100.41% 0.50
ly_bsearch_mini3() 0.046015 +100.88% 0.50
bsearch_stdlib() 0.047896 +109.09% 0.48

Even with -march=native -mtune=native:

Function Time Diff Ratio
bsearch_libmdbx() 0.027692 -38.86% 1.64
bsearch_linux() 0.027929 -38.34% 1.62
ly_bsearch_goto2() 0.039052 -13.78% 1.16
ly_bsearch_goto1() 0.039494 -12.81% 1.15
ly_bsearch_switch1() 0.040846 -9.82% 1.11
ly_bsearch_switch2() 0.042474 -6.23% 1.07
ly_bsearch_mini1() 0.044786 -1.12% 1.01
std::lower_bound<> 0.045294 +0.00% 1.00
bsearch_stdlib() 0.045622 +0.72% 0.99
ly_bsearch_mini2() 0.045813 +1.15% 0.99
ly_bsearch_mini3() 0.045961 +1.47% 0.99

So clang has bad optimizer of a cmov-targeting code for modern Intel CPUs. However, for now this clang’s bug (misuse conditional jump instead of CMOVs) is workarounded.

Function Time Diff Ratio
ly_bl_mini1 0.013067 -74.64% 3.94
ly_bl_goto1 0.013099 -74.58% 3.93
ly_bl_mini2 0.013168 -74.45% 3.91
ly_bl_goto2 0.013220 -74.35% 3.90
ly_bl_mini0 0.013285 -74.22% 3.88
ly_bl_clz_goto 0.013654 -73.50% 3.77
ly_bl_mini3 0.013983 -72.87% 3.69
ly_bl_switch2 0.018225 -64.64% 2.83
ly_bl_switch1 0.021003 -59.24% 2.45
ly_bl_clz_switch 0.022119 -57.08% 2.33
bsearch_linux 0.049469 -4.01% 1.04
bsearch_libmdbx 0.050171 -2.64% 1.03
bsearch_stdlib 0.050686 -1.64% 1.02
std::lower_bound 0.051533 +0.00% 1.00
Описание

Экстремально-быстрая “одно-переходная” реализация двоичного поиска для случаев дешевых сравнений