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

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

На всякий случай отмечу, что я не претендую на какое-либо первенство в изобретении алгоритма. Более того, в моём понимании здесь нет ничего алгоритмически/математически нового, речь только о реализации общеизвестного алгоритма двоичного поиска с использованием всех актуальных возможностей и особенностей аппаратуры.

Изначально эта реализация (алгоритм, если угодно) была создана в конце 90-х, сугубо из интереса по мотивам каких-то олимпиадных и тренировочных задач по информатике. Но практический смысл потеряла очень быстро, так как Intel вскоре зарубил производительность CMOV.

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

Бенчмарк и весь вспомогательный код написаны на C++, но большинство оцениваемых функций поиска написаны в синтаксисе C, как мне требовалось для libmdbx. По той же причине большинство тестируемых реализаций не предполагает поиск при нулевом размере. Точнее говоря, при нулевом размере происходит чтение одного элемента, т.е. за концом вектора нулевого размера. В моих целевых сценариях это не принципиально.

In English

Extremmely fast “single-branch” (aka branchless) 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.

I want to note that I do not claim any primacy in the invention of the algorithm. Moreover, in my understanding there is nothing algorithmically/mathematically new here, contrary we should only talking about the implementation of a well-known binary search algorithm using whole actual capabilities and features of an equipment.

Initially, this implementation (algorithm, if you like) was created independently in the late 90s, purely of interest on some Olympiad and training tasks in computer science. But it lost its practical meaning very quickly, as Intel soon breaks CMOV performance.

For each evaluated function, the benchmark measures the total time spent searching for different stochastic values in vectors of different stochastic size, and then normalizes and outputs sorted results. Therefore, the results correspond to the cumulative average performance of each function. If necessary, using options on the command line, you can vary most of the parameters, including the distribution of the size of vectors, control the skew in the distribution of values, the number of duplicates, etc. All other details are in the source code.

The benchmark and all the auxiliary code are written in C++, but most of the evaluated search functions are written in C syntax, as I needed for libmdbx. For the same reason, most of the tested implementations do not assume a zero-size search. More precisely, when the size is zero, one element is read, i.e. beyond the end of the vector of zero size. In my target scenarios, this does not matter.

Как использовать бенчмарк / How to use benchmark

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

Для более точных замеров (может потребовать много времени) / 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

x86_64, i7-1280P, gcc 12.2 (0-3ubuntu1~22.04), -Ofast

x86_64, i7-1280P, clang 14, -Ofast

x86_64, Xeon Gold 5317, gcc 12.2 (0-3ubuntu1~22.04), -march=native -Ofast

x86_64, Xeon Gold 5317, clang 17 (++20230504031411+edcdc81e2bb3-1~exp1~20230504151525.909), -march=native -Ofast

VLIW E2Kv5, Эльбрус-8СВ, LCC 1.26.17, -Ofast