BugTraq.Ru: форум / programming / Знатоки могут припомнить статью "ARRAY LAYOUTS FOR...

информационная безопасность
без паники и всерьез

подробно о проекте

Анализ криптографических сетевых...

Модель надежности двухузлового...

Специальные марковские модели надежности...

Очередное исследование 19 миллиардов...

Оптимизация ввода-вывода как инструмент...

Зловреды выбирают Lisp и Delphi

bugtraq.ru / форум / programming

Имя

Пароль

если вы видите этот текст, отключите в настройках форума использование JavaScript


ФОРУМ


	все доски
	FAQ
	IRC
	новые сообщения

	site updates
	guestbook
	beginners
	sysadmin
	programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap

регистрация

Легенда:

новое сообщение

закрытая нитка

новое сообщение

в закрытой нитке

старое сообщение

Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
Новичкам также крайне полезно ознакомиться с данным документом.

Знатоки могут припомнить статью "array layouts for... 27.07.22 23:43 Число просмотров: 2831
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 21.10.22 00:21 Количество правок: 1

<"чистая" ссылка>

Знатоки могут припомнить статью "ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING" от марта 2017, где примерно аналогичный поиск, но:
1. Алгоритма тут никакого нового нет, а подобный branchless поиск я написал лет за 20 до этой статьи ;)
2. У них там небольшой баг.
3. В реальности код из статьи портиться компилятором (этот вариант тоже есть в бенчмарке).

[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

<"чистая" ссылка>

Page build time: 0 s

Design: Vadim Derkach