|
|
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, как его соорудить? (КА) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 12:04:25 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)Aleksandr Sharahov, как его соорудить? (КА) Построить имитационную модель, описывающую очередь (включая общую память) + 2-3 читающих потока + 2-3 пишущих потока (с их локальными данными). Определить возможные состояния потоков между операторами, работающими с очередью (включая общую память) + локальные данные. Определить общее состояние системы как сумму всего. Прогнать модель по всем возможным переходам состояний системы. Наткнуться на ошибки при работе очереди и исправить их. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 12:25:27 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Теоретиков много и реализаций много. Для Delphi я видел только одну реализацию (два стека, инверсия) и мне этот вариант не нравится непрогнозируемостью времени исполнения. Есть в Tail накопится 100500 элементов, то при Dequeue бог знает, сколько займёт инверсия. Не факт, что теорию ты грамотно реализуешь на Delphi. Или в теории нет ошибок. Или в реализации на другом языке. Вон, с точки зрения теории, мой вариант прекрасен. Однако где-то закралась ошибка (и). Ну или вот реализация MSQueue от автора известной lock-free библиотеки libcds. Однако, его реализация не подходит для менейджед-типов (описал в первом посте почему) Я тебя спросил (как и всех впрочем), потому что у тебя глаз не замылен. И могут появиться идеи ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 12:59:41 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Да, тестовое приложение, где два пишущих потока и два читающих - есть (в репозитории ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 13:02:14 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUреализация MSQueue от автора известной lock-free библиотеки libcds ... не подходит для менейджед-типов (описал в первом посте почему) Честно говоря, не понял, почему оно не должно работать для указателя на строку. Кто строку юзает, тот ее и освобождает ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 14:28:40 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUДля Delphi я видел только одну реализациюGpLockFreeQueue, OTL смотрел? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 14:32:25 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
vavanSOFT FOR YOUДля Delphi я видел только одну реализациюGpLockFreeQueue, OTL смотрел? первое я ему уже подкидывал, когда он ещё супер-пупер-мега-менеджер памяти делал чем-то не подошло ему ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 15:10:50 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Строка D11 Пока один поток копирует строку, второй поток может её удалить Код: 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. Поток A читает валидный указатель-строку Поток B освобождает валидую строку Поток А обращается к несуществующей области памяти ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 15:22:07 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUAleksandr Sharahov, Строка D11 Пока один поток копирует строку, второй поток может её удалить ... Поток A читает валидный указатель-строку Поток B освобождает валидую строку Поток А обращается к несуществующей области памяти 1. Я там не вижу строку D11. 2. Зачем они это делают? Почему вместо того, чтобы работать с *указателем* на строку, они работают со строкой? К работе со строкой надо переходить, когда есть полная уверенность в успешном извлечении данных из очереди. В нашем случае это указатель на данные. Его-то можно безопасно извлечь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 15:31:33 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
vavanSOFT FOR YOUДля Delphi я видел только одну реализациюGpLockFreeQueue, OTL смотрел? Смотрел Если я правильно понял, его реализация - имеет ограничение на количество элементов. А я хочу без ограничения Кроме того, он там сильно заморочился на теги, много атомиков В данной реализации должно быть быстрее Когда ошибку найдём ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 15:36:31 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Строку D11 надо смотреть здесь :) У них видимо данные не менаджатся и данная реализация устраивает ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 15:42:38 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, И в чем проблема? Указатели нельзя копировать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 15:48:48 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Ну если ты пишешь шаблоны - то копирование происходит просто Value := Node.Value. А финализация Finalize(Node.Value) Строку я привёл в качестве примера. Это может быть структура, содержащая строки, интерфейсы и динамические массивы. Или вообще Weak экземпляры классов :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 15:52:48 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Кстати я избавился от ассемблера, заменил FTail на "tagged pointer" Сейчас работает стабильнее, но ошибки всё равно детектятся: Код: plaintext 1. 2. Код теперь выглядит так: Код: 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 15:58:24 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Правильные пацаны помещают в очередь указатели на свои структуры данных. А ты экономишь одну загрузку адреса, и поэтому их реализация тебе не подходит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 15:59:40 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUAleksandr Sharahov, Ну если ты пишешь шаблоны - то копирование происходит просто Value := Node.Value. А финализация Finalize(Node.Value) Строку я привёл в качестве примера. Это может быть структура, содержащая строки, интерфейсы и динамические массивы. Или вообще Weak экземпляры классов :) Финализировать раздельно надо. Отдельно элемент очереди. И отдельно (после разыменования указателя и использования структуры) свою структуру данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 16:04:48 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Персона Иванов ИИ обладает фамилией, именем и т.д., но не является элементом очереди. Это объект или запись класса персона. Иван Иваныч может одновременно стоять в 10 очередях: на квартиру, за зарплатой, на автобус, за хлебом... Но вместо него в этих очередях стоят адреса. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 16:15:50 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Ну во-первых, претензии не ко мне - а к автору статьи :) Во-вторых, если мы храним указатель, то где-то его нужно выделять и освобождать. Либо должны будем юзать свой ограниченный буфер памяти в виде lock-free стека, что приведёт к лимитированности очереди и дополнительным атомикам, либо будем обращаться к стандартному менеджеру, который синхронизируется критической секцией, со всеми вытекающими. Тем более, для малых типов данных использовать указатель на память в куче - очень расточительно. Наконец, lock-free алгоритмы являются отличной возможностью поломать голову И я свою, похоже, сломал ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 16:19:10 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, я же тебе уже говорил, Empty и всё такого рода это бессмысленные функции, а она у тебя опять в коде ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 16:20:47 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Никто ж не против Иван Иваныча или адресов. Меня интересует общий случай, когда можешь поместить адрес, Иван Иваныча или динамический массив - и все они войдут и выдут из очереди во время ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 16:21:19 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), А я тебе говорил, что это сравнение Value на nil. И стоят они там, где нужно проверить Value на nil :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 16:22:24 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUAleksandr Sharahov, Никто ж не против Иван Иваныча или адресов. Меня интересует общий случай, когда можешь поместить адрес, Иван Иваныча или динамический массив - и все они войдут и выдут из очереди во время ну, тогда это действительно серьезный случай ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 16:29:38 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahovkealon(Ruslan)Aleksandr Sharahov, как его соорудить? (КА) Построить имитационную модель, описывающую очередь (включая общую память) + 2-3 читающих потока + 2-3 пишущих потока (с их локальными данными). Определить возможные состояния потоков между операторами, работающими с очередью (включая общую память) + локальные данные. Определить общее состояние системы как сумму всего. Прогнать модель по всем возможным переходам состояний системы. Наткнуться на ошибки при работе очереди и исправить их. Добавлю, что на однопроцессрной машине бесполезно этим заниматься.. 1 процессор и N ядер не подходят тоже. От автора статьи так и не дождались его конфигурации ради чего это затевается. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 16:30:22 |
|
||
|
Lock-free: Доведём очередь до ума
|
|||
|---|---|---|---|
|
#18+
X-CiteДобавлю, что на однопроцессрной машине бесполезно этим заниматься.. 1 процессор и N ядер не подходят тоже. От автора статьи так и не дождались его конфигурации ради чего это затевается. На 1 процессоре можно легко сымитировать N-процессорную очередь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.11.2017, 16:34:24 |
|
||
|
|

start [/forum/topic.php?fid=58&msg=39549691&tid=2041445]: |
0ms |
get settings: |
13ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
1248ms |
get topic data: |
11ms |
get forum data: |
4ms |
get page messages: |
69ms |
get tp. blocked users: |
2ms |
| others: | 250ms |
| total: | 1618ms |

| 0 / 0 |
