powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Lock-free: Доведём очередь до ума
22 сообщений из 147, страница 6 из 6
Lock-free: Доведём очередь до ума
    #39556091
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUkealon(Ruslan),

Да еклмн
Где там ошибка?!
не внемлишь же, уже говорил про эту ошибку


вот тебе зависание:

Код: 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.
var
  CCCC: Integer;
function TSyncQueue<T>.Enqueue(const Value: T): Boolean;
var
  Node: PNode;
  Tail: TSyncPointer;
  test: Boolean;
  x: T;
begin
  test := InterlockedIncrement(CCCC) = 3;
  // новый узел
  Node := TSyncAllocator<Pointer,TNothing,T>.New;
  Node.Value := Value;
  Node.Next := nil;

  // подмен€ем FTail на узел
  Tail := FTail.AtomicExchange(Node);
  (*repeat
    Tail := FTail.Copy;
  until (FTail.AtomicCmpExchange(Node, Tail)); *)
  // инициализируем Next предущего узла или сам FHead
  if (Tail.Empty) then
  begin
    if test then begin
      Enqueue(Value);
      Dequeue(x);
    end;
    //FHead.Fill(Node);
    FHead.AtomicExchange(Node);
  end else
  begin
    PNode(Tail.Value).Next := Node;
  end;

  Result := True;
end;

...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39556118
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
хотя нет вру, ожидание срабатывает

непонятно как без ожидания проверить
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39556426
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

В Dequeue же просто вхолостую работает цикл, если Next не инициализирован
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39556440
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,
да заметил, 20968902

TestUG падает раз из 5-7 запусков, причём так же как и раньше - два потока для этого достаточно
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39556470
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

А идеи, как оно происходит - появились?

Вообще, когда Enqueue есть, а Dequeue нет - это чистой воды потеря элемента. Мои тесты тоже иногда показывают, что теряют элемент.
Уж не ABA ли?
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39556484
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Добавил автотест, получил вот такую картину:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
Iteration 1... done
Iteration 2... done
Iteration 3... done
Iteration 4... done
Iteration 5... done
Iteration 6... done
Iteration 7... done
Iteration 8... done
Iteration 9... done
Iteration 10... done
Iteration 11...
Элемент 5448036 потерян
Элемент 5448037 потерян
Элемент 5448038 потерян
Элемент 5448039 потерян


Press Enter to quit

Т.е. потеряно сразу 4 элемента, идущих подряд. Точно ABA. Только где?
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39556565
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUТ.е. потеряно сразу 4 элемента, идущих подряд. Точно ABA. Только где?
не обязательно, проверь без переиспользования памяти, это исключит АБА
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39556579
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

Как это - без переиспользования памяти?
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39556589
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUkealon(Ruslan),

Как это - без переиспользования памяти?выделяешь большой блок и от него отщипываешь пока не закончится

н-р на 100 млн элементов, твоей очереди на 10 секунд точно хватит
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39556628
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

Можно в Dequeue нод не возвращать системе
Если комп под рукой - посмотри, пожалуйста
Я только к вечеру до компа дойду
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39557014
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUkealon(Ruslan),

Можно в Dequeue нод не возвращать системе
Если комп под рукой - посмотри, пожалуйста
Я только к вечеру до компа дойду
за 10 раз TestUG не повторился, скорее всего ABA выходит

PS: около 10-11 млн/c держится - "менеджер памяти ноды" надо менять
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39557103
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

В коде есть возможность «эмулировать» очередь через стек
И в стеке используется та же модель аллоцирования памяти. А именно free list - самый элементарный и быстродейственный вариант

И стек не давал ошибок, не давал ABA. Следовательно, дело не в менеджменте памяти, а в самом алгоритме
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39557115
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

про менеджер был вывод, что он довольно медленный

АБА конечно в алгоритме
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39557152
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

Да быстрее вроде некуда. Стек и память никуда не удаляется
А как «долгость» может инициировать ABA?
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39557168
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

это так, на заметку, с АБА это не связано
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39567487
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

небольшими оптимизациями удалось приблизиться к техническому пределу на 4-х потоках
https://sourceforge.net/p/cl4fpc/code/HEAD/tree/Containers/lfqueues.pas


Код: 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.
  1 threads
Cicle count: 20324
Cicle count: 21207
Cicle count: 21943
Cicle count: 21369
Cicle count: 21195
Cicle count: 21202
  2 threads
Cicle count: 16711
Cicle count: 16556
Cicle count: 16906
Cicle count: 15959
Cicle count: 16327
Cicle count: 16101
  3 threads
Cicle count: 12555
Cicle count: 13022
Cicle count: 12897
Cicle count: 12576
Cicle count: 13717
Cicle count: 12582
  4 threads
Cicle count: 10971
Cicle count: 10340
Cicle count: 8797
Cicle count: 9477
Cicle count: 10483
Cicle count: 9759

хз тока зачем это надо если критическая секция даст тоже самое.
По идее дальше вся проблема в функции разгрузки
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39567515
vavan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)хз тока зачем это надо если критическая секция даст тоже самоеlf-контейнеры (кроме прочих их достоинств и преимуществ) могут оказаться нужны когда контейнеров надо ахулиард и может оказаться нежелательным задействовать такую массу объектов синхронизации
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39567530
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vavankealon(Ruslan)хз тока зачем это надо если критическая секция даст тоже самоеlf-контейнеры (кроме прочих их достоинств и преимуществ) могут оказаться нужны когда контейнеров надо ахулиард и может оказаться нежелательным задействовать такую массу объектов синхронизациитут така вещь, что все эти оптимизации уже есть в критической секции и реальных обектов синхронизации не так много создаётся. Фактически, в большинстве случаев срабатывает обычный спин-лок.

хотя как вариант возможно неплохое применение на обшаренной между процессами памяти
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39567553
vavan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)все эти оптимизации уже есть в критической секциикрит. секция при всех ее прелестях вещь весьма виндовая а lf без мутексов и т.п. бывают кросс-платформенные
kealon(Ruslan)реальных обектов синхронизации не так много создаётсяно создаться таки могут, а уж "если неприятность может случиться то она непременно случится" (С)
kealon(Ruslan)Фактически, в большинстве случаев срабатывает обычный спин-локну пока contention/starvation не случатся вообще конкурентов у cs практически нет
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39568139
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

А моя очередь разве не быстрее крит секции?
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39568145
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А вот это никто не смотрел?
http://www.thedelphigeek.com/2010/02/dynamic-lock-free-queue-doing-it-right.html

Ну это я так, на правах мимокрокодила :)
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39568160
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alekcvp,

Смотрели, но не осилили
Можешь ради интереса поставить его код в какой-нибудь тест
Можно вообще сравнительный тест замутить
...
Рейтинг: 0 / 0
22 сообщений из 147, страница 6 из 6
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Lock-free: Доведём очередь до ума
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]