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

Ответ 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] на самом деле в машинном коде низкого уровня? Это означает

• Возьмите адрес a в памяти.

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

• Извлеките значение из этого адреса.

Таким образом, каждый раз, когда вы извлекаете значение из 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.

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

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

То, что современный компилятор может оптимизировать один, чтобы быть одинаково быстрым, - это то, что вы можете проверить, посмотрев на вывод сборки, который он производит. Вы делаете это, передавая параметр "-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), это совершенно другой зверь. Однако в этом случае вы должны обращаться к этим массивам с помощью методов в любом случае, нет доступа к указателю/массиву.

Ответ 2

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

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

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

Ответ 3

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

Ответ 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

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

Ответ 5

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

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

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

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

Ответ 6

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

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

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

Ответ 7

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

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

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

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

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

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

Ответ 8

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

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

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

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

Ответ 9

Это неправда. Это точно так же быстро, как и с индексом. В Objective-C вы можете использовать такие массивы, как в C, и в объектно-ориентированном стиле, где объектно-ориентированный стиль намного медленнее, поскольку он выполняет некоторые операции в каждом вызове из-за динамической природы вызова.

Ответ 10

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

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

Ответ 11

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

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

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