Здравствуйте, VladFein, Вы писали:

VF>Здравствуйте, antropolog, Вы писали:

A>>А надо было всего-лишь реализовать простой паттерн — привязку продюсера к конкретному потоку. В данном случае это делается отдельной очередью на каждый поток, и помещением таски в очередь с индексом = taskID % threadNum

VF>Такого требования нет в задании.
конечно нет, ведь я описываю имплементацию

VF>Таск от любого клиента может выполняться любым потоком, если только другой поток не выполняет в это время таск этого клиента.
вот именно, что "может", а не "должен", а вы все пытаетесь прочесть как "должен"

VF>Мне видится простой алгоритм: все таски (с ID клиента) ставятся в одну очередь, в порядке поступления.
VF>CThreadPool имеет set "клиентов в процессе".
VF>Потокам при создании передаётся callback на:
VF>CTask* CThreadPool::NextTask(int& _clientId);
VF>Где [in, out] _clientId — при вызове равен ID предыдущего клиента (например, -1 для начала), а по возвращении — текущего.
VF>Потоки работают в бесконечном цикле NextTask() / Execute(). Ведь конечного условия не дано?

VF>CThreadPool::NextTask() удаляет ID предыдущего клиента из set'а, перебирает лист в поисках первого ID клиента, не найденного в том set'е, добавляет его в set, удаляет из очереди и возвращает потоку.
А если в очереди лежат только ID уже работающих клиентов, то нужно поток усыпить, а затем по прибытию нового таска, опять проверить список, так?

итого имеем:
set, queue, и один mutex, который защищает обе эти структуры и лочится на время работы:
NextTask,
AddTask
и всё это для того чтобы забалансить таски по тредам.

В то время как в моём случае:
отдельная lock-free очередь на каждый тред
NextTask/AddTask работает с конкретной очередью, мьютекс не нужен, поиск в очереди не нужен, добавление/удаление таски — одна CAS операция. Единственный недостаток — теоретическая разбалансировка, я повторюсь — теоретическая, например при малом количестве клиентов, и если у них внезапно совпал id % threadnum (ну или hash(id) % threadnum ). В реальном мире такая разбалансировка практически не встречается, а если встречается то на малом количестве "долгих клиентов" и при невезучем случае.

Иными словами — мой алгоритм оптимален для много клиентов с мелкими тасками ( т.к. минимальный shared state и отсутствие блокировок). Ваш алгоритм оптимален для "долгоиграющих" задач он небольшого количества клиентов (т.к. во-первых идеально балансирует, а во-вторых частота обращения к очереди задач относительно редка ). Но повторюсь, об оптимальной балансировке в вакууме ( как и о трейде latency<->throughput ) можно написать диссертацию, а в тестовом задании ничего не сказано о балансировке, поэтому выбирается наиболее простой вариант ( и в то же время самый распространённый ), имплементация которого тривиальна.

Здравствуйте, VladFein, Вы писали:

VF>Здравствуйте, antropolog, Вы писали:

A>>А надо было всего-лишь реализовать простой паттерн — привязку продюсера к конкретному потоку. В данном случае это делается отдельной очередью на каждый поток, и помещением таски в очередь с индексом = taskID % threadNum

VF>Такого требования нет в задании.
конечно нет, ведь я описываю имплементацию

VF>Таск от любого клиента может выполняться любым потоком, если только другой поток не выполняет в это время таск этого клиента.
вот именно, что "может", а не "должен", а вы все пытаетесь прочесть как "должен"

VF>Мне видится простой алгоритм: все таски (с ID клиента) ставятся в одну очередь, в порядке поступления.
VF>CThreadPool имеет set "клиентов в процессе".
VF>Потокам при создании передаётся callback на:
VF>CTask* CThreadPool::NextTask(int& _clientId);
VF>Где [in, out] _clientId — при вызове равен ID предыдущего клиента (например, -1 для начала), а по возвращении — текущего.
VF>Потоки работают в бесконечном цикле NextTask() / Execute(). Ведь конечного условия не дано?

VF>CThreadPool::NextTask() удаляет ID предыдущего клиента из set'а, перебирает лист в поисках первого ID клиента, не найденного в том set'е, добавляет его в set, удаляет из очереди и возвращает потоку.
А если в очереди лежат только ID уже работающих клиентов, то нужно поток усыпить, а затем по прибытию нового таска, опять проверить список, так?

итого имеем:
set, queue, и один mutex, который защищает обе эти структуры и лочится на время работы:
NextTask,
AddTask
и всё это для того чтобы забалансить таски по тредам.

В то время как в моём случае:
отдельная lock-free очередь на каждый тред
NextTask/AddTask работает с конкретной очередью, мьютекс не нужен, поиск в очереди не нужен, добавление/удаление таски — одна CAS операция. Единственный недостаток — теоретическая разбалансировка, я повторюсь — теоретическая, например при малом количестве клиентов, и если у них внезапно совпал id % threadnum (ну или hash(id) % threadnum ). В реальном мире такая разбалансировка практически не встречается, а если встречается то на малом количестве "долгих клиентов" и при невезучем случае.

Иными словами — мой алгоритм оптимален для многоих клиентов с мелкими тасками ( т.к. минимальный shared state и отсутствие блокировок). Ваш алгоритм оптимален для "долгоиграющих" задач он небольшого количества клиентов (т.к. во-первых идеально балансирует, а во-вторых частота обращения к очереди задач относительно редка ). Но повторюсь, об оптимальной балансировке в вакууме ( как и о трейде latency<->throughput ) можно написать диссертацию, а в тестовом задании ничего не сказано о балансировке, поэтому выбирается наиболее простой вариант ( и в то же время самый распространённый ), имплементация которого тривиальна.