Множество отложенных действий (типа js setTimeout()) - как эффективно?

libuv, io_uring что-то такое

При инициализации проги выяснить точность системного sleep() путем тестирования.

Дальше засунуть все таймауты в дерево по упорядоченное по времени наступления событий, и начинать его обход, используя sleep() с рассчетом чтоб не проморгать наступление события, добирать нужный момент времени при помощи busywait.

Таким образом даже без linux-rt можно обеспечить приличную точность.

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

Спасибо!

Добавлю: если у него всего 2-3 сотни событий то, возможно, вместо дерева будет быстрее связный список. Хоть и разницу в скорости будет скорее всего не заметно, но связный список ещё и проще кодить.

Дальше засунуть все таймауты в дерево по упорядоченное по времени наступления событий

По фен-шую надо не в дерево, а в priority queue (кучу)

priority queue - это то, что хочет автор темы (ТЗ), а дерево - это то, как эту priority queue можно реализовать.

В C++, например, есть готовый контейнер под названием std::priority_queue, который внутри реализуется структурой данных «куча»

На 2-3 сотне может получится так что массив будет не сильно медленнее. А если таймауты вообще не вставляются в процессе работы, то и гарантированно будет самым оптимальным.

Что это за структура данных такая? Я это слово слышал только в качестве обозначения пула для динамического выделения памяти, что тут явно мимо.

А всё, нашёл.

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

timerfd + epoll.

Не, это малость про другое.

Какая точность нужна?

libuv, io_uring что-то такое

поддержу-ка !

если понадобились таймеры в значительных количествах, лучшее не велосипедное решение это брать готовую event queue. Почти точно ещё что-нибудь вкусное пригодится, тот-же асинхронный IO :-)

libuv очень хорош и проработан. Насколько помню он от node.js

ещё можно элементарно tcl вкатить и юзать Tcl_CreateTimerHandler.

Делал подобное: LOR #1, LOR #2.

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

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

• самый простой, timer_list, когда очередь – это двухсвязный список. Эффективное добавление, удаление, проверга готовности. Но все это хорошо работает только если таймеры добавляются строго в конец (например, если все тайм-ауты в программе одинаковые);
• более сложный, timer_heap, на основе структуры данных heap. Здесь нужно будет заморочиться с реализацией этого heap-а если нужно таймеры отменять еще до времени их срабатывания, если же отмены таймеров нет, то все проще. Не очень эффективен если нужно реально большое количество таймеров (от сотен тысяч и более);
• специфический, timer_wheel, который может обрабатывать огромные количества таймеров, но округляет время срабатывания каждого из них. При этом весьма эффективный и на добавление, и на изъятие таймеров.

Но если в проекте уже используются библиотеки вроде libuv или asio, или же в проекте есть собственный event loop на базе select/epool/чего-то еще, то можно использовать тамошние возможности.

На текущий момент план такой: рисую вариацию binary heap (tnx @annulen), который суть дерево (tnx @timdorohin), но в корневом узле минимальный (ближайший) launch time, т.е. время извлечения O(0). При этом, чтобы при добавлении узлов (которое будет весьма частым: периодические запуски нужно заново добавлять сразу после исполнения) не копировать куски дерева туда-сюда:

• организую не в массиве а в {Node* parent; Node* children[2]} (плюс кастомный memory manager);
• разрешаю узлы с 1 потомком.

В худшем случае, если у ВСЕХ узлов будет по 1 потомку, это будет double-linked list, который по слухам (tnx @firkax) мой объём вытянет. Но такое случится только если каждый добавляемый узел будет иметь launch time больше всех предыдущих; в противном случае добавление заполнит пустого второго ребёнка какого-то промежуточного узла (UPD TODO противоречит последнему пункту?).

Ну и чтобы какая-нить заклинившая задача, долго выполняющаяся и постоянно повторно добавляющая себя с delay=0, не заблокировала все остальные задачи в очереди, буду делать так:

• храню в узлах не delay, а launch time (по-другому собственно и никак; к слову – в наносекундах от моего epoch2 = 2025-01-01);
• если при добавлении узла, идя по дереву от корня, я напарываюсь на узел с таким же launch time, то пропускаю его и его потомков с совпадающими launch time и добавляю новую задачу в конец (самым дальним потомком).
• соответственно, у одного узла запрещаю детей с одинаковыми launch time, а для добавления ноды, чей launch time больше чем у обоих детей, выбираю поддерево с бОльшим launch time.

Как-то так. Пока что вроде всё выглядит красиво.

Posix-таймеры (timer_create и т.д.) с уведомлением через поток (функция запускается в потоке) с SIGEV_THREAD или SIGEV_THREAD_ID.

binary heap

время извлечения O(0)

Извлечение с удалением - O(log N).

• Я про извлечение корневого узла.
• Я храню узлы не в массиве.

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

Если я забью на

Ну и чтобы какая-нить заклинившая задача, долго выполняющаяся и постоянно повторно добавляющая себя с delay=0, не заблокировала все остальные задачи в очереди

то не выродится.

Извлечение с удалением - O(log N).

Да, похоже про O(0) я загнул. Тогда снова встаёт вопрос – нафига велосипедить, есть есть готовый std::priority_queue.

std::priority_queue

Основан на двоичной куче. Можно написать свой, который объединяет 2 операции - извлечение со вставкой (замена вершины) - для повторяющихся таймеров. Можно реализовать фибоначчиеву кучу, которая быстрее при выставке (если правильно помню).

Поискать другие алгоритмы и структуры для очередей с приоритетами.

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

Если «очередь» состоит чисто из целых чисел, которые надо расставить по дереву в правильном порядке - то да, выглядит красиво, хотя и так, по-моему, желательно увеличить количество потомков у узла (например 4), чтобы делать меньше перестановок.

Если же очередь состоит из некоторых структур с другими данными (и в том числе эти структуры могут участвовать в каких-то других списках, то есть перемещать их на другое место в памяти это не просто memcpy) - то всё получается сложнее. Тут получается два с половиной варианта:

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

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

2а) Хранить в куче указатели на структуры + рядом закешированные ключи сравнения, чтобы хотя бы сравнивать без указателей, ценой удвоения расхода памяти на кучу, хотя наверно это несущественно т.к. структуры данных всё равно занимают заметно больше.

Во вариантах 1 и 2а, если увеличить количество потомков у узла, можно заметно уменьшить описанные вредные эффекты.

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

Ну и всё-таки, сравнение с обычным b-tree (дерево с блоками размера процовой страницы т.е. 4кб): в нём указанных проблем с лишними хождениями по указателям почти нет, постоянно делать свапы не нужно, иногда приходится делать сплит или объединение блоков но это иногда - редко, и затрагиваются этой операцией обычно только 1-2 узла. И можно без проблем хранить структуры в самом btree без лишних указателей. Куча точно лучше?

Мысли читаешь. :) За исключением того, что куча походу таки-лучше потому что:

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

Насчёт увеличить число потомков узла – тоже прикидываю, но главным образом с целью не перетасовывать всё дерево при каждом извлечении элемента, а опять же – допускать узлы-пустышки на каждом уровне чтобы потом редуцировать смежные пустышки, не перелопачивая всё дерево; типа такого (но ещё недодумал):

      1     take min    X            X           X     3 free, compress  4
    2   3   ------->  2   3   ---> X   3  ---> X   X   ===============> 5 6
   4 5   6           4 5   6      4 5   6     4 5   6

В случае увеличения числа потомков (я начал было рисовать на бумажке 3 а не 4), логика сжатия может оказаться проще (а может и не оказаться).

UPD. На этой схеме фигня нарисована: дети 4-ки теряются. Поэтому и начал думать в сторону широких узлов. Хотя зреет ощущение, что и они не помогут, т.к. принципиально не устраняют этой проблемы.

Если предполагается хранение кучи в линейном массиве с индексами вида i*N+{1..N} для потомков, то это compress всё равно будет полным перетасовыванием и заберёт почти всё сэкономленное раньше время. Просто взять и перенести целиком кусок дерева в другое место (как ты кажется предполагаешь, судя по «дети 4-ки теряются») можно только если узлы хранятся отдельно друг от друга и связываются явным образом через поля в структурах. А такое хранение тоже портит скорость кучи.

Чтобы сделать compress без таскания по одному элементу (во время ли забирания вершины, или потом всех вместе, но по одному), придётся делать слияние трёх получившихся веток, а это по-моему ещё дольше чем три раза утащить вниз получившиеся дырки.

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

Зачем изобретать свой планировщик?

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

Зато нет проблемы с инвалидацией адресов узлов. А с кастомным memory manager (lock-free arena with fixed-size blocks) издержки только из-за доп.памяти на указатели.

придётся делать слияние трёх получившихся веток, а это по-моему ещё дольше чем три раза утащить вниз получившиеся дырки.

Тут я ещё не додумал. Вполне возможно, что и забью.

переизобретение пирамиды без шуток похвально

для нынешних cpu кэшей вроде как статистика вставок извлечений эвристируется апроксимируется лучшее весами в реализации например

https://grantjenks.com/docs/sortedcontainers/introduction.html#sorted-list

т.е задачка pq вопрос баланса операций бывают ли «протухания»(т.е к моменту когда элемент стал извлекатся он всё ещё актуален)

далее если есть вечные(т.е переодические) очередники ибо там с кратностями длительностей тож можно поигратся для «дерево деревьев»

т.е(в целом) «возможно» строит малые группы подсортировывать квадратично а сами группы мерджить пирамидой арности 3-4 на дереве

в а целом праскическое изучение своих реализаций позволит «замочит ноги» для лучшего ощущения конкретной задачи

в целом тут любая реализация достаточно если не гигалиарды событий в наносек

https://grantjenks.com/docs/sortedcontainers/performance-scale.html и обоснование https://grantjenks.com/docs/sortedcontainers/implementation.html

https://grantjenks.com/docs/sortedcontainers/performance.html#:~:text=Sorted ...

скажем 2-3 сотни

упс -> статическим массивом

Поскольку лисапедостроители, вместо того, чтобы изучать матчасть, продолжают праздно флудить, то просто оставлю это здесь: Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility

ИМХО, это просто из категории must read для тех, кто хочет реализовать обслуживание таймеров собственными руками.

Сенькс, прочитал. Прикольно. Как переварю, появится повод повелосипедить и пофлудить ещё и по этим схемам. :)

UPD: Хотя идея просыпаться на каждый тик – для высокоточных таймеров выглядит так себе. Но ты об этом писал в своём первом ответе:

округляет время срабатывания каждого из них

бывают ли «протухания»(т.е к моменту когда элемент стал извлекатся он всё ещё актуален)

В многопоточной среде не вижу вариантов кроме мьютексов на время пользовательских операций (добавление / удаление / триггер пользовательского колбэка по достижении времени).

самое НЕэффективное решение, которое нашло свой путь в мою башку, – 2-3 сотни потоков, в каждом sleep(delay).

Если использовать сопрограммы и «засыпать» большую часть времени внутри них, то это решение должно получиться гораздо менее вычислительно затратным, чем постоянно отсчитывать и сверять время по таймерам для каждой из задач. Да и проще будет сопровождать исходный код спустя какое-то время.

Интересно потому что. Вообще, попытаться реализовать что-либо самому и собрать соответствующие грабли – лучший способ понять мотивацию чужих решений.

Во, про coroutines тут ещё никто не вспоминал. Но на второй взгляд, это способ пробуждения, он ортогонален разработке структур, управляющих временем пробуждения.

Во, про coroutines тут ещё никто не вспоминал.

А чего их вспомнинать, если у вас в тегах только C и Linux, но нет C++.

Это специально, чтобы предлагали более низкоуровневые решения и алгоритмы вместо готовых контейнеров. Хотя вот std::priority_queue всё равно просочился – и это оказалось хорошо.

Кроме того, на какой-то cppcon чувак, рассказывавший про оптимизацию корутин в шланге, показывал их логику вообще на #define-ах, так что настоящему джедаю отсутствие плюсов не помеха. :)

Хотя вот std::priority_queue всё равно просочился – и это оказалось хорошо.

ЕМНИП, я у себя в реализации не смог использовать std::priority_queue, т.к. в ней нет возможности изъять произвольный элемент из любого места очереди. А это критично если есть необходимость отменять таймеры еще до их срабатывания.

Вот этот момент я держу в голове с самого начала, но провентилировать его до сих пор не добрался.

А ещё, если остановлюсь-таки на std::priority_queue, то скорость тасования underlying std::vector буду увеличивать путём хранения в нём только указателей на реальную структуру.

А если вы таки для C++ и посмотрели на мою библиотеку, то чем она не устроила?

«Я сам». :) У меня уже достаточно много наработок, минималистично-заточенных строго под мои нужды и представления о прекрасном. Иначе давно уже взял бы готовое, тут уже много всякого предлагали.

«Я сам». :)

Ну удачи тогда :)))

добирать нужный момент времени при помощи busywait

Да-да, чтобы ядро процесс шедулило пореже потому что он жрёт cpu.

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

А тебе какая разница подсунуть пользователю рекламу через пять секунд просмотра или через десять? Ты этим же занимаешься и поэтому помалкиваешь о своих «задачах», правда?