Spurious wakes
От: Videoman Россия https://hts.tv/
Дата: 02.03.21 20:49
Оценка: 50 (6)
Тут на форуме, лет 5 назад, проскакивала тема про condition variables и ложные срабатывания. Помню была ярая дискуссия про то, почему они возникают. Была просто куча версий и помню, что даже один человек написал что-то разумное про lock-free хеш-таблицу, но как-то дальше все сумбурно было. Нечаянно натолкнулся на статью от Microsoft, о том почему это происходит, где, на мой взгляд, эта особенность наиболее понятно описана.

Заодно, те кто в танке, могут узнать о мощьнейшем-новейшем объекте ожидания от Microsoft — Wait­On­Address. Может кто-то очень хочет создать "халявные" 1М объектов синхронизации на процесс без использования ресурсов ядра и не знает как это сделать . Правда если их все поставить одновременно на ожидание, думаю ядро сильно удивится. С другой стороны на это нужно будет 1М потоков, так что наверное это не реально.

P.S. Заранее извиняюсь если я зря опять откопал стюардессу.
Отредактировано 02.03.2021 21:48 Videoman . Предыдущая версия . Еще …
Отредактировано 02.03.2021 20:52 Videoman . Предыдущая версия .
Re: Spurious wakes
От: Mystic Artifact  
Дата: 02.03.21 22:05
Оценка:
Здравствуйте, Videoman, Вы писали:

V>Заодно, те кто в танке, могут узнать о мощьнейшем-новейшем объекте ожидания от Microsoft — Wait­On­Address. Может кто-то очень хочет создать "халявные" 1М объектов синхронизации на процесс без использования ресурсов ядра и не знает как это сделать .


Интересно, и правда, спасибо.

Только локальное решение все равно будет приблизительно на порядок лучше, за счет локальности и безхаковости. А их решение — узкоспецифичное. Собственно говоря не видя нутрянку, прогнозов сделать нельзя, и уж тем более нельзя сказать то, что они говорят в документации... Про то что решение это лучше чем цикл. С почему? А потому, что в реальной задаче цикл не пустой, а их функция — не конкурент.

Это тоже догадки. Но я даже представить себе боюсь как это может работать как бы "эффективно".
Re[2]: Spurious wakes
От: Videoman Россия https://hts.tv/
Дата: 02.03.21 22:20
Оценка:
Здравствуйте, Mystic Artifact, Вы писали:

MA> Только локальное решение все равно будет приблизительно на порядок лучше, за счет локальности и безхаковости. А их решение — узкоспецифичное. Собственно говоря не видя нутрянку, прогнозов сделать нельзя, и уж тем более нельзя сказать то, что они говорят в документации... Про то что решение это лучше чем цикл. С почему? А потому, что в реальной задаче цикл не пустой, а их функция — не конкурент.


Что-то я не понял о каком локальном решении идет речь. Они шедулят-пробуждают потоки в зависимости от состояния хешь-таблицы. Под "легким" объектом у них подразумевается то, что пока ожидание не нужно, никакие ресурсы не используются, но как можно не используя ядро усыпить поток? Или я не понял что имеется в виду под локальным решением .
Отредактировано 02.03.2021 22:20 Videoman . Предыдущая версия .
Re[3]: Spurious wakes
От: Mystic Artifact  
Дата: 02.03.21 23:11
Оценка:
Здравствуйте, Videoman, Вы писали:

V>Что-то я не понял о каком локальном решении идет речь. Они шедулят-пробуждают потоки в зависимости от состояния хешь-таблицы. Под "легким" объектом у них подразумевается то, что пока ожидание не нужно, никакие ресурсы не используются, но как можно не используя ядро усыпить поток? Или я не понял что имеется в виду под локальным решением .


Их решение универсальное — по адресу. В конкретной логике конкретной программы — это скорее всего лишнее. Ну т.е. из серии — из пушки — по воробьям. Это все имеет право на жизнь, если это делает клиентский код проще — но мне сдается, что оно этого как раз и не сделает. Руку на отсечение не дам, просто видится в голове очень невкусное нутро.
Re[4]: Spurious wakes
От: Alexander G Украина  
Дата: 03.03.21 08:30
Оценка: 15 (1)
Здравствуйте, Mystic Artifact, Вы писали:

MA> Их решение универсальное — по адресу. В конкретной логике конкретной программы — это скорее всего лишнее. Ну т.е. из серии — из пушки — по воробьям. Это все имеет право на жизнь, если это делает клиентский код проще — но мне сдается, что оно этого как раз и не сделает. Руку на отсечение не дам, просто видится в голове очень невкусное нутро.


Естественный случай для ожидания на адресе -- это ожидание на счётчике очереди, или реализация std::latch.

Но даже обычный std::mutex оптимальнее всего сделать на WaitOnAddress.

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

Эта реализация общая у WaitOnAddress и SRWLOCK.

Перебор элементов в списке ждунов -- дешевая операция по сравнению с собсна вызовом ядра.
Ну то есть одинаково будет SetEvent / WaitOnSingeObject и WaitOnAddress / WakeByAddress

При этом мьютекс на WaitOnAddress выиграет за счёт:
* В случае, когда нет борьбы за ресурс, он будет сводиться к проверке и модификации атомарной переменной, т.е. ни одного DLL вызова, всё может быть полностью инлайн.
Для сравнения, критическая секция или SRWLOCK тоже будут на атомарном compare-and-swap, но там будет ещё WinAPI DLL вызов.
* Никаких динамической инициализации, выделение ресурсов и прочего.
Т.е. мьютекс может быть статически инициализированная глобальная переменная, или массив из миллионов переменных, всё это будет работать.
Русский военный корабль идёт ко дну!
Re: Spurious wakes
От: Alexander G Украина  
Дата: 03.03.21 08:33
Оценка: 3 (1)
Здравствуйте, Videoman, Вы писали:

V>P.S. Заранее извиняюсь если я зря опять откопал стюардессу.


В С++20 есть std::atomic<T>::wait, где этот самый WaitOnAddress завёрнут в С++, реализация MSVC подоспела полгода назад.
Русский военный корабль идёт ко дну!
Re[2]: Spurious wakes
От: Videoman Россия https://hts.tv/
Дата: 03.03.21 08:38
Оценка:
Здравствуйте, Alexander G, Вы писали:

AG>В С++20 есть std::atomic<T>::wait, где этот самый WaitOnAddress завёрнут в С++, реализация MSVC подоспела полгода назад.


Безусловно что WaitOnAddress используется в реализациях под Windows. По сути это низкоуровневые потроха реализации Condition Variable. Я просто до этого не встречал более менее понятного объяснения почему происходят ложные пробуждения.
Re: Spurious wakes
От: Pzz Россия https://github.com/alexpevzner
Дата: 03.03.21 08:44
Оценка: +2
Здравствуйте, Videoman, Вы писали:

V>Заодно, те кто в танке, могут узнать о мощьнейшем-новейшем объекте ожидания от Microsoft — Wait­On­Address. Может кто-то очень хочет создать "халявные" 1М объектов синхронизации на процесс без использования ресурсов ядра и не знает как это сделать . Правда если их все поставить одновременно на ожидание, думаю ядро сильно удивится. С другой стороны на это нужно будет 1М потоков, так что наверное это не реально.


О, в венду futex'ы завезли. И 20-и лет не прошло...
Re[2]: Spurious wakes
От: Videoman Россия https://hts.tv/
Дата: 03.03.21 09:55
Оценка:
Здравствуйте, Pzz, Вы писали:

Pzz>О, в венду futex'ы завезли. И 20-и лет не прошло...


Судя по тому что API появился в Windows 8, а та была выпущена аж в 2012 году, то 9 лет уж как... Так что, завезли, завезли. Просто народ еще не проснулся и не может решить какие использовать: 1,2,4 или 8 байт .
Re[3]: Spurious wakes
От: Pzz Россия https://github.com/alexpevzner
Дата: 03.03.21 10:55
Оценка: +1
Здравствуйте, Videoman, Вы писали:

Pzz>>О, в венду futex'ы завезли. И 20-и лет не прошло...


V>Судя по тому что API появился в Windows 8, а та была выпущена аж в 2012 году, то 9 лет уж как... Так что, завезли, завезли. Просто народ еще не проснулся и не может решить какие использовать: 1,2,4 или 8 байт .


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

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

В линухе с этим проще, futex не предназначен для использования прикладными программистами, и автоматически используется или не используется внутри реализаций стандартных примитивов синхронизации.
Re[4]: Spurious wakes
От: Videoman Россия https://hts.tv/
Дата: 03.03.21 13:17
Оценка:
Здравствуйте, Pzz, Вы писали:

Pzz>Ну с другой стороны, если ты этим пользуешься, то либо ты не поддерживаешь 7-ку, либо в рантайме решаешь, чем пользоваться, что несколько лениво.


Дело хозяйское. Сейчас доля примерно 25%

Pzz>Сейчас 7-ку уже, наверное, можно не поддерживать в новых программах, но несколько лет назад еще было нельзя.


Если нужно использование в контексте condition variable, то можно использовать специальный API именно для этого случая. Он доступен начиная с Vista.

Pzz>В линухе с этим проще, futex не предназначен для использования прикладными программистами, и автоматически используется или не используется внутри реализаций стандартных примитивов синхронизации.


На сколько я понял, реализация там примерно такая же и "проблема" ложных срабатываний там также актуальна.
Отредактировано 03.03.2021 13:17 Videoman . Предыдущая версия .
Re[5]: Spurious wakes
От: Pzz Россия https://github.com/alexpevzner
Дата: 03.03.21 15:44
Оценка:
Здравствуйте, Videoman, Вы писали:

Pzz>>В линухе с этим проще, futex не предназначен для использования прикладными программистами, и автоматически используется или не используется внутри реализаций стандартных примитивов синхронизации.


V>На сколько я понял, реализация там примерно такая же и "проблема" ложных срабатываний там также актуальна.


Конечно. Просто линуксная реализация прячет весь геморрой под капотом.

В ложных пробуждениях я не вижу никакой проблмы с точки зрения корректности (никто, вроде, и не обещал), но есть потенциальная проблема с точки зрения загрузки CPU, если эти пробуждения случаются слишком часто.
Re: Spurious wakes
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 04.03.21 21:03
Оценка:
Здравствуйте, Videoman, Вы писали:

V>Тут на форуме, лет 5 назад, проскакивала тема про condition variables и ложные срабатывания. Помню была ярая дискуссия про то, почему они возникают. Была просто куча версий и помню, что даже один человек написал что-то разумное про lock-free хеш-таблицу, но как-то дальше все сумбурно было.


Если это та дискуссия, в которой я участвовал, то я высказывал, что значительная часть ложных срабатываний происходит от того, что пока одна задача просыпается, другая успевает забрать свежевыпеченную плюшку.

Но вот у меня совершенно неожиданно в соседнем табе оказалась рояль в кустах заметка о том, что всё немного сложнее (и лечить это в общем можно пытаться, но большого толку не будет).

V>Заодно, те кто в танке, могут узнать о мощьнейшем-новейшем объекте ожидания от Microsoft — Wait­On­Address. Может кто-то очень хочет создать "халявные" 1М объектов синхронизации на процесс без использования ресурсов ядра и не знает как это сделать . Правда если их все поставить одновременно на ожидание, думаю ядро сильно удивится. С другой стороны на это нужно будет 1М потоков, так что наверное это не реально.


Ну, как уже сказали, futex он давно такой.
У меня к этому только замечание по WakeByAddressSingle: это вообще слишком тупое API. Я бы предпочёл как минимум выбор — будить первого ставшего в очередь или последнего (и с последним может иметь весьма большую пользу).
The God is real, unless declared integer.
Re[2]: Spurious wakes
От: Videoman Россия https://hts.tv/
Дата: 05.03.21 08:03
Оценка:
Здравствуйте, netch80, Вы писали:

N>Если это та дискуссия, в которой я участвовал, то я высказывал, что значительная часть ложных срабатываний происходит от того, что пока одна задача просыпается, другая успевает забрать свежевыпеченную плюшку.


Что-то типа того. Проблема родственная ABA.

N>Ну, как уже сказали, futex он давно такой.

N>У меня к этому только замечание по WakeByAddressSingle: это вообще слишком тупое API. Я бы предпочёл как минимум выбор — будить первого ставшего в очередь или последнего (и с последним может иметь весьма большую пользу).

Насколько я помню, все это обсуждалось в контексте С++ std::condition_variable. Ну Lunux там под капотом futex, на Windows другой API у которого под капотом, как я понял, WakeOnAddress. А по поводу WakeByAddressSingle: это просто повторение интерфейса условных переменных. А что, у futex есть возможность будить последнего?
Re[3]: Spurious wakes
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 05.03.21 11:39
Оценка:
Здравствуйте, Videoman, Вы писали:

V> А что, у futex есть возможность будить последнего?


Увы, тоже нет. Ни у кого нет (у большинства вообще не определяется, кого будят, но обычно будят первого заснувшего).

V> А по поводу WakeByAddressSingle: это просто повторение интерфейса условных переменных.


В чём-то даже не его, а юниксового классического sleep/wakeup механизма. Это уже условные переменные делались в его стиле с переносом в userland.
The God is real, unless declared integer.
Re[2]: Spurious wakes
От: Alexander G Украина  
Дата: 05.03.21 11:48
Оценка:
Здравствуйте, netch80, Вы писали:

N>У меня к этому только замечание по WakeByAddressSingle: это вообще слишком тупое API. Я бы предпочёл как минимум выбор — будить первого ставшего в очередь или последнего (и с последним может иметь весьма большую пользу).


В чём смысл будить последнего?

По факту там в WaitOnAddress "приблизительно FIFO", т.е. будится обычно первый.
Это можно понять, если мы уже дошли до переключения контекста, то пусть переключение будет максимально "честным".

Будить последнего означает маскимально "нечестное" переключение, когда минимальная часть потоков будет работать, остальные простаивать.

Насколько я понимаю, "нечестность" выгодна с точки зрения производительности, когда до переключения вообще не дошли, т.е. когда поток не освобождает ресурс, или когда поток тут же сам захватывает его обратно, "нечестное" переключение не имеет преимуществ по производительности, и имеет только недостаток неравномерного прогресса.
Русский военный корабль идёт ко дну!
Re[3]: Spurious wakes
От: Videoman Россия https://hts.tv/
Дата: 05.03.21 12:21
Оценка:
Здравствуйте, Alexander G, Вы писали:

AG>Насколько я понимаю, "нечестность" выгодна с точки зрения производительности, когда до переключения вообще не дошли, т.е. когда поток не освобождает ресурс, или когда поток тут же сам захватывает его обратно, "нечестное" переключение не имеет преимуществ по производительности, и имеет только недостаток неравномерного прогресса.


Скорее всего имеются ввиду какие-то I/O сценарии, типа Completion Ports, где чем позже поток пришел на ожидание, тем выше вероятность того что его ресурсы еще "горячие" (закешированы) и тем меньше мы тратим ресурсов на прогрев, кроме самого переключения контекста.
Re[3]: Spurious wakes
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 05.03.21 13:05
Оценка: 7 (1)
Здравствуйте, Alexander G, Вы писали:

N>>У меня к этому только замечание по WakeByAddressSingle: это вообще слишком тупое API. Я бы предпочёл как минимум выбор — будить первого ставшего в очередь или последнего (и с последним может иметь весьма большую пользу).

AG>В чём смысл будить последнего?

Представь себе типовой пул ниток — исполнителей заданий. Нитка отработала и ищет следующее задание. Если нет — становится в очередь. Тут приходит задание. Какую нитку будить? Оказывается, вставшую последней — немного выгоднее с точки зрения кэша, особенно если они как-то произвольно раскиданы по ядрам: её код и специфические данные (например, состояние коннекта, если она его держит куда-то наружу) лучше сохранятся.

AG>По факту там в WaitOnAddress "приблизительно FIFO", т.е. будится обычно первый.

AG>Это можно понять, если мы уже дошли до переключения контекста, то пусть переключение будет максимально "честным".

Иногда эта "честность" нужна, а иногда, наоборот, вредна. Не всегда честность требует FIFO.

AG>Будить последнего означает маскимально "нечестное" переключение, когда минимальная часть потоков будет работать, остальные простаивать.


А зачем считать по тому, какая часть ниток в принципе простаивает? Считать надо по общей занятости от их предельной. Например, если задач ровно на 3 нитки, а их всего 10, то загрузка 30%.
Это не считая стоимости переключения. А вот если считать с ней, то ситуация, когда работают только 3, а остальные простаивают, выгоднее.

AG>Насколько я понимаю, "нечестность" выгодна с точки зрения производительности, когда до переключения вообще не дошли, т.е. когда поток не освобождает ресурс, или когда поток тут же сам захватывает его обратно, "нечестное" переключение не имеет преимуществ по производительности, и имеет только недостаток неравномерного прогресса.


Как раз имеет преимущество — см. выше. А "неравномерный прогресс" для случая пула ниток вообще по барабану.

С другой стороны, да, где-то желателен как раз честный FIFO. Но смысл в нём — гарантия eventual прогресса (как это будет по-русски?). Где нужны такие жёсткие гарантии — вводят специальные меры типа того, что задачи становятся в специальную очередь, и передают флаг друг другу. А ещё там бывают приоритеты...
The God is real, unless declared integer.
Re[4]: Spurious wakes
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 05.03.21 13:08
Оценка:
Здравствуйте, Videoman, Вы писали:

AG>>Насколько я понимаю, "нечестность" выгодна с точки зрения производительности, когда до переключения вообще не дошли, т.е. когда поток не освобождает ресурс, или когда поток тут же сам захватывает его обратно, "нечестное" переключение не имеет преимуществ по производительности, и имеет только недостаток неравномерного прогресса.


V>Скорее всего имеются ввиду какие-то I/O сценарии, типа Completion Ports, где чем позже поток пришел на ожидание, тем выше вероятность того что его ресурсы еще "горячие" (закешированы) и тем меньше мы тратим ресурсов на прогрев, кроме самого переключения контекста.


Ну не всегда I/O, но в заметной мере да (я бы обобщил, как минимум, на синхронно исполняющиеся CPU-bound задачи). И completion port — как раз типовой случай, где это (если верить некоторым коллегам по соседству) сделано изначально.
The God is real, unless declared integer.
Re[5]: Spurious wakes
От: Videoman Россия https://hts.tv/
Дата: 05.03.21 17:09
Оценка:
Здравствуйте, netch80, Вы писали:

N>Ну не всегда I/O, но в заметной мере да (я бы обобщил, как минимум, на синхронно исполняющиеся CPU-bound задачи). И completion port — как раз типовой случай, где это (если верить некоторым коллегам по соседству) сделано изначально.


Значит я правильно угадал. Но всетаки это, на мой взгляд, какие-то микрооптимизации, потому-что преимущество будет в случае если мы так быстро обрабатываем на CPU запросы, что новые не успевают подходить и мы успеваем их хватать "прогретыми" тредами. Для наглядности, рассмотрим ситуацию когда с нагрузкой справляется один поток. Тогда он быстро обрабатывает новую порцию данных, возвращается и снова берет новую порцию. Пока его производительности хватает, у нас все время работает один поток и переключений нет совсем. Если справляются два потока, то работают только они и ситуация чуть похуже. Когда же у нас числодробилка и все ядра молотят параллельно, то, по-моему, эта схема уже не работает как задумано. Все ядра будут отрабатывать свои полные кванты и далее уходить в планировщик. Тут уже все сильно зависит от ОС, сможет ли она сообразить закрепить потоки за теми же ресурсами.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.