Size: a a a

2020 November 18

d

disba1ancer in pro.algorithms
Александр Караев
Привет.
Подскажите, какую структуру данных лучше взять для достаточно типичной задачи: есть множество коллбэков, необходимо удалять/добавлять новые (write доступ), вызывать их в цикле (read доступ), всё это в многопотоке и с условием, что коллбэк внутри себя может стриггерить удаление/добавление другого коллбэка. Хранятся они по уникальным ключам, удаляются по ним же.

Пока что в голову лезет достаточно жуткое решение с тремя пулами (current, items_to_add, items_to_remove) под тремя мьютексами и нетривиальной логикой. Но я уверен, что есть какие-то общепринятые практики
Чём-то напоминает мои муки с тред пулом...
источник

d

disba1ancer in pro.algorithms
@Ioann_V может тут дискутировать про тредпул будем?
источник

I

Ioann_V in pro.algorithms
Не, лучше в графоне
источник

AS

Arsen Stotskyi in pro.algorithms
Время прихода клиента моделируется по экспоненциальному распределению со средним временем tсреднее.прих. для интервалов между поступлениями.

tсреднее.прих., мин = 6

Если я правильно понял, то интервал между поступлениями это 1/6 ?
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Arsen Stotskyi
Время прихода клиента моделируется по экспоненциальному распределению со средним временем tсреднее.прих. для интервалов между поступлениями.

tсреднее.прих., мин = 6

Если я правильно понял, то интервал между поступлениями это 1/6 ?
Он же рандомный
источник

AS

Arsen Stotskyi in pro.algorithms
Тут дальше

Время обслуживания клиента моделируется по экспоненциальному распределению со средним временем tсредн.обслуж.
tсредн.обслуж., мин = 0.6

Ограничения на работу кассового зала: tраб.зал.
tраб.зал. от 24 по 13
источник

AS

Arsen Stotskyi in pro.algorithms
Как мне рассчитать Среднее число заявок, обслуживаемых в единицу времени каждым кассиром ?
источник

m

magras in pro.algorithms
Александр Караев
не, смотри..

lock(mutex);
for (const auto& [id, callback] : m_map) {
 callback();
}
unlock(mutex)

и теперь внезапно внутри callback у нас написано: m_map.clear() или m_map.erase(123) (под мьютексом, конечно). Это либо дедлок на одном потоке, либо инвалидация итераторов, либо висячая ссылка, либо всё вместе :)
Мне кажется эта проблема обычно решается копированием нужной цепочки под локом и отпусканием лока. Правда я не пониял, почему итерация идет по всей мапе. Я бы предположил, что в мапе по событию мы находим цепочку коллбэков, копируем ее, отпускаем лок и начинаем их исполнять.
источник

АК

Александр Караев... in pro.algorithms
magras
Мне кажется эта проблема обычно решается копированием нужной цепочки под локом и отпусканием лока. Правда я не пониял, почему итерация идет по всей мапе. Я бы предположил, что в мапе по событию мы находим цепочку коллбэков, копируем ее, отпускаем лок и начинаем их исполнять.
копировать на каждый вызов целую пачку функций дороговато..
я упростил, предполагая, что мы уже по имени события нашли список коллбэков, которые нужно вызвать (то есть снаружи это тоже обернуто в некоторую мапу)
источник

АК

Александр Караев... in pro.algorithms
magras
Мне кажется эта проблема обычно решается копированием нужной цепочки под локом и отпусканием лока. Правда я не пониял, почему итерация идет по всей мапе. Я бы предположил, что в мапе по событию мы находим цепочку коллбэков, копируем ее, отпускаем лок и начинаем их исполнять.
в процитированном примере id нужен просто как номер для дальнейшего удаления
источник

m

magras in pro.algorithms
Александр Караев
копировать на каждый вызов целую пачку функций дороговато..
я упростил, предполагая, что мы уже по имени события нашли список коллбэков, которые нужно вызвать (то есть снаружи это тоже обернуто в некоторую мапу)
Лок фри тоже не бесплатный. Там много проблем с управлением временем жизни объектов. Простое с точки зрения пользователя решение - это использовать std::atomic<shared_ptr>. Есть варианты с очередями на удаление и амортизацией.
источник

MS

Mikola Summer Duck in pro.algorithms
Оооо кто-то сказал локфри
источник

АК

Александр Караев... in pro.algorithms
magras
Лок фри тоже не бесплатный. Там много проблем с управлением временем жизни объектов. Простое с точки зрения пользователя решение - это использовать std::atomic<shared_ptr>. Есть варианты с очередями на удаление и амортизацией.
очередей на удаление я хотел избежать, много мороки.
на локфри я не настаиваю, потоков у меня действительно мало.
основная решаемая проблема - это модификация контейнера из того же потока во время итерации по нему (и всё это приправлено наличием нескольких потоков)
источник

MS

Mikola Summer Duck in pro.algorithms
Александр Караев
Привет.
Подскажите, какую структуру данных лучше взять для достаточно типичной задачи: есть множество коллбэков, необходимо удалять/добавлять новые (write доступ), вызывать их в цикле (read доступ), всё это в многопотоке и с условием, что коллбэк внутри себя может стриггерить удаление/добавление другого коллбэка. Хранятся они по уникальным ключам, удаляются по ним же.

Пока что в голову лезет достаточно жуткое решение с тремя пулами (current, items_to_add, items_to_remove) под тремя мьютексами и нетривиальной логикой. Но я уверен, что есть какие-то общепринятые практики
Коллбеки — простые функции? Помещаются в указатель?
источник

АК

Александр Караев... in pro.algorithms
Mikola Summer Duck
Коллбеки — простые функции? Помещаются в указатель?
конечно же нет
источник

АК

Александр Караев... in pro.algorithms
shared_ptr на std::function - это прям простейшее решение, но не много ли индирекции? да и атомарный счётчик дёргать не хочется.
с другой стороны, я вместо std::function взял кастомную реализацию с SSO побольше и полиси, возможно докрутить туда аллокатор..
источник

MS

Mikola Summer Duck in pro.algorithms
Александр Караев
конечно же нет
Твоё „множество коллбеков“ владеет добавляемыми в него коллбеками?
источник

АК

Александр Караев... in pro.algorithms
Mikola Summer Duck
Твоё „множество коллбеков“ владеет добавляемыми в него коллбеками?
да
источник

MS

Mikola Summer Duck in pro.algorithms
Тогда локальная арена и вектор атомарных указателей в арену.
источник

АК

Александр Караев... in pro.algorithms
Mikola Summer Duck
Тогда локальная арена и вектор атомарных указателей в арену.
не уловил, зачем атомарность.
мне фактически хватит std::shared_ptr<const std::function<void()>>
источник