효율성: 어레이와 포인터 비교
포인터를 통한 메모리 액세스는 어레이를 통한 메모리 액세스보다 효율적이라고 합니다.저는 C를 배우고 있으며 위와 같은 내용이 K&R에 기재되어 있습니다.구체적으로 그들은 말한다.
어레이 서브스크립션에 의해 달성할 수 있는 조작은 포인터로 실행할 수도 있습니다.일반적으로 포인터 버전이 더 빠릅니다.
아래의 코드를 Visual C++로 분해했습니다.(저는 686 프로세서입니다.모든 최적화를 무효로 했습니다).
int a[10], *p = a, temp;
void foo()
{
temp = a[0];
temp = *p;
}
놀랍게도 포인터를 통한 메모리 액세스는 어레이를 통한 메모리액세스에 의해 실행되는2개의 명령으로 이루어집니다.대응하는 코드는 다음과 같습니다.
; 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)는 가변적이기 때문에 올바른 메모리 위치를 찾기 위해 추가 검색이 필요합니다.
다른 변수가 있다는 것을 알게 될 것이다.x0으로 설정(비설정)const) 및 사용방법a[x]추가 계산을 도입할 수도 있습니다.
코멘트 중 하나에 다음과 같이 기술합니다.
제안하신 대로 하면 어레이를 통한 메모리 액세스에 대한 3가지 명령(인덱스 가져오기, 어레이 요소의 값 가져오기, temp에 저장)이 생성됩니다.하지만 아직 효율이 보이지 않습니다. :- (
이에 대한 제 답변은 포인터 사용의 효율성을 거의 느끼지 못할 것이라는 것입니다.최신 컴파일러는 어레이 조작과 포인터 조작을 동일한 기본 머신 코드로 변환할 수 있는지 확인하는 작업만으로 충분치 않습니다.
실제로 최적화가 활성화되지 않으면 포인터 코드의 효율성이 떨어질 수 있습니다.다음 번역을 검토해 주십시오.
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의 초기 버전으로 거슬러 올라가며, 1978년 고대 버전에는 함수가 아직 기록되어 있습니다.
getint(pn)
int *pn;
{
...
}
그 이후로 컴파일러는 엄청나게 발전해 왔습니다.
포인터는 자연스럽게 단순한 유도 변수를 나타내지만, 서브스크립트는 본질적으로 보다 정교한 컴파일러 최적화를 필요로 합니다.
대부분의 경우 첨자 표현식을 사용하는 것만으로 문제에 레이어를 추가해야 합니다.서브스크립트 i를 스테이트 머신으로서 증분시키는 루프로서, a[i]는 사용할 때마다 기술적으로 각 요소의 사이즈에 곱하여 베이스 주소에 부가하는 것을 필요로 한다.
포인터를 사용하기 위해 액세스 패턴을 변환하기 위해 컴파일러는 전체 루프를 분석하여 각 요소가 액세스되고 있는지 판단해야 합니다.그런 다음 컴파일러는 첨자에 요소 크기를 곱하는 여러 인스턴스를 이전 루프 값의 단순한 증분으로 대체할 수 있습니다.이 공정은 공통 하위 표현식 제거 및 유도 가변 강도 감소라고 하는 최적화를 결합합니다.
포인터를 사용하여 쓸 경우 프로그래머는 일반적으로 어레이를 처음부터 순서대로 진행하기 때문에 최적화 프로세스 전체가 필요하지 않습니다.
컴파일러가 최적화를 실행할 수 있는 경우도 있고 실행할 수 없는 경우도 있습니다.최근에는 고급 컴파일러를 사용하는 것이 일반적이기 때문에 포인터 기반 코드가 항상 빠른 것은 아닙니다.
일반적으로 어레이는 연속적이어야 하므로 포인터의 또 다른 장점은 증분적으로 할당된 복합 구조를 만드는 것입니다.
임베디드 플랫폼을 프로그래밍하는 경우 포인터 방식이 인덱스를 사용하는 것보다 훨씬 빠르다는 것을 금방 알 수 있습니다.
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 * size of (struct bar))를 계산해야 하며, 두 번째 루프는 매번 p에 size of (struct bar)를 추가해야 합니다.곱셈 연산에서는 많은 프로세서의 추가보다 더 많은 클럭 사이클이 사용됩니다.
루프 내에서 a[i]를 여러 번 참조하면 개선되는 것을 알 수 있습니다.일부 컴파일러는 이 주소를 캐시하지 않기 때문에 루프 내에서 여러 번 재계산될 수 있습니다.
하나의 구조를 사용하고 여러 요소를 참조하도록 표본을 업데이트해 보십시오.
속도는 무엇보다도 루프에서 향상됩니다.어레이를 사용할 때는 증분하는 카운터를 사용합니다.위치를 계산하기 위해 시스템은 이 카운터에 배열 요소의 크기를 곱한 다음 주소를 가져오는 첫 번째 요소의 주소를 추가합니다.포인터를 사용하여 다음 요소로 이동하기 위해 필요한 것은 모든 요소가 메모리 내에서 서로 옆에 있다고 가정하고 요소의 크기에 따라 현재 포인터를 증가시키는 것입니다.
따라서 포인터 산술은 루프를 실행할 때 계산 작업이 다소 덜 소요됩니다.또한 올바른 요소에 대한 포인터를 갖는 것이 배열 내에서 인덱스를 사용하는 것보다 빠릅니다.
그러나 현대 개발은 많은 포인터 조작을 서서히 없애고 있다.프로세서는 점점 더 빨라지고 어레이는 포인터보다 관리가 용이해집니다.또한 어레이는 코드의 버그 수를 줄이는 경향이 있습니다.어레이는 인덱스 체크를 허용하여 어레이 외부의 데이터에 액세스하지 않도록 합니다.
팍스디아블로가 말했듯이, 어떤 새로운 컴파일러도 그들을 매우 비슷하게 만들 것이다.
게다가 포인터보다 배열이 더 빠른 상황도 볼 수 있었습니다.이것은 벡터 연산을 사용하는 DSP 프로세서에 있습니다.
이 경우 배열을 사용하는 것은 제한 포인터를 사용하는 것과 비슷합니다.왜냐하면 2개의 어레이를 사용함으로써 컴파일러는 두 어레이가 같은 위치를 가리키지 않는다는 것을 알 수 있기 때문입니다.그러나 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를 덮어쓸 수 있기 때문에 파이프로 연결되지 않습니다.
대부분의 사람들이 이미 자세한 답변을 했기 때문에, 저는 단지 직관적인 예를 들겠습니다.어레이와 포인터를 대규모로 사용하는 경우 포인터를 사용하는 효율이 더욱 높아집니다.예를 들어, 대규모 롱 int 데이터 세트를 여러 하위 세트로 정렬한 다음 병합하여 정렬하려는 경우.
long int * testData = calloc(N, sizeof(long int));
2017년 일일 8G 램 머신의 경우,N최대 400000000, 즉 이 원래 데이터 세트에 약 1.5G의 메모리를 사용합니다.그리고 만약 당신이 그것을 사용하고 있다면MPI, 를 사용하여 데이터를 빠르게 분리할 수 있습니다.
MPI_Scatterv(testData, partitionLength, partitionIndex, MPI_LONG, MPI_IN_PLACE, N/number_of_thread, MPI_LONG, 0, MPI_COMM_WORLD);
간단히 치료할 수 있습니다.paritionLength저장하는 포인터로서N/number_of_thread각 동일한 부분의 길이와 처리partitionIndexN/number_of_threads stacking 인덱스를 증분적으로 저장하는 포인터입니다.4 코어 CPU가 있고 작업을 4 스레드로만 분리한다고 가정합니다. MPI참고 자료로 봤을 때 빠른 의미로 작업을 수행할 것입니다.그러나 어레이를 사용하는 경우 이 루틴은 먼저 파티션 포인트를 찾기 위해 어레이에서 포인터 계산을 실행해야 합니다.포인터만큼 직접적이진 않죠또한 분할된 데이터 세트를 병합할 때K-way merge가속할 수 있습니다.정렬된 4개의 데이터 세트를 저장할 온도 공간이 필요합니다.여기서 포인터를 사용할 경우 4개의 주소만 저장하면 됩니다.그러나 어레이를 사용하면 4개의 서브 어레이 전체가 저장되므로 효율적이지 않습니다.사용하지 않는 경우MPI_Barrier세이프인 것을 , 「스루 세이프」를 참조해 주세요.MPI메모리 구현이 나쁘다고 불평할 수도 있습니다.어레이 방식과 포인터 방식으로 8 스레드에 4000000의 긴 값을 정렬하기 위한 32G 머신을 구입했고, 이에 대응하여 11.054980s와 13.182739s를 받았습니다.또한 크기를 1000000000으로 늘리면 어레이를 사용하는 경우 정렬 프로그램이 정상적으로 실행되지 않습니다.그래서 많은 사람들이 C의 스칼라를 제외한 모든 데이터 구조에 포인터를 사용합니다.
첫 번째 경우 컴파일러는 어레이의 주소(첫 번째 요소의 주소이기도 함)를 직접 알고 액세스합니다.두 번째 경우, 그는 포인터의 주소를 알고 그 메모리 위치를 가리키는 포인터의 값을 읽습니다.이것은 실제로는 다른 방향의 하나이기 때문에, 여기에서는 아마 속도가 느릴 것입니다.
질문에는 좋은 답변을 얻을 수 있지만, 학습 중이기 때문에 그 수준의 효율은 거의 눈에 띄지 않는다는 점을 지적할 필요가 있습니다.
최대한의 퍼포먼스를 얻기 위해 프로그램을 튜닝할 때는 프로그램 구조에서 큰 문제를 찾아 수정하는 데 최소한 많은 주의를 기울여야 합니다.이러한 사항을 수정한 후에는 낮은 수준의 최적화를 통해 더 큰 차이를 만들 수 있습니다.
이것은 매우 오래된 질문이며 이미 답변이 되었기 때문에 대답할 필요가 없습니다.단, 간단한 답변을 알지 못했기 때문에 알려드립니다.
답변: 간접접근(포인트/어레이)은 (베이스) 주소를 로드하는 명령을 1개 추가할 수 있지만, 그 이후의 모든 액세스(구조체 포인터의 경우 어레이/멤버)는 이미 로드된 (베이스) 주소에 오프셋을 추가하는 것에 불과하기 때문에 하나의 명령으로 해야 합니다.따라서 어떤 면에서는 직접 접속과 같은 효과를 얻을 수 있습니다.따라서 대부분의 경우 어레이/포인터를 통한 액세스는 동등하며 요소에 대한 액세스도 변수에 대한 직접 액세스와 같습니다.
예를 들어, 10개의 요소를 가진 배열(또는 포인터) 또는 10개의 멤버를 가진 구조(구조물에 대한 포인터를 통해 액세스)가 있고 요소/구성원에 액세스하는 경우, 가능한 추가 명령은 처음에 한 번만 필요합니다.그 후 모든 요소/구성원 액세스는 하나의 명령으로 해야 합니다.
예전에는 포인터가 배열보다 빨랐습니다.확실히 C언어가 설계되었을 때는 포인터가 꽤 빨랐습니다.그러나 오늘날 옵티마이저는 어레이가 더 제한적이기 때문에 포인터를 사용하는 것보다 어레이 최적화를 더 잘 수행할 수 있습니다.
최신 프로세서의 명령 세트도 어레이 액세스를 최적화하도록 설계되어 있습니다.
즉, 최근에는 특히 인덱스 변수가 있는 루프에서 어레이를 사용하면 어레이 속도가 더 빨라지는 경우가 많습니다.
물론 여전히 링크 리스트 등에 포인터를 사용하고 싶지만 인덱스 변수를 사용하는 대신 어레이를 포인터로 이동하는 오래된 최적화는 최적화를 해제하는 것이 될 수 있습니다.
"일반적으로 포인터 버전이 더 빠를 것입니다"는 대부분의 경우 컴파일러가 어레이와 서브스크립트를 갖는 것보다 포인터를 갖는 효율적인 코드를 생성하는 것이 더 쉽다는 것을 의미합니다(즉, 컴파일러는 어레이의 시작부터 주소를 이동해야 합니다).그러나 최신 프로세서와 최적화 컴파일러를 사용하면 일반적인 경우 어레이 액세스 속도가 포인터 액세스보다 느리지 않습니다.
특히, 같은 결과를 얻으려면 최적화를 켜야 합니다.
0은 상수로 정의되기 때문에 a[0]도 상수이며 컴파일러는 컴파일 시 위치를 알고 있습니다."일반"의 경우 컴파일러는 기본 + 오프셋에서 요소 주소를 계산해야 합니다(오프셋은 요소 크기에 따라 조정됨).
OTOH, p는 변수이며, indirection에는 추가 이동이 필요합니다.
일반적으로 어레이 인덱스는 내부적으로 포인터 산술로서 처리되기 때문에 K&R이 의도한 요점은 알 수 없습니다.
Abhiith의 asm 코드에 의해 이것이 사실이 아니라는 증거가 처음에 제시되는 어레이 토론보다 ptr이 빠른 것에 조금 놀랐습니다.
mov eax, dord ptr _a; // 주소에서 직접 값을 로드합니다.
대
mov eax, dword ptr _p; // p의 주소/값을 eax에 로드합니다.
그리고.
mov ecx, dword ptr [eax]; // 로드된 주소를 사용하여 값에 액세스하여 ecx에 넣습니다.
배열은 CPU가 직접 액세스할 수 있도록 고정된 주소를 나타냅니다. ptr에서는 어레이를 참조하지 않고 CPU가 값에 액세스하기 위해 어레이를 참조할 필요가 없습니다.
두 번째 코드 배지는 배열 오프셋을 계산해야 하므로 호환성이 없습니다. ptr에 대해 계산하려면 적어도 1/2의 명령이 더 필요합니다.
컴파일러가 컴파일 시간 동안 추론할 수 있는 모든 것(고정 주소, 오프셋 등)은 실행 코드의 핵심입니다.반복 코드 비교 및 변수 할당:
어레이:
; 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
대
PTR
; 2796 : tmp2 = *p;
mov eax, DWORD PTR _p$[ebp]
mov ecx, DWORD PTR [eax]
mov DWORD PTR _tmp2$[ebp], ecx
플러스
; 2801 : ++p;
mov eax, DWORD PTR _p$[ebp]
add eax, 4
mov DWORD PTR _p$[ebp], eax
어레이에 비해 ptr load address를 먼저 사용하는 것이 아니라 ptr load address를 먼저 사용하는 것입니다.
안부 전합니다
어레이의 효율과 포인터의 효율: 벡터화의 경우
gcc와 같은 컴파일러를 사용하는 경우 자동 벡터화의 이점을 얻기 위해 포인트 단위로 어레이를 사용하는 것이 매우 합리적일 수 있습니다.
기본 블록 벡터화(일명 SLP)는 ftree-slp-vectorize 플래그로 이니블로 되어 있으며 루프 벡터화와 동일한 플랫폼 의존 플래그가 필요합니다.기본 블록 SLP는 -O3 및 -ftree-vectorize가 네이블일 때 디폴트로 네이블입니다.
표시 가능한 루프
현재 벡터화할 수 없는 루프의 예는 다음과 같습니다.
예 1: 마운트할 수 없는 루프:
while (*p != NULL) {
*q++ = *p++;
}
벡터화 가능한 루프
"vector"는 예에서 보여지는 벡터화 기능을 나타냅니다.
예 1:
int a[256], b[256], c[256];
foo () {
int i;
for (i=0; i<256; i++){
a[i] = b[i] + c[i];
}
}
결산
따라서 포인터나 어레이가 더 낫다는 의견이 많지만 가장 좋은 점은 다음과 같습니다.
- 최상의 플래그를 사용하여 코드를 컴파일하려면
- 컴파일러 탐색기를 사용하여 생성된 바이트 코드를 확인합니다.
- 마지막으로 실제 런타임 속도를 벤치마킹합니다.
언급URL : https://stackoverflow.com/questions/2305770/efficiency-arrays-vs-pointers
'programing' 카테고리의 다른 글
| NuxtJS/VueJs: 페이지가 클라이언트 측에서만 렌더링되었는지 확인하는 방법 (0) | 2022.07.10 |
|---|---|
| C에서 '콜백'이란 무엇이며 어떻게 구현됩니까? (0) | 2022.07.10 |
| vuejs2 데이터에 하위 구성 요소 동적 삽입($compile 또는 v-html 남용 없음) (0) | 2022.07.10 |
| Unsupported Operation이 표시되는 이유목록에서 요소를 제거하려고 할 때 예외가 발생합니까? (0) | 2022.07.10 |
| C의 소켓을 통한 구조 전달 (0) | 2022.07.10 |