Comments 28
Спасибо. Пара вопросов. Насколько лучше/хуже вели себя ваши реализации?
Рекверстирую статью о том как ещё вы тестировали свои неблокирующие контейнеры.
Рекверстирую статью о том как ещё вы тестировали свои неблокирующие контейнеры.
+4
На самом деле самодельные контейнеры я тестировал точно так же, только там еще три раза по столько тестов было на правильность и устойчивость самого алгоритма. Результаты были примерно такие же, по крайней мере того же порядка, пару раз мне удавалось увидеть в тестах намного лучшие результаты (~10 нс/сообщение), однако там стабильность самого алгоритма вызывала большие вопросы.
Я вообще то считаю что именно вот эта достаточно узкая тема исчерпана. Дело в том что работающих алгоритмов единицы и они все хорошо известны. А вот сопутствующие вопросы, такие как эффективное управление потоками, поллинг неблокирующих структур, generic реализация, проблемы эффективного копирования обьектов — непаханное поле. Может быть когда нибудь.
Я вообще то считаю что именно вот эта достаточно узкая тема исчерпана. Дело в том что работающих алгоритмов единицы и они все хорошо известны. А вот сопутствующие вопросы, такие как эффективное управление потоками, поллинг неблокирующих структур, generic реализация, проблемы эффективного копирования обьектов — непаханное поле. Может быть когда нибудь.
+4
CPU на занятых ядрах, я так понимаю, на 100% молотит?
+1
Разумеется, это общепринятый в этой среде подход.
Эх, чувствую я, следующий мой пост об этом будет.
Эх, чувствую я, следующий мой пост об этом будет.
+5
Хочется увидеть сравнение с очередью на быстрых мьютексах (которые пытаются сначала сделать спинлоки, а затем уйти в ядро). Возможно, что такой подход будет не сильно медленнее lock-free подхода, а может и быстрее в данных тестах (кто знает?). Ну и хочется увидеть еще сравнение с wait-free single consumer/single producer.
+5
Уже пишу :)
Быстро не обещаю, но через несколько дней будет.
В качестве анонса: да, под Intel/Linux обычные механизмы работают удивительно быстро. Я сейчас гоняю тесты и самому не верится, буду перепроверять.
Быстро не обещаю, но через несколько дней будет.
В качестве анонса: да, под Intel/Linux обычные механизмы работают удивительно быстро. Я сейчас гоняю тесты и самому не верится, буду перепроверять.
+3
Тут все дело в том, что ОС шедулер обладает информацией, кто кого ждет, и поэтому может подгонять, чтобы быстрее разбудить заснувший поток. По крайней мере на винде шедулер так старается делать. Поэтому может даже получиться быстрее, чем атомарные операции, т.к. там процессор молотит в холостую, а ось может вытеснить поток, который взял спинлок и зашедулить поток, который будет пытаться его взять. Но тут нужны тесты, чтобы делать какие-либо выводы.
+3
Спасибо, не знал. По современным скедьюлерам вообще немного информации, я кажется читал что-то похожее, но с пометкой что это сделало бы сам скедьюлер слишком тяжелым и медленным.
В любом случае постараюсь учесть и придумать какой нибудь адекватный тест. Вообще-то мне давно хотелось хотелось сделать планомерную серию тестов при разных scheduling policies, но тогда публикации придется ждать минимум месяц.
В любом случае постараюсь учесть и придумать какой нибудь адекватный тест. Вообще-то мне давно хотелось хотелось сделать планомерную серию тестов при разных scheduling policies, но тогда публикации придется ждать минимум месяц.
0
Здесь, кстати, изложены некоторые соображения: When are lock free data structures less performant than mutual exclusion (mutexes)?
+3
Да, но это к сожалению общие соображения, да и пример выбран очень грубый. Вот я собственно и пытаюсь подвести количественную базу под такие обсуждения.
0
Ну так я же специально выбрал boost::lockfree::queue для тестирования, она идет под все системы и платформы. Мне не на чем проверить, но я подозреваю что под Windows результаты будут очень близкие. Вот на чем бы я с удовольствием их погонял, это SPARC, там совершенно другая организация ядер и потоков. Наш последний SPARC сервер утилизовали к сожалению в прошлом году, проверить не на чем.
0
Я правильно понял, что вы проверяете latency на 100%-загруженном процессоре?
0
По поводу последнего, например можно начать отсюда Reactive Spin-locks: A Self-tuning Approach, ну а вообще исследование структур данных для взаимодействия в многопоточной среде, без конкретика, в вакууме — совершенно бессмысленное занятие, тема громадная, решений миллион. Начинать надо с формализации требований к системе и платформе и уже от этого плясать.
0
Все-таки добавлять задержку в 50 мкс тоже не совсем корректно. Вы, фактически, разгрузили систему в 100 раз. В большинстве случаев, к тому моменту, когда на запись приходит сообщение, ваша очередь уже пуста. Но в таком режиме вообще не понятно, зачем использовать очередь, да еще и произвольной длины, когда можно диспетчеризорвать сообщение потребителю сразу же. Потому что свободные потребители всегда есть.
0
Речь как раз шла не о быстродействии и загрузке системы, а о мимимизации latency, задержки обработки каждого отдельного пакета. Простое быстродействие прекрасно обеспечивается собиранием сообщений в группы, вот там как раз неблокирующие алгоритмы не нужны. Попробуйте для контраста написать систему, которая получает всего лишь одно сообщение в час, но отреагировать должна за время <= 1 мкс, мало не покажется.
Я как раз считаю что 50 мкс задержки мало, для абсолютно корректного исключения неких предполагаемых адаптивных алгоритмов ядра я бы использовал 100 миллисекунд минимум. У меня к сожалению терпения не хватает ждать завершения каждого теста несколько часов, на это только профессиональные исследователи на зарплате спосбны.
Я как раз считаю что 50 мкс задержки мало, для абсолютно корректного исключения неких предполагаемых адаптивных алгоритмов ядра я бы использовал 100 миллисекунд минимум. У меня к сожалению терпения не хватает ждать завершения каждого теста несколько часов, на это только профессиональные исследователи на зарплате спосбны.
0
Вы все равно не получите гарантированное время меньше 1 мкс. Потому что планировщик вас всегда может притормозить. И уж точно в таком случае не нужно использовать многопоточность, от которой будут только накладные расходы
0
не нужно использовать многопоточность, от которой будут только накладные расходы— это немножко уж слишком чересчур кардинальный взгляд.
Гарантированно получить 1 мкс конечно нельзя, можно гарантировать процент транзакций который произойдет быстрее 1 мкс. В этом и состоит количественный подход.
0
Нет, ну что значит — кардинальный:) Все зависит от характера нагрузки же.
— Если время обработки сообщения заведомо меньше интервала между событиями, то многопоточность не нужна
— Если время обработки сообщения в среднем значительно меньше интервала между событиями, то нужна очередь некого фиксированного размера
— Если время обработки сообщения в среднем незначительно меньше интервала между событиями, то от сверхнизкой latency придется отказаться.
— Если время обработки сообщения в среднем больше интервала между событиями, то все, приплыли.
— Если время обработки сообщения заведомо меньше интервала между событиями, то многопоточность не нужна
— Если время обработки сообщения в среднем значительно меньше интервала между событиями, то нужна очередь некого фиксированного размера
— Если время обработки сообщения в среднем незначительно меньше интервала между событиями, то от сверхнизкой latency придется отказаться.
— Если время обработки сообщения в среднем больше интервала между событиями, то все, приплыли.
+1
— Если время обработки сообщения заведомо меньше интервала между событиями, то многопоточность не нужна
например несколько логически независимых потоков пишут в один выходной канал
— Если время обработки сообщения в среднем значительно меньше интервала между событиями, то нужна очередь некого фиксированного размера
если «в среднем», то рано или поздно возникнет ситуация когда буфер переполнился и входной поток будет вынужден ждать. А если он не может ждать?
— Если время обработки сообщения в среднем больше интервала между событиями, то все, приплыли.
естественно, однако в спецификацию очереди время обработки сообщения вообще не входит, по определению. Это задача пользовательского кода, обеспечить обработку, в частности за счет распараллеливания, для чего очередь и сделана многопоточной. В задачу библиотеки, какой эта структура является, входит условие внести как можно меньшую задержку при передаче, что мы и оцениваем.
0
«Полная развязка входного и выходного потоков возможна лишь в аллоцирующем варианте, достигается это, однако, за счет неконтролируемого потребления памяти и неконтролируемо большой задержки.»
А можно же попросить ОС дать читателю повыше приоритет, а писателю пониже? Возможно, чтобы какое-то ядро только и занималось разгребанием очереди.
А можно же попросить ОС дать читателю повыше приоритет, а писателю пониже? Возможно, чтобы какое-то ядро только и занималось разгребанием очереди.
0
Проблема в том что последний из потоков в цепочке обязательно завязан на внешнего потребителя, например пишет в сокет, и вот тут от нас уже ничего не зависит. Речь шла о том чтобы полностью развязать входной и выходной потоки, так чтобы при любых задержках в передаче выходных данных, входной поток об этом не знал и не беспокоился.
Приоритет конечно поднять можно, но при принудительных блокировках потока, на write() например, это никак не поможет. К тому же приоритет приоритету рознь, если буду писать еще, я на этом обязательно остановлюсь.
Приоритет конечно поднять можно, но при принудительных блокировках потока, на write() например, это никак не поможет. К тому же приоритет приоритету рознь, если буду писать еще, я на этом обязательно остановлюсь.
0
Статья и впрямь замечательная, но было бы в намного лучше, если бы вы все же объяснили, что отложено по вертикальной шкале на графиках (по горизонтальной догадался — общее время выполнения программы).
0
Не совсем так, измерялось время обработки каждого сообщения отдельно, и по оси X отложено latency, время обработки одного сообщения. Соответственно, по оси Y отложено число таких событий, то есть число сообщений обработанных за данное время. Таким образом, все приведенные графики — гистограммы.
0
Sign up to leave a comment.
Испытания boost::lockfree на скорость и задержку передачи сообщения