Почему код с несколькими вложенными циклами может сразу заканчиваться в GCC, а на VS - вечнее? - PullRequest
Новая
       32

Почему код с несколькими вложенными циклами может сразу заканчиваться в GCC, а на VS - вечнее?

5 голосов
/ 13 марта 2012 
long long r = 0;
long long k = 0;
for (; k < 9999999999999; k++) 
{
    for (long long i = 0; i < 9999999999999; i++) 
    {
        for (long long j = 0; j < 9999999999999; j++) 
        {
            r = (r + (i * j) % 100) % 47;
            if (r != 0) 
            {
                r++;
            }
        }
    }
 }

Этот код выполняется на i3Core за 0,000001 секунды в секунду, проверяется с помощью boost::timer::auto_cpu_timer на i7Core.

Но в Visual Studio 2010 он работает бесконечно долго.

Что не так с GCC или VS? GCC слишком много оптимизирует?

Ответы [ 2 ]

15 голосов
/ 13 марта 2012

Да, GCC оптимизирует этот код.

В частности, он знает, что вы не используете результат, поэтому он удаляет все его.
(Вы никогда не используете переменную r.)

Это называется Устранение мертвого кода .

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

cout << r << endl;

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

Я только что проверил это в VS2010 x64.Глядя на сборку, становится ясно, что VS2010 не может оптимизировать весь цикл .

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

Связанные и более подробно: Как GCC оптимизирует неиспользуемую переменную, увеличенную в цикле?

1 голос

Вы используете неопределенное поведение

Ваш код имеет неопределенное поведение на i * j на большинстве платформ, потому что: 

9999999999999 * 9999999999999 > 2^64

и long long равно 2^64 на большинстве платформ, поскольку аппаратная поддержка для 128-разрядных целых чисел просто слишком мала.

Благодаря GCC -O3 за указание на это в предупреждении: можно предположить, что UB не происходит, и выполнить цикл меньшераз.См. Также: Почему этот цикл выдает «предупреждение: итерация 3u вызывает неопределенное поведение» и выводит более 4 строк?

Так что может произойти все что угодно.

Давайте декомпилируем его, чтобы увидеть, что на самом деле происходит

GCC 4.8: 

gcc -c -g -std=c99 -O0 a.c
objudmp -S a.o

Вывод: 

a.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <main>:
int main() {
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
    long long r = 0;
   4:   48 c7 45 e0 00 00 00    movq   $0x0,-0x20(%rbp)
   b:   00 
    long long k = 0;
   c:   48 c7 45 e8 00 00 00    movq   $0x0,-0x18(%rbp)
  13:   00 
    for (; k < 9999999999999; k++) 
  14:   e9 f8 00 00 00          jmpq   111 <main+0x111>
    {
        for (long long i = 0; i < 9999999999999; i++) 
  19:   48 c7 45 f0 00 00 00    movq   $0x0,-0x10(%rbp)
  20:   00 
  21:   e9 d2 00 00 00          jmpq   f8 <main+0xf8>
        {
            for (long long j = 0; j < 9999999999999; j++) 
  26:   48 c7 45 f8 00 00 00    movq   $0x0,-0x8(%rbp)
  2d:   00 
  2e:   e9 ac 00 00 00          jmpq   df <main+0xdf>
            {
                r = (r + (i * j) % 100) % 47;
  33:   48 8b 45 f0             mov    -0x10(%rbp),%rax
  37:   48 0f af 45 f8          imul   -0x8(%rbp),%rax
  3c:   48 89 c1                mov    %rax,%rcx
  3f:   48 ba 0b d7 a3 70 3d    movabs $0xa3d70a3d70a3d70b,%rdx
  46:   0a d7 a3 
  49:   48 89 c8                mov    %rcx,%rax
  4c:   48 f7 ea                imul   %rdx
  4f:   48 8d 04 0a             lea    (%rdx,%rcx,1),%rax
  53:   48 c1 f8 06             sar    $0x6,%rax
  57:   48 89 c2                mov    %rax,%rdx
  5a:   48 89 c8                mov    %rcx,%rax
  5d:   48 c1 f8 3f             sar    $0x3f,%rax
  61:   48 29 c2                sub    %rax,%rdx
  64:   48 89 d0                mov    %rdx,%rax
  67:   48 c1 e0 02             shl    $0x2,%rax
  6b:   48 01 d0                add    %rdx,%rax
  6e:   48 8d 14 85 00 00 00    lea    0x0(,%rax,4),%rdx
  75:   00 
  76:   48 01 d0                add    %rdx,%rax
  79:   48 c1 e0 02             shl    $0x2,%rax
  7d:   48 29 c1                sub    %rax,%rcx
  80:   48 89 ca                mov    %rcx,%rdx
  83:   48 8b 45 e0             mov    -0x20(%rbp),%rax
  87:   48 8d 0c 02             lea    (%rdx,%rax,1),%rcx
  8b:   48 ba 99 5c 41 4c ae    movabs $0x572620ae4c415c99,%rdx
  92:   20 26 57 
  95:   48 89 c8                mov    %rcx,%rax
  98:   48 f7 ea                imul   %rdx
  9b:   48 c1 fa 04             sar    $0x4,%rdx
  9f:   48 89 c8                mov    %rcx,%rax
  a2:   48 c1 f8 3f             sar    $0x3f,%rax
  a6:   48 29 c2                sub    %rax,%rdx
  a9:   48 89 d0                mov    %rdx,%rax
  ac:   48 89 45 e0             mov    %rax,-0x20(%rbp)
  b0:   48 8b 55 e0             mov    -0x20(%rbp),%rdx
  b4:   48 89 d0                mov    %rdx,%rax
  b7:   48 01 c0                add    %rax,%rax
  ba:   48 01 d0                add    %rdx,%rax
  bd:   48 c1 e0 04             shl    $0x4,%rax
  c1:   48 29 d0                sub    %rdx,%rax
  c4:   48 29 c1                sub    %rax,%rcx
  c7:   48 89 c8                mov    %rcx,%rax
  ca:   48 89 45 e0             mov    %rax,-0x20(%rbp)
                if (r != 0) 
  ce:   48 83 7d e0 00          cmpq   $0x0,-0x20(%rbp)
  d3:   74 05                   je     da <main+0xda>
                {
                    r++;
  d5:   48 83 45 e0 01          addq   $0x1,-0x20(%rbp)
    long long k = 0;
    for (; k < 9999999999999; k++) 
    {
        for (long long i = 0; i < 9999999999999; i++) 
        {
            for (long long j = 0; j < 9999999999999; j++) 
  da:   48 83 45 f8 01          addq   $0x1,-0x8(%rbp)
  df:   48 b8 fe 9f 72 4e 18    movabs $0x9184e729ffe,%rax
  e6:   09 00 00 
  e9:   48 39 45 f8             cmp    %rax,-0x8(%rbp)
  ed:   0f 8e 40 ff ff ff       jle    33 <main+0x33>
int main() {
    long long r = 0;
    long long k = 0;
    for (; k < 9999999999999; k++) 
    {
        for (long long i = 0; i < 9999999999999; i++) 
  f3:   48 83 45 f0 01          addq   $0x1,-0x10(%rbp)
  f8:   48 b8 fe 9f 72 4e 18    movabs $0x9184e729ffe,%rax
  ff:   09 00 00 
 102:   48 39 45 f0             cmp    %rax,-0x10(%rbp)
 106:   0f 8e 1a ff ff ff       jle    26 <main+0x26>
int main() {
    long long r = 0;
    long long k = 0;
    for (; k < 9999999999999; k++) 
 10c:   48 83 45 e8 01          addq   $0x1,-0x18(%rbp)
 111:   48 b8 fe 9f 72 4e 18    movabs $0x9184e729ffe,%rax
 118:   09 00 00 
 11b:   48 39 45 e8             cmp    %rax,-0x18(%rbp)
 11f:   0f 8e f4 fe ff ff       jle    19 <main+0x19>
 125:   b8 00 00 00 00          mov    $0x0,%eax
                    r++;
                }
            }
        }
    }
}
 12a:   5d                      pop    %rbp
 12b:   c3                      retq

, поэтому все циклы кажутся присутствующими.

С -O3: 

0000000000000000 <main>:
   0:   31 c0                   xor    %eax,%eax
   2:   c3                      retq

, поэтому он был явно оптимизирован.Ничто в стандарте C не препятствует этой оптимизации, поэтому GCC делает это.

Если мы добавим printf("%lld", r); в конце, как упомянуто в Mystical, это займет вечность даже с -O3 и сгенерированным оптимизированным кодомпочти такой же, как и неоптимизированный.

Для бесконечных циклов становится интереснее: Разрешено ли компиляторам устранять бесконечные циклы?

Как предотвратить возникновение: Как запретить GCC оптимизировать цикл ожидания занятости?

...