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

[hoxnox]

Спасибо. Пара вопросов. Насколько лучше/хуже вели себя ваши реализации?
Рекверстирую статью о том как ещё вы тестировали свои неблокирующие контейнеры.

[degs]

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

[milo]

CPU на занятых ядрах, я так понимаю, на 100% молотит?

[degs]

Разумеется, это общепринятый в этой среде подход.
Эх, чувствую я, следующий мой пост об этом будет.

[gridem]

Хочется увидеть сравнение с очередью на быстрых мьютексах (которые пытаются сначала сделать спинлоки, а затем уйти в ядро). Возможно, что такой подход будет не сильно медленнее lock-free подхода, а может и быстрее в данных тестах (кто знает?). Ну и хочется увидеть еще сравнение с wait-free single consumer/single producer.

[degs]

Уже пишу :)
Быстро не обещаю, но через несколько дней будет.
В качестве анонса: да, под Intel/Linux обычные механизмы работают удивительно быстро. Я сейчас гоняю тесты и самому не верится, буду перепроверять.

[gridem]

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

[degs]

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

[gridem]

Здесь, кстати, изложены некоторые соображения: When are lock free data structures less performant than mutual exclusion (mutexes)?

[gridem]

И еще: Multi-threaded programming: efficiency of locking

[degs]

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

[degs]

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

[khim]

А как насчёт Windows? Там с 8й версии тоже futex появился. Правда в отличие от Linux'а с shared memory не работает, но внутри программы должен давать возможность сделать почти такие же структуры как в Linux (некоторые экзотические операции, впрочем, будут медленнее).

[degs]

Ну так я же специально выбрал boost::lockfree::queue для тестирования, она идет под все системы и платформы. Мне не на чем проверить, но я подозреваю что под Windows результаты будут очень близкие. Вот на чем бы я с удовольствием их погонял, это SPARC, там совершенно другая организация ядер и потоков. Наш последний SPARC сервер утилизовали к сожалению в прошлом году, проверить не на чем.

[23derevo]

Я правильно понял, что вы проверяете latency на 100%-загруженном процессоре?

[degs]

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

[HounD]

По поводу последнего, например можно начать отсюда Reactive Spin-locks: A Self-tuning Approach, ну а вообще исследование структур данных для взаимодействия в многопоточной среде, без конкретика, в вакууме — совершенно бессмысленное занятие, тема громадная, решений миллион. Начинать надо с формализации требований к системе и платформе и уже от этого плясать.

[Lol4t0]

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

[degs]

Речь как раз шла не о быстродействии и загрузке системы, а о мимимизации latency, задержки обработки каждого отдельного пакета. Простое быстродействие прекрасно обеспечивается собиранием сообщений в группы, вот там как раз неблокирующие алгоритмы не нужны. Попробуйте для контраста написать систему, которая получает всего лишь одно сообщение в час, но отреагировать должна за время <= 1 мкс, мало не покажется.
Я как раз считаю что 50 мкс задержки мало, для абсолютно корректного исключения неких предполагаемых адаптивных алгоритмов ядра я бы использовал 100 миллисекунд минимум. У меня к сожалению терпения не хватает ждать завершения каждого теста несколько часов, на это только профессиональные исследователи на зарплате спосбны.

[Lol4t0]

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

[degs]

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

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

[Lol4t0]

Нет, ну что значит — кардинальный:) Все зависит от характера нагрузки же.

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

[degs]

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

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

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

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

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

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

[Lol4t0]

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

Специально же написал значительно. В проитивном случае свой вариант есть. А если буфер переполнится, то ждать все равно придется. Хотя бы того же выделения памяти.

[agmt]

«Полная развязка входного и выходного потоков возможна лишь в аллоцирующем варианте, достигается это, однако, за счет неконтролируемого потребления памяти и неконтролируемо большой задержки.»
А можно же попросить ОС дать читателю повыше приоритет, а писателю пониже? Возможно, чтобы какое-то ядро только и занималось разгребанием очереди.

[degs]

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

[Mingun]

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

[degs]

Не совсем так, измерялось время обработки каждого сообщения отдельно, и по оси X отложено latency, время обработки одного сообщения. Соответственно, по оси Y отложено число таких событий, то есть число сообщений обработанных за данное время. Таким образом, все приведенные графики — гистограммы.