В C доступ к моему индексу массива быстрее или доступ по указателю быстрее?
В C доступ к индексу массива быстрее или доступ по указателю быстрее? Я имею в виду, что быстрее будет меньше тактов. Массив не является константным массивом.
8 ответов
templatetypedef подвел итог. Чтобы добавить поддержку своего ответа. Возьмите эти примеры функций:
unsigned int fun1 (unsigned int * x)
{
без знака int ra, рб;
R b=0;
для (ra=0;ra<1000;ra++) rb+=*x++;
возвращать (РБ);
}
unsigned int fun2 ( unsigned int *x)
{
без знака int ra, рб;
R b=0;
для (ra=0;ra<1000;ra++) rb+=x[ra];
возвращать (РБ);
}Теперь GCC произвел это:
00000000 fun1:
0: e52d4004 push {r4}; (str r4, [sp, # -4]!)
4: e1a03000 mov r3, r0
8: e2804efa добавить 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 добавить r3, r2, #4
20: e080000c добавить r0, r0, ip
24: e1530004 cmp r3, r4
28: e0800001 добавить r0, r0, r1
2c: 1afffff7 bne 10
30: e49d4004 pop {r4}; (лдр 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 добавь r3, r3, #4
48: e7901003 ldr r1, [r0, r3]
4c: e2833004 добавить r3, r3, #4
50: e082200c добавить r2, r2, ip
54: e3530efa cmp r3, #4000; 0xfa0
58: e0822001 добавить 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 sub r2, r2, #1 10: e490c004 ldr ip, [r0], #4 14: e08c3003 добавить 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 sub r2, r2, #1 40: e490c004 ldr ip, [r0], #4 44: e08c3003 добавить 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 мог бы сделать немного лучше, мне нужно изучить это еще немного, чтобы понять, что мой код сделал, чтобы вызвать это.
РЕДАКТИРОВАТЬ:
Я надеялся заставить компилятор как минимум использовать инструкцию ldr rd,[rs],#4, которая поддерживает указатели, и надеялся, что компилятор увидит, что он может уничтожить адрес массива, рассматривая его как указатель, а не как смещение в массив (и используйте вышеупомянутую инструкцию, что в основном и сделал clang/llvm). Или, если бы он сделал массив, он бы использовал инструкцию ldr rd,[rm,rn]. По сути, он надеялся, что один из компиляторов сгенерирует одно из следующих решений:
Фун:
MOV R1, № 0
MOV R2, # 1000
funa_loop:
ldr r3,[r0],#4
добавить r1, r1, r3
подводные лодки r2,r2,#1
bne funa_loop
MOV R0, R1
BX LR
funb:
MOV R1, № 0
MOV R2, # 0
funb_loop:
ldr r3,[r0,r2]
добавить r1, r1, r3
добавить r2,r2,#4
cmp r2,#0x4000
bne funb_loop
MOV R0, R1
BX LR
FUNC:
MOV R1, № 0
MOV R2, # 4000
подводные лодки r2, r2, # 4
func_loop:
beq func_done
ldr r3, [r0, r2]
добавить r1, r1, r3
подводные лодки r2, r2, # 4
b func_loop
func_done:
MOV R0, R1
BX LRНе совсем добраться, но довольно близко. Это было забавное упражнение. Обратите внимание, что выше все ARM ассемблер.
В общем, (не мой конкретный пример кода C и не обязательно ARM), ряд популярных архитектур, которые вы будете загружать с адреса на основе регистра (ldr r0,[r1]), и загрузка с индексом / смещением регистра (ldr r0,[r1,r2]), где адрес является суммой двух регистров. один регистр в идеале является базовым адресом массива, а второй - индексом / смещением. Первая загрузка из регистра поддается указателям, вторая - массивам. если ваша C-программа НЕ собирается изменять или перемещать указатель или индекс, то в обоих случаях это означает, что вычисляется статический адрес, а затем используется обычная загрузка, и массив, и указатель должны выдавать одинаковые инструкции. Для более интересного случая изменения указателя / индекса.
Указатель ldr r0,[r1] ... добавить r1, r1, некоторое число Индекс массива ldr r0,[r1,r2] ... добавить r2, r2, некоторое число
(замените нагрузку на магазин, а добавьте на саб при необходимости)
В некоторых архитектурах нет инструкции по регистру из трех регистров, поэтому вам нужно сделать что-то вроде
индекс массива: MOV R2, R1 ... ldr r0,[r2] ... добавить r2, r2, некоторое число
Или, в зависимости от компилятора, он может стать действительно плохим, особенно если вы компилируете для отладки или без оптимизации, и при условии, что у вас нет трех регистра, добавляющего
индекс массива: MOV R2,#0 ... MOV R3, R1 добавить r3, r2 лдр r4,[r3] ... добавить г2, некоторое число
Так что вполне возможно, что оба подхода равны. Как видно на ARM, он может объединять две (в пределах, ограниченных для непосредственных) инструкций указателя в одну, что делает это немного быстрее. Решение с индексами массивов сжигает больше регистров, и в зависимости от количества доступных регистров для архитектуры, которая подталкивает вас к необходимости выкладывать регистры в стек быстрее и чаще (чем с указателями), замедляя вас еще больше. Если вы не возражаете против уничтожения базового адреса, суть в том, что решение с указателем может дать вам преимущество с точки зрения производительности. Это во многом связано с вашим кодом и компилятором. Для меня это удобочитаемость, и я чувствую, что массивы легче читать и отслеживать, а во-вторых, мне нужно сохранить этот указатель, чтобы освободить malloc или снова пройти через эту память и т. Д. Если это так, я, вероятно, буду использовать массив с индекс, если это однократный проход, и я не забочусь об уничтожении базового адреса, я буду использовать указатель. Как вы видели выше в коде, сгенерированном компилятором, если производительность критична, то, в любом случае, вручную закодируйте решение на ассемблере (основываясь на предложенных подходах, позволив компиляторам попробовать это в первую очередь).
Это полностью зависит от системы, какой из них быстрее, но оба они функционально эквивалентны друг другу, и я был бы очень удивлен, если бы один действительно был быстрее. То есть код
myArr[index]
Полностью эквивалентно
*(&myArr[0] + index)
Точно так же, написание
*ptr
Эквивалентно написанию
ptr[0]
Большинство компиляторов достаточно умны, чтобы понять это, поэтому я бы удивился, если бы один был быстрее другого.
Что еще более важно, вы, вероятно, не должны слишком беспокоиться об этом. Беспокойство об оптимизации после того, как все остальное работает. Если вы обнаружите, что доступ к массиву действительно убивает вас, подумайте о поиске более быстрой альтернативы. В противном случае, не беспокойтесь об этом; иметь бесконечно более ценный чистый, читаемый, обслуживаемый код, чем оптимизированный, если нет острой необходимости в оптимизации.
Простые операции с индексами компилируются с одним и тем же машинным кодом на каждом компиляторе, к которому я когда-либо прикасался. По индексу обычно рекомендуется для удобства чтения.
Более сложные случаи, в которых используется различная логика доступа к указателю и индексация массива, должны быть рассмотрены в каждом конкретном случае. Если вы сомневаетесь, профилируйте свой код - как всегда.
Там нет значимого ответа на ваш вопрос. Операции на уровне языка не имеют конкретной "скорости", связанной с ними. Сами по себе они не могут быть "быстрее" или "медленнее".
Только инструкции ЦП могут быть быстрее или медленнее, и только инструкции ЦП могут потреблять циклы ЦП. Чтобы каким-то образом перенести это понятие "скорость" из инструкций ЦП обратно в операции уровня языка [из которых были созданы эти инструкции ЦП], в общем случае вам необходимо знать контекст. Это так, потому что одна и та же операция на уровне языка может генерировать совершенно разные инструкции ЦП в разных контекстах (даже не говоря уже о том, что это может также зависеть от настроек компилятора и т. Д.)
Другими словами, опубликовать фактический код. Как абстрактный вопрос без контекста, он просто не имеет смысла.
На самом низком уровне эти операции в основном имеют тенденцию компилироваться в одно и то же. Если вы действительно заинтересованы, вы должны получить компилятор C для генерации вывода сборки (например, с помощью gcc -S) так что вы можете проверить, тем более что это зависит, как минимум, от:
- Ваша целевая платформа.
- твой компилятор.
- ваш уровень оптимизации.
Вы обнаружите, что даже если бы была разница (что сомнительно), этот уровень микрооптимизации в основном не стоит тех усилий, которые вы вложили в него. Вам лучше делать макрооптимизации, такие как улучшенные алгоритмы, так как это дает больше отдачи от инвестиций.
В таких ситуациях, когда эффект, вероятно, будет минимальным, я всегда оптимизирую для удобства чтения.
Явное устранение общих подвыражений может работать на вас. Может быть разница, если вы используете архитектуру 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 хаха) компилятора, не имея достаточного количества регистров для генерации и сохранения адреса один раз, вместо этого генерируя его для каждой ссылки. Для случая x86 локальная переменная необходима для хранения указателя, и лишь немногие компиляторы будут создавать переменные стека, если явно не указано иное. В 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 строк, которая достаточно сложна для начала, но в ситуации, подобной описанной выше? Если поиски являются значительной частью общей обработки? Если ускорения достаточно велики?
Так почему не? Плюсы и минусы. Это всегда плюсы и минусы. Делая лучшее из них. Абсолютные? Редко (если вообще).
При доступе к массиву через индекс вы фактически выполняете две операции: сложение (добавление индекса к базовому адресу массива), затем доступ к памяти (фактически чтение или запись того, что находится по результирующему адресу). Я предполагаю, что когда вы говорите о "доступе по указателю", вы имеете в виду, что у вас уже есть указатель на целевой элемент. Таким образом, по логике, использование указателя сохраняет часть "сложения" и, следовательно, должно быть быстрее или, по крайней мере, не медленнее.
Тем не мение...
Грубо говоря, в современном компьютере доступ к памяти намного дороже, чем добавление (особенно, если оно выпадает из кэшей), поэтому разница, если таковая имеется, будет незначительной. На некоторых архитектурах (например, x86 или PowerPC) добавление и доступ к памяти могут быть объединены в один код операции. Вещи также будут разными, в зависимости от того, является ли адрес массива константой времени компиляции (т. Е. Массив не является константными данными, но объявлен как глобальная переменная, по сравнению с блоком, полученным с помощью malloc()). Использование массива может помочь компилятору найти лучший код в отношении универсального указателя (в частности, когда restrict ключевое слово используется). Контекст имеет огромное влияние (например, сколько бесплатных регистров существует на тот момент?).
Так:
- Нет абсолютного ответа на ваш вопрос. Вы должны попытаться принять меры.
- Если есть заметная разница (есть вероятность, что ее не будет), трудно предсказать, в каком направлении, и это зависит от огромного набора внешних факторов, включая конкретную версию компилятора и флаги оптимизации, архитектуру и модель процессора, макет памяти и тд.
- Вы не сможете получить какой-либо надежный результат оптимизации, не имея достаточно глубоких знаний по сборке и немного теории компиляции.
- Сначала вы должны сосредоточиться на создании правильного кода, а затем беспокоиться только об оптимизации; и нет проблем с производительностью, пока она не будет должным образом измерена в реальных условиях.
Так же. Это все O(1), а время на часах ничтожно мало. Вы в основном получаете доступ к адресу памяти.