Vengo 20 мая 2014 в 14:52

Lock-free стек для Windows

9 мин

24K

Программирование * C++ *

+51

Комментарии 44

scumware 20 мая 2014 в 15:05

Спасибо, это интересно.
В чём диаграммки делали?

Vengo 20 мая 2014 в 15:07

Да, это была целая история…
Одно барахло везде попадалось. В итоге, поставили DataScene

lek 20 мая 2014 в 15:28

Спасибо. Пара замечаний:
1. Похоже, вы забыли голову (m_stack_head) выровнять.
2. Если тело функции внутри объявления класса идет, такие функции по умолчанию считаются inline. C++STD 2012, 7.1.2: A function defined within a class definition is an inline function.

Vengo 20 мая 2014 в 16:30

Спасибо за ваши замечания — исправлено по обоим пунктам.

splav_asv 20 мая 2014 в 16:16

А как связано наличие 128bit CAS и Windows 8? В x86_64 всегда вроде инструкция CMPXCHG16B была… Берется да вызывается.

Vengo 20 мая 2014 в 16:22

Наверное, криво написано в статье…
Связаны эти вещи всего лишь, потому что в WinAPI функция InterlockedCompare64Exchange128 пришла начиная с Windows 8, а так на ассемблере может и всегда можно было.

splav_asv 20 мая 2014 в 16:24

Отвечу отчасти сам себе. В первых 64bit камнях AMD этой инструкции как оказалось небыло. А начиная с Win 8 Windows требует ее поддержку и предоставляет API.

FSA 20 мая 2014 в 16:39

Было бы странно, если бы в продуктам M$ не встречалось удачных кусков. У них задача даже проще, чем у разработчиков кроссплатформенных продуктов, которым нужно учитывать особенности всех поддерживаемых систем, т.к. разрабатывают под вполне известное окружение с некоторой долей разнообразия (версии Windows в смысле).
Кстати, отличный момент для доказательства себе своей крутости :) Просто приготовь патч для OpenSource продуктов! и попробуй пропихнуть его в основное дерево

amarao 20 мая 2014 в 17:11

В проектах с хорошим governance — это довольно просто. Например, в openstack есть чёткая процедура как из «постороннего человека» оказаться в самой мякотке. На всю бюрократию надо минут 15-20, ещё примерно пол-часа час на изучение git review и других фрагментов gerrit'а. После этого можно предлагать блюпринты, писать патчи, фиксить баги и т.д. И оно войдёт в проект правильно, с автоматическим гигантским тестированием, проверкой совместимости с кодом разных вендоров и разных конфигураций, и без каких-либо «ну я тут покодил вот мой патч как он там у вас будет я не знаю, но примите пожалуйста».

AllexIn 21 мая 2014 в 10:02

Речь же не о бюрократической сложности, а о сложности по разработке решения работающего одинавого хорошо под всеми возможными платформами.

amarao 21 мая 2014 в 10:09

Я отвечал на тезис «Просто приготовь патч для OpenSource продуктов! и попробуй пропихнуть его в основное дерево „

int19h 21 мая 2014 в 07:23

Не могу не заметить, что «продукты MS» и «кроссплатформенные продукты» — это несколько пересекающиеся множества. Особенно в последнее время.

Vengo 21 мая 2014 в 07:46

Часто проблемы с переносом на Windows бывают, например, c pthread. Хотя есть пару реализаций под WinAPI, но выглядят они как-то не очень.
А так, некоторые вещи из posix поддерживаются в VS SDK, поэтому ~~малая~~ часть проблем с переносом уходит. Вот здесь у них, например, гид по переносу на Win32

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

А вот многие вещи от Гугла или тот же SQLite, как раз, в большей степени кросс-платформенные: собираются на чём хочешь.

gridem 21 мая 2014 в 12:06

Не совсем понятно, зачем дожидаться, пока продьюсеры закончат свою работу? Как раз интересно посмотреть в сценарии, когда молотят одновременно и продьюсеры, и консьюмеры, т.е. когда конкурентность одновременно и на push, и на pop операциях. Именно такие сценарии представляют наибольший интерес, т.к. они встречаются наиболее часто в реальности.

Vengo 21 мая 2014 в 13:12

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

gridem 21 мая 2014 в 13:44

Критерий очень простой: локальный счетчик количества извлеченных элементов ==iterations (в случае, когда n_producers == n_consumers). Более того, приведенный тест не гарантирует, что все элементы будут извлечены: возможно ситуация, когда евент сработал, и элементов к тому времени уже нет.

Vengo 21 мая 2014 в 14:54

Если возникает «ситуация, когда евент сработал, и элементов к тому времени уже нет.», то ничего страшного не будет — это значит, что consumer-ы уже всё разобрали и условие во втором цикле consumer «while (stack.pop(value))» нас тут же выбросит на конец потока. На самом деле, это как раз неплохой сценарий: в том смысле что consumer-ы быстро справились и не надо чистить

gridem 21 мая 2014 в 15:10

Либо другой вариант: консьюмеры отработали не весь список, но он стал пустым, а продьюсеры еще молотят данные. В таком случае консьюмеры закончат работу, а продьюсеры — нет.

Vengo 21 мая 2014 в 15:18

А это невозможно, потому что hEvtDone ставится после выхода их блокирующего вызова producer_threads.join_all() в методе run_test. Это гарантирует окончание работы всех производителей до того, как consumer-ы пройдут Wait на событии и приступят к своим вторым циклам по чистке стека.

Vengo 21 мая 2014 в 15:15

Кажется, что предложенный вами критерий «локальный счетчик количества извлеченных элементов ==iterations» насильственно закрепощает потоки потребители обрабатывать ровно столько заданий, сколько вбросил побратим-производитель в случае p=c, а если p!=c, то это вообще неверно. Так выходит?

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

gridem 21 мая 2014 в 15:22

Ну вот количество итераций для продьюсера вас не смущают, а вот для консьюмера внезапно стало смущать. Не очень понятно.

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

Vengo 21 мая 2014 в 15:36

Тогда каждый поток должен знать об общем количестве потоков каждого типа, значит ему это нужно давать в аргументе. Это меняет структуру организации worker потоков. Лучше ли это?

И главное для чего? Избежать 1 Wait-а на поток? Общее заданий >>>> числа потоков и один wait на поток ничего не стоит, потому что мы можем потерять на нём 1 раз 10 мс, и то без нагрузки на CPU — это же не sleep…

gridem 21 мая 2014 в 15:47

Как я указывал выше, цель — чтобы продьюсеры и консьюмеры работали параллельно. Здесь же в тестах они работают последовательно, сначала отрабатывают продьюсеры, а потом — консьюмеры. Т.е. нет замеров именно конкурентного доступа к данным, когда есть и те и другие. Конечно, частично они будут пересекаться, но непонятно насколько частично и как это сказывается на производительности. Поэтому хотелось бы видеть одновременное действие producers/consumers в разных пропорциях.

Vengo 21 мая 2014 в 16:09

Это совсем не верно. Посмотрите, пожалуйста, на код функции run_test.

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

Задержка между (1) и (2) только на время запуска (!) потоков, но никак не их работу. Лучше бы было только стартовать каждый из типов попеременно, но это не даст никакой заметной разницы.

gridem 21 мая 2014 в 19:45

Не совсем так. Потребители во втором пункте, конечно, стартуют, но вторая часть этого пункта не совсем корректна. Они начинают потреблять только после того, как пройдет 10 мс, либо после того, как выполнится 3-я часть. При этом мне неочевидно, что пересечение между началом работы потребления и началом реальной работы производителей является существенным вкладом в общее время работы. Возможно, я чего-то упустил.

Vengo 22 мая 2014 в 06:42

А, вот, насчет 10 мс рассогласования на старте вы совершенно правы, и об этом мы написали чуть выше. Можно было бы избежать этого, например, изменив внешний цикл на do-while, чтобы потребители сразу пробовали брать задания.

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

gridem 22 мая 2014 в 08:22

Если время составляет 10-40 секунд, то в таком случае, безусловно, этой паузой можно пренебречь.

mickey99 21 мая 2014 в 12:21

Спасибо, интересно.

А нельзя ли для масштаба добавить к трём lock-free стэкам ещё и простейший стэк с блокировкой (CriticalSection или mutex)?

Vengo 21 мая 2014 в 14:49

Ответ добавили в конец статьи.

mickey99 21 мая 2014 в 15:05

Спасибо

Nickname 21 мая 2014 в 15:21

Судя по графику, на 2 и 4 потоках mutex обгоняет?

Vengo 21 мая 2014 в 15:29

Вроде бы нет… вот результаты в сыром виде (но надо иметь в виду, что было только по 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

gridem 21 мая 2014 в 19:46

Мьютекс имеет смысл использовать только в случае небольшого числа потоков. Поэтому было бы интересно увидеть сравнительный график вблизи единицы, скажем 1, 2, 4. Результат может удивить.

Vengo 22 мая 2014 в 06:45

Результаты работы теста c mutex при малом числе потоков действительно удивляют: даже на этих грубых числах уже видно, что числа с mutex, как минимум сравнимы, а то и меньше, чем у lock-free.

khizmax 21 мая 2014 в 18:11

Спасибо за хорошую статью и проведенную работу по сравнительному анализу! Независимые данные всегда особо ценны, в том числе и критика. Как автор libcds, постараюсь в одной из следующих статей своего эпического цикла объяснить, как появился интерфейс контейнеров в libcds, — это может быть интересно. Быть может, хабрасообщество подскажет более красивое решение тех проблем, с которыми я столкнулся при разработке библиотеки.
По поводу майкрософтовского SList. Я несколько лет назад где-то на просторах сети находил внутреннее устройство, — довольно интересно: если мне не изменяет память, они борются с ABA-проблемой с помощью SEH (structured exception handling). Грубо говоря, если получаем SEGFAULT, аккуратно обрабатываем его на очень низком уовне. К сожалению, пруф я сейчас найти не смог.
И по поводу Microsoft вообще, присоединюсь, покидаю на вентилятор: я считаю, что существование Windows — это большая удача для кросс-платформенных разработчиков, ибо ставит нетривиальные задачи по обобщению *nix и Windows подхода при кросс-платформенной разработке. Да, колемся, плачем, но продолжаем решать нестандартные задачи по унификации столь разных API столь разных операционных систем и компиляторов

gridem 22 мая 2014 в 08:27

Да, чуда не произошло.

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

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

Vengo 22 мая 2014 в 09:22

Не могли бы вы показать конкретнее?

У нас вот в таком случае:

UMS::SList<std::function<void()>> stack;
...
stack.push([]{}) // producer
...
stack.pop(value) // consumer
value()          //

ничего не падает

gridem 22 мая 2014 в 09:29

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

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

И желательно потребителей запускать до производителей.

gridem 22 мая 2014 в 09:32

Да, и еще одно замечание. Количество производителей стоит сделать = 1, а потребителей = числу ядер. Тогда вероятность ситуации сильно возрастет.

Vengo 22 мая 2014 в 09:52

Мы, вот, всё пытаемся воспроизвести ваш сценарий — пока безуспешно… но попутно кое-что заметили плохое ))

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

Вы какой версией пользовались?

gridem 22 мая 2014 в 09:59

Да, действительно, если добавить эту строчку, то все становится отлично. По крайней мере, сейчас у меня тоже не падает )

Vengo 22 мая 2014 в 10:03

Извините за этот наш косяк…
Сначала всё было нормально, но потом поспешили исправить то, о чем говорил lek, и ~~насмешили~~ накосячили.
Спасибо за вашу внимательность.

gridem 22 мая 2014 в 10:50

Хотелось бы понять, как MS удалось это реализовать. Работает действительно быстро. Проблем сходу не видно.

Vengo 22 мая 2014 в 10:56

Вот здесь написано отчасти про их внутреннее устройство и про решение ABA проблемы, кстати тоже. Только вот момент насчёт выигранных четырех бит, как-то не до конца понятен…

Зарегистрируйтесь на Хабре, чтобы оставить комментарий