LINUX.ORG.RU

timertt — библиотека с реализацией таймерных нитей для C++11

 ,


4

2

Дабы выбросить из своего проекта ACE Framework пришлось сделать свою реализацию таймеров. Получилась небольшая библиотека, которая не имеет внешних зависимостей и использует только возможности стандартной библиотеки C++11. Проверялась под Windows (MSVC++2013, MinGW-w64 GCC 4.9.1) и Linux (GCC 4.9.1).

Лицензия: 3-х секционная BSD. Т.е. использоваться может без проблем как в открытых, так и в закрытых проектах.

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

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

Библиотека поддерживает три таймерных механизма: timer_wheel, timer_heap и timer_list, у каждого из которых есть свои преимущества и недостатки. Может поддерживаться большое количество таймеров (сотни тысяч, миллионы или даже десятки миллионов) и обеспечивается высокая скорость обработки таймеров (до нескольких миллионов в секунду, но это зависит от времени работы связанных с таймером пользовательских событий).

В коде все это выглядит приблизительно следующим образом:

#include <iostream>
#include <cstdlib>

#include <timertt/all.hpp>

using namespace std;
using namespace std::chrono;
using namespace timertt;

int main()
{
	timer_wheel_thread_t tt;

	// Timer thread must be started before activation of timers.
	tt.start();

	// The simple single-shot timer.
	tt.activate( milliseconds( 20 ),
			[]() { cout << "Simple one-shot" << endl; } );

	// The simple periodic timer.
	// Will work until timer thread finished.
	tt.activate( milliseconds( 20 ), milliseconds( 20 ),
			[]() {
				static int i = 0;
				cout << "Simple periodic (" << i << ")" << endl;
				++i;
			} );

	// Allocation of timer and explicit activation.
	auto id1 = tt.allocate();
	tt.activate( id1, milliseconds( 30 ),
			[]() {
				cout << "Preallocated single-shot timer" << endl;
			} );

	// Periodic timer with timer preallocation, explicit activation
	// and deactivation from the timer action.
	auto id2 = tt.allocate();
	tt.activate( id2, milliseconds( 40 ), milliseconds( 15 ),
			[id2, &tt]() {
				static int i = 0;
				cout << "Preallocated periodic (" << i << ")" << endl;
				++i;
				if( i > 2 )
					tt.deactivate( id2 );
			} );

	// Single-shot timer with explicit activation and deactivation
	// before timer event.
	auto id3 = tt.allocate();
	tt.activate( id3, milliseconds( 50 ),
			[]() {
				cerr << "This timer must not be called!" << endl;
				std::abort();
			} );
	tt.deactivate( id3 );

	// Wait for some time.
	this_thread::sleep_for( milliseconds( 200 ) );

	// Finish the timer thread.
	tt.shutdown_and_join();
}

Скачать можно с SourceForge: только header-only вариант или же полный вариант с тестами/примерами. Документация там же в Wiki (пока на русском языке, потихоньку будет переводиться на английский).

Еще чуть-чуть подробностей по релизу здесь.

Сразу поясню для желающих спрашивать «нафига это нада?» и/или «афтар, а чем это лучше/хуже?». Если вы в своем проекте уже используете какой-то фреймворк/библиотеку, предоставляющий таймеры (например, ACE/Boost/Qt/wxWidgets/libuv/libev/libevent/you-name-it), то, скорее всего, timertt вам не нужен. Если только вы не обнаружите, что ваш инструмент не очень хорошо справляется с миллионом таймеров или же вам надоело натягивать свою прикладную логику на API вашего инструмента (актуально, например, для ACE, где таймерные очереди реализованы здорово, на вот API для них несколько своеобразный и не всегда удобный).

Если же в вашем проекте никаких тяжеловесных зависимостей нет, а таймеры нужны, то можно и в сторону timertt посмотреть.

Ну а вообще делал для себя, но не вижу причин не выложить в виде OpenSource.

★★★★

Нее, таймеры с отдельным потоком вместо event loop не нужны.

Зопили безпоточную реализацию с возможностью встраивания в event loop посредством classname::get_read_fd()+classname::process_timers(). А тогда уже сделай поток с простейшим select() внутри - для тех кому покатит и в отдельном потоке.

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

Какой смысл повторять то, что уже отлично работает в том же libuv?

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

А какой смысл повторять то, что уже отлично работает в том же boost?

Этот код может полезен где-то в XP будет, да ..

anonymous ()
Ответ на: комментарий от Pavval

Событийно-ориентированные приложения — это не только те, что байтики из сети читают. Иногда и более высокоуровневые механизмы коммуникаций используют, MQTT или AMQP, например. А прикладная логика занимается обработкой сообщений, полученных через уже готовый транспорт. Зачастую там нужно таймауты для разных стадий обработки отслеживать. Например, получил сообщение A, отослал куда-то запрос B, должен получить на него ответ в течении 30 секунд. Не получил, отослал в ответ на A сообщение с описанием ошибки по тайм-ауту.

evenl-loop в таком приложении может быть и не твой, а твои обработчики сообщений может дергать кто-то еще.

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

А какой смысл повторять то, что уже отлично работает в том же boost?

А прочитать исходное сообщение полностью слабо? Там сказано, что если Boost используется, то смысла тянуть что-то еще нет. А вот если не используется...

Или по-вашему, boost уже задействован в каждом проекте?

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

event-loop в таком приложении может быть и не твой

И только последние пидоры (привет, boost::asio) не позволяют в него встраиваться со своими источниками событий. И да, в таком случае - читай вторую часть моего поста. Я всего-лишь предложил обобщение либы на случай доступного для встраивания event-loop, чтобы избежать необходимости перекидывать событие в другой поток и необходимости иметь лишний поток под чисто ожидание.

Pavval ★★★★★ ()

// Timer thread must be started before activation of timers.
tt.start();

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

UPD. И про event-loop тут все правильно говорят.

staseg ★★★★★ ()
Последнее исправление: staseg (всего исправлений: 1)
Ответ на: комментарий от Pavval

И только последние пидоры

Ну, к таковым еще можно смело относить ACE Framework с его весьма продвинутой схемой Reactor-ов (включая ThreadPool Reactor) и Proactor-ов. Так же не уверен, что можно вклинится в event-loop какого-нибудь ZeroMQ или ZeroC. А так же системы вроде TIBCO Rendezvois, где, AFAIK, собственный диспетчер событий.

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

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

Во-вторых, OpenSource же. Кому нужно, сможет сделать.

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

только последние пидоры (привет, boost::asio) не позволяют в него встраиваться со своими источниками событий.

io_service::poll/io_service::poll_one - это разве не то, что нужно?

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

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

В конструкторе поток не стартует, чтобы дать возможность разделить создание объекта и его запуск. Создавать может быть необходимо в одном месте, а запускать и останавливать в другом.

Если стартовать автоматически в activate, то как бы не пришлось потом объяснять, что если кто-то вызвал shutdown, то после этого activate не должны рестартовать нить.

UPD. И про event-loop тут все правильно говорят.

Правильно ли я понимаю, что от использования timertt в своем проекте отделает только отсутствие возможности встраивания в event-loop?

Или же это все досужие разговоры на форуме?

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

В конструкторе поток не стартует, чтобы дать возможность разделить создание объекта и его запуск. Создавать может быть необходимо в одном месте, а запускать и останавливать в другом.

Поэтому этот случай и крайний.

Если стартовать автоматически в activate, то как бы не пришлось потом объяснять, что если кто-то вызвал shutdown, то после этого activate не должны рестартовать нить.

А пользователю таймера вообще нужен shutdown? Даже если так, нужно просто различать внешнюю «остановку таймера» и внутреннюю «остановку рабочего потока».

Правильно ли я понимаю, что от использования timertt в своем проекте отделает только отсутствие возможности встраивания в event-loop?
Или же это все досужие разговоры на форуме?

Библиотеки, создающие рабочие потоки всегда вызывают у меня опасения. Если я правильно понял, обработчики будут вызываться в дочернем потоке (спасибо, что в всего в одном), а это потенциальные проблемы синхронизации на ровном месте. Я в своем-то коде стараюсь обходиться без потоков, пока они реально не понадобятся, а трахаться с библиотечными потоками я просто ненавижу.

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

io_service::poll/io_service::poll_one - это разве не то, что нужно?

Конечно нет. event loop на костылях с таймаутами в цивилизованном обществе делать не принято.

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

Поэтому этот случай и крайний.

У кого как.

А пользователю таймера вообще нужен shutdown? Даже если так, нужно просто различать внешнюю «остановку таймера» и внутреннюю «остановку рабочего потока».

Вообще-то да. Даже у std::thread есть метод join(), который рекомендуют вызывать.

Кроме того, какая нахрен внешная и внутренняя остановка? Просто start, просто shutdown_and_join. Кому нужно что-то другое, запросто может отнаследоваться и проделать в своих конструкторах/деструкторах все, что захочет.

Библиотеки, создающие рабочие потоки всегда вызывают у меня опасения.

Ну понятно.

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

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

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

Вообще-то да. Даже у std::thread есть метод join(), который рекомендуют вызывать.

Но ведь джоин вовсе не останавливает поток...

Кроме того, какая нахрен внешная и внутренняя остановка? Просто start, просто shutdown_and_join. Кому нужно что-то другое, запросто может отнаследоваться и проделать в своих конструкторах/деструкторах все, что захочет.

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

И еще мне будет крайне неприятно обкладывать свой код мутексами.

Ну понятно.

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

staseg ★★★★★ ()

ОМГ, это аналог:

#include <iostream>
#include <thread>
using namespace std;

int main()
{
    thread t( [](){ 
        this_thread::sleep_for( 200ms );
        cout << "ORLY?\n";
    } );

    t.join();
}

?

anonymous ()
Ответ на: комментарий от staseg

Но ведь джоин вовсе не останавливает поток...

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

Поскольку timertt реализует таймерную нить, в которой, по сути, выполняется бесконечный цикл, то нужно иметь еще и способ дать команду прервать этот цикл. Отсюда и необходимость в методе shutdown.

Для простоты использования есть простой метод shutdown_and_join, который выполняет обе операции.

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

Если дело дойдет до обслуживания миллиона таймеров, то придется разбираться, как они обслуживаются в конкретной либе. И чем отличаются механизмы wheel от list, в каких условиях применимы одни, в каких другие.

В общем закон дырявых абстракций не на пустом месте возник.

Я хочу создать таймер, я могу захотеть явно запустить таймер, я могу захотеть явно остановить таймер, и конечно я захочу поставить таймеру в очередь задачу!

Либо я по-русски читать разучился, либо ты говоришь именно о методах start (запустить таймер), shutdown_and_join (остановить таймер) и activate (поставить таймеру в очередь задачу).

Поэтому я и говорю о разделении пользовательского интерфейса от деталей реализации.

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

И еще мне будет крайне неприятно обкладывать свой код мутексами.

Это понятно. Просто твой сценарий использования таймеров сильно отличается от моего. У меня, например, обработчик события таймера просто посылает сигнал в тот или иной рабочий поток.

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

У непредвзятого пользователя может быть 100500 причин не использовать библиотеку. В том числе и потому, что пользователь привык сам писать один-единственный event-loop, в котором он будет вызывать какой-нибудь метод timer.handle_expired_timers() или timer.next_time_step().

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

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

Да, только после того, как вы свой пример отмасштабируете хотя бы на 10K таймеров. Часть из которых будет периодическими.

А так да, в основе что-то подобное.

eao197 ★★★★ ()

Какое ограничение в вашей библиотеке по числу таймеров? Упирается ли оно в RLIMIT_SIGPENDING? И что делать пользователю timertt, если ему нужно больше таймеров?

nerdogeek ()
Ответ на: комментарий от eao197

Да, только после того, как вы свой пример отмасштабируете хотя бы на 10K таймеров.

10К таймеров в одном потоке, когда одна задача «отложит» 9999 и похерит все планирование? Cool story, bro.

anonymous ()
Ответ на: комментарий от nerdogeek

С лимитом RLIMIT_SIGPENDING оно вообще никак не связано. На тестах я запускал и 3M таймеров. Можно и больше. Все будет упираться в количество памяти и скоростью обработчиков самих таймерных событий. Например, если пользователь задаст 1M таймеров на интервал в 10ms, то, скорее всего, его обработчики просто не уложатся в этот интервал. А если задаст 10M таймеров на 24-часовой интервал, то все должно работать нормально.

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

10К таймеров в одном потоке, когда одна задача «отложит» 9999 и похерит все планирование? Cool story, bro.

Не делайте обработку таймерных заявок на нити таймера, а переукладывайте заявки в очереди рабочих потоков.

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

10К таймеров в одном потоке, когда одна задача «отложит» 9999 и похерит все планирование?

И да, это еще можно допустить, если это все будет выполнятся в главном треде, такая себе плата за безопасность, но в одном отдельном - ну его нах. Тут нужен пул тредов.

anonymous ()
Ответ на: комментарий от eao197

а переукладывайте заявки в очереди рабочих потоков.

А зачем тогда нужна твоя библиотека, если я сам буду тредами и очередями задач управлять?

anonymous ()
Ответ на: комментарий от eao197

С лимитом RLIMIT_SIGPENDING оно вообще никак не связано

А какие тогда средства ОС используются для реализации таймера?

nerdogeek ()

хотите рекомендовать свой проект/библиотеку исходников - давайте ссылку на репозитарий кода. Мне вот например влом выкачивать некий архивы 7z чтобы посмотреть код и убедиться что оно ненужно..и так практически всем ;-)

и да! sf.net уже не торт :-)

MKuznetsov ★★★★★ ()

Ах, ДА, чуть не забыл..!!!

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

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

Правильно ли я понимаю, что от использования timertt в своем проекте отделает только отсутствие возможности встраивания в event-loop?

Или же это все досужие разговоры на форуме?

Если бы мой текущий рабочий проект только писался, то я бы захотел заюзать либу, но заюзал бы исключительно при наличии интеграции в event-loop. Ибо ничего не делающие потоки плодить у нас не принято. Равно как и выдумывать синхронизацию там, где можно обойтись одним потоком.

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

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

Да никуда нормально нельзя. Делать в своем цикле таймауты, для того, чтобы вызвать poll - это уровень студенческой поделки. Как минимум ты просыпаешь проц без дела, а также жрешь процессорное время на эти пробуждения.

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

Ну в Akka или Node так и сделали, просто попросили по хорошему не делать блокирующих или длительных CPU-intensive операций. Так Akka хоть не на одном ядре и еденичные простои переживает. А вот нода вполне накроется. Но главное не это. Главное - при такой возможности отстрела ног, ПОСОНЫ, брат жив (и доволен)!

vertexua ★★☆☆☆ ()
Последнее исправление: vertexua (всего исправлений: 1)
Ответ на: комментарий от vertexua

Akka или Node
брат жив (и доволен)!

Кому и кобыла невеста.

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

Обожаю ЛОРовских перфекционистов. Они или в жизни нифига не написали, или же они еще те быдлокодеры, но старательно корчат из себя Ъ.

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

Обожаю ЛОРовских перфекционистов.

Ну запости сюда пример рабочего проекта на node.js «хотя бы на 10K таймеров».

Они или в жизни нифига не написали, или же они еще те быдлокодеры

Несомненно.

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

А зачем тогда нужна твоя библиотека, если я сам буду тредами и очередями задач управлять?

Зачем вам нужна моя библиотека — хз. Вероятно, вообще не нужна.

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

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

А какие тогда средства ОС используются для реализации таймера?

Походу те, что скрываются в реализации std::condition_variable::wait_until(). В POSIX это pthread_cond_timedwait(). В Win32, подозреваю, какой-то из WaitForSingleObject*.

Вот здесь немного расписано про то, как работают разные таймерные механизмы.

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

хотите рекомендовать свой проект/библиотеку исходников - давайте ссылку на репозитарий кода.

Стабильные версии здесь: tags/timertt, разрабатываемые версии здесь: branches/timertt.

Мне вот например влом выкачивать некий архивы 7z чтобы посмотреть код и убедиться что оно ненужно..и так практически всем ;-)

За всех не надо говорить. У меня, например, наоборот. Выбешивает, когда кто-то дает просто ссылку на github и даже не удосуживается собрать какой-никакой дистрибутив.

и да! sf.net уже не торт :-)

Мне пох. У меня работает :)

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

От задачи зависит. В timertt поддерживаются три механизма. Самые эффективные с точки зрения активизации и переустановки (периодические таймеры) — это timer_wheel/timer_heap. Самый эффективный о обработке однократных таймеров — timer_list. Если в задаче используются только однократные таймеры с одинаковым таймаутом, то timer_list будет самым эффективным.

Что до использования односвязных списков внутри реализации timer_wheel, то там это вообще самая эффективная структура. Как на добавление, так и на обработку, так и на изъятие.

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

Если бы мой текущий рабочий проект только писался, то я бы захотел заюзать либу, но заюзал бы исключительно при наличии интеграции в event-loop.

Собственно, на этом все.

Если бы кому-то реально было нужно, можно было бы вести разговор о том, как таймерные механизмы вынести из таймерных нитей наружу и придумать какой-то API вроде timer.next_timer_step().

Но мне это не нужно, у меня куча рабочих нитей и на них можно расставлять заявки на обработку событий. Для таких целей timertt со своей выделенной рабочей нитью работает нормально.

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

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

 typedef boost::function< void () > Callback;
 typedef std::multimap< boost::posix_time::ptime, Callback > TimeToCallback;
И создать тред, который раз в N миллисекунд будет пробуждаться и просматривать итератором контейнер типа TimeToCallback. Список просматривается до тех пор, пока текущее время больше первого аргумента в паре итератора.
Выбор структуры данных не ограничивается std::multimap - можно оптимизировать.

nerdogeek ()
Ответ на: комментарий от eao197

Стабильные версии здесь: tags/timertt,

В thread_basic_t у тебя невиртуальный деструктор. Ну и код непричесан, видно, что частично скопипащенно. Про его перегруженность промолчу.

anonymous ()

http://sourceforge.net/p/sobjectizer/wiki/timertt 1.0/#timer_heap

Операции вставки и удаления в heap-структуре довольно эффективны (O(log n), где n — это количество тймеров)

Не рассматривали ли вы возможность использования http://en.wikipedia.org/wiki/Van_Emde_Boas_tree для быстрой вставки и удаления ( O(log log N) ), операции get_min/max ( O(1) ) ?

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

Выбор структуры данных не ограничивается std::multimap - можно оптимизировать.

Мои замеры показывают, что heap-like структуры (будь то heap, set или map) заметно проигрывают в скорости wheel и list-у. В разы. И это объективно, к сожалению.

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

В thread_basic_t у тебя невиртуальный деструктор.

Он и не должен быть виртуальным. По замыслу там нет базового интерфейсного класса с публичными виртуальными методами activate/deactivate/start/shutdown. Поэтому нет смысла пользователю держать у себя timertt::details::thread_basic_t * и затем к этому указателю применять оператор delete.

Про его перегруженность промолчу.

Ну уж не надо себя сдерживать. Анонимы же все знают и умеют лучше всех. Глядишь чему-то научусь, а то я давно не программировал, подрастерял форму-то.

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

Не рассматривали ли вы возможность использования http://en.wikipedia.org/wiki/Van_Emde_Boas_tree для быстрой вставки и удаления ( O(log log N) ), операции get_min/max ( O(1) ) ?

get_min и в heap-е на основе array является O(1).

У меня была задача быстро получить работающий вариант. Поэтому на экзотические структуры данных не смотрел.

Буде такая надобность или интерес, плюс время, то посмотрю.

Однако, по-моему получается вот какая штука. timer_heap выгоднее timer_wheel либо при небольшом количестве таймеров, либо если таймеров много, но они сильно разрежены во времени. Например, 100K таймеров равномерно распределены на интервал в 24 или более часов. Но тогда удаление из обычного heap-array будет составлять мизерные накладные расходы. И имеет ли смысл делать более изощренную структуру... Вопрос?

Если же таймеров много и они распределены довольно плотно, то timer_wheel эффективнее.

Главный недостаток timer_wheel — это гранулярность таймера. Этого недостатка лишен timer_heap. Поэтому, если нужны более точные таймеры на основе timer_heap, то heap-array имеет смысл менять на какую-то структуру, которая позволяет эффективно вычленить не один минимальный элемент, а все элементы, которые меньше какого-то T. Позволяет ли это структура Van-Emde-Boas я не в курсе, не изучал.

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

Попробуйте добавлять события для таймера с возрастающим значением таймаута. Получится O(N^2) вставка в список. Если так уж хочется списков, можно попробовать стр-ру данных skip-list - есть мн-во имплементаций типа lock-free.

Ещё интересно как будут обработаны события после длительной задержки (система ушла в swapping)?

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

Попробуйте добавлять события для таймера с возрастающим значением таймаута. Получится O(N^2) вставка в список.

Мы про какой механизм говорим? Про timer_heap, так там же binary heap, у него в худшем случае на insert-ах должно быть O(lon N), если Wiki не врет.

Если про timer_list, то там вставка начинается не с головы, а с хвоста списка. Поэтому операция вставки таймеров с монотонно возрастающим таймаутом для timer_list самая лучшая. Она за O(1) выполняется. А вот если таймер должен попасть куда-то в середину списка, тогда да, дело швах. Не для такого сценария timer_list предназначен.

Ещё интересно как будут обработаны события после длительной задержки (система ушла в swapping)?

Если C++ runtime реализует нормальный steady_clock, то когда система вернутся из паузы, то все просроченные к этому времени таймерные заявки будут обработаны всем скопом.

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

Он и не должен быть виртуальным.

А смысл вообще добавлять пустой?

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

Несомненно. К примеру:

template<
	typename ERROR_LOGGER,
	typename ACTOR_EXCEPTION_HANDLER >

и все с этим связанное - костыли, которых нет в «ACE/Boost/Qt/wxWidgets/libuv/libev/libevent/you-name-it», и которые идут против идеологии С++. Собственная реализация умных указателей - тоже костыль, да и без них можно обойтись для решения такой задачи.

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

А смысл вообще добавлять пустой?

Он не пустой, он содержит базовую для всех нитей функциональность, связанную собственно с нитью. А базовые классы добавляют уже функциональность таймерных механизмов. Другое дело, что отнаследоваться от него можно было через protected или private, но тогда во всех наследниках пришлось бы прописывать using-и имен из базового типа.

и все с этим связанное - костыли, которых нет в «ACE/Boost/Qt/wxWidgets/libuv/libev/libevent/you-name-it», и которые идут против идеологии С++

Упс, что-то я не знаю, видимо, про идеологию C++. По поводу необходимости ERROR_LOGGER-а и ACTOR_EXCEPTION_HANDLER-а подробности вот здесь (см. так же пример).

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

Был бы в C++11/14 штатный шаблон интрузивного умного указателя, свой бы делать не пришлось (а shared_ptr — это неинтрузивный указатель, дополнительные накладные расходы).

Без указателя у меня не получилось решить проблему идентификации таймеров и обеспечения их эффективной деактивации. Подробности здесь

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

Можно ещё хранить массив map. Размер массива 24 * 60 * 60 * 1000. Каждый map будет хранить с точностью более миллисекунды таймеры. Тогда скорее всего можно добиться почти константного времени основных операций за счёт потребления памяти (порядка 1 Gb). Такое решение около real-time. Хотя для real-time потребуются многие другие важные заточки.

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

Имхо, это будет вариант timer_wheel-а, но вот с такими параметрами. Если интересуетесь этой темой, то есть мощная работа Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility. Там рассмативаются разные реализации таймерных механизмов. Есть разные версии этой работы, датированные разными годами. Эта ссылка на самую последнюю из увиденных мной, от 1997-го года. (Сам правда, просмотрел ее по диагонали, т.к. глубоко погружаться не было времени).

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