Comments 44
Спасибо, это интересно.
В чём диаграммки делали?
В чём диаграммки делали?
Да, это была целая история…
Одно барахло везде попадалось. В итоге, поставили DataScene
Одно барахло везде попадалось. В итоге, поставили DataScene
Спасибо. Пара замечаний:
1. Похоже, вы забыли голову (m_stack_head) выровнять.
2. Если тело функции внутри объявления класса идет, такие функции по умолчанию считаются inline. C++STD 2012, 7.1.2: A function defined within a class definition is an inline function.
1. Похоже, вы забыли голову (m_stack_head) выровнять.
2. Если тело функции внутри объявления класса идет, такие функции по умолчанию считаются inline. C++STD 2012, 7.1.2: A function defined within a class definition is an inline function.
А как связано наличие 128bit CAS и Windows 8? В x86_64 всегда вроде инструкция CMPXCHG16B была… Берется да вызывается.
Было бы странно, если бы в продуктам M$ не встречалось удачных кусков. У них задача даже проще, чем у разработчиков кроссплатформенных продуктов, которым нужно учитывать особенности всех поддерживаемых систем, т.к. разрабатывают под вполне известное окружение с некоторой долей разнообразия (версии Windows в смысле).
Кстати, отличный момент для доказательства себе своей крутости :) Просто приготовь патч для OpenSource продуктов! и попробуй пропихнуть его в основное дерево
Кстати, отличный момент для доказательства себе своей крутости :) Просто приготовь патч для OpenSource продуктов! и попробуй пропихнуть его в основное дерево
В проектах с хорошим governance — это довольно просто. Например, в openstack есть чёткая процедура как из «постороннего человека» оказаться в самой мякотке. На всю бюрократию надо минут 15-20, ещё примерно пол-часа час на изучение git review и других фрагментов gerrit'а. После этого можно предлагать блюпринты, писать патчи, фиксить баги и т.д. И оно войдёт в проект правильно, с автоматическим гигантским тестированием, проверкой совместимости с кодом разных вендоров и разных конфигураций, и без каких-либо «ну я тут покодил вот мой патч как он там у вас будет я не знаю, но примите пожалуйста».
Не могу не заметить, что «продукты MS» и «кроссплатформенные продукты» — это несколько пересекающиеся множества. Особенно в последнее время.
Часто проблемы с переносом на Windows бывают, например, c pthread. Хотя есть пару реализаций под WinAPI, но выглядят они как-то не очень.
А так, некоторые вещи из posix поддерживаются в VS SDK, поэтомумалая часть проблем с переносом уходит. Вот здесь у них, например, гид по переносу на Win32
А вообще, то что называется кросс-платформенным решением часто не является таковым в полной мере, потому что именно Windows и не поддерживается… И не потому что это невозможно портировать. Так что, скорее, это правильно называть кросс-nix-овые продукты.
А вот многие вещи от Гугла или тот же SQLite, как раз, в большей степени кросс-платформенные: собираются на чём хочешь.
А так, некоторые вещи из posix поддерживаются в VS SDK, поэтому
А вообще, то что называется кросс-платформенным решением часто не является таковым в полной мере, потому что именно Windows и не поддерживается… И не потому что это невозможно портировать. Так что, скорее, это правильно называть кросс-nix-овые продукты.
А вот многие вещи от Гугла или тот же SQLite, как раз, в большей степени кросс-платформенные: собираются на чём хочешь.
Не совсем понятно, зачем дожидаться, пока продьюсеры закончат свою работу? Как раз интересно посмотреть в сценарии, когда молотят одновременно и продьюсеры, и консьюмеры, т.е. когда конкурентность одновременно и на push, и на pop операциях. Именно такие сценарии представляют наибольший интерес, т.к. они встречаются наиболее часто в реальности.
Нужен критерий остановки для потребителей. Само по себе отсутствие заданий в стеке не означает, что их больше не будет, т.к. вероятно какие-то производители просто запаздывают и положат задания позднее. Поэтому сначала мы ждем пока все производители отработают и до тех пор честно пробуем найти еще задания в стеке, а вот когда они закончили работу, тогда пустой стек можно считать концом.
Критерий очень простой: локальный счетчик количества извлеченных элементов ==iterations (в случае, когда n_producers == n_consumers). Более того, приведенный тест не гарантирует, что все элементы будут извлечены: возможно ситуация, когда евент сработал, и элементов к тому времени уже нет.
Если возникает «ситуация, когда евент сработал, и элементов к тому времени уже нет.», то ничего страшного не будет — это значит, что consumer-ы уже всё разобрали и условие во втором цикле consumer «while (stack.pop(value))» нас тут же выбросит на конец потока. На самом деле, это как раз неплохой сценарий: в том смысле что consumer-ы быстро справились и не надо чистить
Кажется, что предложенный вами критерий «локальный счетчик количества извлеченных элементов ==iterations» насильственно закрепощает потоки потребители обрабатывать ровно столько заданий, сколько вбросил побратим-производитель в случае p=c, а если p!=c, то это вообще неверно. Так выходит?
И, кроме того, дело-то в том, что исходно обсчитывался квадрат {p X c}, где p почти везде не равно c, так что случай p=c, как бы вырожденный.
И, кроме того, дело-то в том, что исходно обсчитывался квадрат {p X c}, где p почти везде не равно c, так что случай p=c, как бы вырожденный.
Ну вот количество итераций для продьюсера вас не смущают, а вот для консьюмера внезапно стало смущать. Не очень понятно.
Ну и проблема в вырожденности легко снимается, когда количество итераций для консьюмера = iterations * n_producers / n_consumers (можно сделать, чтобы всегда делилось нацело без остатка, но это не важно).
Ну и проблема в вырожденности легко снимается, когда количество итераций для консьюмера = iterations * n_producers / n_consumers (можно сделать, чтобы всегда делилось нацело без остатка, но это не важно).
Тогда каждый поток должен знать об общем количестве потоков каждого типа, значит ему это нужно давать в аргументе. Это меняет структуру организации worker потоков. Лучше ли это?
И главное для чего? Избежать 1 Wait-а на поток? Общее заданий >>>> числа потоков и один wait на поток ничего не стоит, потому что мы можем потерять на нём 1 раз 10 мс, и то без нагрузки на CPU — это же не sleep…
И главное для чего? Избежать 1 Wait-а на поток? Общее заданий >>>> числа потоков и один wait на поток ничего не стоит, потому что мы можем потерять на нём 1 раз 10 мс, и то без нагрузки на CPU — это же не sleep…
Как я указывал выше, цель — чтобы продьюсеры и консьюмеры работали параллельно. Здесь же в тестах они работают последовательно, сначала отрабатывают продьюсеры, а потом — консьюмеры. Т.е. нет замеров именно конкурентного доступа к данным, когда есть и те и другие. Конечно, частично они будут пересекаться, но непонятно насколько частично и как это сказывается на производительности. Поэтому хотелось бы видеть одновременное действие producers/consumers в разных пропорциях.
Это совсем не верно. Посмотрите, пожалуйста, на код функции run_test.
1. Стартуют все производители и начинают накидывать задания
2. Стартуют все потребители и уже начинают потреблять задания
3. Ждем окончания работы производителей
4. Ждем окончания работы работы потребителей
Задержка между (1) и (2) только на время запуска (!) потоков, но никак не их работу. Лучше бы было только стартовать каждый из типов попеременно, но это не даст никакой заметной разницы.
1. Стартуют все производители и начинают накидывать задания
2. Стартуют все потребители и уже начинают потреблять задания
3. Ждем окончания работы производителей
4. Ждем окончания работы работы потребителей
Задержка между (1) и (2) только на время запуска (!) потоков, но никак не их работу. Лучше бы было только стартовать каждый из типов попеременно, но это не даст никакой заметной разницы.
Не совсем так. Потребители во втором пункте, конечно, стартуют, но вторая часть этого пункта не совсем корректна. Они начинают потреблять только после того, как пройдет 10 мс, либо после того, как выполнится 3-я часть. При этом мне неочевидно, что пересечение между началом работы потребления и началом реальной работы производителей является существенным вкладом в общее время работы. Возможно, я чего-то упустил.
А, вот, насчет 10 мс рассогласования на старте вы совершенно правы, и об этом мы написали чуть выше. Можно было бы избежать этого, например, изменив внешний цикл на do-while, чтобы потребители сразу пробовали брать задания.
Однако, этот фрагмент кода, касается лишь самого теста. Нигде в тексте статьи мы не апеллируем к абсолютным числам по тестам. Проводится лишь сравнение реализаций. А поскольку каждый из 3(4) тестов имеет эти 10 мс, и время работы 1 теста составляет ~10-40 секунд, то они в этом плане абсолютно сравнимы и отмена 10мс не изменит соотношения.
Однако, этот фрагмент кода, касается лишь самого теста. Нигде в тексте статьи мы не апеллируем к абсолютным числам по тестам. Проводится лишь сравнение реализаций. А поскольку каждый из 3(4) тестов имеет эти 10 мс, и время работы 1 теста составляет ~10-40 секунд, то они в этом плане абсолютно сравнимы и отмена 10мс не изменит соотношения.
Спасибо, интересно.
А нельзя ли для масштаба добавить к трём lock-free стэкам ещё и простейший стэк с блокировкой (CriticalSection или mutex)?
А нельзя ли для масштаба добавить к трём lock-free стэкам ещё и простейший стэк с блокировкой (CriticalSection или mutex)?
Ответ добавили в конец статьи.
Спасибо
Судя по графику, на 2 и 4 потоках mutex обгоняет?
Вроде бы нет… вот результаты в сыром виде (но надо иметь в виду, что было только по 100К заданий и один проход, так что числа грубые):
Сырые числа
mutex 2 2 937
mutex 2 4 1250
mutex 2 8 43203
mutex 2 16 42421
mutex 2 32 36796
mutex 2 64 42812
mutex 4 2 1250
mutex 4 4 1523
mutex 4 8 43046
mutex 4 16 24921
mutex 4 32 38984
mutex 4 64 33789
mutex 8 2 41757
mutex 8 4 43125
mutex 8 8 74589
mutex 8 16 84453
mutex 8 32 82656
mutex 8 64 84746
mutex 16 2 42177
mutex 16 4 42333
mutex 16 8 82900
mutex 16 16 84736
mutex 16 32 85175
mutex 16 64 85458
mutex 32 2 43120
mutex 32 4 43554
mutex 32 8 85083
mutex 32 16 84453
mutex 32 32 84531
mutex 32 64 85634
mutex 64 2 43215
mutex 64 4 43437
mutex 64 8 84768
mutex 64 16 85146
mutex 64 32 85366
mutex 64 64 85651
Мьютекс имеет смысл использовать только в случае небольшого числа потоков. Поэтому было бы интересно увидеть сравнительный график вблизи единицы, скажем 1, 2, 4. Результат может удивить.
Спасибо за хорошую статью и проведенную работу по сравнительному анализу! Независимые данные всегда особо ценны, в том числе и критика. Как автор libcds, постараюсь в одной из следующих статей своего эпического цикла объяснить, как появился интерфейс контейнеров в libcds, — это может быть интересно. Быть может, хабрасообщество подскажет более красивое решение тех проблем, с которыми я столкнулся при разработке библиотеки.
По поводу майкрософтовского SList. Я несколько лет назад где-то на просторах сети находил внутреннее устройство, — довольно интересно: если мне не изменяет память, они борются с ABA-проблемой с помощью SEH (structured exception handling). Грубо говоря, если получаем SEGFAULT, аккуратно обрабатываем его на очень низком уовне. К сожалению, пруф я сейчас найти не смог.
И по поводу Microsoft вообще, присоединюсь, покидаю на вентилятор: я считаю, что существование Windows — это большая удача для кросс-платформенных разработчиков, ибо ставит нетривиальные задачи по обобщению *nix и Windows подхода при кросс-платформенной разработке. Да, колемся, плачем, но продолжаем решать нестандартные задачи по унификации столь разных API столь разных операционных систем и компиляторов
По поводу майкрософтовского SList. Я несколько лет назад где-то на просторах сети находил внутреннее устройство, — довольно интересно: если мне не изменяет память, они борются с ABA-проблемой с помощью SEH (structured exception handling). Грубо говоря, если получаем SEGFAULT, аккуратно обрабатываем его на очень низком уовне. К сожалению, пруф я сейчас найти не смог.
И по поводу Microsoft вообще, присоединюсь, покидаю на вентилятор: я считаю, что существование Windows — это большая удача для кросс-платформенных разработчиков, ибо ставит нетривиальные задачи по обобщению *nix и Windows подхода при кросс-платформенной разработке. Да, колемся, плачем, но продолжаем решать нестандартные задачи по унификации столь разных API столь разных операционных систем и компиляторов
Да, чуда не произошло.
Я тут вечерком протестировал приведенную реализацию на предмет ABA проблемы, и оказалось, что она таки присутствует. Чтобы в этом убедиться, достаточно переписать тест на использование в качестве T=std::function<void()>, на push операцию добавлять []{}, на pop: вызывать соответствующий функтор. Практически сразу программа падает, что говорит о том, что имеется серьезная проблема, которая как раз и связана с ABA при удалении ресурса. Внутри реализации используется 8-байтовый CAS (на x86 архитектуре), который просто не в состоянии решить проблему корректного удаления объекта. Увы.
Не ожидал такого подвоха в библиотечной функции от Microsoft, честно говоря.
Я тут вечерком протестировал приведенную реализацию на предмет ABA проблемы, и оказалось, что она таки присутствует. Чтобы в этом убедиться, достаточно переписать тест на использование в качестве T=std::function<void()>, на push операцию добавлять []{}, на pop: вызывать соответствующий функтор. Практически сразу программа падает, что говорит о том, что имеется серьезная проблема, которая как раз и связана с ABA при удалении ресурса. Внутри реализации используется 8-байтовый CAS (на x86 архитектуре), который просто не в состоянии решить проблему корректного удаления объекта. Увы.
Не ожидал такого подвоха в библиотечной функции от Microsoft, честно говоря.
Не могли бы вы показать конкретнее?
У нас вот в таком случае:
ничего не падает
У нас вот в таком случае:
UMS::SList<std::function<void()>> stack;
...
stack.push([]{}) // producer
...
stack.pop(value) // consumer
value() //
ничего не падает
У меня несколько другой тест. Не падает скорее всего из-за того, что есть небольшая пауза между производителями и потребителями. Поэтому можно просто убрать ожидание на событии, и сделать бесконечный цикл с pop:
И желательно потребителей запускать до производителей.
while (true)
{
std::function<void()> f;
while (!tasks.pop(f));
f();
}
И желательно потребителей запускать до производителей.
Да, и еще одно замечание. Количество производителей стоит сделать = 1, а потребителей = числу ядер. Тогда вероятность ситуации сильно возрастет.
Мы, вот, всё пытаемся воспроизвести ваш сценарий — пока безуспешно… но попутно кое-что заметили плохое ))
После замечаний от lek, из конструктора шаблона, который здесь на странице пропал вызов InitializeSListHead, в архиве с изначальной версией такой проблемы нет. А отсутствие инициализации головы, как раз, приводит к падению на пустом стеке. (Сейчас исправили здесь в статье)
Вы какой версией пользовались?
После замечаний от lek, из конструктора шаблона, который здесь на странице пропал вызов InitializeSListHead, в архиве с изначальной версией такой проблемы нет. А отсутствие инициализации головы, как раз, приводит к падению на пустом стеке. (Сейчас исправили здесь в статье)
Вы какой версией пользовались?
Да, действительно, если добавить эту строчку, то все становится отлично. По крайней мере, сейчас у меня тоже не падает )
Извините за этот наш косяк…
Сначала всё было нормально, но потом поспешили исправить то, о чем говорил lek, инасмешили накосячили.
Спасибо за вашу внимательность.
Сначала всё было нормально, но потом поспешили исправить то, о чем говорил lek, и
Спасибо за вашу внимательность.
Хотелось бы понять, как MS удалось это реализовать. Работает действительно быстро. Проблем сходу не видно.
Вот здесь написано отчасти про их внутреннее устройство и про решение ABA проблемы, кстати тоже. Только вот момент насчёт выигранных четырех бит, как-то не до конца понятен…
Sign up to leave a comment.
Lock-free стек для Windows