LINUX.ORG.RU

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

 ,


5

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.

★★★★

Женя, тебе не нужен отдельный поток для таймеров. В архитектуре твоего приложения вполне можно в диспетчере агентов вызывать перед wait() (когда все события обработаны и дальше делать нечего) timertt::process_penging_timers(), которая пробежит по контейнеру таймеров, вызовет нужные обработчики и вернет время, которое нужно спать до следующего таймера. Ну, а в диспетчере сделать wait_for() вместо wait(). Проснувшись этот поток должен будет снова сходить проведать созревшие таймеры...

По архитектуре работы с контейнером таймеров. Я бы ее организовал по умному, т.е. по принципу Flat Combining (хотя с тупым захватом mutex тоже можно). Первый поток, который вызвал process_penging_timers() захватывает mutex и проводит всю обработку. Если кто-то (из другого потока) хочет поменять таймер (добавить, удалить, отключить, перевести стрелки...), то он либо захватывает тот же mutex (try_lock()) и все проделывает сам, либо если не получилось, записывает свою задачу в lock_free список анонсов операций (который достаточно сделать конкурентным хотя бы на запись, либо можно взять MPMC очередь фиксированного размера) и идет спать (или работать дальше). Ну, а тот, кто захватил mutex отработает этот список анонсов операций. Если же поток готов пойти спать, а process_penging_timers() выполняет кто-то другой, то тогда придется сделать wait() как и раньше без всяких _for (достаточно одного потока, висящего на wait_for()).

Как бонус, возможно, что такое решение удастся совместить с event loop, как тут хочется отдельным товарищам («возможно», потому что я так и не понял, что конкретно не хватает в boost::asio).

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

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

В программировании от идеи до ее корректной реализации очень большой, иногда путь.

Повторюсь, у меня не было цели сделать инструмент для всех. Мне нужно было заменить ACE, в котором таймерная очередь обслуживается на отдельной нити. Соответственно, замена работает по такому же принципу.

Если же говорить вообще, то можно сделать еще одну декомпозицию, разделив понятия timer_mechanism и timer_thread. И сделать возможность пользователю использовать timer_mechanism отдельно от timer_thread.

Но, это требует времени. Которого и так не хватает. Если кто-то в такой реализации действительно заинтересован, можно думать в этом направлении. Если все это только ради потрепаться на форуме, то на это тоже нет времени.

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

конкретно не хватает в boost::asio

лично мне не нравится интерфейс. а у жени — nih-синдром.

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

я беру не с++, а документацию к используемой ос

Кстати да, первая же мысль была, что я б просто выписал прототипы функций и написал пачку небольших и специфичных для каждой ОС реализаций. Ну это, если б мне нечего было делать, и я решил не брать готовое.

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

лично мне не нравится интерфейс. а у жени — nih-синдром.

Можете указать альтернативу таймерам из ACE Framework, которые бы не тянули за собой Boost, Qt, libuv/libev/libevent или еще что-нибудь?

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

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

для начала системные вызовы вместо велосипедов; потом — выбор готовой библиотеки (это не так просто)

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

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

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

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

которые бы не тянули за собой Boost, Qt, libuv/libev/libevent или еще что-нибудь?

А в чем тут собственно проблема?

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

Можете указать альтернативу

конечно

сначала смотри сюда: www.linux.org.ru/forum/development/10871681?cid=10873965

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

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

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

«возможно», потому что я так и не понял, что конкретно не хватает в boost::asio

Вот тебе 2 задачи: 1. встроить свое событие в io_service, 2. встроить io_service в свой event-loop.

Выложи код/псевдокод решения этих задач. Требования здравого смысла: 1. без лишних пробуждений процессора 2. без задержки обработки, т.е. одиночное событие должно обрабатываться мгновенно. Эти требования отлично решаются в отдельности io_service и, например, epoll(). А вот совместить их не выйдет.

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

А вот совместить их не выйдет.

а если в разных потоках?

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

конечно

Вперед. Хотя бы названия.

Общие слова я и сам могу наговорить.

Проблема с ACE была не в том, что там что-то не так было сделано. В ACE, кстати говоря, очень хорошая реализация нескольких типов таймеров. Поддерживающая десятки тысяч таймеров (проверено в продакшене). А в том, что есть маленькая библиотека, которая раньше полностью базировалась на ACE, а затем потихоньку переползла на libc++. И единственное, что осталось от ACE существенное — это таймеры. Заставлять пользователя к библиотеке в 15KLOC качать еще и 9Mb дистрибутива ACE, а затем цеплять все это к своему проекту (и еще не совсеми ACE дружит, не говоря, например, про отсутствие нормальной поддержки MinGW и clang). Так что нужно было, чтобы в эти 15KLOC небольшой библиотечки вошли еще и собственные таймеры, чтобы свести любые внешние зависимости к минимуму.

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

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

а если в разных потоках?

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

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

это был сарказм (с)

epoll использует, если не запутается в своё джеме.

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

Заставлять пользователя к библиотеке в 15KLOC качать еще и 9Mb дистрибутива ACE, а затем цеплять все это к своему проекту (и еще не совсеми ACE дружит, не говоря, например, про отсутствие нормальной поддержки MinGW и clang). Так что нужно было, чтобы в эти 15KLOC небольшой библиотечки вошли еще и собственные таймеры, чтобы свести любые внешние зависимости к минимуму.

Если вы даете библиотеку в собранном виде, то статическая линковка ACE спасет отца русской демократии и позволит выкинуть практически все неиспользуемое. А -flto так еще и сделает волосы мягкими и шелковистыми ускорит и сделает еще меньше. Лично проверено.

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

Проблема с ACE была не в том

....

чтобы свести любые внешние зависимости к минимуму.

это и называется nih-синдром.

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

какой реакции на свои творения ты в результате ожидаешь на лоре?

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

Если вы даете библиотеку в собранном виде, то статическая линковка ACE спасет отца русской демократии и позволит выкинуть практически все неиспользуемое.

1. Не только в собранном, но и в исходном.

2. Нужна динамическая линковка.

3. Заголовочные файлы ACE все равно нужны. А это уже может спровоцировать проблемы при совместном использовании с другими библиотеками.

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

какой реакции на свои творения ты в результате ожидаешь на лоре?

Анонимные тимлиды поднимают настроение.

Вменяемые люди подталкивают в нужном направлении.

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

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

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

Давайте так. Вы прочитаете вот это

вам поставить оценку за лабараторку? или это курсовая??

код остаётся говном, вне зависимости от сопутствующей документации.

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

Вот тебе 2 задачи: 1. встроить свое событие в io_service, 2. встроить io_service в свой event-loop.

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

1. встроить свое событие в io_service

Что конкретно тут нужно? io_service может выполнять команды, преобразуй свои события в его команды и отдавай ему на выполнение. Они будут выполняться моментально (io_service epoll'ит на eventfd и при появлении команды в его очереди, он словит event на файловом дискрипторе).

Если под «встроить свое событие в io_service», то, возможно, архитектура boost::asio не позволит это сделать.

встроить io_service в свой event-loop.

io_service это и есть event-loop на событиях на файловых дескрипторах. Если твой event-loop работает, например, на условной переменной, то я не знаю, как их совместить. Epoll тоже файловый дескриптор, поэтому его можно отдать на poll'ing в io_service. Но в общем случае я не знаю как решать такую задачу на одном потоке. Я бы для обоих event_loop'ов создал отдельный поток и организовал между ними обмен сообщениями (командами). Вообще, любой event-loop, насколько я знаю, организован таким образом, что он ждет событий, а пока их нет - весь поток спит. Я не знаю, как зарулить события на условной переменной в события на файловом дескрипторе и наоборот, кроме как создать для каждого свой обработчик событий на своем потоке.

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

Не только в собранном, но и в исходном.

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

Нужна динамическая линковка.

Так на вашу библиотеку и будет динамическая, а то, что в ней внутри, ее личное дело, хоть ACE, ICU и Qt в полном комплекте.

Заголовочные файлы ACE все равно нужны.

Это, если библиотека == набор хедеров, и вся реализация торчит наружу.

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

вам поставить оценку за лабараторку? или это курсовая??

код остаётся говном, вне зависимости от сопутствующей документации.

Ну хорошо. Во-первых, спасибо, что таки привлекли мое внимание к make_exec_list в timer_list. Эта реализация делалась из реализации для timer_wheel, поэтому я забыл, что в list-е не нужно переносить элементы по одному, можно сразу отрубить кусок. За это спасибо.

Теперь пойдем по вашим авторитетным претензиям.

// нахрен юзеру другие источники ?
// достаточно зашибенной библиотеки упендюренной в хидер

Юзер — это автор библиотеки. Ему достаточно одного типа таймера, steady_clock-а. Поскольку из стандартной библиотеки это единственный тип таймера в stdlib, который должен переживать перевод часов вперед/назад (по крайней мере по документации).

Для первой версии этого достаточно. Будет необходимость использовать другой тип clock-а, будем думать. Не будет (что скорее всего), останется как есть.

// кстати это всё внутри lock

Именно. Это все под lock-ом. Идея такая: захватить mutex, выгрести под ним по максимуму все готовые таймеры, освободить mutex, запустить все сработавшие таймеры, затем опять захватить mutex. При работе с реально большим количеством таймеров этот подход позволяет избежать лишних накладных расходов (порядка >10M таймеров в секунду в зависимости от платформы и компилятора).

// очень важно..а то забудем куда положили и не найдём
t->m_status = timer_status_t::wait_for_execution;

Именно. Это очень важно. Есть две политики запуска таймерных событий.

Первая: по одному. Т.е., захватили mutex, изъяли первую заявку из очереди, освободили mutex, обработали заявку. В этом случае, если пользователь внутри таймерного события (или где-то в стороне, на совсем другой нити) деактивирует эту заявку, то ниоткуда ее вычеркивать не нужно. Достаточно просто пометить ее, что она деактивирована. Тогда, после обработки, если заявка была периодической, ее не нужно ставить повторно в очередь. Все просто. Но цена — захват и освобождение mutex-а на каждую заявку.

Вторая политика заключается в том, чтобы захватить mutex, построить список, освободить mutex, затем пройти по списку. И вот тут уже начинаются интересные вещи. А что, если заявку в этот момент деактивируют. В каком списке она находится: в текущем рабочем или в ожидающем? Если в ожидающем, то все хорошо, она просто изымается. А вот если в рабочем? Можно ли ее удалять прямо сейчас? И, если она периодическая, как указать, что нельзя ее помещать в очередь ожидания повторно.

Отсюда и появляется статус заявки. Который сначала выставляется в wait_for_execution, а потом, для периодической заявки, переводится в active. А вот если во время обработки заявка была деактивирована, то она помечается сначала как wait_for_deactivation. И только когда обработка всего текущего списка будет завершена, только тогда она окончательно деактивируется и получает статус deactivated.

Так что да, это очень важный момент в коде.

// кстати m_tail очень сцуко важное поле (как и m_prev)
// позволяет удалять таймер за O(1)
// правда путём траха на других операциях, но там юзер может и подождать

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

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

// priority queue ? не, не слышал..

Ну а это вообще шедеврально. Квалифицированный вы наш, таймерный механизм на основе heap-а (а как раз heap очень часто лежит в основе приоритеных очередей) чуть ниже по коду. Если же в механизме timer_list, где операция изъятия любого элемента, на который есть прямой указатель, обходится в O(1), будет под капотом задействована priority_queue с O(log N), то как это будет называться?

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

Так на вашу библиотеку и будет динамическая, а то, что в ней внутри, ее личное дело, хоть ACE, ICU и Qt в полном комплекте.

Не так все просто. ACE требует специальные действия выполнять при старте приложения для своей инициализации. Они для этого даже собственный макрос main() определяют, в котором свой main реализуется, а пользовательские действия запихивают в ace_main_i. Если этого не сделать, то приложение, скорее всего на каком-нибудь вызове ACE тупо грохнется.

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

Не так все просто. ACE требует специальные действия выполнять при старте приложения для своей инициализации.

Да, аж целый вызов ACE::init().

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

Да, аж целый вызов ACE::init().

Тем не менее, вызывать нужно. Следовательно, ace.dll/so (особенно dll) нужна будет и исполнимому файлу, а не только моей dll/so-ке.

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

Тем не менее, вызывать нужно. Следовательно, ace.dll/so (особенно dll) нужна будет и исполнимому файлу, а не только моей dll/so-ке.

А в чем проблема вызвать ACE::init() из библиотеки? Можно даже автоматом сразу при ее загрузке.

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

А в чем проблема вызвать ACE::init() из библиотеки? Можно даже автоматом сразу при ее загрузке.

Если сложить все вместе, то оно того не стоит. Больше потратишь время на убеждение того, что ACE в зависимостях — это не страшно.

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

Если сложить все вместе, то оно того не стоит. Больше потратишь время на убеждение того, что ACE в зависимостях — это не страшно.

Оно делается один раз и «забывается». Да и работает со старыми компиляторами. Впрочем дело твое, раз у тебя работает и все устраивает - то почему бы и нет. Главное не увлекаться.

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

Юзер — это автор библиотеки. Ему достаточно одного типа таймера, steady_clock-а.

мне показалось, или вы создавая тред предложили остальным стать юзерами ? :-) тогда вместо тренировки в механизмах логичнее предлагать выбор источника времени

Именно. Это все под lock-ом. Идея такая: захватить mutex, выгрести под ним по максимуму

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

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

зачем пользователю выбирать некий «таймерный механизм» ?? я вот вижу только одну причину - автору лень делать хорошо :(

А именно: таймеры всегда добавляются в конец очереди. Например, все таймеры одноразовые и имеют одинаковую паузу срабатывания.

что-то фантазии не хватает, чтобы представить это IRL. Ближе к реальности - первыми создаются «абсолютные» таймеры(это которых у вас нет), потом идут «длинные» одноразовые и последними «короткие» периодические. Или вы предлагаете держать разные механизмы (читай «рабочие нити») для разных типов таймеров?

Ну а это вообще шедеврально

шедеврально - это в шаблонах С++ ТРИ полных реализации xxx_timer отличающихся внутренним типом prio.q.

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

мне показалось, или вы создавая тред предложили остальным стать юзерами ? :-)

Показалось.

тогда вместо тренировки в механизмах логичнее предлагать выбор источника времени

Как я уже говорил, если кому-то будет нужно, можно будет на эту тему подумать в будущей версии.

Если цель - держать 100500 таймеров для куевой тучи нитей, это плохая идея.

Цель не в этом. Одна нить должна обрабатывать 100500 таймеров.

Ваш list_timer_t просто таки напрашивается (иначе какой в нём смысл) на неблокирующую реализацию.

Ахринеть, дайте два. Давайте еще и lock-free list подтянем и механизм hazard pointers в придачу.

Впрочем, если 8-10M таймеров в секунду не будет хватать, придется и об этом думать.

зачем пользователю выбирать некий «таймерный механизм» ?? я вот вижу только одну причину - автору лень делать хорошо :(

Если вы не видите, то это могут быть ваши личные проблемы. Как с уровнем квалификации, так и с элементарным кругозором.

Тут уже, если не ошибаюсь, несколько раз говорилось, что на реально больших объемах таймеров нет общего универсального механизма. В каждом есть свои плюсы и минусы. Соответственно, если задача реально требовательная к реализации таймеров, то пользователю придется вникать, что лежит под капотом. И «сделать хорошо» будет означать предложить несколько реализаций под разные сценарии. Поинтересуйтесь, на досуге, сколько типов таймерных очередей поддерживает тот же ACE Framework. И причинами, побудившими авторов ACE к разработке такого количества реализаций.

Если задача не требовательная, то timer_heap или timer_wheel, в зависимости от приблизительного количества таймеров.

что-то фантазии не хватает, чтобы представить это IRL

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

Сценарий, с которым я сам сталкивался, это рестрансляция прикладных сообщений. Некий промежуточный компонент B получает сообщения от A, передает их C, выставляя тайм-аут на получение ответа от C. Если в течении тайм-аута ответ не получен, то В отсылает A соответствующее уведомление и забывает про это сообщение. Получается исключительно монотонный таймер, все тайм-ауты одинаковые, никаких периодических заявок. Идеальный сценарий для timer_list.

шедеврально - это в шаблонах С++ ТРИ полных реализации xxx_timer отличающихся внутренним типом prio.q.

А то, что внутри STL, к примеру, ЧЕТЫРЕ полных реализации простого линейного контейнера объектов (vector, deque, list, forward_list) вас не смущает?

Сейчас три xxx_timer. Возможно, со временем будет больше. Возможно, тогда будет больше информации, которая позволит переиспользовать общие куски кода. Пока удалось переиспользовать только функциональность, вынесенную в thread_basic_t. Еще куда-то напрашиваются enum timer_status_t и ensure_timer_deactivated. Но в том же timer_heap нет timer_status_t и ensure_timer_deactivated там реализуется совсем иначе.

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

итак, продолжим..про m_tail и «школьные алгоритмы» например..

вы ввели m_tail уверяя, что он позволяет в редких случаях проводить операцию добавления за O(1). Но на самом деле, операция добавления (старта таймера) и так может реализоваться за константное время.

Следите за руками

  • Если добавляемый таймер имеет минимальную метку то помещаем ровно в начало очереди. (время=const). Иначе нет смысла его туда помещать - положим его в стек (на базе тех-же списков, и тоже время=const). В нитке пользователя делать больше нечего. Отожранно минимальное константное время(на одно сравнение и пересылку двух указателей) и в принципе можно реализовать без мутекса
  • В нитке таймера после сработки актуального таймера остаётся смержить несортированный стек-список размером K в отсортированный активный список размером N. На случайных данных это вдвое быстрее чем O(K*N), а в реальной жизни и более того - даже близко к O(K). Кстати блокировать стек на всё время лишнее, достаточно скопировать и обнулить один указатель, то есть тоже подумавши можно сделать non-blocking
  • Что получается? m_head, m_prev ненужны - для реализации достаточно односвязных списков. Нитки блокируются на мизерное константное время. Общее время на старт K таймеров при N ожидаемых - O(K) с малым множителем на пользователях плюс O(K*N/2) на нитке таймера. Против O(K*N) непредсказуемого пользователем ожидания на его нитках.

это была только одна операция одного класса. Вам надо переосмысливать их все

Вместо попыток ваять «быстро-суперски-удобные» shared_ptr и штампования копипастой новых «механизмов» стоит наверное подумать о сути задачи и нормально реализовать что-то одно.

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

Отожранно минимальное константное время(на одно сравнение и пересылку двух указателей) и в принципе можно реализовать без мутекса

И чем вы будете защищаться от вытеснения текущей нити между одним сравнением и обменом двух указателей?

В нитке таймера после сработки актуального таймера остаётся смержить несортированный стек-список размером K в отсортированный активный список размером N.

Это автоматически делается посредством binary heap. При этом там вообще должная степень упорядоченности заявок обеспечивается автоматически.

Что получается?

*йня полна. Хотя вам, несомненно, нравится, т.к. физдеть — это не реальный код отлаживать.

m_head, m_prev ненужны - для реализации достаточно односвязных списков.

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

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

Сценарий, с которым я сам сталкивался, это рестрансляция прикладных сообщений. Некий промежуточный компонент B получает сообщения от A, передает их C, выставляя тайм-аут на получение ответа от C. Если в течении тайм-аута ответ не получен, то В отсылает A соответствующее уведомление и забывает про это сообщение. Получается исключительно монотонный таймер, все тайм-ауты одинаковые, никаких периодических заявок. Идеальный сценарий для timer_list.

сценарий высосанный школьником из пальца для обоснования timer_list. IRL у proxy всегда есть таймеры более длительные чем таймаут на ответ - и они всегда будут в конце списка. И быстрые таймеры будут всегда об них спотыкаться

А теперь рассмотрите еще возможность деактивации таймера в любой момент.

О да!! деактивация и удаление это супер-критическая операция. Нить пользователя конечно-же может ждать непредсказуемое время взводя таймер, но удалять должна строго за O(1).

лаба видимо называлась «таймеры оптимизированные к удалению» ??

MKuznetsov ★★★★★ ()

За такой код нужно голову ржавой пилой отрезать. Долго ты еще будешь нам тут свои поделки показывать?

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

сценарий высосанный школьником из пальца для обоснования timer_list. IRL у proxy всегда есть таймеры более длительные чем таймаут на ответ - и они всегда будут в конце списка. И быстрые таймеры будут всегда об них спотыкаться

Может попробуете, чисто для разнообразия, не говорить за всех и реже употреблять слова «всегда»?

Не доверяете моему опыту, тогда, повторюсь, поинтересуйтесь, почему в том же ACE Framework одна из реализаций таймерных очередей — это тот самый timer_list.

О да!! деактивация и удаление это супер-критическая операция. Нить пользователя конечно-же может ждать непредсказуемое время взводя таймер, но удалять должна строго за O(1).

Деактивация — это такая же по важности операция, как и активация. Достигать оптимальности активации забивая на деактивацию... Оригинально, ничего не скажешь.

Но хотелось бы выслушать ваше мнение на счет наличия в STL четырех контейнеров, предоставляющих очень эффективные операции прохода от начала к концу контейнера и добавления элемента в конец контейнера: vector, list, deque, forward_list. Вас таки не смущает, что в STL есть четыре разных реализации, заточенных под разные сценарии использования? Или у Степанова лаба, видимо, называлась «контейнеры, оптимизированные к ...»?

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

Долго ты еще будешь нам тут свои поделки показывать?

Не помню, чтобы заставлял вас смотреть.

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

ваше мнение на счет наличия в STL четырех контейнеров, предоставляющих очень эффективные операции

вы сами ответили :-) там исторически вылизанная эффективная реализация, а у вас ТРИ куска нового тормозного непродуманного copy-past`ного г-на.

почему в том же ACE Framework одна из реализаций таймерных очередей — это тот самый timer_list

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

Деактивация — это такая же по важности операция, как и активация.

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

PS/ и не стоит так нервничать. Хочешь мы тут будем тебя и ЭТО только нахваливать??

Какое редкое, эпичное, развесистое говнецо. Экая глыба человеческого материала! Не всякий школьник, а тем более студент сможет такое произвести. Да ещё и не приходя в сознание!! Ну и что, что код медленный? Зато длинный! А как отформачено, откоменчено и отдокано? Надо-бы прикрепить тред..лучше сделать прямую ссылку из Develop..или даже отдельный,первый пункт главного меню - в назидание потомкам, пусть знают что copy-paste рулит, думать вредно, а алгоритмы для слабоков.

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

И чем вы будете защищаться от вытеснения текущей нити между одним сравнением и обменом двух указателей?

man CAS

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

вы сами ответили :-) там исторически вылизанная эффективная реализация, а у вас ТРИ куска нового тормозного непродуманного copy-past`ного г-на.

Молодой человек, ладно вы C++ код читать не умеете, так вы и по-русски не понимаете.

Еще раз:

Но хотелось бы выслушать ваше мнение на счет наличия в STL четырех контейнеров, предоставляющих очень эффективные операции прохода от начала к концу контейнера и добавления элемента в конец контейнера: vector, list, deque, forward_list. Вас таки не смущает, что в STL есть четыре разных реализации, заточенных под разные сценарии использования?

Почему при годами вылизанных реализациях есть ЧЕТЫРЕ разных типа контейнера?

Даю подсказку: кроме двух названных мной операций, есть еще несколько неназванных, как то: вставка в начало, изъятие из начала, вставка в середину, изъятие из середины, доступ по индексу, сортировка, изъятие группы элементов, добавление группы элементов (в конец, в начало, в произвольную позицию)...

Итак, вас в реализации STL ничего не смущает?

Ну а что до потоков говна, то свой уровень вы уже продемонстрировали. Можно было бы посоветовать вам поинтересоваться самыми распространенными схемами обслуживания таймеров (wheel, heap, hash, list), но ведь вы все равно не будете. Это же усилия прилагать нужно, а так х*як-х*як и очередной высер на форуме.

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

man CAS

А подумать?

Есть два указателя на структуры. Сравнивать нужно содержимое структур. А затем, в зависимости от результата, менять два указателя местами.

Вы все еще настаиваете на CAS-е для этого сценария?

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

а у вас ТРИ куска нового тормозного непродуманного copy-past`ного г-на.

Детский сад, ты даже не знаешь во что его реализация на самом деле упрется и умничаешь, строя из себя не пойми что. Если у тебя не совсем тяжелый случай, попробуй ускорить, причем достаточно ускорить его в два раза, ведь это ж «ТРИ куска нового тормозного непродуманного copy-past`ного г-на», будет совсем легко ;)

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

Вот пример, который надо ускорить (корявый, но пускабельный):

#include <iostream>
#include <cstdlib>

#include "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();
	
	int counter = 0;
	for( int i = 0 ; i < 1000000000 ; ++i )
	tt.activate( milliseconds( 100 ),
			[&counter](){ ++counter; } );

	while( counter != 1000000000 )
		this_thread::sleep_for( chrono::milliseconds( 100 ) );
	
	cout << counter << endl;
}
anonymous ()
Ответ на: комментарий от x_hash

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

Я думаю в общем виде? На тебе мою реальную задачу, из которой вытекает вышеуказаные постановки задач:

Есть прога, написанная в однопоточном стиле и отлично так работающая. Event loop сделан на ::WaitForMultipleObjects (да, винда). Источники событий - как правило разные виндовые примитивы синхронизации (EVENT, расшареные между процессами семафоры, пайпы, и т.д.). Надо в прогу добавить работу по сети (определенное кол-во сокетов). Как сделать это, используя boost::asio, но не делая лишний поток? Т.е. мне нужно решение одной из двух указанных мною выше задач. Однопоточность важна как писец, потому что недопустим ни гемор с синхронизацией потоков (уведомления, синхронизация данных) ни проседание производительности от переключения потоков (увеличение latency обработки событий).

===========

Если под «встроить свое событие в io_service», то, возможно, архитектура boost::asio не позволит это сделать.

Так в том то и дело. Есть у меня или виндовый HANDLE, или же юниксовый fd (пофиг, давай хоть для одной системы решим). Что делать? А нифига - нету такого в asio. Будет свободное время - накатаю им код.

io_service это и есть event-loop на событиях на файловых дескрипторах. Если твой event-loop работает, например, на условной переменной, то я не знаю, как их совместить.

Представь, что у меня fd, а не что-то другое. Зоопарк примитивов синхронизации в unix - отдельная тема для плача. Так вот, у меня есть мой event loop на epoll(), который крутит мои fd. Как мне интегрировать это с io_service? Да никак.

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

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

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

хотелось бы выслушать ваше мнение на счет наличия в STL

моё мнение про STL в своё время пришлось мучительно переводить на литературный английский, убирая междометия, чтобы в HP не сильно обиделись :-) В кратце - STL позволял быстро писать медленный код. (сейчас вроде как получше, но тогда было просто ужасно)

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

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

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

Это не у меня. Это у MKuznetsov идея фикс

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

Т.е. у него есть два указателя: new_timer и min_timer. Нужно сначала проверить (new_timer->m_when < min_timer->m_when). И если это так, то нужно поменять new_timer и min_timer местами. Для последнего действия достаточно atomic exchange. Но перед этим еще нужно будет сделать сравнение временных меток. Вот если между сравнением и atomic exchange нить будет вытеснена, то как он целостность своих данных без мутекса собирается обеспечивать?

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

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

Понятно. Хотя это и не ответ на мой вопрос.

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

Источники событий - как правило разные виндовые примитивы синхронизации (EVENT, расшареные между процессами семафоры, пайпы, и т.д.). Надо в прогу добавить работу по сети (определенное кол-во сокетов). Как сделать это, используя boost::asio, но не делая лишний поток?

Это конечно, злостный оффтопик, но если уже есть пайпы, то почему для работы с сокетами нужно boost::asio тянуть, а не работать напрямую с асинхронным вводом-выводом Win32?

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