Пользователь
20,9
рейтинг
21 января 2014 в 18:21

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

Не так давно в boost-1.53 появился целый новый раздел — lockfree реализующий неблокирующие очереди и стек.
Я последние несколько лет работал с так называемыми неблокируюшими алгоритмами (lock-free data structures), мы их сами писали, сами тестировали, сами использовали и втайне ими гордились. Естественно, у нас немедленно встал вопрос, переходить ли с самодельных библиотек на boost, и если переходить, то когда?
Вот тогда у меня и возникла в первый раз идея применить к 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 структуры данных, которые не требуют останавливать поток для синхронизации с другими потоками.
Вот об одной такой структуре и поговорим.

Первый подход к помосту

Я буду работать только с одной из структур — boost::lockfree::queue реализующей однонаправленную очередь с произвольным числом пишущих и читающих потоков. Эта структура существует в двух вариантах — аллоцирующем память по мере необходимости и имеющем бесконечную емкость, и вариант с фиксированным буфером. Строго говоря, они оба не являются неблокирующими, первый потому что системное выделение памяти не является lock-free, второй, потому что рано или поздно буфер переполнится и пишущие потоки будут вынуждены ждать неопределенное время пока не появится место для записи. Начнем с первого варианта, а ближе к концу я сравню с результатами для фиксированного буфера.
Добавлю еще что у меня 4-ядерная Linux Mint-15.
Возьмем код прямо отсюда и попробуем запустить, вот что получается:
boost::lockfree::queue is lockfree
produced 40000000 objects.
consumed 40000000 objects.

real	0m15.332s
user	1m0.376s
sys	0m0.064s


То есть, если подходить к делу по простому, около 400 нс на сообщение, вполне удовлетворительно. Эта реализация передает int и запускает по 4 читающих и пишущих потока.
Давайте чуть-чуть модифицируем код, я хочу запускать произвольное число потоков и еще я люблю видеть статистику. Какое будет распределение если запустить тест 100 раз подряд?


Вот, пожалуйста, выглядит вполне разумно. По оси X общее время исполнения в наносекундах деленное на число переданных сообщений, по оси Y — число таких событий.

А вот результат для разного числа писателей/читателей:


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

Второй подход к помосту

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

threads  : 1 write, 1 read
failed   : 0 pushes, 3267 pops
bandwidth: 177.864 ns
latency  : 1.03614e+08 ns

Мы теперь еще подсчитываем число неудачных попыток прочитать сообщение из очереди и записать в очередь (первое здесь конечно всегда будет равно нулю, это аллоцирующий вариант).
Однако это что еще такое? Задержка, которую мы интуитивно предполагали того же порядка — 200 нс, вдруг превышает 100 миллисекунд, в полмиллиона раз больше! Этого просто не может быть.
Но ведь мы теперь знаем задержку каждого сообщения, вот давйте и посмотрим как это выглядит в реальном времени, здесь приведены результаты нескольких идентичных запусков, чтобы было видно насколько случаен процесс:


это если у нас пишет и читает по одному потоку, а если по четыре то вот:


Что же происходит? В какой то произвольный момент часть читающих потоков отправляется системой отдохнуть. Очередь начинает стремительно расти, сообщения сидят в ней и ждут обработки. Через некоторое время ситуация меняется, число пишущих потоков становится меньше чем читающих и очередь потихоньку рассасывается. Такие колебания происходят с периодом от миллисекунд до секунд и очередь работает в пакетном режиме — миллион сообщений записали, миллион прочли. При этом быстродействие остается очень высоким, но каждое отдельное сообщение может провести в очереди несколько миллисекунд.
Что будем делать? Прежде всего задумаемся, тест в таком виде явно неадекватен. У нас половина активных потоков занята только тем что вставляет сообщения в очередь, такого просто не может случиться на реальной системе, иными словами тест устроен так что генерирует траффик заведомо провосходящий мощность машины.
Придется ограничить входной траффик, достаточно вставить usleep(0) после каждой записи в очередь. На моей машине это дает задержку 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;
}


Сергей Дегтярев @degs
карма
94,5
рейтинг 20,9
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (28)

  • +4
    Спасибо. Пара вопросов. Насколько лучше/хуже вели себя ваши реализации?
    Рекверстирую статью о том как ещё вы тестировали свои неблокирующие контейнеры.
    • +4
      На самом деле самодельные контейнеры я тестировал точно так же, только там еще три раза по столько тестов было на правильность и устойчивость самого алгоритма. Результаты были примерно такие же, по крайней мере того же порядка, пару раз мне удавалось увидеть в тестах намного лучшие результаты (~10 нс/сообщение), однако там стабильность самого алгоритма вызывала большие вопросы.
      Я вообще то считаю что именно вот эта достаточно узкая тема исчерпана. Дело в том что работающих алгоритмов единицы и они все хорошо известны. А вот сопутствующие вопросы, такие как эффективное управление потоками, поллинг неблокирующих структур, generic реализация, проблемы эффективного копирования обьектов — непаханное поле. Может быть когда нибудь.

  • +1
    CPU на занятых ядрах, я так понимаю, на 100% молотит?
    • +5
      Разумеется, это общепринятый в этой среде подход.
      Эх, чувствую я, следующий мой пост об этом будет.

      • +5
        Хочется увидеть сравнение с очередью на быстрых мьютексах (которые пытаются сначала сделать спинлоки, а затем уйти в ядро). Возможно, что такой подход будет не сильно медленнее lock-free подхода, а может и быстрее в данных тестах (кто знает?). Ну и хочется увидеть еще сравнение с wait-free single consumer/single producer.
        • +3
          Уже пишу :)
          Быстро не обещаю, но через несколько дней будет.
          В качестве анонса: да, под Intel/Linux обычные механизмы работают удивительно быстро. Я сейчас гоняю тесты и самому не верится, буду перепроверять.
          • +3
            Тут все дело в том, что ОС шедулер обладает информацией, кто кого ждет, и поэтому может подгонять, чтобы быстрее разбудить заснувший поток. По крайней мере на винде шедулер так старается делать. Поэтому может даже получиться быстрее, чем атомарные операции, т.к. там процессор молотит в холостую, а ось может вытеснить поток, который взял спинлок и зашедулить поток, который будет пытаться его взять. Но тут нужны тесты, чтобы делать какие-либо выводы.
            • 0
              Спасибо, не знал. По современным скедьюлерам вообще немного информации, я кажется читал что-то похожее, но с пометкой что это сделало бы сам скедьюлер слишком тяжелым и медленным.
              В любом случае постараюсь учесть и придумать какой нибудь адекватный тест. Вообще-то мне давно хотелось хотелось сделать планомерную серию тестов при разных scheduling policies, но тогда публикации придется ждать минимум месяц.
              • +3
                Здесь, кстати, изложены некоторые соображения: When are lock free data structures less performant than mutual exclusion (mutexes)?
                • +2
                  • 0
                    Вот это я постараюсь использовать. Только вот, они там измеряют общее время исполнения, слишком грубо и дает ответ не на тот вопрос который задавали. Мой то пунктик как раз в замере каждого сообщения и применении статистики.
                • 0
                  Да, но это к сожалению общие соображения, да и пример выбран очень грубый. Вот я собственно и пытаюсь подвести количественную базу под такие обсуждения.
          • 0
            А как насчёт Windows? Там с 8й версии тоже futex появился. Правда в отличие от Linux'а с shared memory не работает, но внутри программы должен давать возможность сделать почти такие же структуры как в Linux (некоторые экзотические операции, впрочем, будут медленнее).
            • 0
              Ну так я же специально выбрал boost::lockfree::queue для тестирования, она идет под все системы и платформы. Мне не на чем проверить, но я подозреваю что под Windows результаты будут очень близкие. Вот на чем бы я с удовольствием их погонял, это SPARC, там совершенно другая организация ядер и потоков. Наш последний SPARC сервер утилизовали к сожалению в прошлом году, проверить не на чем.
      • 0
        Я правильно понял, что вы проверяете latency на 100%-загруженном процессоре?
        • 0

          Точнее сказать что сам читающий поток занимает процессор на 100%, в системах сознательно использующих такой подход, на эту задачу ставят выделенный CPU.

  • 0
    По поводу последнего, например можно начать отсюда Reactive Spin-locks: A Self-tuning Approach, ну а вообще исследование структур данных для взаимодействия в многопоточной среде, без конкретика, в вакууме — совершенно бессмысленное занятие, тема громадная, решений миллион. Начинать надо с формализации требований к системе и платформе и уже от этого плясать.
  • 0
    Все-таки добавлять задержку в 50 мкс тоже не совсем корректно. Вы, фактически, разгрузили систему в 100 раз. В большинстве случаев, к тому моменту, когда на запись приходит сообщение, ваша очередь уже пуста. Но в таком режиме вообще не понятно, зачем использовать очередь, да еще и произвольной длины, когда можно диспетчеризорвать сообщение потребителю сразу же. Потому что свободные потребители всегда есть.
    • 0
      Речь как раз шла не о быстродействии и загрузке системы, а о мимимизации latency, задержки обработки каждого отдельного пакета. Простое быстродействие прекрасно обеспечивается собиранием сообщений в группы, вот там как раз неблокирующие алгоритмы не нужны. Попробуйте для контраста написать систему, которая получает всего лишь одно сообщение в час, но отреагировать должна за время <= 1 мкс, мало не покажется.
      Я как раз считаю что 50 мкс задержки мало, для абсолютно корректного исключения неких предполагаемых адаптивных алгоритмов ядра я бы использовал 100 миллисекунд минимум. У меня к сожалению терпения не хватает ждать завершения каждого теста несколько часов, на это только профессиональные исследователи на зарплате спосбны.
      • 0
        Вы все равно не получите гарантированное время меньше 1 мкс. Потому что планировщик вас всегда может притормозить. И уж точно в таком случае не нужно использовать многопоточность, от которой будут только накладные расходы
        • 0
          не нужно использовать многопоточность, от которой будут только накладные расходы
          — это немножко уж слишком чересчур кардинальный взгляд.
          Гарантированно получить 1 мкс конечно нельзя, можно гарантировать процент транзакций который произойдет быстрее 1 мкс. В этом и состоит количественный подход.
          • +1
            Нет, ну что значит — кардинальный:) Все зависит от характера нагрузки же.

            — Если время обработки сообщения заведомо меньше интервала между событиями, то многопоточность не нужна
            — Если время обработки сообщения в среднем значительно меньше интервала между событиями, то нужна очередь некого фиксированного размера
            — Если время обработки сообщения в среднем незначительно меньше интервала между событиями, то от сверхнизкой latency придется отказаться.
            — Если время обработки сообщения в среднем больше интервала между событиями, то все, приплыли.
            • 0
              — Если время обработки сообщения заведомо меньше интервала между событиями, то многопоточность не нужна

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

              — Если время обработки сообщения в среднем значительно меньше интервала между событиями, то нужна очередь некого фиксированного размера

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

              — Если время обработки сообщения в среднем больше интервала между событиями, то все, приплыли.

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

              • 0
                если «в среднем», то рано или поздно возникнет ситуация когда буфер переполнился и входной поток будет вынужден ждать
                Специально же написал значительно. В проитивном случае свой вариант есть. А если буфер переполнится, то ждать все равно придется. Хотя бы того же выделения памяти.
  • 0
    «Полная развязка входного и выходного потоков возможна лишь в аллоцирующем варианте, достигается это, однако, за счет неконтролируемого потребления памяти и неконтролируемо большой задержки.»
    А можно же попросить ОС дать читателю повыше приоритет, а писателю пониже? Возможно, чтобы какое-то ядро только и занималось разгребанием очереди.
    • 0
      Проблема в том что последний из потоков в цепочке обязательно завязан на внешнего потребителя, например пишет в сокет, и вот тут от нас уже ничего не зависит. Речь шла о том чтобы полностью развязать входной и выходной потоки, так чтобы при любых задержках в передаче выходных данных, входной поток об этом не знал и не беспокоился.
      Приоритет конечно поднять можно, но при принудительных блокировках потока, на write() например, это никак не поможет. К тому же приоритет приоритету рознь, если буду писать еще, я на этом обязательно остановлюсь.
  • 0
    Статья и впрямь замечательная, но было бы в намного лучше, если бы вы все же объяснили, что отложено по вертикальной шкале на графиках (по горизонтальной догадался — общее время выполнения программы).
  • 0
    Не совсем так, измерялось время обработки каждого сообщения отдельно, и по оси X отложено latency, время обработки одного сообщения. Соответственно, по оси Y отложено число таких событий, то есть число сообщений обработанных за данное время. Таким образом, все приведенные графики — гистограммы.

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