스택에서보다 힙 내의 데이터에 더 빨리 액세스할 수 있습니까?

스택에서보다 힙 내의 데이터에 더 빨리 액세스할 수 있습니까?

일반적인 질문으로 들릴 수도 있고 비슷한 질문(여기서나 웹에서나)을 많이 봐왔지만, 어떤 질문도 저의 딜레마와는 다릅니다.

다음 코드가 있다고 가정합니다.

void GetSomeData(char* buffer)
{
    // put some data in buffer
}

int main()
{
     char buffer[1024];
     while(1)
     {
          GetSomeData(buffer);
          // do something with the data
     }
     return 0;
}

buffer [ 1024 ]를 글로벌하게 선언하면 퍼포먼스가 향상됩니까?

time 명령어를 사용하여 unix에서 몇 가지 테스트를 실행했는데 실행 시간에는 거의 차이가 없습니다.

하지만 확신이 안 서...

이론적으로 이 변화가 변화를 가져올까요?

스택에서보다 힙 내의 데이터에 더 빨리 액세스할 수 있습니까?

원래 그런 게 아니라...지금까지 작업한 모든 아키텍처에서 모든 프로세스 "메모리"는 현재 데이터를 보관하고 있는 CPU 캐시/RAM/스왑 파일의 수준과 다른 프로세스에서 볼 수 있도록 트리거되는 하드웨어 수준의 동기화 지연에 따라 동일한 속도로 동작할 수 있습니다.프로세스/CPU(코어)의 변경 등

페이지 장애/스왑을 담당하는 OS와 아직 액세스되지 않은 페이지 또는 스왑 아웃된 페이지에 대한 액세스에 대한 트래핑 하드웨어(CPU)는 어떤 페이지가 "글로벌"인지 "스택"인지 "히프"인지를 추적하지 않습니다.메모리 페이지는 메모리 페이지입니다.

메모리가 배치되는 글로벌/스택/히프 사용 현황은 OS 및 하드웨어에서 알 수 없으며 모두 동일한 성능 특성을 가진 동일한 유형의 메모리에 의해 백업되지만 기타 미묘한 고려사항이 있습니다(이 목록 뒤에 자세히 설명되어 있습니다).

• allocation - 프로그램이 메모리를 "배치" 및 "배치 해제"하는 데 소비하는 시간(가끔 포함)sbrk히프 사용률 증가에 따른 가상 주소 할당(또는 이와 유사)
• access - 프로그램이 글로벌 vs 스택 vs 힙에 액세스하기 위해 사용하는 CPU 명령의 차이 및 힙 기반 데이터를 사용할 때 런타임 포인터를 통한 추가 방향 지정,
• 레이아웃 - 특정 데이터 구조("collections")는 보다 캐시 친화적인 반면(더 빠른 속도) 일부의 범용 구현에는 힙 할당이 필요하며 캐시 친화적이지 않을 수 있습니다.

할당 및 할당 해제

글로벌 데이터(C++ 네임스페이스 데이터 멤버 포함)의 경우 가상 주소는 보통 컴파일 시에 계산되어 하드코드됩니다(절대적인 용어로, 또는 세그먼트레지스터로부터의 오프셋으로서 생각할 수 있습니다).프로세스가 OS에 의해 로드될 때 조정이 필요할 수 있습니다).

스택 베이스의 데이터의 경우, 스택 포인트간 레지스터 상대 주소를 계산해, 컴파일시에 하드 코드 할 수도 있습니다.그런 다음 stack-pointer-register는 함수 입력 및 반환 시(즉, 실행 시) 함수 인수, 로컬 변수, 반환 주소 및 저장된 CPU 레지스터의 총 크기에 따라 조정할 수 있습니다.스택 기반 변수를 추가하면 스택포인트인터 레지스터 조정에 사용되는 총 크기가 변경되기만 할 뿐, 그 영향은 더욱 악화되지 않습니다.

위의 두 가지 방법 모두 런타임 할당/할당 해제 오버헤드가 효과적으로 없는 반면 힙 기반 오버헤드는 매우 현실적이며 일부 애플리케이션에서는 중요할 수 있습니다.

힙 기반 데이터의 경우 런타임 힙 할당 라이브러리는 내부 데이터 구조를 참조하여 애플리케이션이 메모리를 해방하거나 삭제할 때까지 라이브러리가 애플리케이션에 제공한 특정 포인터와 관련된 힙 메모리 블록의 어떤 부분을 관리하는지 추적해야 합니다.힙 메모리를 위한 가상 주소 공간이 부족할 경우 다음과 같은 OS 함수를 호출해야 할 수 있습니다.sbrk추가 메모리를 요구하다(Linux가 호출할 수도 있음)mmap대용량 메모리 요청에 대한 백업 메모리를 만든 다음 해당 메모리 매핑을 해제합니다.free/delete).

접근

절대 가상 주소 또는 세그먼트 또는 스택포인트 레지스터 상대 주소는 글로벌 및 스택 기반 데이터의 컴파일 시에 계산할 수 있기 때문에 런타임접근은 매우 빠릅니다.

힙 호스트된 데이터를 사용하면 프로그램은 힙 상의 가상 메모리 주소를 유지하는 런타임 결정 포인터를 통해 데이터에 액세스해야 합니다. 때로는 런타임에 특정 데이터 멤버에 대한 포인터에서 오프셋을 적용하기도 합니다.일부 아키텍처에서는 시간이 좀 더 걸릴 수 있습니다.

힙 액세스의 경우 데이터에 액세스할 수 있도록 포인터와 힙 메모리가 모두 레지스터에 있어야 합니다(따라서 CPU 캐시에 대한 요구가 증가하고 확장 시 캐시 누락/장애 오버헤드가 증가합니다).

주의: 레이텐시 또는 throughput이 매우 중요한 것을 쓰고 있지 않는 한, 이러한 비용은 거의 의미가 없습니다.

레이아웃

소스코드의 연속된 행이 글로벌 변수를 나열하면 인접 메모리 위치에 배열됩니다(정렬 목적으로 패딩할 수도 있음).같은 함수에 나열된 스택 기반 변수도 마찬가지입니다.X바이트의 데이터가 있는 경우 N바이트 캐시 라인의 경우 X/N 또는 X/N + 1개의 캐시 라인을 사용하여 액세스할 수 있는 메모리에 적절하게 패키지되어 있다는 것을 알 수 있습니다.다른 스택 콘텐츠(함수 인수, 반환 주소 등)가 프로그램에 동시에 필요할 가능성이 높기 때문에 캐싱이 매우 효율적입니다.

힙 기반 메모리를 사용하는 경우 힙 할당 라이브러리에 대한 연속 호출은 특히 할당 크기가 일정한 비트(예를 들어 3바이트 할당 후 13바이트 할당)가 다르거나 이미 많은 할당 및 할당 해제('조각화'의 원인)가 있는 경우 서로 다른 캐시 행의 메모리에 대한 포인터를 쉽게 반환할 수 있습니다.즉, 다수의 작은 힙 할당 메모리에 액세스하려면 최악의 경우 포인터를 포함하는 메모리를 힙에 로드해야 할 뿐만 아니라 캐시 행의 수만큼 폴트 인해야 합니다.힙 할당 메모리는 스택 할당 데이터와 캐시 라인을 공유하지 않으므로 시너지 효과가 없습니다.

또한 C++ 표준 라이브러리는 스택 기반 메모리에서 사용하도록 설계된 링크 목록, 균형 잡힌 바이너리 트리, 해시 테이블 등 보다 복잡한 데이터 구조를 제공하지 않습니다.따라서 스택을 사용할 때 프로그래머는 메모리 내에서 연속되는 어레이에 대해 가능한 모든 것을 실행하는 경향이 있습니다.이는 다소 무리한 검색을 의미하더라도 마찬가지입니다.캐시 효율은 요소가 더 많은 캐시 라인에 분산되어 있는 힙 기반 데이터 컨테이너보다 전반적으로 더 나은 결과를 가져올 수 있습니다.물론 스택 사용량은 많은 요소로 확장되지 않으며, 적어도 힙을 사용하는 백업 옵션이 없으면 처리할 데이터가 예상보다 많을 경우 작동이 중지되는 프로그램이 생성됩니다.

예제 프로그램에 대한 토론

이 예에서는 글로벌 변수를 함수 로컬(스택/자동) 변수와 비교합니다.더미는 필요 없어요히프 메모리는new또는malloc/realloc히프 메모리의 경우, 퍼포먼스상의 문제는, 애플리케이션 자체가, 어느 주소에서 사용되고 있는 메모리의 양을 추적하고 있는 것입니다.메모리에의 포인터로서 갱신에 시간이 걸리는 모든 레코드는, 다음에 의해서 배포됩니다.new/malloc/realloc포인터로서 갱신에 시간이 걸립니다.deleted 또는freed.

글로벌 변수의 경우 메모리의 할당은 컴파일 시에 효과적으로 수행될 수 있습니다.스택 기반 변수의 경우 일반적으로 함수가 호출될 때마다 로컬 변수(및 일부 하우스키핑 데이터) 크기의 컴파일 시간 계산 합계에 의해 증가하는 스택포인터가 있습니다그래서 언제?main()스택 포인터를 변경하는 데 시간이 걸릴 수 있습니다.단, 스택포인터가 수정되지 않은 경우 수정되지 않는 것이 아니라 다른 양으로 수정되었을 가능성이 있습니다.buffer변경되어 런타임 성능에는 전혀 차이가 없습니다.

메모

나는 위에서 지루하고 대부분 무관한 세부사항들을 생략한다.예를 들어, 어떤 CPU는 다른 함수에 대한 호출을 시작할 때 어떤 함수의 상태를 저장하기 위해 레지스터의 "윈도우"를 사용합니다.어떤 함수 상태는 스택이 아닌 레지스터에 저장됩니다.일부 함수 인수는 스택이 아닌 레지스터로 전달됩니다.모든 운영시스템이 가상 어드레싱을 사용하는 것은 아닙니다.PC 등급 이외의 하드도 있습니다.ware의 메모리 아키텍처는 복잡할 수 있습니다.다양한 의미가 있습니다.

Jeff Hill의 답변에서 인용:

스택은 액세스 패턴에 의해 메모리 할당 및 할당 해제가 간단해지기 때문에 고속입니다(포인터/정수는 단순히 증가 또는 감소합니다).한편, 힙은 할당 또는 자유와 관련된 훨씬 복잡한 부기가 있습니다.또, 스택내의 각 바이트는 매우 빈번하게 재사용되는 경향이 있습니다.즉, 이 바이트는 프로세서의 캐시에 매핑되기 때문에 매우 빠릅니다.힙의 또 다른 퍼포먼스 히트는 대부분 글로벌리소스로서 일반적으로 멀티스레딩의 안전성이 필요합니다.즉, 각 할당 및 할당 해제는 일반적으로 프로그램 내의 다른 모든 힙액세스와 동기화되어야 합니다.

There is blog post available on this topic stack-allocation-vs-heap-allocation-performance-benchmark Which shows the allocation strategies benchmark. Test is written in C and performs compare between pure allocation attempts, and allocation with memory init. At different total data sizes, number of loops are performed and time is measured. Each allocation consists of 10 different alloc/init/free blocks with different sizes (total size shown in charts).

Test are run on Intel(R) Core(TM) i7-6600U CPU, Linux 64 bit, 4.15.0-50-generic, Spectre and Meltdown patches disabled.

With out init:

With init:

In the result we see that there is significant difference in pure allocations with out data init. The stack is faster than heap, but take a note that loop count is ultra high.

When allocated data is being processed, the gap between stack & heap performance seems to reduce. At 1M malloc/init/free (or stack alloc) loops with 10 allocation attempts at each loop, stack is only 8% ahead of heap in terms of total time.

Your question doesn't really have an answer; it depends on what else you are doing. Generally speaking, most machines use the same "memory" structure over the entire process, so regardless of where (heap, stack or global memory) the variable resides, access time will be identical. On the other hand, most modern machines have a hierarchial memory structure, with a memory pipeline, several levels of cache, main memory, and virtual memory. Depending on what has gone on previously on the processor, the actual access may be to any one of these (regardless of whether it is heap, stack or global), and the access times here vary enormously, from a single clock if the memory is in the right place in the pipeline, to something around 10 milliseconds if the system has to go to virtual memory on disk.

In all cases, the key is locality. If an access is "near" a previous access, you greatly improve the chance of finding it in one of the faster locations: cache, for example. In this regard, putting smaller objects on the stack may be faster, because when you access the arguments of a function, you're access on stack memory (with an Intel 32-bit processor, at least---with better designed processors, arguments are more likely to be in registers). But this will probably not be an issue when an array is involved.

중요한 점은 다음과 같은 코드의 루프는 큰 어레이의 각 요소에 대해 읽고 쓰는 것만으로 어레이가 스택 상에 있을 때와 히프 상에 있을 때(GCC, Windows 10, -O3 플래그)에 있을 때, 재부팅 직후(히프 플래그먼테이션이 최소화되었을 때)에도 일관되게 5배 빠르게 실행됩니다.

const int size = 100100100;
int vals[size]; // STACK
// int *vals = new int[size]; // HEAP
startTimer();
for (int i = 1; i < size; ++i) {
    vals[i] = vals[i - 1];
}
stopTimer();
std::cout << vals[size - 1];
// delete[] vals; // HEAP

물론 처음에는 스택 크기를 400MB로 늘려야 했습니다.컴파일러가 모든 것을 최적화하지 않도록 하려면 마지막에 마지막 요소를 인쇄해야 합니다.

스택에 버퍼를 할당하는 경우 최적화 범위는 메모리에 액세스하는 비용이 아니라 종종 매우 비싼 동적 메모리 할당을 힙에서 제거하는 것입니다(스택 버퍼 할당은 스레드 시작 시 스택 전체가 할당되므로 즉시로 간주할 수 있습니다).

힙에 선언된 변수 및 변수 배열이 더 느리다는 것은 사실일 뿐입니다.이렇게 생각해 보세요.

글로벌하게 생성된 변수는 한 번 할당되고 프로그램이 닫히면 할당 해제됩니다.힙 객체의 경우 함수를 실행할 때마다 변수를 즉석에서 할당하고 함수의 마지막에 할당 해제해야 합니다.

함수 내에서 객체 포인터를 할당해 본 적이 있습니까?함수가 종료되기 전에 메모리를 해방/삭제하는 것이 좋습니다.그렇지 않으면 디컨스트럭터 내에서 자유/삭제된 클래스 오브젝트에서는 이 작업을 하지 않는다는 메모리 누설이 발생합니다.

어레이의 액세스에 관해서는, 모두 동일하게 동작합니다.메모리 블록은 처음에 size of (Data Type)* 요소에 의해 할당됩니다.나중에 접속하려면 ->

1 2 3 4 5 6 
^ entry point [0]
      ^ entry point [0]+3

언급URL : https://stackoverflow.com/questions/24057331/is-accessing-data-in-the-heap-faster-than-from-the-stack