Programming
C++
Comments 44
+2
Да, это была целая история…
Одно барахло везде попадалось. В итоге, поставили DataScene
+2
Спасибо. Пара замечаний:
1. Похоже, вы забыли голову (m_stack_head) выровнять.
2. Если тело функции внутри объявления класса идет, такие функции по умолчанию считаются inline. C++STD 2012, 7.1.2: A function defined within a class definition is an inline function.
+2
Спасибо за ваши замечания — исправлено по обоим пунктам.
0
А как связано наличие 128bit CAS и Windows 8? В x86_64 всегда вроде инструкция CMPXCHG16B была… Берется да вызывается.
0
Наверное, криво написано в статье…
Связаны эти вещи всего лишь, потому что в WinAPI функция InterlockedCompare64Exchange128 пришла начиная с Windows 8, а так на ассемблере может и всегда можно было.
+4
Отвечу отчасти сам себе. В первых 64bit камнях AMD этой инструкции как оказалось небыло. А начиная с Win 8 Windows требует ее поддержку и предоставляет API.
+1
Было бы странно, если бы в продуктам M$ не встречалось удачных кусков. У них задача даже проще, чем у разработчиков кроссплатформенных продуктов, которым нужно учитывать особенности всех поддерживаемых систем, т.к. разрабатывают под вполне известное окружение с некоторой долей разнообразия (версии Windows в смысле).
Кстати, отличный момент для доказательства себе своей крутости :) Просто приготовь патч для OpenSource продуктов! и попробуй пропихнуть его в основное дерево
+2
В проектах с хорошим governance — это довольно просто. Например, в openstack есть чёткая процедура как из «постороннего человека» оказаться в самой мякотке. На всю бюрократию надо минут 15-20, ещё примерно пол-часа час на изучение git review и других фрагментов gerrit'а. После этого можно предлагать блюпринты, писать патчи, фиксить баги и т.д. И оно войдёт в проект правильно, с автоматическим гигантским тестированием, проверкой совместимости с кодом разных вендоров и разных конфигураций, и без каких-либо «ну я тут покодил вот мой патч как он там у вас будет я не знаю, но примите пожалуйста».
0
Речь же не о бюрократической сложности, а о сложности по разработке решения работающего одинавого хорошо под всеми возможными платформами.
+1
Я отвечал на тезис «Просто приготовь патч для OpenSource продуктов! и попробуй пропихнуть его в основное дерево „
0
Не могу не заметить, что «продукты MS» и «кроссплатформенные продукты» — это несколько пересекающиеся множества. Особенно в последнее время.
0
Часто проблемы с переносом на Windows бывают, например, c pthread. Хотя есть пару реализаций под WinAPI, но выглядят они как-то не очень.
А так, некоторые вещи из posix поддерживаются в VS SDK, поэтому малая часть проблем с переносом уходит. Вот здесь у них, например, гид по переносу на Win32

А вообще, то что называется кросс-платформенным решением часто не является таковым в полной мере, потому что именно Windows и не поддерживается… И не потому что это невозможно портировать. Так что, скорее, это правильно называть кросс-nix-овые продукты.

А вот многие вещи от Гугла или тот же SQLite, как раз, в большей степени кросс-платформенные: собираются на чём хочешь.
+1
Не совсем понятно, зачем дожидаться, пока продьюсеры закончат свою работу? Как раз интересно посмотреть в сценарии, когда молотят одновременно и продьюсеры, и консьюмеры, т.е. когда конкурентность одновременно и на push, и на pop операциях. Именно такие сценарии представляют наибольший интерес, т.к. они встречаются наиболее часто в реальности.
+1
Нужен критерий остановки для потребителей. Само по себе отсутствие заданий в стеке не означает, что их больше не будет, т.к. вероятно какие-то производители просто запаздывают и положат задания позднее. Поэтому сначала мы ждем пока все производители отработают и до тех пор честно пробуем найти еще задания в стеке, а вот когда они закончили работу, тогда пустой стек можно считать концом.
0
Критерий очень простой: локальный счетчик количества извлеченных элементов ==iterations (в случае, когда n_producers == n_consumers). Более того, приведенный тест не гарантирует, что все элементы будут извлечены: возможно ситуация, когда евент сработал, и элементов к тому времени уже нет.
0
Если возникает «ситуация, когда евент сработал, и элементов к тому времени уже нет.», то ничего страшного не будет — это значит, что consumer-ы уже всё разобрали и условие во втором цикле consumer «while (stack.pop(value))» нас тут же выбросит на конец потока. На самом деле, это как раз неплохой сценарий: в том смысле что consumer-ы быстро справились и не надо чистить
0
Либо другой вариант: консьюмеры отработали не весь список, но он стал пустым, а продьюсеры еще молотят данные. В таком случае консьюмеры закончат работу, а продьюсеры — нет.
0
А это невозможно, потому что hEvtDone ставится после выхода их блокирующего вызова producer_threads.join_all() в методе run_test. Это гарантирует окончание работы всех производителей до того, как consumer-ы пройдут Wait на событии и приступят к своим вторым циклам по чистке стека.
0
Кажется, что предложенный вами критерий «локальный счетчик количества извлеченных элементов ==iterations» насильственно закрепощает потоки потребители обрабатывать ровно столько заданий, сколько вбросил побратим-производитель в случае p=c, а если p!=c, то это вообще неверно. Так выходит?

И, кроме того, дело-то в том, что исходно обсчитывался квадрат {p X c}, где p почти везде не равно c, так что случай p=c, как бы вырожденный.
0
Ну вот количество итераций для продьюсера вас не смущают, а вот для консьюмера внезапно стало смущать. Не очень понятно.

Ну и проблема в вырожденности легко снимается, когда количество итераций для консьюмера = iterations * n_producers / n_consumers (можно сделать, чтобы всегда делилось нацело без остатка, но это не важно).
0
Тогда каждый поток должен знать об общем количестве потоков каждого типа, значит ему это нужно давать в аргументе. Это меняет структуру организации worker потоков. Лучше ли это?

И главное для чего? Избежать 1 Wait-а на поток? Общее заданий >>>> числа потоков и один wait на поток ничего не стоит, потому что мы можем потерять на нём 1 раз 10 мс, и то без нагрузки на CPU — это же не sleep…
0
Как я указывал выше, цель — чтобы продьюсеры и консьюмеры работали параллельно. Здесь же в тестах они работают последовательно, сначала отрабатывают продьюсеры, а потом — консьюмеры. Т.е. нет замеров именно конкурентного доступа к данным, когда есть и те и другие. Конечно, частично они будут пересекаться, но непонятно насколько частично и как это сказывается на производительности. Поэтому хотелось бы видеть одновременное действие producers/consumers в разных пропорциях.
0
Это совсем не верно. Посмотрите, пожалуйста, на код функции run_test.

1. Стартуют все производители и начинают накидывать задания
2. Стартуют все потребители и уже начинают потреблять задания
3. Ждем окончания работы производителей
4. Ждем окончания работы работы потребителей

Задержка между (1) и (2) только на время запуска (!) потоков, но никак не их работу. Лучше бы было только стартовать каждый из типов попеременно, но это не даст никакой заметной разницы.
0
Не совсем так. Потребители во втором пункте, конечно, стартуют, но вторая часть этого пункта не совсем корректна. Они начинают потреблять только после того, как пройдет 10 мс, либо после того, как выполнится 3-я часть. При этом мне неочевидно, что пересечение между началом работы потребления и началом реальной работы производителей является существенным вкладом в общее время работы. Возможно, я чего-то упустил.
0
А, вот, насчет 10 мс рассогласования на старте вы совершенно правы, и об этом мы написали чуть выше. Можно было бы избежать этого, например, изменив внешний цикл на do-while, чтобы потребители сразу пробовали брать задания.

Однако, этот фрагмент кода, касается лишь самого теста. Нигде в тексте статьи мы не апеллируем к абсолютным числам по тестам. Проводится лишь сравнение реализаций. А поскольку каждый из 3(4) тестов имеет эти 10 мс, и время работы 1 теста составляет ~10-40 секунд, то они в этом плане абсолютно сравнимы и отмена 10мс не изменит соотношения.
0
Если время составляет 10-40 секунд, то в таком случае, безусловно, этой паузой можно пренебречь.
+2
Спасибо, интересно.

А нельзя ли для масштаба добавить к трём lock-free стэкам ещё и простейший стэк с блокировкой (CriticalSection или mutex)?
0
Вроде бы нет… вот результаты в сыром виде (но надо иметь в виду, что было только по 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
0
Мьютекс имеет смысл использовать только в случае небольшого числа потоков. Поэтому было бы интересно увидеть сравнительный график вблизи единицы, скажем 1, 2, 4. Результат может удивить.
0
Результаты работы теста c mutex при малом числе потоков действительно удивляют: даже на этих грубых числах уже видно, что числа с mutex, как минимум сравнимы, а то и меньше, чем у lock-free.
+2
Спасибо за хорошую статью и проведенную работу по сравнительному анализу! Независимые данные всегда особо ценны, в том числе и критика. Как автор libcds, постараюсь в одной из следующих статей своего эпического цикла объяснить, как появился интерфейс контейнеров в libcds, — это может быть интересно. Быть может, хабрасообщество подскажет более красивое решение тех проблем, с которыми я столкнулся при разработке библиотеки.
По поводу майкрософтовского SList. Я несколько лет назад где-то на просторах сети находил внутреннее устройство, — довольно интересно: если мне не изменяет память, они борются с ABA-проблемой с помощью SEH (structured exception handling). Грубо говоря, если получаем SEGFAULT, аккуратно обрабатываем его на очень низком уовне. К сожалению, пруф я сейчас найти не смог.
И по поводу Microsoft вообще, присоединюсь, покидаю на вентилятор: я считаю, что существование Windows — это большая удача для кросс-платформенных разработчиков, ибо ставит нетривиальные задачи по обобщению *nix и Windows подхода при кросс-платформенной разработке. Да, колемся, плачем, но продолжаем решать нестандартные задачи по унификации столь разных API столь разных операционных систем и компиляторов
+1
Да, чуда не произошло.

Я тут вечерком протестировал приведенную реализацию на предмет ABA проблемы, и оказалось, что она таки присутствует. Чтобы в этом убедиться, достаточно переписать тест на использование в качестве T=std::function<void()>, на push операцию добавлять []{}, на pop: вызывать соответствующий функтор. Практически сразу программа падает, что говорит о том, что имеется серьезная проблема, которая как раз и связана с ABA при удалении ресурса. Внутри реализации используется 8-байтовый CAS (на x86 архитектуре), который просто не в состоянии решить проблему корректного удаления объекта. Увы.

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

У нас вот в таком случае:
UMS::SList<std::function<void()>> stack;
...
stack.push([]{}) // producer
...
stack.pop(value) // consumer
value()          //


ничего не падает
0
У меня несколько другой тест. Не падает скорее всего из-за того, что есть небольшая пауза между производителями и потребителями. Поэтому можно просто убрать ожидание на событии, и сделать бесконечный цикл с pop:

while (true)
{
    std::function<void()> f;
    while (!tasks.pop(f));
    f();
}

И желательно потребителей запускать до производителей.
0
Да, и еще одно замечание. Количество производителей стоит сделать = 1, а потребителей = числу ядер. Тогда вероятность ситуации сильно возрастет.
0
Мы, вот, всё пытаемся воспроизвести ваш сценарий — пока безуспешно… но попутно кое-что заметили плохое ))

После замечаний от lek, из конструктора шаблона, который здесь на странице пропал вызов InitializeSListHead, в архиве с изначальной версией такой проблемы нет. А отсутствие инициализации головы, как раз, приводит к падению на пустом стеке. (Сейчас исправили здесь в статье)

Вы какой версией пользовались?
0
Да, действительно, если добавить эту строчку, то все становится отлично. По крайней мере, сейчас у меня тоже не падает )
0
Извините за этот наш косяк…
Сначала всё было нормально, но потом поспешили исправить то, о чем говорил lek, и насмешили накосячили.
Спасибо за вашу внимательность.
0
Хотелось бы понять, как MS удалось это реализовать. Работает действительно быстро. Проблем сходу не видно.
0
Вот здесь написано отчасти про их внутреннее устройство и про решение ABA проблемы, кстати тоже. Только вот момент насчёт выигранных четырех бит, как-то не до конца понятен…
Only those users with full accounts are able to leave comments., please.