LINUX.ORG.RU

Вместо миллионов таймеров

 ,


1

3

Имею в наличии миллионы объектов, каждый из которых в идеале должен быть способен дергать обработчик(-и) с индивидуальной частотой.

Из идей:
1) забить на таймеры
Contra: последовательный (или чуть быстрее - в N потоков) перебор и обработка объектов, что сильно зависит от нижележащих вычислительных слоев (ОС, железо) => неравномерность обработки и просто много лишней работы по процессингу «низкочастотных» объектов в угоду более «высокочастотным»

2) один таймер, каждый объект имеет свой множитель частоты
Contra: требуется обработка всех объектов за время не большее, чем один такт таймера => немасштабируемость

3) каждый объект действительно связан со своим собственным таймером
Contra: например это, а в linux чота неясно, сколько можно без последствия для здоровья зарядить hr-timers

4) Компромисс в виде микса (2) и (3), имея несколько более разумное кол-во таймеров (10-100-10000)

Критика и рекомендации приветствуются.

один поток просыпается раз в N и из очереди расписаний выгребает кого пнуть. N считается как наименьшее общее частное от периодов пежду пинками

зы. толкьо пинать в томже потоке стоит осторожно ибо в обработчике пинка может оказаться чтение последний новостей от гугла на полчаса

Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)

один таймер, каждый объект имеет свой множитель частоты
Contra: требуется обработка всех объектов за время не большее, чем один такт таймера => немасштабируемость

Всех-то зачем? Только тех, чья частота должна сейчас сработать.

tailgunner ★★★★★ ()

В cocos2dx (игровой движок на OpenGL ES) видел такое решение: движок старается рисовать 60 кадров в секунду (просто делает eglSwapBuffers, а дальше уже андроид или другая ОС заботится о тайминге); перед рисованием кадра один раз получает время через системный API и пробегает все подвешенные на таймер функторы, запуская те из них, у кого подошло время очередного срабатывания. Если функтор вешается с интервалом в 0 миллисекунд, то будет запускаться один раз на кадр.

quiet_readonly ★★★★ ()

А можно озвучить пороговые значения тиков и среднюю временную оценку выполняемых задач.

pon4ik ★★★★★ ()

Напиши свой таймер в юзерспейсе, нужен будет только conditional variable. Опционально, per core. Будет работать с отсортированным списком таймеров. Объекты, которым надо «выстрелить» через какое-то время, ставят себя в очередь.

mv ★★★★★ ()

Што? Что вообще такое в твоём понимании «таймер»? Всего-то нужно, менеджер у которого регистрируются объекты, в менеджере отсортированный список deadline'ов и поток который спит до ближайшего времени срабатывания nanosleep'ом, просыпается, получает реальное время, вызывает все обработчики которые пора вызвать и засыпает опять.

slovazap ★★★★★ ()
Ответ на: комментарий от t184256

Эмм.. Изъясняться щас буду туповато, т.к. не знаю что именно я имею ввиду, я этот вопрос не разгребал ни разу ))

А если запилить так, что один поток четко отрабатывает по нужным интервалам и тупо «постит» уведомления для тех, кто что-то где-то «слушает». Я бы предположительно копал в сторону select/poll/epoll/kqueue/fifo. Ммм?

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

то это будет медленная, кривая и неоттестированнная реализация того, что и так умеет уже существующий планировщик, не?

t184256 ★★★★★ ()
Ответ на: комментарий от t184256

Планировщик? В контексте одной прилаги? Брось ссылкой. Пойду читать. Яш сказал что не копал в ту сторону ни разу.

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

Кто-то же раздает тредам процессорное время... Чего такого не умеет он, что его хочется испортить оберткой?

t184256 ★★★★★ ()

Я бы делал примерно так:
Все задания ставятся в очередь, отсортированную по времени следующего срабатывания.
Работают несколько потоков (а может и один).
Если поток видит в очереди задание, которому пришло время, то выполняет его, иначе засыпает на некоторое время.

Выбор количества потоков зависит от интенсивности и может быть динамическим.

German_1984 ★★ ()

Несколько пулов отсортированных по времени сна объектов.

andreyu ★★★★★ ()

Один таймер и медленные задачи в отдельном потоке выполнять.

Y ★★ ()
Ответ на: комментарий от mv

Опционально, per core.

Я думаю, не опционально, а крайне желательно.

post-factum ★★★★★ ()

Плюсую очередь с приоритетом. Единственный косяк это вставка в начало очереди. Вот тут придётся немного подумать головой :).

true_admin ★★★★★ ()
Ответ на: комментарий от pon4ik

А можно озвучить пороговые значения тиков

Присоединяюсь к вопросу. Хотелось бы услышать о каких интервалах и каком разрешении по времени идёт речь, много ли таймеров с кратными интервалами, насколько важно соблюдать точность интервалов и т.д.

А иначе, если ты, ТС, ставишь задачу в общем виде, то общее решение - возьми более мощное железо. Что-то оптимизировать можно только зная конкретные условия.

no-such-file ★★★★★ ()
Ответ на: комментарий от deep-purple

Значит не нужны никакие таймеры, а нужно постоянно что-то лопатить в реальном времени.

slovazap ★★★★★ ()

5) Тебе нужен scheduler, например EDF

beastie ★★★★★ ()

Если C++11 может рассматриваться в качестве языка реализации, то запустить в программе сотни миллионов, даже миллиарды таймеров не проблема. Как раз для этих целей я себе timertt написал. Несколько миллионов таймеров — легко :)

Но можно пойти и дальше. Взять SObjectizer и представить каждый ваш объект в виде агента с отложенными/периодическими сообщениями. Несколько миллионов агентов — это тоже не проблема. Как раз одна из областей, в которой SObjectizer использовали — это имитационное моделирование, где объекты модели представлялись агентами.

eao197 ★★★★★ ()
Последнее исправление: eao197 (всего исправлений: 1)

У тебя при любом раскладе получается, что в каждый конкретный тик таймера должны дернуть экземпляр обработчика все объекты, которым пришло время это сделать. Иначе задача теряет смысл.

Предложу другую идею. Заведи пул экземпляров обработчика. Таймер будет один. В очередной его тик все объекты, которым пришло время дернуть обработчик, ставятся в очередь.

Очередь разгребается пулом экземпляров обработчика асинхронно. То есть, очередной тик таймера наступает независимо от того, насколько очередь заполнена. Даже если она не пуста, в неё всё равно помещается очередной набор объектов.

Так действуя, сможешь хотя бы отследить - как очередь заполняется, как разгребается, сколько ресурсов требуется, каких размеров пул нужен, может быть - даже динамически управлять его размером. Профилировать сможешь (только смотри - делай это когда никто не видит). В общем, получишь определённый контроль над процессом и необходимую для дальнейшей оптимизации информацию.

anonymous ()

И ещё совет - активно ищите неоднородности в задаче: в каждый тик таймера Т должны дернуть обработчик N(T) объектов. Как выглядит N(T)? Она близка к константе? Это можно использовать. Она имеет пики? Это можно использовать. Все можно использовать в свою пользу.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.