Почему мой индекс массива быстрее указателя
Почему индекс массива быстрее указателя?
Не предполагается ли указатель быстрее, чем индекс массива?
** я использовал time.h clock_t для тестирования двух функций, каждый цикл 2 миллиона раз.
Pointer time : 0.018995
Index time : 0.017864
void myPointer(int a[], int size)
{
int *p;
for(p = a; p < &a[size]; p++)
{
*p = 0;
}
}
void myIndex(int a[], int size)
{
int i;
for(i = 0; i < size; i++)
{
a[i] = 0;
}
}
Ответы
Ответ 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 в оптимизированном коде должна быть идентичной.
FYI, если граница массива известна во время компиляции, например, int A[constant_expression], тогда обращения к этому массиву могут быть намного быстрее, чем указатель. Это связано главным образом с тем, что доступ к массиву свободен от анализатора указателей. Компиляторы могут отлично вычислять информацию о зависимостях вычислений и доступов в массиве фиксированного размера, поэтому он может выполнять расширенные оптимизации, включая автоматическую распараллеливание.
Однако, если вычисления основаны на указателях, компиляторы должны выполнить анализ указателей для дальнейшей оптимизации, что в значительной степени ограничено в C/С++. Обычно он заканчивается консервативными результатами анализа указателей и дает несколько возможностей оптимизации.
Ответ 2
Это может быть сравнение в цикле for, которое вызывает разницу. Условие терминации проверяется на каждой итерации, и ваш пример "указатель" имеет несколько более сложное условие завершения (с адресом & a [size]). Поскольку & a [размер] не изменяется, вы можете попробовать установить его в переменную, чтобы не перерасчитывать ее на каждой итерации цикла.
Ответ 3
Разрывы в массиве p[i] составляют *(p + i). Компиляторы используют инструкции, которые выполняют математику + разыменование в 1 или 2 циклах (например, инструкцию x86 LEA) для оптимизации скорости.
С контуром указателя он разделяет доступ и смещение на отдельные части, и компилятор не может его оптимизировать.
Ответ 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-битного процессора, чем для вычисления адреса назначения с некоторого смещения. Но я не уверен.
EDIT:. Это действительно связано с 64-битной архитектурой, потому что тот же код с одинаковыми флагами компиляции не показывает реальной разницы в производительности в 32-разрядной системе.
Ответ 5
Время так близко друг к другу, что, если вы делали их неоднократно, вы не можете видеть большую часть разницы. Оба сегмента кода составляют одну и ту же сборку. По определению нет разницы.
Ответ 6
Я бы предложил запустить каждый цикл 200 миллионов раз, а затем запустить каждый цикл 10 раз и выполнить самые быстрые измерения. Это будет учитывать эффекты от планирования ОС и так далее.
Я бы предложил вам разобрать код для каждого цикла.
Ответ 7
Похоже, что индексное решение может сохранить несколько инструкций с помощью сравнения в цикле for.
Ответ 8
Доступ к данным через индекс массива или указатель в точности эквивалентен. Пройдите через следующую программу со мной...
Есть цикл, который продолжается до 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 <[email protected]>
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 <[email protected]>
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)
