В C доступ к индексу массива происходит быстрее или быстрее достигается с помощью указателя? Чем быстрее я имею в виду, тем меньше циклов синхронизации. Массив не является постоянным массивом.
В C, доступ к моему индексу массива быстрее или доступ по указателю быстрее?
Ответ 1
templatetypedef подвел итог. Чтобы добавить поддержку в его ответ. Возьмите эти примерные функции:
unsigned int fun1 ( unsigned int *x )
{
unsigned int ra,rb;
rb=0;
for(ra=0;ra<1000;ra++) rb+=*x++;
return(rb);
}
unsigned int fun2 ( unsigned int *x )
{
unsigned int ra,rb;
rb=0;
for(ra=0;ra<1000;ra++) rb+=x[ra];
return(rb);
}
Теперь gcc произвела это:
00000000 fun1:
0: e52d4004 push {r4} ; (str r4, [sp, #-4]!)
4: e1a03000 mov r3, r0
8: e2804efa add r4, r0, #4000 ; 0xfa0
c: e3a00000 mov r0, #0
10: e1a02003 mov r2, r3
14: e492c004 ldr ip, [r2], #4
18: e5931004 ldr r1, [r3, #4]
1c: e2823004 add r3, r2, #4
20: e080000c add r0, r0, ip
24: e1530004 cmp r3, r4
28: e0800001 add r0, r0, r1
2c: 1afffff7 bne 10
30: e49d4004 pop {r4} ; (ldr r4, [sp], #4)
34: e12fff1e bx lr
00000038 fun2:
38: e3a03000 mov r3, #0
3c: e1a02003 mov r2, r3
40: e790c003 ldr ip, [r0, r3]
44: e2833004 add r3, r3, #4
48: e7901003 ldr r1, [r0, r3]
4c: e2833004 add r3, r3, #4
50: e082200c add r2, r2, ip
54: e3530efa cmp r3, #4000 ; 0xfa0
58: e0822001 add r2, r2, r1
5c: 1afffff7 bne 40
60: e1a00002 mov r0, r2
64: e12fff1e bx lr
Код отличается, но я удивлен пропущенными возможностями для оптимизации.
Clang/llvm произвел следующее:
00000000 fun1: 0: e3a01000 mov r1, #0 4: e3a02ffa mov r2, #1000 ; 0x3e8 8: e1a03001 mov r3, r1 c: e2522001 subs r2, r2, #1 10: e490c004 ldr ip, [r0], #4 14: e08c3003 add r3, ip, r3 18: e2c11000 sbc r1, r1, #0 1c: e182c001 orr ip, r2, r1 20: e35c0000 cmp ip, #0 24: 1afffff8 bne c 28: e1a00003 mov r0, r3 2c: e12fff1e bx lr 00000030 fun2: 30: e3a01000 mov r1, #0 34: e3a02ffa mov r2, #1000 ; 0x3e8 38: e1a03001 mov r3, r1 3c: e2522001 subs r2, r2, #1 40: e490c004 ldr ip, [r0], #4 44: e08c3003 add r3, ip, r3 48: e2c11000 sbc r1, r1, #0 4c: e182c001 orr ip, r2, r1 50: e35c0000 cmp ip, #0 54: 1afffff8 bne 3c 58: e1a00003 mov r0, r3 5c: e12fff1e bx lr
Вы могли заметить, что компилятор создал точный код, указатель или смещение. И, изменяя компиляторы, мне было лучше, чем изменять указатель против индексации массива. Я думаю, что llvm мог бы сделать немного лучше, мне нужно изучить это еще раз, чтобы понять, что мой код сделал, чтобы вызвать это.
EDIT:
Я надеялся, что компилятор должен как минимум использовать команду ldr rd, [rs], # 4, которая поддерживает указатели, и надеется, что компилятор увидит, что он может уничтожить адрес массива, обрабатывая его, как указатель, чем смещение в массив (и используйте приведенную выше инструкцию, которая в основном является тем, что сделал clang/llvm). Или, если бы он сделал массив, что он будет использовать инструкцию ldr rd, [rm, rn]. В основном надеялся, что один из компиляторов будет генерировать одно из этих решений:
funa:
mov r1,#0
mov r2,#1000
funa_loop:
ldr r3,[r0],#4
add r1,r1,r3
subs r2,r2,#1
bne funa_loop
mov r0,r1
bx lr
funb:
mov r1,#0
mov r2,#0
funb_loop:
ldr r3,[r0,r2]
add r1,r1,r3
add r2,r2,#4
cmp r2,#0x4000
bne funb_loop
mov r0,r1
bx lr
func:
mov r1,#0
mov r2,#4000
subs r2,r2,#4
func_loop:
beq func_done
ldr r3,[r0,r2]
add r1,r1,r3
subs r2,r2,#4
b func_loop
func_done:
mov r0,r1
bx lr
Не получилось, но довольно близко. Это было весело. Обратите внимание, что это все ARM-ассемблер.
В общем, (не мой конкретный пример кода C и не обязательно ARM), ряд популярных архитектур вы будете иметь нагрузку от адреса на основе регистров (ldr r0, [r1]) и нагрузку с регистром index/offset (ldr r0, [r1, r2]), где адрес является суммой двух регистров. один регистр идеально представляет собой базовый адрес массива, а второй - индекс/смещение. Первая загрузка из регистра поддается указателям, а вторая - массивам. если ваша программа C НЕ собирается изменять или перемещать указатель или индекс, то в обоих случаях это означает, что статический адрес, который вычисляется, используется при нормальной нагрузке, как массив, так и указатель должны давать одни и те же инструкции. Для более интересного случая изменения указателя/индекса.
Pointer ldr r0,[r1] ... add r1,r1,some number Array index ldr r0,[r1,r2] ... add r2,r2,some number
(замените нагрузку на хранилище и добавьте с помощью подстроки по мере необходимости)
В некоторых архитектурах нет указателя индекса регистра регистров, поэтому вам нужно сделать что-то вроде
array index: mov r2,r1 ... ldr r0,[r2] ... add r2,r2,some number
Или в зависимости от компилятора он может стать очень неудачным, esp, если вы компилируете для отладки или без оптимизации, и предположим, что у вас нет трех регистра добавить
array index: mov r2,#0 ... mov r3,r1 add r3,r2 ldr r4,[r3] ... add r2,some number
Таким образом, вполне возможно, что оба подхода равны. Как видно из ARM, он может комбинировать два (внутри пределов для непосредственных) инструкций указателя в один, что делает это немного быстрее. Средство индекса массива сжигает больше регистров и в зависимости от количества доступных регистров для архитектуры, что подталкивает вас к необходимости свопа регистров в стек раньше и чаще (чем вы с указателями), замедляя вас еще больше. Если вы не возражаете уничтожить базовый адрес, нижняя строка - это решение указателя, которое может дать вам преимущество с точки зрения производительности. Он имеет много общего с вашим кодом и компилятором. Для меня это читаемость вступает в игру, и я чувствую, что массивы легче читать и следовать, а во-вторых, мне нужно сохранить этот указатель, чтобы освободить malloc или снова пройти через эту память и т.д. Если это так, я, вероятно, буду использовать массив с индекс, если это однократный проход, и я не забочусь об уничтожении базового адреса, я буду использовать указатель. Как вы видели выше, с кодом, сгенерированным компилятором, если производительность критическая, тогда в любом случае вручную обработайте решение на ассемблере (на основе предложенных подходов, позволяя компиляторам сначала попробовать его).
Ответ 2
Он полностью зависит от системы, который быстрее, но два функционально эквивалентны друг другу, и я был бы действительно удивлен, если бы на самом деле было быстрее. То есть код
myArr[index]
Полностью эквивалентен
*(&myArr[0] + index)
Аналогично, записывая
*ptr
Является эквивалентным записи
ptr[0]
Большинство компиляторов достаточно умны, чтобы понять это, поэтому я был бы поражен, если бы кто-то был быстрее другого.
Что еще более важно, вы, вероятно, не должны слишком беспокоиться об этом. Беспокоитесь об оптимизации после того, как все остальное работает. Если вы обнаружите, что доступ к массиву действительно убивает вас, подумайте о том, чтобы найти более быструю альтернативу. В противном случае, не беспокойтесь об этом; это бесконечно более ценно, чтобы иметь чистый, читаемый, поддерживаемый код, чем оптимизировать код, если у вас нет необходимости в оптимизации.
Ответ 3
Простые операции индекса скомпилируются с одним и тем же машинным кодом на каждом компиляторе, который я когда-либо касался. По индексу обычно рекомендуется для удобочитаемости.
Более сложные случаи, которые включают в себя различную логику для доступа к указателю и индексированию массива, должны быть рассмотрены в каждом конкретном случае. Если вы сомневаетесь, прокомментируйте свой код - как всегда.
Ответ 4
Нет никакого значимого ответа на ваш вопрос. Операции на уровне языка не имеют определенной "скорости", связанной с ними. Сами по себе они не могут быть "быстрее" или "медленнее".
Только инструкции CPU могут быть более быстрыми или медленными, и только инструкции ЦП могут потреблять циклы ЦП. Чтобы как-то перенести эту концепцию "скорости" с инструкций процессора обратно на операции на уровне языка [эти команды процессора были сгенерированы из], в общем случае вам нужно знать контекст. Это связано с тем, что одна и та же операция на уровне языка может генерировать совершенно разные команды ЦП в разных контекстах (даже не говоря о том, что она также может зависеть от настроек компилятора и т.д.)
Другими словами, разместите фактический код. В качестве абстрактного контекстно-зависимого вопроса это просто не имеет смысла.
Ответ 5
На самом низком уровне эти операции в основном сводятся к одному и тому же. Если вам действительно интересно, вы должны заставить свой компилятор C генерировать вывод сборки (например, с gcc -S), чтобы вы могли проверить, тем более, что это зависит от минимального уровня:
- ваша целевая платформа.
- ваш компилятор.
- уровень оптимизации.
Вы обнаружите, что даже если есть разница (что вызывает сомнения), этот уровень микро-оптимизации в основном не стоит усилий, которые вы вкладываете в него. Вам лучше делать макрооптимизации, такие как улучшенные алгоритмы, поскольку это та вещь, которая предлагает большую отдачу от инвестиций.
В таких ситуациях, когда эффект, вероятно, будет минимальным, я всегда оптимизирую для удобочитаемости.
Ответ 6
Явное исключение общих подвыражений может сработать для вас. Возможно, существует разница, если вы используете архитектуру x86 или RISC и качество оптимизатора.
Когда я пишу процедуру, которая должна запускаться через массив или индексированную структуру, я вычисляю указатель на базу элемента массива/структуры и использую это для адресации. Основной случай
struct SOMETHING list[100];
int find_something (...)
{
int i;
i=0;
while (i<(sizeof(list)/sizeof(struct SOMETHING)))
{
if (list[i].active && list[i].last_access+60<current_time) return i;
++i;
}
return -1;
}
может быть уточнен (я помогу компилятору создать лучший код):
int find_something (...)
{
int i;
struct SOMETHING *pList;
i=0;
while (i<(sizeof(list)/sizeof(struct SOMETHING)))
{
pList=&list[i];
if (pList->active && pList->last_access+60<current_time) return i;
++i;
}
return -1;
}
Это просто для иллюстрации, и простота кода, вероятно, будет генерировать указатель неявно, но если процедура более сложна, это может быть не так. Использование "list [i]". так как в первом примере вы запускали (на x86) риск (RISC haha) компилятора, не имея достаточного количества регистров для генерации и хранения адреса один раз, вместо этого генерируя его для каждой отдельной ссылки. Для x86-case для хранения указателя необходима локальная переменная, и несколько компиляторов будут создавать переменные стека, если явно не указано. В RISC у компилятора есть много регистров, и обычно они решат, что стоит создать (и сохранить) указатель один раз для каждой итерации.
Цикл можно уточнить далее:
pList=list;
i=0;
while (i<(sizeof(list)/sizeof(struct SOMETHING)))
{
if (pList->active && pList->last_access+60<current_time) return i;
pList+=1;
++i;
}
Эта конструкция лишена каких-либо накладных расходов на расчет. "pList + = 1" (другие могут предпочесть "++ pList" ) приводит к добавлению константного значения (равного размеру отдельной строки/члена) в pList.
И далее:
pList=list;
pEndList=&list[sizeof(list)/sizeof(struct SOMETHING)];
while (pList!=pEndList)
{
if (pList->active && pList->last_access+60<current_time) return pList-list;
pList+=1;
}
Это исключает инкремент индекса и заменяет его одним умножением вне и одним делением внутри цикла (выполняется только один раз, в возвратной конструкции).
Теперь, прежде чем все, что вы не оптимизаторы, начнете кричать о кровавом убийстве, я хочу сказать, что какие конструкции приемлемы, определяется размером и сложностью функции, в которой они находятся. Я бы, вероятно, не рассматривал эту конструкцию в 300-строчной функции, которая достаточно сложна для начала, но в такой ситуации, как выше? Если поиск является значительной частью общей обработки? Если ускорения достаточно велики?
Так почему бы и нет? За и против. Это всегда плюсы и минусы. Избавьтесь от них. Абсолютные? Редко (если когда-либо).
Ответ 7
То же самое. Все это O (1), а тактовая частота пренебрежимо мала. Вы в основном получаете доступ к адресу памяти.
Ответ 8
При доступе к массиву через индекс вы фактически выполняете две операции: добавление (добавление индекса к адресу базового массива), затем доступ к памяти (фактически чтение или запись того, что находится на результирующем адресе). Я полагаю, что когда вы говорите о "доступе по указателю", вы имеете в виду, что у вас уже есть указатель на целевой элемент. Таким образом, логически использование указателя сохраняет часть "добавления" и, следовательно, должно быть быстрее или, по крайней мере, медленнее.
Однако...
В грубом приближении на современном компьютере доступ к памяти намного дороже, чем добавление (особенно если оно выпадает из кэшей), поэтому разница, если таковая имеется, будет незначительной. На некоторых архитектурах (например, x86 или PowerPC) доступ к сложениям и памяти может быть объединен в один код операции. Вещи также будут разными, в зависимости от того, является ли адрес массива постоянной времени компиляции (т.е. Массив не является постоянным данным, а объявляется как глобальная переменная, а также блок, полученный с помощью malloc()). Использование массива может помочь компилятору найти лучший код в отношении общего указателя (в частности, когда используется ключевое слово restrict). Контекст имеет огромное влияние (например, сколько свободных регистров существует в этот момент?).
Итак:
- Абсолютного ответа на ваш вопрос нет. Вы должны попытаться принять меры.
- Если есть обнаружимая разница (есть вероятность, что их не будет), трудно предсказать, в каком направлении, и это зависит от огромного набора внешних факторов, включая конкретные версии компилятора и флаги оптимизации, архитектуру процессора и модель, расположение памяти и т.д.
- Вы не сможете добиться какой-либо надежной оптимизации оптимизации, не имея достаточно глубоких знаний об сборке и немного теории компиляции.
- Сначала вам следует сосредоточиться на создании правильного кода, а затем беспокоиться только об оптимизации; и нет проблемы с производительностью до тех пор, пока она не будет должным образом измерена в реальных условиях.