Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Испытания boost::lockfree на скорость и задержку передачи сообщения

Anna | 24.06.2014 | нет комментариев
Не так давным-давно в boost-1.53 возник целый новейший раздел — lockfree реализующий неблокирующие очереди и стек.
Я последние несколько лет работал с так называемыми неблокируюшими алгорифмами (lock-free data structures), мы их сами писали, сами тестировали, сами применяли и втайне ими гордились. Безусловно, у нас незамедлительно встал вопрос, переходить ли с самодельных библиотек на boost, и если переходить, то когда?
Вот тогда у меня и появилась в 1-й раз идея применить к boost::lockfree кое-какие из методологий которыми мы испытывали личный код. К счастью, сам алгорифм нам тестировать не придется и дозволено сосредоточиться на измерении продуктивности.
Я постараюсь сделать статью увлекательной для всех. Тем кто еще не сталкивался с сходственными задачами будет благотворно посмотреть на то что такие алгорифмы способны, а основное, где и как их стоит либо не стоит применять. Для тех кто имеет навык разработки неблокирующих очередей допустимо будет увлекательно сравнить данные количественных измерений. Я сам по крайней мере таких публикаций еще не видел.

Введение: что такое неблокирующие конструкции данных и алгорифмы

В нынешнее программирование крепко вошло представление многопоточности, впрочем работа с потоками немыслима без средств синхронизации, так возникли mutex, semaphore, condition variable и их последующие потомки. Впрочем первые типовые функции были довольно тяжелыми и неторопливыми, больше того, они были реализованы внутри ядра, то есть требовали контекстного переключения на всякий вызов. Время перключения слабо зависит от CPU, следственно чем стремительней становились процессоры, тем огромнее относительного времени требовалось на синхронизацию потоков. Тогда возникла идея, что при минимальной аппаратной поддержке дозволено было бы сделать конструкции данных инвариантные при одновременной работе с несколькими потоками. Тем кто хотел бы об этом подробнее, рекомендую вот эту серию публикаций.
Основные алгорифмы были разработаны и положены в длинный ящик, их время тогда еще не пришло. Вторую жизнь они получили когда представление времени обработки сообщения (latency) стало чуть ли не больше значимым чем привычная скорость CPU. О чем вообще речь?

Вот примитивный пример:

Пускай у меня есть некоторый сервер тот, что получает сообщения, обрабатывет и посылает результат. Представим что мне пришло 1 миллион сообщений и сервер совладал с ними за 2 секунды, то есть по 2 мкс на транзакцию и меня это устраивает. Как раз это и именуется быстродействием (bandwidth) и не является правильной мерой при обработке сообщений. Позднее я с изумлением узнаю что всякий приславшинй мне сообщение заказчик получил результат не ранее чем через 1 секунду, что их не устраивает абсолютно. В чем дело? Один из допустимых сценариев: сервер стремительно получает все сообщения и складывает их в буфер; потом обрабатывает их параллельно, тратя на всякое 1 секунду, но поспевает обработать все совместно каждого лишь за 2 секунды; и стремительно посылает обратно. Это пример отличной скорости системы в целом и в то же время недопустимо огромный latency.

Подробнее дозволено прочитать в изложении интервью Herb Sutter, он немножко в ином контексте, но дюже темпераментно обговаривает эту задачу. Подсознательно кажется что представления быстродействия и latency одинаковы — чем огромнее первое, тем поменьше второе. При детальном рассмотрении оказывается, впрочем, что они само­стоятельны и даже антикоррелированы.
Какое это имеет отношение к неблокирующим конструкциям? Самое прямое, дело в том, что для latency любая попытка притормозить либо остановить поток губительна. Усыпить поток легко, но разбудить его немыслимо. Его может разбудить ласковым поцелуем только ядро операционной системы, а оно это делает сурово по расписанию и с перерывами на обед. Испробуйте обьяснить кому нибудь, что ваша программа, которая обязалась по тех. заданию реагировать в течении 200 наносекунд, в данный момент уснула на 10 миллисекунд(нормальное время для *nix систем) и ее отменнее не тревожить. На поддержка приходят lock-free конструкции данных, которые не требуют останавливать поток для синхронизации с другими потоками.
Вот об одной такой структуре и побеседуем.

ле всякой записи в очередь. На моей машине это дает задержку 50 мкс с отличной точностью. Посмотрим:


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

Вот итог для нескольких комбинаций числа пишущих и читающих потоков, для сохранения приемлемого масштаба по X, 1% самых крупных отсчетов отброшен:

Обратите внимание что latency уверенно остается в пределах 300 нс и только хвост разделения вытягивается все дальше.

А вот итоги для одного и четырех пишуших потоков соответственно.


Тут значительное увеличение задержки налицо, в основном за счет резкого роста хвоста. Вновь мы видим что четыре (== CPU) потока которые безостановочно молотят вхолостую вырабатывая свой квант времени, что порождает огромное число неконтролируемых притормаживаний. Правда средняя задержка уверенно остается в пределах 600 нс, для некоторых задач это теснее на грани возможного, скажем если у вас ТЗ Отчетливо оговаривающее что 99.9% сообщений обязаны быть доставлены за определенное время (у меня такое случалось).
Обратите также внимание, насколько подросло всеобщее время исполнения, раз в 150. Это демонстрация заявления кототое я делал в самом начале — минимальная latency и наивысшее быстродействие единовременно не достигаются. Эдакий неповторимый правило неопределенности.

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

А что насчет fixed capacity queue?

fixed capacity — иной вариант boost::lockfree::queue построенный на внутреннем буфере жестко заданного размера. С одной стороны это разрешает избежать обращения к системному аллокатору, с иной, если буфер заполнится, пишущему потоку тоже придется ожидать. Для некоторых типов задач это абсолютно исключено.
Тут будем трудиться по тому же способу. Вначале, обученные навыком, посмотрим динамику задержек:


Алый график соответствыет используемому в примере из boost 128 байт, зеленый — максимально допустимому 65534 байт.

Кстати

В документации сказано что наивысший размер — 65535 байт — не верьте, получите core dump

Исскуственную задержку мы не вставляли, следственно безусловно что очередь работает в пакетном режиме, заполняется и освобождается крупными долями. Впрочем фиксированная емкость буфера вносит некоторый порядок и отлично видно что среднее для задержки по крайней мере существует. Еще один непредвиденныйдля любителей больших буферов итог в том, что размер буфера не влияет никак на всеобщую скорость выполнения. То есть если вас устраивет latency в 32 мкс (что кстати абсолютно довольно для многих приложений) дозволено применять fixed_capacity lockfree::queue с крошечным применением памяти получив впридачу восхитительную скорость.
Но тем не менее, давайте оценим как данный вариант ведет себя в многопоточной программе:


немножко невзначай было увидеть такое Отчетливое распределение на две группы, там где скорость читателей превосходит скорость писателей мы получаем наши желанные сотни наносекунд, там где напротив — прыжком растет до 30-40 микросекунд, схоже это время переключения контекста на моей машине. Это итог для 128-байтового буфера, дле 64К выглядит дюже схоже, только правая группа уползает вдалеке-вдалеке, на десятки миллисекунд.
Отлично это либо нехорошо? Зависит от задачи, с одной стороны мы можем уверенно гарантировать что задержка никогда не превысит 40 мкс при всяких условиях, и это отлично; с иной, если нам требуетсягарантировать некоторую максимальную задержку поменьше этого значения, то нам придется трудно. Всякое метаморфоза равновесия читателей/писателей, скажем из за незначительного метаморфозы обработки сообщений, может привести к скачкообразному метаморфозы задержки.

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


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

Пора переходить к завершению

Я верю что те кто имеет навык сумеют извлечь что-то пригодное сами из итогов тестов. Вот что думаю я сам:

  • Если вас волнует лишь быстродействие, все варианты приблизительно равнозначны и дают среднее время порядка сотен наносекунд на сообщение. При этом fixed_capacity очередь является больше легковесной, от того что занимает фиксированный обьем памяти. Бывают впрочем приложения, логгер скажем, где скептически значимо как дозволено стремительней «освободить» читающий поток, в таком случае аллоцируюшая очередь подходит отменнее, с иной стороны она может потреблять память безгранично.
  • Если требуется минимизация latency, времени обработки всякого сообщения в отдельности, обстановка осложняется. Для приложений где требуется не блокировать пишущий поток (логгеры) безоговорочно стоит предпочесть аллоцирующий вариант. Для случая ограниченной памяти однозначно подходит fixed_capacity, размеры буфера придется подобрать исходя из статистики сигнала.
  • В любом случае алгорифм неустойчив касательно интенсивности потока данных. При превышении некоторого скептического порога задержка прыжком повышается на несколько порядков и очредь реально (но не официально) становится блокирующей. Как правило требуется тонкая настройка Дабы принудить систему трудиться не сваливаясь в блокируюший режим.
  • Полная развязка входного и выходного потоков допустима лишь в аллоцирующем варианте, достигается это, впрочем, за счет неконтролируемого потребления памяти и неконтролируемо огромный задержки.
  • Fixed_capacity разрешает добиться стремительной передачи данных единовременно ограничивая махимальную latency некоторым умным пределом. Сама fixed_capacity очередь является по сути дюже легковесной конструкцией. Основной минус — пишущие потоки блокируются если читаюшие не справляются либо зависают по всякий причине. Крупные размеры буфера, на мой взор, необходимы довольно редко, они разрешают добиться переходной динамики, что-то приближающееся к аллоцируюшей очереди.
  • Дюже неприятным для меня сюрпризом оказалось то, какое огромное отрицательное воздействие оказывают постоянно работаюшие вхолостую читающие потоки на динамику. Даже в случае когда всеобщее число потоков <= CPU, добавление еще одного потребляющего 100% потока не улучшает, а ухудшает динамику. Схоже тактика «крупных серверов», когда всякому главному потоку присваевается отдельное ядро, работает вдалеке не неизменно.
  • В связи с этим, одна не упомянутая и до сих пор не решенная задача — как результативно применять поток ждущий какого либо события. Если его усыплять — карма latency портится неизбежно, если применять для других задач — появляется задача стремительного переключения с задачи на задачу. Я думаю недурным приближением к идеалу было бы дать вероятность добавлять читающий поток в boost::io_service, так Дабы результативно обслуживать правда бы редчайшие события. Был бы рад услышать если у кого нибудь есть идеи.

Для тех кому нужно – код

#include <boost/thread/thread.hpp>
#include <boost/lockfree/queue.hpp>
#include <time.h>
#include <atomic>
#include <iostream>

std::atomic<int> producer_count(0);
std::atomic<int> consumer_count(0);
std::atomic<unsigned long> push_fail_count(0);
std::atomic<unsigned long> pop_fail_count(0);

#if 1
boost::lockfree::queue<timespec, boost::lockfree::fixed_sized<true>> queue(65534);
#else
boost::lockfree::queue<timespec, boost::lockfree::fixed_sized<false>> queue(128);
#endif

unsigned stat_size=0, delay=0;
std::atomic<unsigned long>* stat=0;
std::atomic<int> idx(0);

void producer(unsigned iterations)
{
	timespec t;
    for (int i=0; i != iterations;   i) {
          producer_count;
        clock_gettime(CLOCK_MONOTONIC, &t);
        while (!queue.push(t))
              push_fail_count;
		if(delay) usleep(0);
    }
}

boost::atomic<bool> done (false);
void consumer(unsigned iterations)
{
    timespec t, v;
    while (!done) {
        while (queue.pop(t)) {
              consumer_count;
        	clock_gettime(CLOCK_MONOTONIC, &v);
			unsigned i=idx  ;
			v.tv_sec-=t.tv_sec;
			v.tv_nsec-=t.tv_nsec;
			stat[i]=v.tv_sec*1000000000 v.tv_nsec;
		}
		  pop_fail_count;
    }

    while (queue.pop(t)) {
              consumer_count;
        	clock_gettime(CLOCK_MONOTONIC, &v);
			unsigned i=idx  ;
			v.tv_sec-=t.tv_sec;
			v.tv_nsec-=t.tv_nsec;
			stat[i]=v.tv_sec*1000000000 v.tv_nsec;
	}
}

int main(int argc, char* argv[])
{
    boost::thread_group producer_threads, consumer_threads;
	int indexed=0, quiet=0;
	int producer_thread=1, consumer_thread=1;
	int opt;
	while((opt=getopt(argc,argv,"idqr:w:")) !=-1)
	switch(opt) {
		case 'r': consumer_thread=atol(optarg); break;
		case 'w': producer_thread=atol(optarg); break;
		case 'd': delay=1; break;
		case 'i': indexed=1; break;
		case 'q': quiet=1; break;
		default : return 1;
	}
	int iterations=6000000/producer_thread/consumer_thread;
	unsigned stat_size=iterations*producer_thread*consumer_thread;
	stat=new std::atomic<unsigned long>[stat_size];

	timespec st, fn;
	clock_gettime(CLOCK_MONOTONIC, &st);

    for (int i=0; i != producer_thread;   i)
        producer_threads.create_thread([=](){ producer(stat_size/producer_thread); });
    for (int i=0; i != consumer_thread;   i)
        consumer_threads.create_thread([=]() { consumer(stat_size/consumer_thread); });

    producer_threads.join_all();
    done=true;
    consumer_threads.join_all();
	clock_gettime(CLOCK_MONOTONIC, &fn);

	std::cerr << "threads  : " << producer_thread <<" write, " 
			  << consumer_thread << " read" << std::endl;
	std::cerr << "failed   : " << push_fail_count << " pushes, "
			  << pop_fail_count  << " pops" << std::endl;
	fn.tv_sec-=st.tv_sec;
	fn.tv_nsec-=st.tv_nsec;
	std::cerr << "bandwidth: " << (fn.tv_sec*1e9 fn.tv_nsec)/stat_size << " ns"<< std::endl;

	double ct=0;
	for(auto i=0; i < stat_size;   i)
		ct =stat[i];
	std::cerr << "latency  : "<< ct/stat_size << " ns"<< std::endl;

	if(!quiet) {
		if(indexed) for(auto i=0; i < stat_size;   i)
			std::cout<<i<<" "<<stat[i]<<std::endl;
		else for(auto i=0; i < stat_size;   i)
			std::cout<<stat[i]<<std::endl;
	}

	return 0;
}

 

Источник: programmingmaster.ru

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля помечены (обязательно)

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2014 © BB3x.ru - русская поддержка форума phpBB