Может ли компилятор C++ объединить соседние блокировки мьютексов?
Рассмотрим следующий код со смежными секциями мьютекса, содержащими доступ к общей памяти:
std::mutex mutex;
int x;
void func() {
{
std::lock_guard lock{mutex};
x++;
}
{
std::lock_guard lock{mutex};
x++;
}
}
Без мьютексов компилятор, очевидно, мог бы объединить приращения, например:
void func() {
x += 2;
}
Это заставило меня задуматься о том, что может помешать такой оптимизации. Мы знаем, что даже если x равно std::atomic<int>, оптимизация по-прежнему допустима (но, возможно, не выполняется на практике).
А как насчет мьютексов? Законно ли компилятору преобразовывать func в это?
void func() {
std::lock_guard lock{mutex};
x += 2;
}
Понятно, что запись в x должна иметь видимые побочные эффекты для других потоков из-за семантики приобретения-выпуска, но я не уверен, что это запрещает оптимизацию. Возможно, вы можете возразить в соответствии с правилом «как если бы», что вы не можете определить разницу, была ли оптимизация выполнена или нет, поэтому оптимизация является законной (поскольку разница между «разблокировать, затем снова заблокировать» и «продолжать удерживать блокировку» зависит только о времени планирования потоков).
С другой стороны, кажется правдоподобным, что эта оптимизация может привести к скользкой дорожке для каждой программы, содержащей оптимизируемый мьютекс: заблокировать мьютекс, выполнить всю программу, разблокировать мьютекс. Очевидно, что такое поведение будет бесполезным для параллельных приложений, поэтому его можно разумно запретить.
Какой аспект модели памяти C++ и формулировки стандарта разрешают или запрещают такую оптимизацию?
(В настоящее время Clang и GCC не выполняют эту оптимизацию, как можно увидеть здесь. Однако это не является доказательством того, что оптимизация является или обязательно должна быть незаконной.)
... Операция lock() для мьютекса также является операцией Acquire " и Memory_order_acquire "... никакие операции чтения или записи в текущем потоке не могут быть переупорядочены до этой загрузки....
@yeputons Если вы говорите о синхронизации, о том, что происходит раньше, и о том, как они влияют на видимые побочные эффекты, то я не убежден. Я считаю, что ЕСЛИ поток B читает значение V, то все, что происходит до того, как поток A записывает V, должно быть зафиксировано и видимо. Кажется правдоподобным, что нет никаких ограничений на то, какое значение поток B ДОЛЖЕН прочитать. (Я думаю, что это аналогичная ситуация с объединением доступов std::atomic, на которое я дал ссылку.)
@RichardCritten Я думаю, что это верно и для std::atomic, который, как мы думаем, можно объединить: stackoverflow.com/q/45960387/7064452
Интересный вопрос! Кстати, MSVC не оптимизирует его под одну блокировку.
Разрешенное и полезное – разные вещи. Потоки в C++ могут выполняться последовательно. Это бесполезно, и никакая реализация никогда этого не сделает. Здесь то же самое.
Ответы 1
Да, трансформация разрешена по причинам, которые вы сами указали.
Для любого заданного ввода, независимо от того, как выглядит остальная часть кода, набор наблюдаемого поведения, разрешенного преобразованной функцией, всегда будет подмножеством наблюдаемого поведения, разрешенного исходной функцией.
Нет никакого требования, что разблокировка мьютекса приведет к тому, что другой поток, заблокированный при получении блокировки, немедленно проснется и атомарно с разблокировкой получит блокировку. Поэтому совершенно нормально запланировать поток разблокировки так, чтобы он немедленно повторно получил блокировку, независимо от действий любого другого потока.
Была ли снята блокировка, это не наблюдаемое поведение. Наблюдаемое поведение — это всего лишь доступ к объектам, конечное состояние записанных файлов и интерактивный ввод-вывод в соответствии с реализацией. См. [intro.abstract]/6.
Таким образом, освобождение/повторное получение можно пропустить, не влияя на наблюдаемое поведение с помощью этой схемы планирования, которая является допустимой схемой планирования и, следовательно, определяет один из допустимых вариантов наблюдаемого поведения. Компилятору нужно только гарантировать, что реализуется любой выбор допустимого наблюдаемого поведения. См. [intro.abstract]/5.
С другой стороны, кажется правдоподобным, что эта оптимизация может привести к скользкой дорожке для каждой программы, содержащей оптимизируемый мьютекс: заблокировать мьютекс, выполнить всю программу, разблокировать мьютекс. Очевидно, что такое поведение будет бесполезным для параллельных приложений, поэтому его можно разумно запретить.
Существует [intro.progress]/8 , который рекомендует, чтобы поток, выполняющий volatile, и потоки, созданные с помощью main/std::thread, должны предоставлять определенные гарантии параллельного продвижения вперед, что означает, что поток должен, пока он не не прекращено, в конце концов добейтесь прогресса ( [intro.progress]/6).
В целях достижения прогресса, согласно [intro.progress]/4, считается, что блокирующий вызов библиотеки непрерывно проверяет условие, вызывающее его блокировку, причем каждая такая проверка «выполняется». Другими этапами выполнения, которые вызывают прогресс, являются доступ через изменчивые элементы, завершение вызова функции ввода-вывода библиотеки, операции синхронизации и атомарные операции.
Однако я не думаю, что это вообще запрещает трансформацию
while(true)
{
std::lock_guard lock{mutex};
//A
x++; // (assume x is unsigned here)
}
в
std::lock_guard lock{mutex};
while(true)
{
x++;
}
Даже если другой поток попытается заблокировать мьютекс, следующее поведение планирования не нарушит эту гарантию продвижения вперед: неоднократно выполнять цикл до std::jthread, затем переключаться на другой поток, чтобы «достичь прогресса», проверяя условие блокировки, затем переключаться назад и повторите вышесказанное.
Прогресс вперед и планирование потоков в значительной степени оставляются как решение о качестве реализации реализации. См. также N3209, где обсуждается это с момента добавления многопоточного выполнения в C++11.
Я не ожидаю, что какой-либо компилятор предпримет попытку таких преобразований на уровне кода.
Однако даже обычные планировщики ОС не дают строгой гарантии того, что описанная выше схема планирования не сработает. Обычно это становится вероятностно маловероятным в течение длительного времени, поскольку потоки вытесняются через более или менее стохастически шумные интервалы. Если планирование окажется таким, как описано выше, то даже без преобразования компилятора поведение программы будет таким, как если бы преобразование было произведено.
Я мог бы представить себе другие среды, в которых описанное поведение планирования может происходить бесконечно. Предположим, например, что блокировка мьютекса реализована как простая спин-блокировка в однопроцессорной системе, и предположим, что планировщик совершенно справедлив и детерминирован в отношении количества инструкций, которые он позволяет выполнить каждому потоку в любом интервале времени. В такой среде вам может не повезти, поскольку заблокированный поток всегда сможет повторно получить блокировку в том же интервале времени, в котором она была снята.
Или многопоточность может быть полностью совместной, и в этом случае может возникнуть проблема, если мьютекс не будет реализован для выхода после разблокировки.
Я думаю, что стандарт не может давать более строгих гарантий, чем он есть, отчасти потому, что он сделал бы невозможным поддержку таких сред.
Я не уверен, что это правильно. Области AFAIK никогда не следует оптимизировать. (что-то связано с моделью памяти и ее порядком, у меня сейчас нет времени искать это)
@PepijnKramer Я не вижу причин, почему это так. Области действия не имеют значения, пока это не влияет на наблюдаемое поведение и невозможно наблюдать, была ли область «оптимизирована», что бы это ни значило.
@PepijnKramer На самом деле, было бы плохо, если бы компилятор не оптимизировался в нескольких областях. Например, если у меня есть int i = 0; { i = 1; } { i = 2; }, я ожидаю, что оптимизирующий компилятор выдаст только хранилище от 2 до i.
Блокировки могут быть (и на практике являются) несправедливыми. Снятие блокировки и немедленное ее повторное получение будут успешными, если никто не сможет проникнуть внутрь. (А в однопроцессорной системе никто не проникнет, если в потоке еще есть квант.) Таким образом, на практике система ведет себя так, как если бы оптимизация произошла.
Я не верю, что на практике какой-либо компилятор может оптимизировать блокировку/разблокировку мьютекса. Это связано не столько со спецификацией того, что мьютексы делают в соответствии со стандартом, сколько с тем, что на практике компиляторы должны выполнять для блокировки/разблокировки мьютекса - код слишком сложен.
@ ALX23z Даже если бы сложность позволяла это, я не ожидаю, что автор компилятора попытается реализовать такое преобразование по той же причине, по которой они решают не оптимизировать последовательные загрузки/сохранения в одном и том же атоме. Это противоречит ожиданиям программиста и может помешать дальнейшему прогрессу. Типичным примером является панель загрузки, которая обновляет свое состояние в цикле чтения из общего состояния (как атомарного, так и мьютекса). Если цикл не будет регулярно обновлять полосу загрузки, как ожидалось, это будет проблемой качества реализации.
@user17732522 user17732522 Спасибо за хорошо написанный ответ. Я думаю, что согласен с вашими рассуждениями в целом; Аргументы о прогрессе вперед убедительны. Одна вещь: «Была ли блокировка снята, это не наблюдаемое поведение» - есть ли у вас какая-либо техническая информация из Стандарта, подтверждающая это? Я думаю, что многие люди считают, что это вполне наблюдаемое поведение.
@ALX23z В типичных системах Linux std::mutex lock/unlock преобразуется непосредственно в вызовы блокировки/разблокировки pthread (вы можете увидеть это в Godbolt, на который я ссылаюсь). Мне кажется правдоподобным, что компиляторы могут жестко запрограммировать специальные знания о таких вызовах, как будто они обладают специальными знаниями о распределении памяти, встроенных функциях и т. д. Хотя я согласен, что агрессивная оптимизация этих сценариев противоречит духу того, как программисты хотят реализовать параллелизм.
@MCΔT Я добавил ссылку на timsong-cpp.github.io/cppwp/n4950/intro#abstract-6 для определения наблюдаемого поведения.
@MCΔT — это вызовы функций, которые делают черт знает что. У меня есть некоторые сомнения, что компиляторы выполняют такую оптимизацию. Обычно они упрощают инструкции, а вызовы функций действуют как барьеры, если они не встроены.
@ALX23z Они делают предположения о поведении некоторых функций стандартной библиотеки C в целях оптимизации, но я не видел этого для функций стандартной библиотеки C++ или POSIX (за исключением одного случая, когда у них было волшебное поведение). Типичный пример: компиляторы заменяют printf("%s", /*...*/) на puts(/*...*/), заменяют memset/memcpy прямыми машинными инструкциями или наоборот, исключают комбинации malloc/free и т. д.
Я подозреваю, что может быть какая-то формулировка о том, что блокировка (разблокировка) мьютекса является видимым внешним эффектом, похожим на ввод-вывод, например
[intro.progress]/1перечисляет оба.