Эффективность: массивы по сравнению с указателями

Здесь вы получили хорошие ответы на свой вопрос, но поскольку вы учитесь, стоит отметить, что эффективность на таком уровне редко бывает заметной.

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

Вот пример того, как это можно сделать.

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

Наборы инструкций современных процессоров также были разработаны для оптимизации доступа к массивам.

В итоге, массивы в наши дни часто работают быстрее, особенно при использовании в циклах с индексными переменными.

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

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

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

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

например:

int a[10],b[10],c[10];
int *pa=a, *pb=b, *pc=c;
int i;

// fill a and b.
fill_arrays(a,b);

// set c[i] = a[i]+b[i];
for (i = 0; i<10; i++)
{
   c[i] = a[i] + b[i];
}

// set *pc++ = *pa++ + *pb++;
for (i = 0; i<10; i++)
{
   *pc++ = *pa++ + *pb++;
}

В случае 1 компилятор легко выполнит конвейерную обработку добавления a и b и сохранения значения в c.

В случае 2 компилятор не выполняет конвейерную обработку, поскольку он может перезаписывать a или b при сохранении в C.

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

Если вы программируете встроенные платформы, вы быстро узнаете, что метод указателя намного быстрее, чем использование индекса.

struct bar a[10], *p;

void foo()
{
    int i;

    // slow loop
    for (i = 0; i < 10; ++i)
        printf( a[i].value);

    // faster loop
    for (p = a; p < &a[10]; ++p)
        printf( p->value);
}

Медленный цикл должен каждый раз вычислять a + (i * sizeof(struct bar)), в то время как второй цикл просто добавляет sizeof(struct bar) к p каждый раз. Операция умножения использует больше тактов, чем сложение, на многих процессорах.

Вы действительно начинаете видеть улучшения, если ссылаетесь на a[i] несколько раз внутри цикла. Некоторые компиляторы не кэшируют этот адрес, поэтому он может быть пересчитан несколько раз внутри цикла.

Попробуйте обновить пример, чтобы использовать struct и ссылаться на несколько элементов.

Указатели естественным образом выражают простые индукционные переменные, в то время как индексы в некоторой степени внутренне требуют более сложной оптимизации компилятора

Во многих случаях просто использование выражения с индексами требует наличия дополнительного уровня добавил к проблеме. Цикл, увеличивающий нижний индекс i , можно рассматривать как конечный автомат, а выражение a [i] технически требует, чтобы каждый раз при его использовании, чтобы i умножить на размер каждого элемента и прибавить к базовому адресу.

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

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

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

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

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

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

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

«Версия с указателем в целом будет быстрее» означает, что в большинстве случаев компилятору проще сгенерировать более эффективный код, имея указатель (который просто требует для разыменования), чем наличие массива и индекса (что означает, что компилятору необходимо сместить адрес с начала массива). Однако с современными процессорами и оптимизирующими компиляторами доступ к массиву в типичном случае не медленнее, чем доступ по указателю.

Конкретно в вашем случае вам нужно будет включить оптимизацию, чтобы получить тот же результат.

Поскольку 0 определяется как константа, [0] также является константой, и компилятор знает, где он находится во время компиляции. В «нормальном» случае компилятор должен вычислить адрес элемента, исходя из базового + смещения (при этом смещение масштабируется согласно размеру элемента).

OTOH, p - это переменная, и для косвенного обращения требуется дополнительный ход.

В общем, индекс массива внутренне обрабатывается как арифметика указателя, так что я не уверен, что уловил смысл, который пытался донести K&R.