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