Комментарии 16
Было бы здорово добавить padding в очередь Димы Вьюкова и сравнить с Flat Combining Queue.
На счет меньшего проседания есть нюансы. Несомненно, судя по результатам мы видим что пропускная способность (throughput) снижается значительно медленней, но, из-за того что у нас теперь остальные потоки занимаются пассивным ожиданием, у них появляется дополнительный latency на ожидание.
При использовании spin-loop с CASами и добавлении полезной нагрузки можно получить меньший latency с сохранением уровня throughput. Так что тестируйте свои конкретные случаи. Flat Combining может работать медленней несмотря на результаты этих экспериментов.
Огромное спасибо за цикл статей, продолжайте в том же духе!
На счет меньшего проседания есть нюансы. Несомненно, судя по результатам мы видим что пропускная способность (throughput) снижается значительно медленней, но, из-за того что у нас теперь остальные потоки занимаются пассивным ожиданием, у них появляется дополнительный latency на ожидание.
При использовании spin-loop с CASами и добавлении полезной нагрузки можно получить меньший latency с сохранением уровня throughput. Так что тестируйте свои конкретные случаи. Flat Combining может работать медленней несмотря на результаты этих экспериментов.
Огромное спасибо за цикл статей, продолжайте в том же духе!
Полностью согласен. И спасибо за «огромное спасибо» :-)
Все о чем Вы пишете, правильно и относится к тонкой настройке алгоритма под конкретную задачу и даже под конкретное железо. Именно поэтому я не очень доверяю попугаям, в смысле, результатам тестирования, и отношусь к ним с известной долей скепсиса. В том числе и к своим замерам. И всех призываю именно так к ним и относится.
С другой стороны, надо как-то оценить алгоритм, и ничего лучше абстрактных синтетических тестов не придумаешь, когда нет конкретной задачи.
Насчет Flat Combining. Если заглянете ему под капот в libcds, Вы снегодованием удивлением обнаружите, что там для ожидающих потоков по умолчанию стоит back-off стратегия sleep(2ms). «Какой грязный хак!», — скажет искушенный читатель, и будет прав. Но именно этот sleep(2) обеспечил взлет перформанса Flat Combining по сравнению со spin-loop.
Все о чем Вы пишете, правильно и относится к тонкой настройке алгоритма под конкретную задачу и даже под конкретное железо. Именно поэтому я не очень доверяю попугаям, в смысле, результатам тестирования, и отношусь к ним с известной долей скепсиса. В том числе и к своим замерам. И всех призываю именно так к ним и относится.
С другой стороны, надо как-то оценить алгоритм, и ничего лучше абстрактных синтетических тестов не придумаешь, когда нет конкретной задачи.
Насчет Flat Combining. Если заглянете ему под капот в libcds, Вы с
Ну во первых не «взлет», а более «плавное пикирование» и то, пикирование пропускной способности. Латентность при этом только растёт:)
На деле нет никакого взлёта перфоманса, просто выбрали один из вариантов trade-off'а:)
На деле нет никакого взлёта перфоманса, просто выбрали один из вариантов trade-off'а:)
На моих тестах именно взлет, см. презентацию, там даны результаты как со spinlock, так и со sleep(2). Вполне допускаю, что для других задач результат может быть прямо противоположный.
Плюсы sleep(2):
— загрузка только одного ядра;
— больше вероятность провести аннигиляцию пар push()/pop() на пустой очереди (если elimination включена).
Плюсы sleep(2):
— загрузка только одного ядра;
— больше вероятность провести аннигиляцию пар push()/pop() на пустой очереди (если elimination включена).
Но есть минусы. Например, в случае если поток пытался сделать операцию с очередью, но у него не удалость стать «комбайном», то latency его операции может возрасти до 2ms. Если таких операций много, то и суммарное время будет большое. Более того, нить простаивает и не выполняет другую полезную работу.
И еще, допустим у меня есть поток, который так же что-то хочет сделать с очередью, и у него «получилось стать комбайном». И для того чтобы выйти из кода работы с очередью, мы должны выполнить пачку заданий, которые успели скопиться. Даже если изначальная задача была очень простой, итоговый latency может быть бОльшим нежели мы ожидаем.
Как в случае становления комбайном, так и в случае пассивного ожидания проблемы с latency могут быть серьезными.
На самом деле с такой back-off стратегией любая очередь не должна деградировать по throughput с ростом числа нитей.
Так что совсем не могу сказать что это очередь в чем-то лучше остальных по этим тестам. Хорошо бы сравнить очереди на одинаковых стратегиях back-off'а.
И еще, допустим у меня есть поток, который так же что-то хочет сделать с очередью, и у него «получилось стать комбайном». И для того чтобы выйти из кода работы с очередью, мы должны выполнить пачку заданий, которые успели скопиться. Даже если изначальная задача была очень простой, итоговый latency может быть бОльшим нежели мы ожидаем.
Как в случае становления комбайном, так и в случае пассивного ожидания проблемы с latency могут быть серьезными.
На самом деле с такой back-off стратегией любая очередь не должна деградировать по throughput с ростом числа нитей.
Так что совсем не могу сказать что это очередь в чем-то лучше остальных по этим тестам. Хорошо бы сравнить очереди на одинаковых стратегиях back-off'а.
И опять я полностью согласен! Найти оптимальную грань между задержками и пропускной способностью всегда не просто.
Flat Combining мне нравится именно тем, что там все перевернуто с ног на голову: вместо параллельного выполнения — откровенное делегирование своей работы другому потоку. Честно говоря, я не верил, что это может что-нибудь дать, — это диссонировало с моими взглядами. Но практика показала, что для некоторых задач метод может быть очень даже неплох. Видимо, мои тесты и относятся к этим задачам.
Flat Combining мне нравится именно тем, что там все перевернуто с ног на голову: вместо параллельного выполнения — откровенное делегирование своей работы другому потоку. Честно говоря, я не верил, что это может что-нибудь дать, — это диссонировало с моими взглядами. Но практика показала, что для некоторых задач метод может быть очень даже неплох. Видимо, мои тесты и относятся к этим задачам.
Хорошо бы сравнить очереди на одинаковых стратегиях back-off'а.
Действительно, хорошо бы. Займетесь?..
Никакой иронии, — я сам больше доверяю своим тестам, нежели чужим.
Спасибо за увлекательную статью.
Планируется ли враппер или порт на C для библиотеки libcds?
Мной — нет, Боже упаси!
Прошу воспринимать эту фразу как мое личное предпочтение
Прошу воспринимать эту фразу как мое личное предпочтение
Подумав немного, я даже не представляю, как на C сделать враппер над template-классом с, фактически, десятком template-параметров, каждый из которых может принимать несколько значений, в том числе user-defined, и все это — в compile time.
Добрый день!
Читаю вашу серию с самого начала, пока дошел до RCU, очень много полезной информации, чтобы усвоить ее нужно время. Спасибо за Ваш труд!
Попутно возник вопрос, а что Вы думаете про Thread Building Blocks от Intel? На первый взгляд выглядит замечательно просто.
Читаю вашу серию с самого начала, пока дошел до RCU, очень много полезной информации, чтобы усвоить ее нужно время. Спасибо за Ваш труд!
Попутно возник вопрос, а что Вы думаете про Thread Building Blocks от Intel? На первый взгляд выглядит замечательно просто.
День добрый!
Спасибо за отзыв, рад, что инфа оказалась полезна.
Про ThreadBuildingBlocks (TBB). Эта либа, безусловно, заслуживает внимания. В свое время она для меня была одним из источников информации о внутреннем устройстве atomic, когда C++11 ещё не было, а atomic только обсуждался. [далее мое ИМХО, я в TBB давно не заглядывал] А также она была для меня примером, как не надо делать конкурентные контейнеры. Дело в том, что в TBB довольно многие методы помечены как not thread safe. Что толку в контейнере, половина основных методов которого not thread safe?.. Разработчиков TBB можно понять — они стремятся сделать интерфейс как в STL. Но многие вещи из STL не могут быть сделаны в конкурентном контейнере.
Интересно, что только вчера наткнулся на Boost GSoC-2015: одно из заданий — concurrent map. И там написано (выделено мною):
Strangely enough, Boost does not provide an implementation of thread safe concurrent associative sets and maps despite that the unordered implementation from Intel's Thread Building Blocks and Microsoft's Parallel Patterns Library was proposed some years ago for standardisation in N3425 Concurrent Unordered Associative Containers for C++. This is probably because that implementation (the split ordered list algorithm by Shalev and Shavit, 2006) had the serious shortcoming of not being thread safe for some operations, most importantly item deletion, and the workarounds proposed by N3425 did not appeal. Moreover, there are other concurrent hash table algorithms which do not have such shortcomings
Хм… Конкурентный map с небезопасной функцией удаления элементов — это конкурентный map?.. Для безопасного удаления требуется применять HazardPointer, user-space RCU, transactional memory или что-то подобное, а в TBB, судя по этой ремарке, ничего этого нет…
В общем, у нас с TBB разные цели :-) TBB хочет адаптировать конкурентные контейнеры под STL, я в libcds хочу сделать конкурентный контейнер только с теми методами, которые можно поддержать в multithreading окружении, и посмотреть, достаточно ли будет такого интерфейса для повседневных задач.
Спасибо за отзыв, рад, что инфа оказалась полезна.
Про ThreadBuildingBlocks (TBB). Эта либа, безусловно, заслуживает внимания. В свое время она для меня была одним из источников информации о внутреннем устройстве atomic, когда C++11 ещё не было, а atomic только обсуждался. [далее мое ИМХО, я в TBB давно не заглядывал] А также она была для меня примером, как не надо делать конкурентные контейнеры. Дело в том, что в TBB довольно многие методы помечены как not thread safe. Что толку в контейнере, половина основных методов которого not thread safe?.. Разработчиков TBB можно понять — они стремятся сделать интерфейс как в STL. Но многие вещи из STL не могут быть сделаны в конкурентном контейнере.
Интересно, что только вчера наткнулся на Boost GSoC-2015: одно из заданий — concurrent map. И там написано (выделено мною):
Strangely enough, Boost does not provide an implementation of thread safe concurrent associative sets and maps despite that the unordered implementation from Intel's Thread Building Blocks and Microsoft's Parallel Patterns Library was proposed some years ago for standardisation in N3425 Concurrent Unordered Associative Containers for C++. This is probably because that implementation (the split ordered list algorithm by Shalev and Shavit, 2006) had the serious shortcoming of not being thread safe for some operations, most importantly item deletion, and the workarounds proposed by N3425 did not appeal. Moreover, there are other concurrent hash table algorithms which do not have such shortcomings
Хм… Конкурентный map с небезопасной функцией удаления элементов — это конкурентный map?.. Для безопасного удаления требуется применять HazardPointer, user-space RCU, transactional memory или что-то подобное, а в TBB, судя по этой ремарке, ничего этого нет…
В общем, у нас с TBB разные цели :-) TBB хочет адаптировать конкурентные контейнеры под STL, я в libcds хочу сделать конкурентный контейнер только с теми методами, которые можно поддержать в multithreading окружении, и посмотреть, достаточно ли будет такого интерфейса для повседневных задач.
Но в TBB есть и concurrent_hash_map, где erase потокобезопасен.
Действительно, есть.
Почему же тогда boost предлагает для GSoC-2015 задачу concurrent map? Думаю, причина в том, что concurrent_hash_map в TBB основан на fine-grained RW-locks. Беглый взгляд на реализацию показывает, что блокировка ведется на уровне buckets, похоже.
Это не критика TBB, ни в коем случае. Fine-grained lock алгоритмы не менее полезны, чем lock-free, и не менее интересны. Надо будет разобраться с внутренним устройством TBB concurrent_hash_map.
Почему же тогда boost предлагает для GSoC-2015 задачу concurrent map? Думаю, причина в том, что concurrent_hash_map в TBB основан на fine-grained RW-locks. Беглый взгляд на реализацию показывает, что блокировка ведется на уровне buckets, похоже.
Это не критика TBB, ни в коем случае. Fine-grained lock алгоритмы не менее полезны, чем lock-free, и не менее интересны. Надо будет разобраться с внутренним устройством TBB concurrent_hash_map.
Спасибо за развернутый ответ! Очень интересная информация! На самом деле долго думал — неужели нету надежной реализации такой популярной и очень полезное структуры как map.Получается, аналогов CDS толком-то и нету. Обязательно попробую вашу библиотеку для своего проекта.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Lock-free структуры данных. Диссекция очереди