Почему мой индекс массива быстрее, чем указатель

Question

Почему индекс массива быстрее указателя?Разве указатель не должен быть быстрее индекса массива?

** я использовал time.h clock_t для проверки двух функций, каждая из которых выполнялась 2 миллиона раз.

Answer 1

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

Индекс массива в вашем контексте (граница массива неизвестна) в точности идентична операции с указателем. С точки зрения компиляторов, это просто другое выражение арифметики указателей. Вот пример оптимизированного кода x86 в Visual Studio 2010 с полной оптимизацией и без встроенного .

     3: void myPointer(int a[], int size)
     4: {
013E1800  push        edi  
013E1801  mov         edi,ecx  
     5:      int *p;
     6:      for(p = a; p < &a[size]; p++)
013E1803  lea         ecx,[edi+eax*4]  
013E1806  cmp         edi,ecx  
013E1808  jae         myPointer+15h (13E1815h)  
013E180A  sub         ecx,edi  
013E180C  dec         ecx  
013E180D  shr         ecx,2  
013E1810  inc         ecx  
013E1811  xor         eax,eax  
013E1813  rep stos    dword ptr es:[edi]  
013E1815  pop         edi  
     7:      {
     8:          *p = 0;
     9:      }
    10: }
013E1816  ret 

    13: void myIndex(int a[], int size)
    14: {
    15:      int i;
    16:      for(i = 0; i < size; i++)
013E17F0  test        ecx,ecx  
013E17F2  jle         myIndex+0Ch (13E17FCh)  
013E17F4  push        edi  
013E17F5  xor         eax,eax  
013E17F7  mov         edi,edx  
013E17F9  rep stos    dword ptr es:[edi]  
013E17FB  pop         edi  
    17:      {
    18:          a[i] = 0;
    19:      }
    20: }
013E17FC  ret 

На первый взгляд, myIndex выглядит быстрее, потому что количество инструкций меньше, однако две части кода по сути одинаковы. Оба в конечном итоге используют rep stos, что является повторяющейся (циклической) инструкцией x86. Единственное отличие заключается в вычислении границы цикла. Цикл for в myIndex имеет счетчик отключений size как есть (т.е. вычисление не требуется). Но для myPointer нужны некоторые вычисления, чтобы получить счетчик циклов for. Это единственная разница. Важные операции цикла точно такие же. Таким образом, разница незначительна.

Подводя итог, производительность myPointer и myIndex в оптимизированном коде должна быть одинаковой.

---

К вашему сведению, если граница массива известна во время компиляции, например, int A[constant_expression], тогда доступ к этому массиву может быть намного быстрее, чем указатель. Это происходит главным образом потому, что доступ к массиву свободен от проблемы анализа указателей . Компиляторы могут отлично вычислять информацию о зависимостях вычислений и обращений к массиву фиксированного размера, поэтому могут выполнять расширенную оптимизацию, включая автоматическое распараллеливание.

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

Answer 2

Это может быть сравнение в цикле for, которое вызывает разницу. Условие завершения проверяется на каждой итерации, и ваш пример «указателя» имеет несколько более сложное условие завершения (принимая адрес & a [size]). Поскольку & a [размер] не изменяется, вы можете попробовать установить его в переменную, чтобы избежать его пересчета на каждой итерации цикла.

Answer 3

Разыменование массива p[i] равно *(p + i). Компиляторы используют инструкции, которые выполняют математические операции + разыменование в 1 или 2 циклах (например, инструкция LEA x86), чтобы оптимизировать скорость.

С помощью цикла указателя он разделяет доступ и смещение на отдельные части, и компилятор не может его оптимизировать.

Answer 4

Упс, на моей 64-битной системе результаты совсем другие.Я понял, что это

 int i;

 for(i = 0; i < size; i++)
 {
     *(a+i) = 0;
 }

примерно в 100 раз!медленнее, чем

 int i;
 int * p = a;

 for(i = 0; i < size; i++)
 {
     *(p++) = 0;
 }

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

РЕДАКТИРОВАТЬ:
Это действительно имеет отношение к 64-битной архитектуре, потому что тот же код с одинаковыми флагами компиляции не показывает реальной разницы в производительностив 32-битной системе.

Answer 5

Оптимизация компилятора - сопоставление с образцом.

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

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

---

Если вам действительно любопытно, попробуйте скомпилировать код с помощью gcc -S -Os, это даст наиболее читаемый, но оптимизированный код ассемблера. На ваших двух функциях я получаю следующий ассемблер с этим:

pointer code:
.L2:
    cmpq    %rax, %rdi
    jnb .L5
    movl    $0, (%rdi)
    addq    $4, %rdi
    jmp .L2
.L5:

index code:
.L7:
    cmpl    %eax, %esi
    jle .L9
    movl    $0, (%rdi,%rax,4)
    incq    %rax
    jmp .L7
.L9:

Различия незначительны, но действительно могут вызвать разницу в производительности, главное, что разница между использованием addq и incq может быть значительной.

Answer 6

Это очень сложная вещь, потому что компиляторы очень хорошо оптимизируют эти вещи.Тем не менее, лучше предоставить компилятору как можно больше информации, поэтому в этом случае я бы посоветовал использовать std :: fill и позволить компилятору выбирать.

Но ... Если вы хотите вникнуть в детали

a) Процессоры обычно дают указатель + значение бесплатно, например: mov r1, r2 (r3).
b)Это означает, что для операции с индексом требуется всего лишь: mul r3, r1, size
Это всего один дополнительный цикл на цикл.
c) ЦП часто предоставляют интервалы задержки / задержки, то есть вы часто можете скрывать операции с одним циклом.

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

Answer 7

Доступ к данным через индекс массива или указатель в точности эквивалентен. Пройдите со мной нижеприведенную программу ...

Есть цикл, который продолжается до 100 раз, но когда мы видим код дизассемблирования, то есть данные, к которым мы обращаемся, имеют наименьшую сопоставимость инструкций для доступа через массив Index

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

int a[100];
fun1(a,100);
fun2(&a[0],5);
}
void fun1(int a[],int n)
{
int i;
for(i=0;i<=99;i++)
{
a[i]=0;
printf("%d\n",a[i]);
}
}
void fun2(int *p,int n)
{
int i;
for(i=0;i<=99;i++)
{
*p=0;
printf("%d\n",*(p+i));
}
}


disass fun1
Dump of assembler code for function fun1:
   0x0804841a <+0>: push   %ebp
   0x0804841b <+1>: mov    %esp,%ebp
   0x0804841d <+3>: sub    $0x28,%esp`enter code here`
   0x08048420 <+6>: movl   $0x0,-0xc(%ebp)
   0x08048427 <+13>:    jmp    0x8048458 <fun1+62>
   0x08048429 <+15>:    mov    -0xc(%ebp),%eax
   0x0804842c <+18>:    shl    $0x2,%eax
   0x0804842f <+21>:    add    0x8(%ebp),%eax
   0x08048432 <+24>:    movl   $0x0,(%eax)
   0x08048438 <+30>:    mov    -0xc(%ebp),%eax
   0x0804843b <+33>:    shl    $0x2,%eax
   0x0804843e <+36>:    add    0x8(%ebp),%eax
   0x08048441 <+39>:    mov    (%eax),%edx
   0x08048443 <+41>:    mov    $0x8048570,%eax
   0x08048448 <+46>:    mov    %edx,0x4(%esp)
   0x0804844c <+50>:    mov    %eax,(%esp)
   0x0804844f <+53>:    call   0x8048300 <printf@plt>
   0x08048454 <+58>:    addl   $0x1,-0xc(%ebp)
   0x08048458 <+62>:    cmpl   $0x63,-0xc(%ebp)
   0x0804845c <+66>:    jle    0x8048429 <fun1+15>
   0x0804845e <+68>:    leave  
   0x0804845f <+69>:    ret    
End of assembler dump.
(gdb) disass fun2
Dump of assembler code for function fun2:
   0x08048460 <+0>: push   %ebp
   0x08048461 <+1>: mov    %esp,%ebp
   0x08048463 <+3>: sub    $0x28,%esp
   0x08048466 <+6>: movl   $0x0,-0xc(%ebp)
   0x0804846d <+13>:    jmp    0x8048498 <fun2+56>
   0x0804846f <+15>:    mov    0x8(%ebp),%eax
   0x08048472 <+18>:    movl   $0x0,(%eax)
   0x08048478 <+24>:    mov    -0xc(%ebp),%eax
   0x0804847b <+27>:    shl    $0x2,%eax
   0x0804847e <+30>:    add    0x8(%ebp),%eax
   0x08048481 <+33>:    mov    (%eax),%edx
   0x08048483 <+35>:    mov    $0x8048570,%eax
   0x08048488 <+40>:    mov    %edx,0x4(%esp)
   0x0804848c <+44>:    mov    %eax,(%esp)
   0x0804848f <+47>:    call   0x8048300 <printf@plt>
   0x08048494 <+52>:    addl   $0x1,-0xc(%ebp)
   0x08048498 <+56>:    cmpl   $0x63,-0xc(%ebp)
   0x0804849c <+60>:    jle    0x804846f <fun2+15>
   0x0804849e <+62>:    leave  
   0x0804849f <+63>:    ret    
End of assembler dump.
(gdb) 

Answer 8

Похоже, что решение для индекса может сохранить несколько инструкций со сравнением в цикле for.

Answer 9

Я бы предложил запустить каждый цикл 200 миллионов раз, а затем запустить каждый цикл 10 раз и выполнить самое быстрое измерение. Это исключит эффекты от планирования ОС и так далее.

Я бы тогда предложил вам разобрать код для каждого цикла.

Answer 10

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