|
|
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, гугли bit twiddling hacks ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.11.2020, 16:08 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, 👍 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.11.2020, 16:24 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU Polesov Добавляем первой строкой весьма безобидную ни на что не влияющую операцию Код: pascal 1. и получаем замедление где-то в 1.5 раза Уш-да-уш... Оптимизация asm - дело тонкое ... Выложи текущий вариант модуля Чтобы мы тоже погоняли и сравнили Да чо там выкладывать ) Берем код от Aleksandr Sharahov, сгенеренный D7 (только тип входных параметров меняем на word) Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. Замеряем скорость. Добавляем первой строчкой Код: pascal 1. и сравниваем с тем, что было до ... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.11.2020, 16:28 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
Ну, и до кучи - наверное, самый компактный вариант: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. И, кстати, не самый медленный ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.11.2020, 20:16 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Хотел через умножения? Распишитесь в получении. Не спрашивай, как ) Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 00:41 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU Я тут экспериментирую с SIMD По сути появится возможность анализировать 16 символов за раз Там классная возможность в том, что проведя ряд манипуляций, ты получаешь маску из 16 бит, где ты видишь, символ удовлетворяет твоему условию или нет <..> Получается ты считал 16 символов из памяти. Проанализировал их, получил маску (2 маски по 16 бит) А потом постепенно вычитываешь эти символы из SIMD-регистра и обрабатываешь согласно имеющейся маске Если нет - нужно думать, как делать обработку (возможно, не всю, а некоторые из этапов) тру-симдовским методом - считать обе ветки условия и микшировать их по маске, без посимвольного разбора и условных jmp-ов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 00:54 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Так этот вариант ещё медленнее, чем через сдвиги ) Но спрашивать не буду Видимо всё равно не пойму ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 01:37 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
Sapersky, Зависит от алгоритма Наибольшей производительности получается достичь если все символы ASCII Условно говоря при конвертации Ansi в Utf8 - тупо кидаешь все символы и всё Но возникает вопрос, как быть если встречен не целевой символ Можно прочитать и обработать его стандартным способом А можно прикинуть, что в SIMD регистр уже прочитаны данные, а в маске лежит инфа, где что лежит Получается я SIMD регистр могу использовать не просто, чтобы анализировать, где какие символы идут Но и как оперативное хранилище прочитанных данных! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 01:48 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU Aleksandr Sharahov, Так этот вариант ещё медленнее, чем через сдвиги ) Но спрашивать не буду Видимо всё равно не пойму ) Да, он примерно на 25% медленнее, но зато прикольный: использованные в нем константы - единственные, которые позволяют независимо возводить биты числа в квадрат. Других троек констант с такими свойствами нет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 01:49 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU Aleksandr Sharahov, Так этот вариант ещё медленнее, чем через сдвиги ) Кстати, асм-версия на умножениях обгоняет асм-версию на сдвигах примерно на 10%: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 02:15 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU Sapersky, Условно говоря при конвертации Ansi в Utf8 - тупо кидаешь все символы и всё Но возникает вопрос, как быть если встречен не целевой символ SOFT FOR YOU А можно прикинуть, что в SIMD регистр уже прочитаны данные, а в маске лежит инфа, где что лежит Получается я SIMD регистр могу использовать не просто, чтобы анализировать, где какие символы идут Но и как оперативное хранилище прочитанных данных! Если использовать bsr, то нужно очищать каждый найденный бит. Если просто всё перебирать, то это shr/and/условие для каждого бита. Я кстати возился со строками и SIMD год назад: https://www.sql.ru/forum/1319647-a/poisk-v-fayle-s-ispolzovaniem-mmf хотя там разбор маски точно неоптимален, перебор всех бит на Паскале. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 06:46 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Описание логики работы алгоритма на умножениях 22239874 и 22239895 . Как и в алгоритме на сдвигах мы вычисляем для переданных параметров (u,v) 2 промежуточных результата t(u) и t(v), а затем на их основе получаем окончательный результат r(u,v)=2*t(u)+t(v). Отличие от алгоритма на сдвигах состоит в том, какими операторами t мы раздвигаем биты каждого параметра. Очевидно, что t(0)=0. Понятно, что если параметр содержит ровно 1 ненулевой бит в i-той позиции, то t(2^i)=2^(2*i)=(2^i)*(2^i), или t(x)=x*x. Т.е. и в этом случае достаточно возвести параметр в квадрат. При возведении в квадрат параметра, содержащего 2 ненулевых бита, в соответствии биномом Ньютона, мы получим (x+y)*(x+y)=x*x+y*y+2*x*y. А правильный результат t(x+y)=x*x+y*y. Т.е. в этом случае мы получили погрешность в виде удвоенного произведения ненулевых битов. Если параметр будет содержать большее количество ненулевых битов, то при возведении в квадрат мы будем получать погрешность для каждой пары битов. Избавиться от погрешности наложением битовой маски на результат возведения в квадрат невозможно, т.к. позиции битов погрешности могут совпадать с позициями битов результата. Однако, если произвольно выбрать некоторое множество разрешенных позиций битов параметра, то для него мы можем указать множество разрешенных позиций битов результата. Далее мы будем рассматривать только "хорошие" множества разрешенных позиций битов параметра, для которых биты погрешности не попадают в множество разрешенных позиций битов результата. Несмотря на то что хороших множеств довольно много, их мощность невелика. Самое большое хорошее множество состоит из 6 битовых позиций, остальные еще меньше. В алгоритме используется минимальное покрытие множества 16 битовых позиций параметра тремя хорошими множествами мощности 5+5+6, которые заданы масками $2492, $4924, $9249. Другие три маски $04104104, $10410410, $41041041 задают три соответствующих им множества разрешенных позиции битов результата. Алгоритм разделяет биты параметра на три части, каждую часть возводит в квадрат, отсекает в них биты погрешности и соединяет части. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 11:42 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, У меня мозги не так хорошо работают, чтобы это понять Но я буду стараться :) А почему ты программируешь на D7? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 12:14 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
Sapersky, Я сейчас низкоуровневый код пишу на Си, а к Delphi/FPC/C++Builder линкую объектники Благодаря инлайн функциям и макросам мне удаётся писать высокопроизводительный код под все 10 платформ (5 ОС по 2 битности). Для x86/x64 юзаются команды SSE2, на ARM - NEON. Пока юзаются регистры по 16 байт. Наверное на следующем уровне перейду на 32 или даже 64. Но пока так - всяко лучше, чем регистры общего назначения ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 12:22 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, мне хватает ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 12:25 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
Sapersky, Раз уже пошла такая пьянка, проиллюстрирую немного :) Есть у меня функции AStrLen/WStrLen/CStrLen. Данная функция написана на Си, но скомпилирована в объектный файл под разные платформы и цепляется как обычная паскалевская функция: Код: pascal 1. 2. 3. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. Из кода хорошо видно, что функция эффективно работает только на 64 битах, когда анализируется сразу 4 символа за итерацию. И то, если указатель выравнен на границу WideChar. Кстати я давно использую этот подход, когда через маски и битовые итерации анализируется сразу несколько символов. Минуса 2: во-первых, очень сильно расходуются регистры общего назначения, во-вторых, по сути ты можешь определить только первое вхождение, состояние остальных символов становится неизвестно. С SIMD по сути ты видишь картину целиком, плюс регистры общего назначения практически не расходуются. А на Си есть возможность зафигачить макросы и инлайн функции, что в итоге выльется в удобоваримые конструкции на несколько платформ и реализация сразу нескольких функций. Вот реализация AStrLen/WStrLen/CStrLen: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. И вот смотри, в какую красоту превращается WStrLen. По сути там 2 кейса: выравненный и невыравненный. В выравненном анализируется 8 символов за итерацию. В невыровненном 7 + 1 :) Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 13:44 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU А почему ты программируешь на D7? ну наконец-то ! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 14:18 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU Sapersky, Я сейчас низкоуровневый код пишу на Си, а к Delphi/FPC/C++Builder линкую объектники Благодаря инлайн функциям и макросам мне удаётся писать высокопроизводительный код под все 10 платформ (5 ОС по 2 битности) Конкретно StrLen - странный пример. Можно подумать, сейчас часто используются нуль-терминированные строки. Или ты там всю RTL переписываешь из любви к искусству? И кстати, какую выгоду даёт выравнивание на x86? У меня сложилось впечатление, что на современных процессорах небольшую, ну может 10%. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 17:09 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
Sapersky Хотя микс из разных языков затрудняет отладку, особенно линковка в виде obj - как их отлаживать из Дельфи? Так же, как функции WinAPI )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 17:31 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
Sapersky, Ну отлаживать конечно сложнее Тут спорить не буду Ну а что делать? Embarcadero оптимизировать свои компиляторы не хочет Под Linux вообще труба, ещё хуже, чем под Виндой Ну и потом, описывая часть кода на Си, есть перспектива реюзания в Си-проектах А насчёт примера StrLen... это просто пример Я планирую масштабное переписывание функций обработки текстов на зиму. Пока есть несколько функций на SIMD, просто решил показать. Есть ещё CompareMem, сравнение строк. Кто хочет - может запилить бенчмарки, мне пока влом ) Насчёт выравнивания... большая тема Но в StrLen оно имеет смысл не с точки зрения оптимизации, а с той точки зрения, что не учитывая выравнивание, ты всегда можешь попасть на недоступную страницу. Выравнивая адрес, ты всегда можешь гарантировать валидное чтение. Или условно валидное ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 17:32 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
А вообще заходите в наше DelphiCommunity в телеграме! Будем обсуждать там то, что не укладывается в формат форума ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 17:34 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
Sapersky И кстати, какую выгоду даёт выравнивание на x86? У меня сложилось впечатление, что на современных процессорах небольшую, ну может 10%. Без него SSE вообще не работает AFAIK. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 19:23 |
|
||
|
Микширование бит
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU Я планирую масштабное переписывание функций обработки текстов на зиму и всё, конечно же, будет самым быстрым во всём мире ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2020, 19:31 |
|
||
|
|

start [/forum/topic.php?fid=58&msg=40023182&tid=2037816]: |
0ms |
get settings: |
5ms |
get forum list: |
11ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
137ms |
get topic data: |
6ms |
get forum data: |
2ms |
get page messages: |
37ms |
get tp. blocked users: |
1ms |
| others: | 208ms |
| total: | 411ms |

| 0 / 0 |
