информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Spanning Tree Protocol: недокументированное применениеАтака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Ростелеком заподозрили в попытке... 
 Линуксовый ботнет, распространяющийся... 
 Конец поддержки Internet Explorer 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Знатоки могут припомнить статью "array layouts for... 27.07 23:43  Число просмотров: 65
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка> <ответить>
Знатоки могут припомнить статью "ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING" от марта 2017, где примерно аналогичный поиск, но:
1. Алгоритма ни тут ни та нового нет, а подобный branchless поиск я написал лет за 20 до этой статьи ;)
2. У них там небольшой баг.
3. В реальности код из статьи портиться компилятором (этот вариант тоже есть в бенчмарке).
<ответить> <programming>
[C++] Ускорение bsearch (очередная успешная попытка) 27.07 23:33  
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 27.07 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 23:43  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка> <ответить>
Знатоки могут припомнить статью "ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING" от марта 2017, где примерно аналогичный поиск, но:
1. Алгоритма ни тут ни та нового нет, а подобный branchless поиск я написал лет за 20 до этой статьи ;)
2. У них там небольшой баг.
3. В реальности код из статьи портиться компилятором (этот вариант тоже есть в бенчмарке).
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2022 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach