Доступ к значениям массива с помощью арифметики указателей и подписки в C

Question

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

Если так, то это все еще так, когда я начинаю отходить от изучения C к Objective-C и Какао на Mac?

Какой стиль кодирования является предпочтительным для доступа к массиву как в C, так и в Objective-C? Что считается (специалистами соответствующих языков) более разборчивым, более «правильным» (из-за отсутствия лучшего термина)?

Answer 1

Вам необходимо понять причину этого требования. Вы когда-нибудь задавались вопросом, почему это быстрее? Давайте сравним код:

int i;
int a[20];

// Init all values to zero
memset(a, 0, sizeof(a));
for (i = 0; i < 20; i++) {
    printf("Value of %d is %d\n", i, a[i]);
}

Все они равны нулю, какой сюрприз :-P Вопрос в том, что означает a[i] на самом деле в машинном коде низкого уровня? Это значит

1. Взять в память адрес a.

2. Добавьте i размер отдельного элемента a к этому адресу (обычно это четыре байта).

3. Получить значение с этого адреса.

Таким образом, каждый раз, когда вы выбираете значение из a, базовый адрес a добавляется к результату умножения i на четыре. Если вы просто разыменовываете указатель, шаги 1. и 2. выполнять не нужно, только шаг 3.

Рассмотрите код ниже.

int i;
int a[20];
int * b;

memset(a, 0, sizeof(a));
b = a;
for (i = 0; i < 20; i++) {
    printf("Value of %d is %d\n", i, *b);
    b++;
}

Этот код может быть быстрее ... но даже если это так, разница крошечная. Почему это может быть быстрее? «* b» соответствует шагу 3. выше. Однако «b ++» отличается от шага 1. и шага 2. «b ++» увеличит указатель на 4.

( важно для новичков : работает ++ на указатель не увеличит указатель одного байта в памяти! Будет увеличить указатель на столько байтов в памяти, как данные, на которые он указывает, по размеру. Это указывает на int и int - это четыре байта на моей машине, поэтому b ++ увеличивает b на четыре!)

Хорошо, но почему это может быть быстрее? Потому что добавление четырех к указателю быстрее, чем умножение i на четыре и добавление этого к указателю. У вас есть дополнение в любом случае, но во втором у вас нет умножения (вы избегаете процессорного времени, необходимого для одного умножения). Учитывая скорость современных процессоров, даже если бы массив составлял 1 млн. Элементов, я хотел бы знать, не могли бы вы действительно сравнить разницу.

То, что современный компилятор может оптимизировать любой из них так, чтобы он был одинаково быстрым, - это то, что вы можете проверить, посмотрев выходные данные сборки, которые он производит. Это можно сделать, передав опцию "-S" (заглавная S) в GCC.

Вот код первого кода C (использовался уровень оптимизации -Os, что означает оптимизацию по размеру и скорости кода, но не выполняйте оптимизацию по скорости, которая заметно увеличит размер кода, в отличие от -O2 и очень сильно отличается -O3):

_main:
    pushl   %ebp
    movl    %esp, %ebp
    pushl   %edi
    pushl   %esi
    pushl   %ebx
    subl    $108, %esp
    call    ___i686.get_pc_thunk.bx
"L00000000001$pb":
    leal    -104(%ebp), %eax
    movl    $80, 8(%esp)
    movl    $0, 4(%esp)
    movl    %eax, (%esp)
    call    L_memset$stub
    xorl    %esi, %esi
    leal    LC0-"L00000000001$pb"(%ebx), %edi
L2:
    movl    -104(%ebp,%esi,4), %eax
    movl    %eax, 8(%esp)
    movl    %esi, 4(%esp)
    movl    %edi, (%esp)
    call    L_printf$stub
    addl    $1, %esi
    cmpl    $20, %esi
    jne L2
    addl    $108, %esp
    popl    %ebx
    popl    %esi
    popl    %edi
    popl    %ebp
    ret

То же самое со вторым кодом:

_main:
    pushl   %ebp
    movl    %esp, %ebp
    pushl   %edi
    pushl   %esi
    pushl   %ebx
    subl    $124, %esp
    call    ___i686.get_pc_thunk.bx
"L00000000001$pb":
    leal    -104(%ebp), %eax
    movl    %eax, -108(%ebp)
    movl    $80, 8(%esp)
    movl    $0, 4(%esp)
    movl    %eax, (%esp)
    call    L_memset$stub
    xorl    %esi, %esi
    leal    LC0-"L00000000001$pb"(%ebx), %edi
L2:
    movl    -108(%ebp), %edx
    movl    (%edx,%esi,4), %eax
    movl    %eax, 8(%esp)
    movl    %esi, 4(%esp)
    movl    %edi, (%esp)
    call    L_printf$stub
    addl    $1, %esi
    cmpl    $20, %esi
    jne L2
    addl    $124, %esp
    popl    %ebx
    popl    %esi
    popl    %edi
    popl    %ebp
    ret

Ну, это другое, это точно. Разница чисел 104 и 108 исходит от переменной b (в первом коде на стеке была одна переменная меньше, теперь у нас есть еще одна, меняющая адреса стека). Реальная разница в коде в цикле for составляет

movl    -104(%ebp,%esi,4), %eax

по сравнению с

movl    -108(%ebp), %edx
movl    (%edx,%esi,4), %eax

На самом деле, мне кажется, что первый подход более быстрый (!), Поскольку он выполняет один машинный код ЦП для выполнения всей работы (ЦПУ делает все это за нас) вместо двух машинных кодов. С другой стороны, две приведенные ниже команды сборки могут иметь меньшее время выполнения, чем приведенная выше.

В качестве заключительного слова я бы сказал, что в зависимости от вашего компилятора и возможностей ЦП (какие команды предлагают ЦП для доступа к памяти каким-либо образом), результат может быть в любом случае. Любой из них может быть быстрее / медленнее. Вы не можете сказать наверняка, если не ограничитесь только одним компилятором (имеется в виду также одна версия) и одним конкретным процессором. Поскольку процессоры могут делать все больше и больше в одной команде сборки (давным-давно, компилятору действительно приходилось вручную извлекать адрес, умножать i на четыре и складывать оба вместе перед извлечением значения), операторы, которые раньше были абсолютной истиной века назад в настоящее время все более и более сомнительным. Также кто знает, как внутренне работают процессоры? Выше я сравниваю одну инструкцию по сборке с двумя другими.

Я вижу, что количество инструкций различно, и время, в которое такие инструкции могут быть разными, также может быть разным. Кроме того, сколько памяти нужно этим инструкциям в их машинном представлении (в конце концов, они должны быть перенесены из памяти в кэш ЦП). Однако современные процессоры не выполняют инструкции так, как вы их кормите. Разделение больших команд (часто называемых CISC) на маленькие подинструкции (часто называемые RISC), что также позволяет им лучше оптимизировать поток программ для внутренней скорости. Фактически, первая отдельная инструкция и две другие инструкции, приведенные ниже, могут привести к одинаковому набору подинструкций , и в этом случае не будет никакой измеримой разницы в скорости.

Что касается Objective-C, то это просто C с расширениями. Таким образом, все, что справедливо для C, будет справедливо и для Objective-C с точки зрения указателей и массивов. Если вы используете Объекты с другой стороны (например, NSArray или NSMutableArray), это совершенно другой зверь. Однако в этом случае вы должны в любом случае обращаться к этим массивам с помощью методов, поэтому нет доступа к указателю / массиву.

Answer 2

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

Нах. Это та же самая операция в любом случае. Подписка является синтаксическим сахаром для добавления (размер элемента * индекс) к начальному адресу массива.

При этом при переборе элементов массива указатель на первый элемент и его увеличение каждый раз в цикле обычно будет немного быстрее, чем каждый раз вычислять позицию текущего элемента из переменной цикла. (Хотя это необычно для большого значения в реальном приложении. Сначала изучите ваш алгоритм, преждевременная оптимизация - корень всего зла и т. Д. И т. Д.)

Answer 3

Это может быть немного не по теме (извините), потому что это не отвечает на ваш вопрос относительно скорости выполнения, но вы должны учитывать, что преждевременная оптимизация - корень всех зол (Кнут). На мой взгляд, особенно когда вы все еще изучаете язык, пишите его так, как его легче всего читать. Затем, если ваша программа работает правильно , подумайте об оптимизации скорости. В большинстве случаев ваш код все равно будет достаточно быстрым.

Answer 4

Меки имеет отличное объяснение. Исходя из моего опыта, одна из вещей, которые часто имеют значение при индексировании по сравнению с указателями, - это то, что другой код находится в цикле. Пример:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>

using namespace std;

typedef int64_t int64;
static int64 nsTime() {
  struct timespec tp;
  clock_gettime(CLOCK_REALTIME, &tp);
  return tp.tv_sec*(int64)1000000000 + tp.tv_nsec;
}

typedef int T;
size_t const N = 1024*1024*128;
T data[N];

int main(int, char**) {
  cout << "starting\n";

  {
    int64 const a = nsTime();
    int sum = 0;
    for (size_t i=0; i<N; i++) {
      sum += data[i];
    }
    int64 const b = nsTime();
    cout << "Simple loop (indexed): " << (b-a)/1e9 << "\n";
  }

  {
    int64 const a = nsTime();
    int sum = 0;
    T *d = data;
    for (size_t i=0; i<N; i++) {
      sum += *d++;
    }
    int64 const b = nsTime();
    cout << "Simple loop (pointer): " << (b-a)/1e9 << "\n";
  }

  {
    int64 const a = nsTime();
    int sum = 0;
    for (size_t i=0; i<N; i++) {
      int a = sum+3;
      int b = 4-sum;
      int c = sum+5;
      sum += data[i] + a - b + c;
    }
    int64 const b = nsTime();
    cout << "Loop that uses more ALUs (indexed): " << (b-a)/1e9 << "\n";
  }

  {
    int64 const a = nsTime();
    int sum = 0;
    T *d = data;
    for (size_t i=0; i<N; i++) {
      int a = sum+3;
      int b = 4-sum;
      int c = sum+5;
      sum += *d++ + a - b + c;
    }
    int64 const b = nsTime();
    cout << "Loop that uses more ALUs (pointer): " << (b-a)/1e9 << "\n";
  }
}

В быстрой системе на основе Core 2 (g ++ 4.1.2, x64), вот время:

    Simple loop (indexed): 0.400842
    Simple loop (pointer): 0.380633
    Loop that uses more ALUs (indexed): 0.768398
    Loop that uses more ALUs (pointer): 0.777886

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

Answer 5

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

• Внеочередное исполнение
• конвейерная
• прогноз ветви
• гиперпотоковый
• ...

Это не просто подсчет машинных инструкций и даже не только подсчет тактов. Кажется, просто измерить в тех случаях, когда это действительно необходимо. Даже если невозможно рассчитать правильное количество циклов для данной программы (мы должны были это делать в университете), но вряд ли это весело и трудно получить правильные результаты. Sidenote: Правильное измерение также сложно в многопоточных / многопроцессорных средах.

Answer 6

Если вы имеете дело с данными типа массива, я бы сказал, что использование подписок делает код более читабельным. На современных машинах (особенно для чего-то простого) читаемый код важнее.

Теперь, если вы имеете дело с порцией данных, которые вы выполняете malloc (), и вы хотите получить указатель внутри этих данных, скажем, 20 байт в заголовке аудиофайла, то я думаю, что адресная арифметика более четко ты пытаешься сделать.

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

РЕДАКТИРОВАТЬ: Согласно некоторым из этих других ответов, подписка является просто синтаксическим элементом и не влияет на производительность, как я полагал. В этом случае определенно используйте любой контекст, который вы пытаетесь выразить через данные доступа внутри блока, на который указывает указатель.

Answer 7

Нет, использование арифметики с указателями не быстрее и, скорее всего, медленнее, потому что оптимизирующий компилятор может использовать такие инструкции, как LEA (Load Effective Address) на процессорах Intel или аналогичные на других процессорах, для арифметики с указателями, которая быстрее, чем add или add / mul , Преимущество состоит в том, что можно выполнять несколько действий одновременно, а НЕ воздействовать на флаги, а также требуется один цикл вычисления. Кстати, ниже из руководства GCC. Так что -Os не оптимизирует в первую очередь по скорости.

Я также полностью согласен с themarko. Сначала попробуйте написать чистый, читаемый и многократно используемый код, а затем подумайте об оптимизации и воспользуйтесь некоторыми инструментами профилирования, чтобы найти узкое место. В большинстве случаев проблема с производительностью связана с вводом / выводом или из-за плохого алгоритма или из-за ошибки, которую вы должны выследить. Кнут - это человек; -)

Мне просто пришло в голову, что вы будете делать это со структурным массивом. Если вы хотите сделать арифметику указателей, то вам определенно следует сделать это для каждого члена структуры. Это звучит как перебор? Да, конечно, это излишне, а также открывает широкие двери, чтобы скрывать ошибки.

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

Answer 8

char p1[ ] = "12345";
char* p2 = "12345";

char *ch = p1[ 3 ]; /* 4 */
ch = *(p2 + 3); /* 4 */

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

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

Итак, общий совет - использовать все, что дает более понятный и простой код. Использование массива [i] дает некоторым инструментам возможность попытаться найти условия отсутствия индекса, поэтому, если вы используете массивы, лучше просто обращаться с ними как с такими.

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

Answer 9

Я работал над оптимизацией c ++ / ассемблера для нескольких названий AAA в течение 10 лет, и я могу сказать, что на конкретных платформах / компиляторе , над которыми я работал, арифметика указателей имела довольно ощутимое значение.

В качестве примера, чтобы представить вещи в перспективе, я смог сделать действительно узкий цикл в нашем генераторе частиц на 40% быстрее, заменив весь доступ к массиву арифметикой указателей до полного недоверия моих коллег. Я слышал об этом от одного из моих учителей как хороший трюк того времени, но я полагал, что не будет никакого способа изменить ситуацию с теми компиляторами / процессорами, которые мы имеем сегодня. Я был не прав;)

Следует отметить, что многие процессоры консоли не обладают всеми прелестными функциями современного процессора cisc, и компилятор иногда немного шатался.

Answer 10

Маловероятно, что будет какая-либо разница в скорости.

Использование оператора массива [], вероятно, предпочтительнее, так как в C ++ вы можете использовать тот же синтаксис с другими контейнерами (например, вектором).