Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, история, 8 лет назад, По-русски

Привет!

Знатокам C++ это конечно всё очевидно и естественно, а вот я как-то привык, что знаковое переполнение в С++ не приводит к настоящему неопределенному поведению на конкретной платформе. То есть понятно, что в зависимости от big-endianness/little-endian результат может получиться разным.

Случайно нашел пример забавного поведения:

#include <iostream>
int main()
{
    for (int i = 0; i < 300; i++)
        std::cout << i << " " << i * 12345678 << std::endl;
}

Этот код при компиляции с -O2 в современном g++ приводит к бесконечному циклу. Неожиданно, правда?

Теги g++, ub
  • Проголосовать: нравится
  • +257
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +117 Проголосовать: не нравится

Полагаю, ход рассуждений компилятора примерно такой:

  1. Раз внутри цикла вычисляется i * 12345678, то это выражение никогда не переполняется. Значит, внутри тела цикла |i| ≤ 173.
  2. Раз внутри тела цикла i ≤ 173, то после выполнения i++ всегда верно i ≤ 174.
  3. А раз i ≤ 174, то условие цикла всегда выполняется.
  4. А раз так, то можно это условие заменить на true.
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -35 Проголосовать: не нравится

    Я бы назвал это багом — компилятор слишком много на себя берёт.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

      Это не баг, это — неопределенное поведение, при котором компилятор вправе делать все_что_угодно.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится -12 Проголосовать: не нравится

        Должно быть хоть какое-то логичное ограничение, где это самое неопределённое поведение может вылезти. Получается, что из-за undefined behaviour где-то, где его результат ни на что не влияет (кроме вывода на экран в данном случае), undefined behaviour распространяется на другой участок кода, где всё как раз прекрасно defined. Так можно докатится до ситуации, где компилятор, заметив где-то потенциальное переполнение просто рубит всё программу и заменяет одним NOP'ом. Очень эффективная оптимизация — если что-то может не работать, зачем вообще это делать.

        Хорошо, я согласен, что формально требования стандарта выполнены. Всё равно остаётся вопрос:

        Если оптимизация настолько умна, то почему она режет код вместо того, чтобы выдать warning о потенциальном переполнении?

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится -15 Проголосовать: не нравится

            AlexDmitriev,

            Ещё один вопрос — я с трудом представляю ситуацию, когда эта оптимизация (насколько я понял — aggressive-loop-optimization) может быть полезной. Точнее не представляю. Это либо кривой код, который лучше бы исправить, либо просто ошибка. Нормальный код, которому может принести пользу такая оптимизация... Не знаю, разве что параметризированный шаблон приходит в голову, где конкретный параметр шаблона позволяет "схлопнуть" цикл, которй может понадобится в общем случае. Мне кажется эта оптимизация evil :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    Хорошо, когда редактор умный

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Или когда оптимизатор тупой — на MSVC 2013 никаких проблем :)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +43 Проголосовать: не нравится

        Да на MSVC вообще не бывает проблем, я помню только одну, о которой постили на CF, а о багах g++ упоминали точно не менее пяти раз. А еще здесь минусуют за упоминание этого факта :)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      А так?

      #include <iostream>
      #include <set>
      int main()
      {
          for (int i = 0; i < 300; i++)
          {
              std::set<int> s;
              s.insert(i * 12345678);
              std::cout << i << " " << std::endl;
          }
      }
      
    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

      Это не редактор умный, а g++.

      Если будете из консоли компилировать код с -Wall -Wextra, то в точности те же самые варнинги получите.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Я компилирую без -Wall -Wextra, и тем не менее получил уведомление о возможной ошибке, так что таки редактор.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

          Прошу прощения, речь не в -Wall и -Wextra, просто я их использую всегда. Дейсвительно, и без них те же варнинги g++ даёт.

          Поскольку вывод g++ совпадает с предупреждениями Вашего редактора, очевидно, что кто-то у кого-то эти варнинги заимствует.

          Очевидно, что это не g++.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Что я делаю не так? Мой компилятор молчит без дополнительных флагов, а редактор всё равно подсказывает

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Возможно у вас просто несколько разных g++-ов стоит.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                У меня один g++. Скорее у вашего g++ выставлен флаг -Wall, или ему подобные, поумолчанию — сделайте g++ -dumpspecs или посмотрите по переменным окружения

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

Last sentence is written in russian, on eng interface :(

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This is so strange! I tested it on my machine, and it does indeed run infinitely.

It's interesting I believe. Why does that happen?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +117 Проголосовать: не нравится

    There is russian explanation from yeputons, so I am just translating:

    -Waggresive-loop-optimization option is turned on by -O2,

    Optimizer infers that because i*12345678 should never overflow, i will never be higher then 173, which means that i < 300 is always true, so it replaces condition "i < 300" with true.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +52 Проголосовать: не нравится

      strange, if you replace endl with '\n' , the code no longer runs infinitely

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        My take on this is that std::endl flushes cache, so the output operation happens in the cycle, so output is produced within the cycle and is expected to conform to language rules, which means no overflow is expected and optimization works.

        If do you "\n", cache is flushed after the cycle ends, so there is no external output within the cycle, which somehow turns off optimization.

        Strange indeed. It probably takes a guy from g++ development team to tell exactly what happens.

»
8 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

By the way, it looks like it's possible to disable that behavior in GCC with a special key: -fno-strict-overflow

»
8 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Это баян, конечно.

Вот ещё интересный пример:

int arr[4];

bool in_array(int a) {
	for(int i = 0; i <= 4; i++)
		if (arr[i] == a)
			return true;
	return false;
}

Функция всегда возвращает true

http://ideone.com/z9npmc

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Объясните почему?)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      Компилятор имеет право считать что UB в коде нет.

      Если i доходит до 4, то получим UB (выход за пределы массива). Значит i не дойдет до 4. Значит раньше мы вышли с return true.

      Следовательно заменяет весь код на return true

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    clang 3.9.0 не воспроизводится.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

    А ещё есть почти легендарный код, который своим выполнением "опровергает" великую теорему ферма.

    https://habrahabr.ru/post/229963/

    int fermat (void)
    {
      const int MAX = 1000;
      int a=1,b=1,c=1;
      while (1) {
        if (((a*a*a) == ((b*b*b)+(c*c*c)))) return 1;
        a++;
        if (a>MAX) {
          a=1;
          b++;
        }
        if (b>MAX) {
          b=1;
          c++;
        }      
        if (c>MAX) {
          c=1;
        }
      }
      return 0;
    }
    
    #include <stdio.h>
    
    int main (void)
    {
      if (fermat()) {
        printf ("Fermat's Last Theorem has been disproved.\n");
      } else {
        printf ("Fermat's Last Theorem has not been disproved.\n");
      }
      return 0;
    }
    
    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +27 Проголосовать: не нравится

      И он неверен, по крайней мере в C11:

      C11 clarifies the answer to this question, in the draft C11 standard section 6.8.5 Iteration statements added the following paragraph:

      An iteration statement whose controlling expression is not a constant expression,156) that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.157)

      and footnote 157 says:

      This is intended to allow compiler transformations such as removal of empty loops even when termination cannot be proven.

      whose controlling expression is not a constant expression !!!!!!!!

      Верный код есть в статье из которой и сделали статью на Хабре, понятия не идею зачем автор изменил код.

      const int MAX = 1000; int a=1,b=1,c=1; while ((c*c*c) != ((a*a*a)+(b*b*b))) { a++; if (a>MAX) { a=1; b++; } if (b>MAX) { b=1; c++; } if (c>MAX) { c=1; } }

      Здесь не константа в условии.

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да, вы правы.

        И это касается не только с++11, но и других стандартов (например ansi, c11, c99, c++03, ...)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Вы говорили про c++11, а процитировали про c11

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Что такое 1000?

»
8 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

And sometimes such advanced optimizations even lead to vulnerabilities: http://lwn.net/Articles/342330/

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

I used "\n" instead of endl and got this:

a.cpp: In function ‘int main()’:
a.cpp:5:38: warning: iteration 174u invokes undefined behavior [-Waggressive-loop-optimizations]
         std::cout << i << " " << i * 12345678 << "\n";
                                      ^
a.cpp:4:5: note: containing loop
     for (int i = 0; i < 300; i++)
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Then this must me a warning bug. Initially whan I was reading this post I thought that gcc does not produce any warnings about that, but it is not good that warning is produced in one case and is not produced in another case.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I confirmed the difference in warning reporting between std::endl and "\n" with GCC 4.8.1 and 4.8.2 . The bug seems to be fixed in GCC >= 4.9.0, I couldn't test if the fix is included in GCC 4.8.3 — 4.8.5 .

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is another example of breaking the code with higher optimization when the code is not completely correct, Nicely explained as well. http://stackoverflow.com/questions/36626810/g-optimization-breaks-for-loops