Быстрее ли итерация элементов массива с указателями, увеличивающимися на 1?

Question

ли это быстрее, чтобы сделать что-то вроде

for (int * pa(arr), * pb(arr+n); pa != pb; ++pa) 
{ 
    // do something with *pa 
} 

чем

for (size_t k = 0; k < n; ++k) 
{ 
    // do something with arr[k] 
} 

???

Я понимаю, что arr[k] эквивалентно *(arr+k), но и в первом методе используется текущий указатель, который увеличивается на 1, а во втором случае, если вы используете указатель, который увеличивается с arr путем последовательного больших чисел. Может быть, у оборудования есть специальные способы увеличения на 1, и поэтому первый метод быстрее? Или нет? Просто любопытно. Надеюсь, мой вопрос имеет смысл.

Answer 1

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

Например, я составил код в GCC 5.1.0 с порождающей сборки:

int __attribute__ ((noinline)) compute1(int* arr, int n) 
{ 
    int sum = 0; 
    for(int i = 0; i < n; ++i) 
    { 
    sum += arr[i]; 
    } 
    return sum; 
} 

int __attribute__ ((noinline)) compute2(int* arr, int n) 
{ 
    int sum = 0; 
    for(int * pa(arr), * pb(arr+n); pa != pb; ++pa) 
    { 
    sum += *pa; 
    } 
    return sum; 
} 

и результат сборки:

compute1(int*, int): 
    testl %esi, %esi 
    jle .L4 
    leal -1(%rsi), %eax 
    leaq 4(%rdi,%rax,4), %rdx 
    xorl %eax, %eax 
.L3: 
    addl (%rdi), %eax 
    addq $4, %rdi 
    cmpq %rdx, %rdi 
    jne .L3 
    rep ret 
.L4: 
    xorl %eax, %eax 
    ret 
compute2(int*, int): 
    movslq %esi, %rsi 
    xorl %eax, %eax 
    leaq (%rdi,%rsi,4), %rdx 
    cmpq %rdx, %rdi 
    je .L10 
.L9: 
    addl (%rdi), %eax 
    addq $4, %rdi 
    cmpq %rdi, %rdx 
    jne .L9 
    rep ret 
.L10: 
    rep ret 
main: 
    xorl %eax, %eax 
    ret 

Как вы можете видеть, наиболее тяжелую часть (петля) обеих функций:

.L9: 
    addl (%rdi), %eax 
    addq $4, %rdi 
    cmpq %rdi, %rdx 
    jne .L9 
    rep ret 

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

Полный пример кода: https://goo.gl/mpqSS0

Answer 2

На это нельзя ответить. Это зависит от вашего компилятора AND на вашем компьютере.

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

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

Answer 3

Любой разумный компилятор будет генерировать код, который идентичен внутри цикла для этих двух вариантов - я смотрел на код, созданный для итерации по std::vector, используя для цикла с целым числом для итератора или с использованием конструкции типа for(auto i: vec) [std::vector внутренне имеет два указателя для begin и end сохраненных значений, так что ваши pa и pb]. Как gcc, так и clang генерируют идентичный код внутри самого цикла [точные детали цикла тонко отличаются между компиляторами, но кроме этого нет никакой разницы]. Настройка петли была несколько иной, но если вы не сделали OFTEN петлями менее 5 элементов [и если да, то почему вы волнуетесь?], актуальным содержанием цикла является то, что важно, а не бит непосредственно перед фактическим циклом.

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