Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
[C++] Ускорение bsearch (очередная успешная попытка) 27.07.22 23:33
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 27.07.22 23:36 Количество правок: 4
|
Речь о поиске при дешевом сравнении. Например, в массиве чиселок, но не строк. Мне такой поиск нужен в предельно быстром виде в libmdbx, для поиска в непустых списках страниц (dirty, spilled, free, etc).
Исходно прицел был в ускорение для E2K за счет ликвидации переходов, ибо VLIW и т.д.
Однако, самый неожиданный результат на более-менее свежих "штеудах" = ускорение поиска в 4 раза и почти в 2.5 раза на Apple M1 Max (aarch64).
С точки зрения алгоритма/математики (конечно) ничего нового, просто убрать лишнее. В практической плоскости сложнее убедить компилятор ничего не испортить. Например, clang жутко портит подобный код с 2017 года (с версии 5). Эту багу оптимизатора обсуждали уже несколько раз, но пока без изменений. Поэтому я из спортивного интереса озадачился обходным путем. В результате получилось хорошо.
LCC 1.26.12, 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 11.3, 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 |
---
clang 14, i7-11700T:
| 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 |
---
Исходники бенчмарка с различными вариантами и т.п. по ссылке.
https://gitflic.ru/project/erthink/bsearch-try
|
|
Знатоки могут припомнить статью "array layouts for... 27.07.22 23:43
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 21.10.22 00:21 Количество правок: 1
|
Знатоки могут припомнить статью "ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING" от марта 2017, где примерно аналогичный поиск, но:
1. Алгоритма тут никакого нового нет, а подобный branchless поиск я написал лет за 20 до этой статьи ;)
2. У них там небольшой баг.
3. В реальности код из статьи портиться компилятором (этот вариант тоже есть в бенчмарке).
|
|
|
подробно о проекте
Анализ криптографических сетевых...
