Почему компилятор превратил мой цикл с условием в бесконечный?

https://blogs.msdn.microsoft.com/oldnewthing/20180924-00/?p=99805
  • Перевод
Один из пользователей компилятора Visual C++ привёл следующий пример кода и спросил, почему его цикл с условием выполняется бесконечно, хотя в какой-то момент условие должно перестать выполняться и цикл должен закончиться:

#include <windows.h>

int x = 0, y = 1;
int* ptr;

DWORD CALLBACK ThreadProc(void*)
{
  Sleep(1000);
  ptr = &y;
  return 0;
}

int main(int, char**)
{
 ptr = &x; // starts out pointing to x

 DWORD id;
 HANDLE hThread = CreateThread(nullptr, 0, ThreadProc, 0, &id);

 // Ждём, пока другой поток изменит значение по указателю ptr
 // на некоторое ненулевое число
 while (*ptr == 0) { }

 return 0;
}

Для тех, кому не знакомы специфичные для платформы Windows функции, вот эквивалент на чистом С++:

#include <chrono>
#include <thread>

int x = 0, y = 1;
int* ptr = &x;

void ThreadProc()
{
  std::this_thread::sleep_for(std::chrono::seconds(1));
  ptr = &y;
}

int main(int, char**)
{
 ptr = &x; // starts out pointing to x

 std::thread thread(ThreadProc);

 // Ждём, пока другой поток изменит значение по указателю ptr
 // на некоторое ненулевое число
 while (*ptr == 0) { }

 return 0;
}

Далее пользователь привёл своё понимание работы программы:
Условный цикл был превращён компилятором в бесконечный. Я вижу это по сгенерированному ассемблерному коду, который однажды загружает значение указателя ptr в регистр (при старте цикла), а затем на каждой итерации сравнивает значение этого регистра с нулём. Поскольку повторной загрузки значения из ptr больше никогда не происходит — то и цикл никогда не заканчивается.

Я понимаю, что объявление ptr как «volatile int*» должно привести к тому, что компилятор отбросит оптимизации и будет считывать значение ptr на каждой итерации цикла, что исправит проблему. Но всё же хотелось бы узнать, почему компилятор не может быть достаточно умным, чтобы делать подобные вещи автоматически? Очевидно, что глобальная переменная, используемая в двух разных потоках, может быть изменена, а значит её нельзя просто закешировать в регистре. Почему компилятор не может сразу сгенерировать корректный код?


Перед тем, как ответить на этот вопрос, начнём с маленькой придирки: «volatile int* ptr» не объявляет переменную ptr в качестве «указателя, для которого запрещены оптимизации». Это «обычный указатель на переменную, для которой запрещены оптимизации». То, что имел в виду автор вышеуказанного вопроса, должно было быть объявлено как «int* volatile ptr».

А теперь вернёмся к основному вопросу. Что же здесь происходит?

Даже самый беглый взгляд на код скажет нам, что здесь нет ни переменных типа std::atomic, ни использования std::memory_order (ни явного, ни неявного). Это означает, что любая попытка доступа к ptr или *ptr из двух разных потоков ведёт к неопределённому поведению. Интуитивно об этом можно думать так: «Компилятор оптимизирует каждый поток так, как-будто он работает в программе один. Единственными точками, где компилятор по стандарту ОБЯЗАН задуматься о доступе к данным из разных потоков, является использование std::atomic или std::memory_order.»

Это объясняет, почему программа вела себя не так, как того ожидал программист. С момента, когда вы допускаете неопределённое поведение — уже нельзя гарантировать совершенно ничего.

Но ладно, давайте задумаемся о второй части его вопроса: почему компилятор недостаточно умён, чтобы распознать такую ситуацию и автоматически отключить оптимизацию с загрузкой значения указателя в регистр? Ну, компилятор автоматически применяет все возможные и не противоречащие стандарту оптимизации. Странно было бы требовать от него уметь читать мысли программиста и отключать какие-то оптимизации, не противоречащие стандарту, которые, возможно, по мнению программиста должны были бы изменить логику работы программы в лучшую сторону. «Ой, а вдруг этот цикл ожидает изменения значения глобальной переменной в другом потоке, хотя и не объявил об этом явно? Возьму-ка я его замедлю в сотню раз, чтобы быть готовым к этой ситуации!». Неужели должно быть так? Вряд ли.

Но допустим, что мы добавим в компилятор правило вроде «Если оптимизация привела к появлению бесконечного цикла, то нужно её отменить и собрать код без оптимизации». Или даже вот так: «Последовательно отменять отдельные оптимизации, пока результатом не станет не-бесконечный цикл». Кроме поразительных сюрпризов, которые это принесёт, даст ли это вообще какую-то пользу?

Да, в этом теоретическом случае мы не получим бесконечный цикл. Он прервётся, если какой-то другой поток запишет в *ptr ненулевое значение. А ещё он прервётся, если другой поток запишет ненулевой значение в переменную x. Становится не понятно, как глубоко должен отработать анализ зависимостей, чтобы «поймать» все случаи, которые могут повлиять на ситуацию. Поскольку компилятор вообще-то не запускает созданную программу и не анализирует её поведение на рантайме, то единственным выходом будет предположить, что вообще никакие обращения к глобальным переменным, указателям и ссылкам нельзя оптимизировать.

int limit;

void do_something()
{
    ...
    if (value > limit)
        value = limit; // перечитываем переменную limit
    ...
    for (i = 0; i < 10; i++)
      array[i] = limit; // перечитываем переменную limit
    ...
}

Это совершенно противоречит духу языка С++. Стандарт языка говорит, что если вы модифицируете переменную и рассчитываете увидеть эту модификацию в другом потоке — вы должны ЯВНО об этом сказать: использовать атомарную операцию или упорядочение доступа к памяти (обычно с помощью использования объекта синхронизации).

Так что, пожалуйста, именно так и поступайте.

Инфопульс Украина

271,60

Creating Value, Delivering Excellence

Поделиться публикацией

Похожие публикации

Комментарии 50
    +2
    Век живи, век учись…
      –15

      Статья должна называться: еще один аргумент в пользу перехода на Rust.

        +3
        А чем в этой ситуации Rust отличается от C++? Неумением оптимизировать циклы?
          +3

          Вообще-то в данном примере происходит не оптимизация цикла, а назальные демоны из-за UB, и все рассуждения автора можно выкинуть.


          Rust умеет оптимизировать циклы. В данном случае компилятор Rust запретит работу с переменной в другом потоке без явного использования примитивов синхронизации.

            0
            То есть, если переменная используется в нескольких потоках, то любые чтение/запись в нее должны быть как минимум атомарными? Тогда это отличная причина не переходить на Rust.
            Кстати, заинтересовало, как эти проверки выполняются для переменной, которая используется в уже скомпилированном коде. Или такой ситуации вообще не возникает?
              0
              Если переменная используется в нескольких потоках — то она неизменяемая (либо она — атомарный контейнер для изменяемого значения). Это частный случай более общего правила владения, которое как раз и является главной фишкой Rust.

                +7
                как минимум атомарными

                Не атомарными, а под защитой примитивов синхронизации. Это могут быть атомики, мьютексы и прочие вещи.


                Тогда это отличная причина не переходить на Rust.

                Ну если вы хорошо знаете C++, то должны знать, что в стандарте C++ сказано, что гонки данных есть UB. Либо вы плохо знаете стандарт C++, либо вы не понимаете, что такое UB, следовательно тоже плохо знаете C++.


                как эти проверки выполняются для переменной, которая используется в уже скомпилированном коде. Или такой ситуации вообще не возникает?

                Эти проверки выполняются только во время компиляции с помощью типажей Send & Sync. Следовательно во время выполнения вы не несете никаких пенальти за безопасность.

                  0
                  «Гонки данных» и «используется в нескольких потоках» — это не одно и то же. Можно использовать одну и ту же память в нескольких потоках без синхронизаций и не получать гонку, так как синхронизация происходит в другом месте.
                  Для примера можно взять очередь на массиве, в которую пишет один поток, и из которой читает другой. Синхронизация памяти очереди происходит неявно с помощью индексов на первый/последний элементы очереди. Но, насколько я понимаю, в Rust'е все равно придется ставить мьютекс, что бы считать/записать данные?
                    +1
                    Синхронизация памяти очереди происходит неявно с помощью индексов на первый/последний элементы очереди.

                    Такая неявность с современными процессорами не пройдёт. Если один поток записал в элемент массива и увеличил индекс, другой поток может увидеть увеличенный индекс, но не увидеть новое значение в массиве. Почитайте про memory barriers.


                    Но, насколько я понимаю, в Rust'е все равно придется ставить мьютекс, что бы считать/записать данные?

                    В Rust можно делать то же, что и во всех других языках. Но код, который компилятор не может проверить на корректность (разыменование указателя, обращение к глобальной мутабельной переменной, вызов unsafe функции и что-то ещё), нужно отмечать как unsafe.

                      –4
                      Почитайте про memory barriers.
                      Да, подзабыл про них. Но насколько я знаю, барьеры — это сильно легче чем мьютексы (в плане производительности).
                      нужно отмечать как unsafe.
                      Ну так то да, но обсуждение началось с утверждения будто необходимость ставить volatile и пользоваться атомарными операциями в плюсах — это повод переходить на Rust. А я привел пример задачи, с которой мирок Rust'а не справляется, и нужен мирок C++.
                        +6
                        А я привел пример задачи, с которой мирок Rust'а не справляется, и нужен мирок C++.

                        Собственно это не мирок С++, а мирок железа. В Rust нужно сказать "Да, я знаю что делаю" и поставить unsafe, в C++ — нет.

                          +1
                          Здравствуйте!

                          Мне казалось, что использование C++ само по себе говорит, что программист думает что знает, что он делает.
                          –1
                          «Мирок» Rust с такими задачами тоже справляется. Заводится новый примитив — очередь сообщений, реализуется через unsafe, после чего спокойно и безопасно используется где нужно. Конечно же, при условии что программист знает что делает.

                          Ну или можно взять модуль std::sync::mpsc.
                +7

                Rust не даст возможность мутировать переменную таким образом в принципе.

                  0
                  это почему?
                    –1
                    Потому что в Rust на одну переменную не может быть двух владеющих ссылок.
                      0
                      Если использовать unsafe — можно все.
                        0

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

                          0

                          Это какой-то миф про unsafe. В книге черным по белому написано что можно делать в unsafe, это 4 вещи:


                          • Разыменовывать сырой указатель
                          • Вызывать unsafe функцию или метод
                          • Обращаться к или модифицировать статическую переменную
                          • Реализовывать unsafe trait

                          Всё. Борроу чеккер и все остальные проверки там никуда не уходят.

                            0
                            Ну так сделать два указателя и менять их в разных потоках, нет?
                              0

                              НЯЗ Этого же можно добиться Arc без всякого ансейфа.

                                –1
                                Коментарии выше основываются на принципе полностью нулевого оверхэда.
                        0

                        ну, без transmute никак.

                    0
                    Здравствуйте!

                    Позвольте мне поправить Вас: «Ещё один аргумент в пользу перехода на Rust или другой безопасный язык для тех, кто не знает, что такое Undefined Behaviour».
                      +9
                      Оха-ха, Rust спасет нас от багов, накормит голодных, оденет оборванцев, снимет котят с дерева…

                      Очень пошлая тенденция поклонников этого нового языка влазить в темы связанные с C/C++ со своими умозаключениями.

                      Undefined Behaviour

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

                      Чем-то это напоминает ситуацию с современным истребителем — за высокую маневренность мы платим полным отсутствием статической устойчивости. Для плюсов сие нормально, и раст тут не при чем

                      P.S.: Вангую очередной срач C/C++ vs Rust…
                        +2
                        Соглашусь, программирование -искусство компромиссов и серебрянной пули — не существует.
                        Из истории известно, что те кто предлагают средство для решения всех проблем, заводят людей в тупик. А упоминание rust-a в статьях о о с++ вызывает отторжение, как и любая навязчивая реклама.
                        Надеюсь что язык в этом не виноват.
                          +3
                          Я отнюдь не против языка Rust как такового — он есть и хорошо что он есть (больше языков, хороших и разных). Причина моей язвительности очень точно Вами сформулирована
                          упоминание rust-a в статьях о о с++ вызывает отторжение, как и любая навязчивая реклама
                            –3
                            упоминание rust-a в статьях о о с++ вызывает отторжение, как и любая навязчивая реклама

                            Понимаете, отторжение вызывает не упоминание языка Rust в статьях про С++, а упоминание более подходящего инструмента, который может решать проблемы на таком уровне, на котором С++ никогда не сможет этого сделать. Вы обижаетесь, минусуете, считаете себя профессионалом, который может решить эти проблемы только лишь силой своего ума, но это не так. Читайте статью https://www.parity.io/why-rust/ .


                            Я понимаю, что это вызывает у вас ломку, вам больно на это смотреть, но я готов платить за это своей кармой. Пусть так. Лишь бы хоть 1 из сотни решился посмотреть в сторону Rust.

                              0
                              Я Вас не минусовал. Вообще не имею такой привычки в конструктивных спорах
                                0

                                Да я не про вас. Я про ситуацию в целом.


                                Долгое время умение программировать на C/C++ считалось вершиной мастерства. Считалось, что самые крутые программисты не допускают ошибок.


                                Компиляторы C/C++ скрывают UB, они используют его для оптимизации кода. Поэтому ошибка может жить десятилетия, ждать свое часа. Либо наоборот, некоторые оптимизации компилятора с использованием UB считаются "очевидными", типа можно вызвать функцию-член у нулевого указателя, если внутри этой функции-члена не происходит вызова полей/методов this.

                                +1
                                Лишь бы хоть 1 из сотни решился посмотреть в сторону Rust

                                Я слежу за развитием Rust. Но он, а точнее сказать, связанная с ним инфраструктура, пока не удовлетворяет тем задачам, которые я решаю
                        0
                        Ошибка в исходном коде должна быть очевидна любому профессиональному программисту на С или С++, но интересно вот что: действительно ли использование std::atomic гарантирует ожидаемую работу этого кода? И должен ли это быть указатель на atomic, или atomic<int*>?
                          +1
                          Ни то и не другое. То есть atomic работать будет, но плохо.
                          Код скопипастен из времен обработки прерывания одноядерного процессора и это типичный стиль написания для микроконтроллеров и сегодня., когда все события в системе контролируется вручную.
                          На микроконтроллер и сегодня можно писать в таком стиле, немного поправив код.
                          volatile int waitFlag; // не нужен тут указатель от слова совсем
                          И опять таки, исключительно для случая небольшого тупого однопроцессорного контроллера, где нет места и необходимости в операционной системе ( впрочем там и thread-ов нет, но может быть обработчик прерывания меняющий флаг)
                          Однако проведенный пример в много-ниточной среде вызовет тупое ожидание в цикле проверки до переключения контекста процессора, впустую занимает время и не дает операционной системе оптимизировать загрузку процессора. В многопроцессорной системе все еще хуже с данным кодом. (синхронизация кеша и прочая весьма дорогая фигня)
                          Корректный код должен использовать мютекс ( в posix нотациии ) поручить его ожидание операционной системе, для чего существуют специальные функции ОС.( wait триггер или waitFor… в Winapi ) С ++ последних версий имеет платформонезависимый интерфейс к этим функциям ( видимо надоело ждать когда же микрософт удосужится реализовать полноценный posix)
                          Atomic почти не меняет ничего из вышесказанного. В тупую ждать в вышеуказанном стиле — плохо.
                          В общем как и сказано статье — так писать не надо, а кому так надо они и сами об этом знают. :)

                            0
                            Полностью с вами согласен, вы всё правильно написали. Поэтому мой вопрос следует читать именно так, как он сформулирован — будет ли код с atomic работать ожидаемым образом. Ни в коем случае не говорил, что так писать — нормальная практика.
                              –1
                              Строго говоря: логически — да, будет. Но при этом крайне неэффективно расходуя ресурсы.
                              0
                              Код скопипастен из времен обработки прерывания одноядерного процессора и это типичный стиль написания для микроконтроллеров и сегодня., когда все события в системе контролируется вручную.

                              Чёрта с два.
                              Для современных мк применяется те-же алгоритмы компиляторов что и для больших машин. Более того — для программы мк необходимо создать объединение из const volatile и volatile. При этом const volatile проверяется, а volatile — меняется. Иначе компилятор может (должен) заоптимизировать код до нуля, ну или закинуть переменные в регистры.
                              В любом случае тупая проверка в цикле — дурной тон.
                              Для одного потока (без ос) — применяется уход в сон. Для работы в составе ос — проверяющий поток должен использовать средства синхронизации. Например уход в зависимость — где его будит управляющий поток, или добровольная отдача машинного времени соседним потокам по условиям проверки.

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

                              В а целом — совсем недавно была статья habr.com/post/423889 Моё разочарование в софте.
                              Где достаточно много народу возмущалось сложившейся ситуацией, грозно сотрясали воздух, и дружно вспоминали высокие деревья. Где теперь все эти люди???
                                0
                                Очевидно что, пример — это просто пример, там ведь Sleep на одну секунду. Но на счет синхронизации — не всегда стоит использовать системные event'ы, так как они обычно довольно дорогие. Если нужно уйти в сон на ~ микросекунду — лучше делать spin-lock.
                            +2
                            Да здесь всё логично. Компилятор не телепат и незнает ничего о ваших потоках. Ему нет дела когда ваш поток исполниться.
                            Так что можно спокойно пройтись по коду функции main и сократить код.
                            у вас в коде переменные выставляются в дефолное сосотояние
                            int x = 0;

                            дальше перед циклом идёт присваивание адреса
                            ptr = &x;

                            Учитывая что *ptr не изменяется в теле цикла — значит условие цикла это константное выражение и можно упростить.
                             *ptr==x  =>   *ptr==0   =>  true 

                            Поэтому цикл превращается в
                             while (true) { }


                              0
                              Неплохо было бы дизассемблировать код для проверки вашего предположения.
                                0
                                godbolt.org/z/Avf7QQ
                                Код получается такой:
                                main:
                                        subq    $24, %rsp
                                        movl    $ThreadProc(), %esi
                                        movq    $x, ptr(%rip)
                                        leaq    8(%rsp), %rdi
                                        call    std::thread::thread<void (&)()>(void (&)())
                                        movq    ptr(%rip), %rax
                                        movl    (%rax), %eax
                                        testl   %eax, %eax
                                        jne     .L29
                                .L28:
                                        jmp     .L28
                                .L29:
                                        cmpq    $0, 8(%rsp)
                                        jne     .L31
                                        xorl    %eax, %eax
                                        addq    $24, %rsp
                                        ret
                                .L31:
                                        call    std::terminate()

                                То есть как можно заметить, указатель сравнивается с 0 только в начале (подозреваю, что на случай, если main() будет вызван не как точка входа, а еще откуда-нибудь и глобальный 'x' перед этим был изменен — стандарт, судя по всему, такое не запрещает), а после у нас действительно начинается бесконечный цикл (.L28: jmp .L28).
                                Скомпилируйте то же самое с -O0 и увидите честный цикл с проверкой условия.
                              0
                              От компилятора данное поведение, думаю, не зависит — у всех так будет из-за того, что ptr не защищена каким-либо примитивом синхронизации.
                              И из-за любви к С++ только, замечу, что в коде нет thread.join() — даже если из цикла будет выход, программа упадет.
                                +1
                                Почему упадёт? После выхода из main() crt вызовет ExitProcess, а он, согласно документации MSDN, прежде всего прерывает выполнение всех потоков процесса.
                                  0
                                  Потому что перед выходом из main отработает деструктор thread. А вызов деструктора thread в состоянии joinable приводит к вызову std::terminate
                                    0
                                    Понятно, я на первый пример смотрел, на WinAPI
                                –1
                                Выше уже много написали про очевидность проблемы, но меня напрягает другое. То что язык C++ (по наследству от языка С) до сих пор по умолчанию «считает» что он выполняется на допотопной однопоточной машине со строгим порядком следования операций, полным доступом к памяти, без какого-либо SIMD, кэширования, контекста выполнения и пр. И вполне может быть что новое поколение программистов, не знакомое с бородатыми архитектурами ЭВМ 70-х, может недоумевать от такой модели.

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

                                Ладно, вообще я люблю C++, но согласитесь, доля истины в этом есть…
                                  0
                                  Недавно была статья, что проблема глубже, в самой архитектуре x86, которая скрывает многоконвеерный спекулятивный процессор с огромным кол-вом регистров за ширмой старого i386 1980-х годов. Поэтому, что c++, что rust, что java, всегда будут далеки от реального железа, потому что от реального железа их отделяет абстракция x86.
                                    0
                                    Проблема еще глубже и не только с архитектурой ххх86. На ARM-e все практически тоже самое.
                                    Проблема с теорией параллельных вычислений нерешенных в принципе. Пока не существует общего метода трансформации последовательных алгоритмов в эквивалентные параллельные, будет необходимость языках и архитектурах подобных с++ и х86 сориентированных в первую очередь на максимальную эффективность в одном потоке. (не уверен что такой метод изобретут, а если и изобретатут о возвращаемся опять в один поток, так проще формулировать)
                                    А в практической плоскости, для алгоритмов с известным распараллеливанием си подобные языки неплохо работают. Такие как glsl, opencl, cuda и прочие языки shader-ов. Более того, они все больше похожи на с++, чем были раньше.
                                      0
                                      По поводу языков шейдеров Вы прямо мне на больную мозоль наступили. Если для обычной графики они вполне ничего подходят (благодаря фиксированным частям графического конвейера и удачным абстракциям) то для вычислительных задач они отвратительны. Отвратительны!

                                      Модель однопоточного выполнения «натягивается» на строго многопоточное, да ещё и с неоднородным доступом к памяти. Ломаются все языковые концепции, которые работали для более примитивных архитектур, не слишком далеко ушедших от абстрактной машины Тьюринга. Внезапно и условный оператор уже не то чем кажется, и порядок выполнения не такой как в исходном коде, и стоимость (казалось бы) одних и тех же операций начинает отличаться в разы. А уж про отладку я вообще молчу. В итоге сгенерированный ассемблерный код оказывается абсолютно несопоставим с исходным. В отличие от x86 архитектуры где всё ещё поддерживается иллюзия последовательного выполнения, тут и близко такого нет.

                                      И весь этот C-синтаксис начинает вредить. Его использование для вычислительных шейдеров — скорее маркетинговый ход, чтобы привлечь закостенелых программистов у которых алгоритм приравнен к коду на C/C++, а вычислительное устройство — к машине Тьюринга. Крутится себе лента с программой, ЭВМ последовательно считывает и выполняет по одной операции — красота! Только неправда.
                                        0
                                        «Стоимость операций»
                                        Дело привычки. Если учесть, что архитектура GPU была (и сейчас) заточена под обработку графики, то ничего удивительного. В данном случае опыт на х86 скорее мешает, чем помогает.
                                        Мне лично не сильно мешает, хотя иногда забавно что битовые операции могу оказаться на порядки медленнее float. Мы избалованы современными процессорами и компиляторами.
                                        Хотя для эффективной программы, все равно в голове нужно держать архитектуру и особенности целевой платформы. Впрочем все зависит от класса решаемых задач. И общих методов для все задач не существует. Компилятор не может догадаться, что именно мы хотим получить и выбрать правильные структуры данных. Хотя бы по той причине, что он не имеет представления в каком контексте будет выполняться программа и какие данные она получит

                                  0
                                  Полезные ссылки.
                                  Implications of C++ Memory Model Discussions on the C Language 2005-08-26 (см. пример)
                                  Memory model (programming) — изучаем внимательно, втч References., например Threads and memory model for C++

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое