границы массива проверить оптимизацию в для цикла

Question

 var ar = new int[500000000]; 

     var sw = new Stopwatch(); 
     sw.Start(); 

     var length = ar.Length; 
     for (var i = 0; i < length; i++) 
     { 
      if (ar[i] == 0); 
     } 

     sw.Stop(); 

sw.ElapsedMilliseconds: ~ 2930ms

 var ar = new int[500000000]; 

     var sw = new Stopwatch(); 
     sw.Start(); 

     for (var i = 0; i < ar.Length; i++) 
     { 
      if (ar[i] == 0); 
     } 

     sw.Stop(); 

sw.ElapsedMilliseconds: ~ 3520ms

Win8x64, VS12, .NET4.5, сборки выпуска, Msgstr "Оптимизировать код".

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

Answer 1

Я также использую Win8 x64, .NET 4.5, билд Release, вне отладчика (это важный); Я получаю:

0: 813ms vs 421ms 
1: 439ms vs 420ms 
2: 440ms vs 420ms 
3: 431ms vs 429ms 
4: 433ms vs 427ms 
5: 424ms vs 437ms 
6: 427ms vs 434ms 
7: 430ms vs 432ms 
8: 432ms vs 435ms 
9: 430ms vs 430ms 
10: 427ms vs 418ms 
11: 422ms vs 421ms 
12: 434ms vs 420ms 
13: 439ms vs 425ms 
14: 426ms vs 429ms 
15: 426ms vs 426ms 
16: 417ms vs 432ms 
17: 442ms vs 425ms 
18: 420ms vs 429ms 
19: 420ms vs 422ms 

Первый платит/«фьюжн» стоимость JIT, но в целом это примерно то же самое (некоторые в каждой колонке выглядят быстрее, но в целом не так много, чтобы говорить о).

using System; 
using System.Diagnostics; 
static class Program 
{ 
    static void Main() 
    { 
     var ar = new int[500000000]; 

     for (int j = 0; j < 20; j++) 
     { 
      var sw = Stopwatch.StartNew(); 
      var length = ar.Length; 
      for (var i = 0; i < length; i++) 
      { 
       if (ar[i] == 0) ; 
      } 

      sw.Stop(); 
      long hoisted = sw.ElapsedMilliseconds; 

      sw = Stopwatch.StartNew(); 
      for (var i = 0; i < ar.Length; i++) 
      { 
       if (ar[i] == 0) ; 
      } 
      sw.Stop(); 
      long direct = sw.ElapsedMilliseconds; 

      Console.WriteLine("{0}: {1}ms vs {2}ms", j, hoisted, direct); 
     } 
    } 
} 

Answer 2

вы вызываете недвижимости на второй так будет медленнее ar.Length

Answer 3

Я думаю, что ответ заключается в том, что сборщик мусора работает и меняет ваши тайминги.

Отказ от ответственности: Я не вижу весь контекст кода OP, потому что вы не опубликовали компилируемый пример; Я предполагаю, что вы перераспределяете массив, а не повторно используете его. Если нет, то это не правильный ответ!

Рассмотрим этот код:

using System; 
using System.Diagnostics; 

namespace Demo 
{ 
    internal class Program 
    { 
     private static void Main(string[] args) 
     { 
      var ar = new int[500000000]; 
      test1(ar); 
      //ar = new int[500000000]; // Uncomment this line. 
      test2(ar); 
     } 

     private static void test1(int[] ar) 
     { 
      var sw = new Stopwatch(); 
      sw.Start(); 

      var length = ar.Length; 
      for (var i = 0; i < length; i++) 
      { 
       if (ar[i] == 0); 
      } 

      sw.Stop();     
      Console.WriteLine("test1 took " + sw.Elapsed); 
     } 

     private static void test2(int[] ar) 
     { 
      var sw = new Stopwatch(); 
      sw.Start(); 

      for (var i = 0; i < ar.Length; i++) 
      { 
       if (ar[i] == 0); 
      } 

      sw.Stop(); 
      Console.WriteLine("test2 took " + sw.Elapsed); 
     } 
    } 
} 

На моей системе он печатает:

test1 took 00:00:00.6643788 
test2 took 00:00:00.3516378 

Если я раскомментировать строку, отмеченную // Uncomment this line. то тайминги изменится:

test1 took 00:00:00.6615819 
test2 took 00:00:00.6806489 

Этом потому что GC собирает предыдущий массив.

[EDIT] Для того, чтобы избежать затрат на запуск JIT, я поставил весь тест в петлю:

for (int i = 0; i < 8; ++i) 
{ 
    test1(ar); 
    ar = new int[500000000]; // Uncomment this line. 
    test2(ar); 
} 

И тогда мои результаты с выделением второго массива закомментированного являются:

test1 took 00:00:00.6437912 
test2 took 00:00:00.3534027 
test1 took 00:00:00.3401437 
test2 took 00:00:00.3486296 
test1 took 00:00:00.3470775 
test2 took 00:00:00.3675475 
test1 took 00:00:00.3501221 
test2 took 00:00:00.3549338 
test1 took 00:00:00.3427057 
test2 took 00:00:00.3574063 
test1 took 00:00:00.3566458 
test2 took 00:00:00.3462722 
test1 took 00:00:00.3430952 
test2 took 00:00:00.3464017 
test1 took 00:00:00.3449196 
test2 took 00:00:00.3438316 

И с включением второго массива:

test1 took 00:00:00.6572665 
test2 took 00:00:00.6565778 
test1 took 00:00:00.3576911 
test2 took 00:00:00.6910897 
test1 took 00:00:00.3464013 
test2 took 00:00:00.6638542 
test1 took 00:00:00.3548638 
test2 took 00:00:00.6897472 
test1 took 00:00:00.4464020 
test2 took 00:00:00.7739877 
test1 took 00:00:00.3835624 
test2 took 00:00:00.8432918 
test1 took 00:00:00.3496910 
test2 took 00:00:00.6471341 
test1 took 00:00:00.3486505 
test2 took 00:00:00.6527160 

Обратите внимание, что test2 последовательно занимает больше времени из-за GC.

К сожалению, GC делает результаты синхронизации довольно бессмысленными.

Например, если изменить тестовый код для этого:

for (int i = 0; i < 8; ++i) 
{ 
    var ar = new int[500000000]; 
    GC.Collect(); 
    test1(ar); 
    //ar = new int[500000000]; // Uncomment this line. 
    test2(ar); 
} 

С линией закомментированной я получаю:

test1 took 00:00:00.6354278 
test2 took 00:00:00.3464486 
test1 took 00:00:00.6672933 
test2 took 00:00:00.3413958 
test1 took 00:00:00.6724916 
test2 took 00:00:00.3530412 
test1 took 00:00:00.6606178 
test2 took 00:00:00.3413083 
test1 took 00:00:00.6439316 
test2 took 00:00:00.3404499 
test1 took 00:00:00.6559153 
test2 took 00:00:00.3413563 
test1 took 00:00:00.6955377 
test2 took 00:00:00.3364670 
test1 took 00:00:00.6580798 
test2 took 00:00:00.3378203 

И это раскомментирована:

test1 took 00:00:00.6340203 
test2 took 00:00:00.6276153 
test1 took 00:00:00.6813719 
test2 took 00:00:00.6264782 
test1 took 00:00:00.6927222 
test2 took 00:00:00.6269447 
test1 took 00:00:00.7010559 
test2 took 00:00:00.6262000 
test1 took 00:00:00.6975080 
test2 took 00:00:00.6457846 
test1 took 00:00:00.6796235 
test2 took 00:00:00.6341214 
test1 took 00:00:00.6823508 
test2 took 00:00:00.6455403 
test1 took 00:00:00.6856985 
test2 took 00:00:00.6430923 

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

Answer 4

Я исследовал это еще немного, и было очень сложно сделать контрольный показатель, который фактически показывает эффект оптимизации устранения ограничений границ.

Первые некоторые проблемы со старым эталоном:

• разборки показали, что JIT компилятор возможность оптимизировать первую версию, а. Это было для меня неожиданностью, но разборки не лгут. Это, конечно, полностью поражает цель этого теста. Исправление: взять длину как аргумент функции.
• Массив слишком большой, что означает промахи в кеше, которые добавляют к нашему сигналу много шума. Исправление: использовать короткий массив, но цикл над ним несколько раз.

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

_loop: mov eax, [somewhere + index] 
     add index, 4 
     cmp index, end 
     jl _loop 

Там нет существенной разницы во времени выполнения, потому что нет существенной разницы в части генерируемого кода, который имеет значение больше всего.