Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Всем привет Я тут в разделе Delphi пытался совместными усилиями покопать мою реализацию lock-free очереди. Она сбоит, но не понятно где. Разные эксперименты к результату не привели. Поэтому я решил обратиться к более широкой аудитории. Большинство "ответчиков" не пытались вникнуть в ситуацию и понять суть алгоритма. К примеру, один из форумчан упрекал меня в том, что код содержит AtomicExchange, а не цикл с AtomicCmpExchange. Я же пробовал много разных подходов, но на тестах алгоритм иногда давал сбой Критерий нахождения ошибки простой: нужно описать ситуацию (сценарий) при котором алгоритм сработает не корректно Я всю голову сломал, придумать такой вариант не смог, может быть у вас получится Суть в следующем: 1) Очередь представляет собой односвязный список от Head к Tail 2) Очередь пуста если Tail не указывает ни на что 3) Поток, изменивший Tail, важнее того, что модифицирует Head 4) Список может быть временно разорван (Next = nil, ещё не инициализирован) - в этом случае просто ждём 5) TSyncPointer - это "tagged pointer", т.е. указатель, в котором меняется счётчик при Atomic-операциях Отвечу на любые вопросы. Надеюсь на помощь. На всякий случай - вот репозиторий . Код: 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. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 20:26 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Сори, вот код с родной разметкой Код: 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. 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. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 20:28 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Опиши ошибку. Что значит - сбой? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 20:47 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Ты взялся за очень сложную задачу. Ее либо решают, либо не решают. Помощи просить бесполезно. Почитай посты этого чела , он достаточно подробно расписывает почему не стоит пытаться писать свое lock-free. Он написал, но также описывает все встреченные им грабли, по которым пришлось пройти. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 20:55 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Dima T, Интересно, кто их тогда пишет, инопланетяне? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 20:59 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, PNode(Tail.Value).Next := Node; Эта операция атомарна? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 21:23 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikronSOFT FOR YOU, Опиши ошибку. Что значит - сбой? Есть тестовое приложение. Там два пишущих потока и два читающих. Числа (вроде бы 10 млн) последовательно закидываются в очередь и тут же читаются А потом происходит анализ прочитанного. Сбой происходит если одно число извлечено несколько раз или наоборот ни разу Есть второй тест Там 5 потоков, каждый делает одно и то же: сначала записывает число, потом тут же его извлекает В этом тесте сбой - когда запись произошла, а прочитать не удалось (очередь считается пустой) mikronSOFT FOR YOU, PNode(Tail.Value).Next := Node; Эта операция атомарна? Да, Next это обычный указатель Когда узел кладётся в FTail - его Next равен nil Когда кладётся ещё один узел - тогда пишется Next предыдущего Здесь идёт обычное присвоение [volatile] указателя ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 21:59 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, я "ответчик" который сходу, нечитал то что ты написал. Но вброшу несколько поинтов. 1) Dephi-разработка в большинстве случаев ориентирована на Windows-среду исполнения. Я готов принять тот факт что существуют всякие там Лазарусы но все таки основной сегмент потребления это OS от Microsoft. Поэтому нас наверное будет интересовать тюнинг этой структуры данных под Windows и ее "родной" API. Если вопрос тюнинга для нас не стоит то тогда не нужен и lock-free и прочее. 2) Совершенно нет никакого смысла делать "классический связный" список. Нам достаточно массива. Завёрнутого в "бублик". Ну и два поинтера которые будут указывать на голову и хвост. Рискну предположить что это оптимально и экономно по месту и когерентно по кешу. 3) До кучи можно добавить эвристику которая будет "растягивать" бублик как только есть потребность. Растягивать экспоненциально. И эвристику которая будет "уплотнять" бублик если он давно не использовался. Над правилами можно подумать. Во времени или в циклах. Вот как-то так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 23:53 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Atomic-функции кроссплатформенные. Под Windows, Mac, Linux, iOS или Android Есть реализации очереди в ограниченном массиве. Есть определённые плюсы в такой реализации Но какой смысл переписывать реализацию, если даже в коде выше мы не можем найти ошибку ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:06 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Тесты хорошие. Я не знаком с Делфи и наверняка глупость, но проверь Tail := FTail.Copy; Head := FHead.Copy; Тип у Tail и Head почему не Node? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:23 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikronSOFT FOR YOU, Тесты хорошие. Я не знаком с Делфи и наверняка глупость, но проверь Tail := FTail.Copy; Head := FHead.Copy; Тип у Tail и Head почему не Node? Это "tagged pointer" Т.е. это указатели на Ноды, но есть ещё счётчик Счётчик нужен для того, чтобы в случае AtomicCmpExchange не возник ABA ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:32 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Код собран с оптимизацией? Если собрать без оптимизации тесты пройдут? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:33 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUAtomic-функции кроссплатформенные. Под Windows, Mac, Linux, iOS или Android Есть реализации очереди в ограниченном массиве. Есть определённые плюсы в такой реализации Но какой смысл переписывать реализацию, если даже в коде выше мы не можем найти ошибку Сходу вопрос. Ты профилировал? Где у тебя bottleneck? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:38 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mayton, Нет, а зачем профилировать? Сейчас же вопрос в корректности, а не в производительности ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:43 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, У меня нечто подобное на с#. В паре мест код можно упростить но ошибок я не вижу. НО я думал TSyncPointer стандартная дейфийская комронента, и на её правильность можно положится. Тепер же выясняется что это твоя поделка, а значит проверять надо с неё. Причём очень внимательно смотреть на оптимизацию в плоть до генерируемого кода. Вопрос, я ту не мог бы переписать без использования TSyncPointer ? Что есть у дельфи для volatilr read и InterlockedExchange? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 01:15 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, В Delphi есть ряд Atomic-функций. Они работают над 4 и над 8 байтами. У меня же используется обёртка над ними с инкрементом счётчика Что же касается корректности, в тесте есть режим, когда вместо очереди используется стек Так вот на стеке всё работает отлично, а он тоже реализован на TSyncPointer ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 01:37 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Это не доказывает ничего т.к. Реализация другая и ошибка может не проявится. Мне кажется ошибка в cmpexchange? Убери пожалуйста в проверку на равенство перед системным вызовом. Это ведь оптимизация, верно? Значит не принципиально. И повтори тест. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 02:06 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, Повторил Воспроизводится :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 02:55 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Вот примерно то что у тебя написано на Delphi. Работает как задумано. Попробуй перевести это в Delphi без TSyncPointer. Код: c# 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 10:51 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, вот ещё тест. Код: c# 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 11:27 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 11:36 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, Не совсем Назови Slot --> Node для большей читабельности :) _head и _tail это не указатели на узлы, это указатели + счётчики Сделаны счётчики для обхода ABA, но с другой стороны в C# не бывает ABA С другой стороны, Head.Value := Node на C# уже не сэмулируешь Ну и самое главное - на данном примере у меня проблема вообще не проявилась (i3). Но проявилась у другого участника (i5) У меня были траблы на другом тесте, где считаются повторяющиеся элементы и потеряные И то баг был задетекчен далеко не с первого запуска Но спасибо за попытку повторить :) Кто знает, может быть на C# с учётом памяти GC, это действительно очень грамотная реализация очереди ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 11:39 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Последная рабочая версия. Код: c# 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. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 11:43 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU_head и _tail это не указатели на узлы, это указатели + счётчики Сделаны счётчики для обхода ABA, но с другой стороны в C# не бывает ABA Я не понимаю проблeмы ABA в контексте конкретной задачи. Я понимаю где она возможна в принципе, но где она имеет значение для конкретной реализации? Почему в С# нету проблемы? Откудого это. SOFT FOR YOUС другой стороны, Head.Value := Node на C# уже не сэмулируешь А где это имеет значение? SOFT FOR YOUНу и самое главное - на данном примере у меня проблема вообще не проявилась (i3). Но проявилась у другого участника (i5) У меня были траблы на другом тесте, где считаются повторяющиеся элементы и потеряные И то баг был задетекчен далеко не с первого запуска Я так понял, что проблема репродуцируема. С дрогой стороны тот же алгоритм на другом языке не имеет проблемы. (по крайней мере не воспроизводится) Следовательно проблема не в алгоритме а в базовых конструкциях. Поэтому попробуйте то же самое без ваших указателей. Просто переведите мой код в делфи для теста. Он к тому же несколько отличается от вашего. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 12:13 |
|
||
|
|

start [/forum/topic.php?fid=16&fpage=17&tid=1340221]: |
0ms |
get settings: |
11ms |
get forum list: |
15ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
33ms |
get topic data: |
14ms |
get forum data: |
3ms |
get page messages: |
95ms |
get tp. blocked users: |
3ms |
| others: | 30ms |
| total: | 212ms |

| 0 / 0 |
