효율성 : 배열 대 포인터

효율성 : 배열 대 포인터

---

포인터를 통한 메모리 액세스는 배열을 통한 메모리 액세스보다 더 효율적이라고합니다. 나는 C를 배우고 있으며 위의 내용은 K & R에 명시되어 있습니다. 특히 그들은 말한다

배열 첨자로 수행 할 수있는 모든 작업은 포인터로도 수행 할 수 있습니다. 일반적으로 포인터 버전이 더 빠릅니다.

Visual C ++를 사용하여 다음 코드를 분해했습니다. (저는 686 프로세서입니다. 모든 최적화를 비활성화했습니다.)

int a[10], *p = a, temp;

void foo()
{
    temp = a[0];
    temp = *p;
}

놀랍게도 포인터를 통한 메모리 액세스는 배열을 통한 메모리 액세스에 의해 취해진 두 명령에 대해 3 개의 명령을 취한다는 것을 알았습니다. 아래는 해당 코드입니다.

; 5    : temp = a[0];

    mov eax, DWORD PTR _a
    mov DWORD PTR _temp, eax

; 6    : temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx

이해하도록 도와주세요. 내가 여기서 무엇을 놓치고 있니 ??

---

많은 답변과 주석에서 지적했듯이 컴파일 시간 상수를 배열 인덱스로 사용했기 때문에 배열을 통한 액세스가 더 쉽습니다. 아래는 변수를 인덱스로 사용하는 어셈블리 코드입니다. 이제 포인터와 배열을 통한 액세스에 대한 동일한 수의 명령이 있습니다. 내 더 광범위한 질문은 여전히 ​​유효합니다. 포인터를 통한 메모리 액세스는 그 자체가 더 효율적이라고 빌려주지 않습니다.

; 7    :        temp = a[i];

    mov eax, DWORD PTR _i
    mov ecx, DWORD PTR _a[eax*4]
    mov DWORD PTR _temp, ecx

; 8    : 
; 9    :    
; 10   :        temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx

---

포인터를 통한 메모리 액세스는 배열을 통한 메모리 액세스보다 더 효율적이라고합니다.

과거에는 컴파일러가 비교적 멍청한 짐승이었을 때도 마찬가지였습니다. gcc더 이상 사실이 아님을 알기 위해 높은 최적화 모드에서 출력 된 코드 중 일부만 보면됩니다 . 이 코드 중 일부는 이해하기 매우 어렵지만 일단 이해하면 그 훌륭함이 분명합니다.

괜찮은 컴파일러는 포인터 액세스 및 배열 액세스에 대해 동일한 코드를 생성하므로 해당 수준의 성능에 대해 걱정할 필요가 없습니다. 컴파일러를 작성하는 사람들은 우리가 인간보다 타겟 아키텍처에 대해 훨씬 더 많이 알고 있습니다. 코드를 최적화 할 때 (알고리즘 선택 등) 매크로 수준에 더 집중하고 도구 제작자가 작업을 수행 할 것을 신뢰하십시오.

---

사실, 컴파일러가 전체를 최적화하지 않은 것에 놀랐습니다.

temp = a[0];

temp다른 값으로 바로 다음 줄에 덮어 쓰기 때문에 존재 a하지 않는 줄 은 표시되지 않습니다 volatile.

경쟁사보다 몇 배 더 뛰어난 최신 VAX Fortran 컴파일러의 벤치 마크 (여기에 내 나이 표시)에 대한 도시 신화를 기억합니다.

컴파일러는 벤치 마크 계산의 결과가 어디에도 사용되지 않았 음을 알아 냈기 때문에 전체 계산 루프를 망각으로 최적화했습니다. 따라서 실행 속도가 크게 향상되었습니다.

---

업데이트 : 최적화 된 코드가 특정 경우에 더 효율적인 이유는 위치를 찾는 방법 때문입니다. a링크 /로드 시간에 결정된 고정 위치에 있으며 이에 대한 참조도 동시에 고정됩니다. 따라서 a[0]또는 실제로 a[any constant]고정 된 위치에있을 것입니다.

그리고 p그 자체도 같은 이유로 고정 된 위치에있을 것입니다. 그러나 *p (의 내용은 p) 가변적이므로 정확한 메모리 위치를 찾기 위해 추가 조회가 필요합니다.

또 다른 변수 x를 0 (아님 const)으로 설정하고 사용 a[x]하면 추가 계산이 발생한다는 것을 알 수 있습니다.

---

귀하의 의견 중 하나에 다음과 같이 진술합니다.

제안한대로 수행하면 배열을 통한 메모리 액세스에 대한 3 가지 지침 (인덱스 가져 오기, 배열 요소의 값 가져 오기, 임시 저장)이 생성되었습니다. 그러나 나는 여전히 효율성을 볼 수 없습니다. :-(

그것에 대한 나의 반응은 포인터를 사용하는 데있어서 효율성을 보지 못할 가능성 이 높다는 것 입니다. 최신 컴파일러는 배열 작업과 포인터 작업이 동일한 기본 기계 코드로 바뀔 수 있다는 것을 알아내는 작업 이상입니다.

실제로 최적화를 설정하지 않으면 포인터 코드의 효율성 이 떨어질 수 있습니다 . 다음 번역을 고려하십시오.

int *pa, i, a[10];

for (i = 0; i < 10; i++)
    a[i] = 100;
/*
    movl    $0, -16(%ebp)              ; this is i, init to 0
L2:
    cmpl    $9, -16(%ebp)              ; from 0 to 9
    jg      L3
    movl    -16(%ebp), %eax            ; load i into register
    movl    $100, -72(%ebp,%eax,4)     ; store 100 based on array/i
    leal    -16(%ebp), %eax            ; get address of i
    incl    (%eax)                     ; increment
    jmp     L2                         ; and loop
L3:
*/

for (pa = a; pa < a + 10; pa++)
    *pa = 100;
/*
    leal    -72(%ebp), %eax
    movl    %eax, -12(%ebp)            ; this is pa, init to &a[0]
L5:
    leal    -72(%ebp), %eax
    addl    $40, %eax
    cmpl    -12(%ebp), %eax            ; is pa at &(a[10])
    jbe     L6                         ; yes, stop
    movl    -12(%ebp), %eax            ; get pa
    movl    $100, (%eax)               ; store 100
    leal    -12(%ebp), %eax            ; get pa
    addl    $4, (%eax)                 ; add 4 (sizeof int)
    jmp     L5                         ; loop around
L6:
*/

이 예제에서 실제로 포인터 예제가 더 길고 불필요하게 . 변경하지 않고 여러 번 로드 pa되며 %eax실제로 와 %eax사이를 번갈아 가며 나타납니다 . 여기서 기본 최적화는 기본적으로 전혀 없습니다.pa&(a[10])

최적화 수준 2로 전환하면 얻을 수있는 코드는 다음과 같습니다.

    xorl    %eax, %eax
L5:
    movl    $100, %edx
    movl    %edx, -56(%ebp,%eax,4)
    incl    %eax
    cmpl    $9, %eax
    jle     L5

어레이 버전 및 :

    leal    -56(%ebp), %eax
    leal    -16(%ebp), %edx
    jmp     L14
L16:
    movl    $100, (%eax)
    addl    $4, %eax
L14:
    cmpl    %eax, %edx
    ja      L16

포인터 버전.

여기서는 클럭 사이클에 대한 분석을하지 않겠습니다 (작업이 너무 많고 기본적으로 게으 르기 때문입니다).하지만 한 가지를 지적하겠습니다. 어셈블러 명령 측면에서 두 버전의 코드에는 큰 차이가 없으며 최신 CPU가 실제로 실행되는 속도를 고려할 때 수십억 개의 작업을 수행하지 않는 한 차이를 느끼지 못할 것 입니다. 나는 항상 가독성을 위해 코드를 작성하는 것을 선호하고 문제가 될 경우에만 성능에 대해 걱정하는 경향이 있습니다.

제쳐두고, 당신이 참조하는 그 진술 :

5.3 포인터 및 배열 : 포인터 버전은 일반적으로 더 빠르지 만 적어도 시작하지 않은 사람에게는 즉시 파악하기가 다소 어렵습니다.

K & R의 초기 버전으로 거슬러 올라갑니다.

getint(pn)
int *pn;
{
    ...
}

컴파일러는 그 이후로 끔찍한 길을 걸어 왔습니다.

---

임베디드 플랫폼을 프로그래밍하는 경우 포인터 방법이 인덱스를 사용하는 것보다 훨씬 빠르다는 것을 금방 알게됩니다.

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);
}

느린 루프는 매번 + (i * sizeof (struct bar))를 계산해야하는 반면 두 번째 루프는 매번 p에 sizeof (struct bar)를 추가해야합니다. 곱하기 연산은 많은 프로세서를 추가하는 것보다 더 많은 클럭 사이클을 사용합니다.

루프 내에서 a [i]를 여러 번 참조하면 실제로 개선이 시작됩니다. 일부 컴파일러는 해당 주소를 캐시하지 않으므로 루프 내에서 여러 번 다시 계산 될 수 있습니다.

구조체를 사용하고 여러 요소를 참조하도록 샘플을 업데이트 해보세요.

---

첫 번째 경우 컴파일러는 배열의 주소 (첫 번째 요소의 주소이기도 함)를 직접 알고 액세스합니다. 두 번째 경우에는 포인터의 주소를 알고 해당 메모리 위치를 가리키는 포인터의 값을 읽습니다. 그것은 실제로 하나의 추가 간접적이므로 여기서는 아마도 더 느립니다.

---

속도는 무엇보다도 루프에서 얻습니다. 배열을 사용할 때 증가하는 카운터를 사용합니다. 위치를 계산하기 위해 시스템은이 카운터에 배열 요소의 크기를 곱한 다음 첫 번째 요소의 주소를 추가하여 주소를 얻습니다. 포인터를 사용하여 다음 요소로 이동하기 위해해야 ​​할 일은 모든 요소가 메모리 내에서 서로 옆에 있다고 가정하여 다음 요소를 가져 오기 위해 요소의 크기로 현재 포인터를 늘리는 것입니다.

따라서 포인터 산술은 루프를 수행 할 때 약간 더 적은 계산을 사용합니다. 또한 오른쪽 요소에 대한 포인터를 갖는 것이 배열 내에서 인덱스를 사용하는 것보다 빠릅니다.

그러나 현대의 개발은 많은 포인터 작업을 서서히 제거하고 있습니다. 프로세서는 점점 더 빨라지고 있으며 어레이는 포인터보다 관리하기가 더 쉽습니다. 또한 배열은 코드에서 버그의 양을 줄이는 경향이 있습니다. 배열은 인덱스 검사를 허용하여 배열 외부의 데이터에 액세스하지 않도록합니다.

---

paxdiablo가 말했듯이 새로운 컴파일러는 그것들을 매우 유사하게 만들 것입니다.

더욱이 나는 배열이 포인터보다 더 빠른 상황을 보았다. 이것은 벡터 연산을 사용하는 DSP 프로세서에있었습니다.

이 경우 배열을 사용하는 것은 제한 포인터 를 사용 하는 것과 유사합니다 . 두 배열을 사용하여 컴파일러는 동일한 위치를 가리 키지 않는다는 것을 암시 적으로 알고 있기 때문입니다. 그러나 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의 경우 컴파일러는 C에 저장하는 동안 a 또는 b를 덮어 쓸 수 있으므로 파이프 라인을 사용하지 않습니다.

---

포인터는 자연스럽게 간단한 유도 변수를 표현하는 반면 첨자는 다소 본질적으로보다 정교한 컴파일러 최적화를 필요로합니다.

---

In many cases just using a subscripted expression requires that an extra layer be added to the problem. A loop that increments a subscript i can be though of as a state machine, and the expression a[i] technically requires, each time it is used, that i be multiplied times the size of each element and added to the base address.

In order to transform that access pattern to use pointers the compiler must analyze the entire loop and determine that, say, each element is being accessed. Then the compiler can replace the multiple instances of multiplying the subscript by the element size with a simple increment of the previous loop value. This process combines optimizations called common subexpression elimination and induction variable strength reduction.

When writing with pointers, the entire optimization process is not necessary because the programmer will typically just step through the array to start with.

Sometimes the compiler can do the optimization and sometimes it can't. It's more common in recent years to have a sophisticated compiler at hand, so pointer-based code is not always faster.

Because arrrays must usually be contiguous, another advantage for pointers is in creating incrementally allocated composite structures.

---

This is a very old question and has been answered, as such I do not need to answer! However, I didn't notice a simple answer so am providing one.

ANSWER: An indirect access (pointer/array) "might" add one additional instruction to load the (base) address, but all accesses after that (elements in case of array / members in case of pointer to struct) should be just one instruction because it is mere addition of an offset to the (base) address that is already loaded. Thus, in a way it is going to be as good as direct access. As such, in majority of the cases, access through array/pointer is equivalent and element accesses are also as good as a direct access to a variable.

Ex. if I have an array (or pointer) with 10 elements or a struct with 10 members (accessed through a pointer to the struct), and I am accessing an element/member, the one possible additional instruction is required only once at the beginning. All the element/member accesses should be just one instruction after that.

---

You're getting good answers to your question here, but since you are learning, it is worth pointing out that efficiencies at that level are seldom noticeable.

When you are tuning a program for maximum performance, you should give at least as much attention to finding and fixing larger issues in the structure of the program. After those have been fixed, low-level optimizations can make a further difference.

Here's an example of how this can be done.

---

Pointers used to be faster than arrays. Certainly back when the C language was designed pointers were quite a bit faster. But these days, optimizers can usually do a better job optimizing arrays than it can with pointers because arrays are more restricted.

Instruction sets of modern processors have also been designed to help optimize array access.

So the bottom line is that arrays are often faster these days, especially when used in loops with index variables.

Of course you would still want to use pointers for things like linked lists, but the old time optimization of walking a pointer through an array rather than using an index variable is now likely to be a dis-optimization.

---

"The pointer version will in general be faster" means that in most cases it's easier for the compiler to generate more efficient code having a pointer (which just needs to be dereferenced) than having an array and subscript (which means that the compiler needs to shift the address from the start of the array). With the modern processors and optimizing compilers, however, array access in the typical case is not slower than pointer access.

Specifically in your case, you would need to switch on the optimization, in order to get the same result.

---

Since 0 is defined as a constant, a[0] is a constant too, and the compiler knows where it is at compile time. In the "normal" case, the compiler would have to compute the element address from a base + offset (with offset being scaled according to the element size).

OTOH, p is a variable, and the indirection requires an extra move.

On a general basis, array index is internally handled as pointer arithmetic anyway, so I'm not sure to see the point that the K&R was trying to make.

---

Since most people has already given detailed answers, I'll just give an intuitive example. If you use array and pointer in larger scale, the efficiency of using pointer will be more significant. For example, if you want to sort a large long int data set by sorting it into several sub set and then merge them.

long int * testData = calloc(N, sizeof(long int));

For daily 8G ram machines in 2017, we can set N to as large as 400000000, which means you will use roughly 1.5G memory for this original data set. And if you are using MPI, you can separate your data quickly by using

MPI_Scatterv(testData, partitionLength, partitionIndex, MPI_LONG, MPI_IN_PLACE, N/number_of_thread, MPI_LONG, 0, MPI_COMM_WORLD);

You can simply treat paritionLength as a pointer which stores N/number_of_thread as length for each identical part, and treat partitionIndex as a pointer which stores N/number_of_threads staring index increamentally . Assume you have an 4-core CPU and you only separate your job in 4 threads. MPI will definitely do the job in a quick sense by the references. But if you are using array, this routine have to run a pointer arithmetic on the array to find the partition point first. Which is not as direct as pointer. Also, when you merge the partitioned data set, you might want to use K-way merge to accelerate. You need a temp space to store the four sorted data set. Here, if you use pointer, you only need to store 4 addresses. However, if you use array, it will store 4 entire sub arrays, which is not efficient. Sometimes, if you are not using MPI_Barrier to make sure your program is thread safe, MPI might even complain that your memory implementation is bad. I got an 32G machine for sorting 400000000 long values on 8 thread by array method and pointer method, I got 11.054980s and 13.182739s correspondingly. And if I increase the size to 1000000000, my sorting program will not be executed successfully if I'm using array. That's why lots of people use pointers for every data structures except scalars in C.

---

i am a little surprised about the ptr faster than array discussion, where the evidence that this is not the case is given initially by the asm code from Abhijith.

mov eax, dord ptr _a; // load directly value from adress _a

vs

mov eax, dword ptr _p; // load adress/value of p into eax

and

mov ecx, dword ptr [eax]; // use loaded adress to access value and put into ecx

An array represents a fixed adress so the cpu can directly access it, not so with the ptr it needs to be dereferenced in order for the cpu to access the value!

The second batch of code is not comareable as the array offset must be calulated, in order to do that for the ptr you would also need at least 1/2 more instructions!

Anything a compiler can infer during compile time(fixed adresses, offsets etc.) is key to performant code. Comparing iterative code and assigning to vars:

Array:

; 2791 : tmp = buf_ai[ l ];

mov eax, DWORD PTR _l$[ebp]
mov ecx, DWORD PTR _buf_ai$[ebp+eax*4]
mov DWORD PTR _tmp$[ebp], ecx

vs

PTR

; 2796 : tmp2 = *p;

mov eax, DWORD PTR _p$[ebp]
mov ecx, DWORD PTR [eax]
mov DWORD PTR _tmp2$[ebp], ecx

plus

; 2801 : ++p;

mov eax, DWORD PTR _p$[ebp]
add eax, 4
mov DWORD PTR _p$[ebp], eax

It's simply for ptr load adress first than use it compared to Array use adress and get value simultaneously!

best regards

ReferenceURL : https://stackoverflow.com/questions/2305770/efficiency-arrays-vs-pointers