힙에 대한 메모리 할당이 스택에 비해 훨씬 느린 이유는?

힙에 대한 메모리 할당이 스택에 비해 훨씬 느린 이유는?

나는 이런 말을 여러 번 들었다.하지만 왜 그런지...힙에서 메모리를 할당할 때 추가 비용이 발생하는가?하드웨어 관련인가?CPU 사이클과 관련이 있는가?많은 추측이 있지만 정확한 답은 없다...누가 좀 자세히 설명해 주시겠습니까?

"unwind"가 말했듯이, 힙 데이터 구조는 스택보다 더 복잡하다.그리고 내 생각에, 일부 메모리 공간은 스레드가 실행되기 시작할 때 스택으로 스레드에 할당되는 반면, 힙은 프로세스 내의 모든 스레드에 의해 공유된다.이 패러다임은 가비지 컬렉션과 같이 각 스레드의 공유 힙 사용을 관리하기 위한 몇 가지 추가적인 메커니즘이 필요하다.내 말이 맞나?

왜냐하면 힙은 스택보다 훨씬 더 복잡한 데이터 구조이기 때문이다.

많은 아키텍처에서 스택에 메모리를 할당하는 것은 스택 포인터를 변경하는 것, 즉 하나의 명령이다.힙에 메모리를 할당하려면 충분한 블록을 찾고, 분할하며, 다음과 같은 작업을 허용하는 "부기"를 관리해야 한다.free()순서가 다른 순서로

스택에 할당된 메모리는 스코프(일반적으로 기능)가 종료될 때 할당 해제되는 것이 보장되며, 일부만 할당 해제할 수는 없다.

답안지를 다시 작성할 편집에서 "heap 데이터 구조"를 언급하십시오.힙으로 알려진 데이터 구조는 동적 메모리 할당과 관련이 없으므로 매우 주의하십시오.확실히 하자면, 나는 자유 가게의 더 많은 언어 변호사 용어를 사용할 것이다.

이미 지적한 바와 같이, 스택 할당은 포인터를 증분해야 하는데, 일반적으로 대부분의 아키텍처에 전용 레지스터를 두고 있으며, 할당 해제는 동일한 양의 작업을 필요로 한다.스택 할당도 특정 기능으로 범위가 지정된다.따라서 스택에 필요한 총 공간을 미리 계산하고 전체 스택 프레임에 대해 단일 증분을 수행하는 것과 같은 컴파일러 최적화에 훨씬 더 적합한 후보군이 될 수 있다.마찬가지로 스택은 데이터 인접성을 더 잘 보장한다.스택의 상단은 거의 항상 캐시 라인 안에 있을 것을 보장하며, 이미 언급했듯이 스택 포인터는 일반적으로 레지스터에 저장된다.일부 아키텍처에서 컴파일러를 최적화하면 더 깊은 스택 프레임에서 함수를 호출하는 인수로 전달된 이전 스택 프레임의 인수를 재사용함으로써 스택에 대한 할당을 완전히 제거할 수 있다.마찬가지로 할당된 변수 스택도 할당을 회피하는 레지스터로 승격될 수 있다.

이에 비해 프리스토어는 훨씬 복잡하다.전혀 다른 주제인 쓰레기 수거 시스템을 다루려고도 하지 않을 겁니다. 그리고 이 질문은 C 언어에 대한 질문이었습니다.일반적으로 자유 저장소의 할당 및 할당 해제에는 자유 목록 또는 블록 풀과 같은 몇 가지 다른 데이터 구조가 포함된다.이러한 데이터 구조와 부기에도 메모리가 필요하기 때문에 공간이 낭비된다.게다가, 장부 기록과 배정이 혼재되어 다른 배정의 데이터 인접성을 해치는 경우가 많다.자유 저장소의 할당에는 기본 운영 체제에 슬래브 할당자의 어떤 형태에서 일반적으로 더 많은 프로세스 메모리를 요청하는 것이 포함될 수 있다.

간단한 비교를 위해, 그리고 참조로 제말록-2.2.5와 슬로카운트의 숫자를 사용하는 제말록 구현은 C언어로 8,800개 이상의 소스 코드와 700개 이상의 시험 코드를 포함한다.이렇게 하면 무료 저장소 할당과 스택 할당 간의 복잡성 차이(수천 줄의 C 코드 대 단일 명령어)를 잘 알 수 있을 것이다.

또한, 무료 매장 할당은 단일 어휘적 범위에 한정되지 않기 때문에, 모든 할당의 수명을 추적해야 한다.마찬가지로, 이러한 할당은 스레드에 걸쳐 전달될 수 있으며, 따라서 스레드 동기화 문제도 문제 공간으로 들어간다.자유점포 할당의 또 다른 큰 문제는 단편화다.단편화는 많은 문제를 야기한다.

• 단편화는 데이터 인접성을 해친다.
• 단편화는 메모리를 낭비한다.
• 단편화는 대규모 할당을 위한 여유 공간을 찾는 일을 더 어렵게 만든다.

현대의 시스템에서는, 스택은 종종 자유 상점에 비해 상대적으로 작기 때문에, 궁극적으로 자유 상점은 더 많은 공간을 관리하고, 따라서 더 어려운 문제를 해결하고 있다.또한, 스택 크기에 대한 제한으로 인해, 자유 상점은 일반적으로 더 큰 할당에 사용되는데, 매우 큰 할당과 아주 작은 할당을 모두 처리해야 하는 것 사이의 불일치는 자유 상점의 일을 더 어렵게 만든다.일반적으로 스택 할당은 몇 킬로바이트 이하의 순서에 따라 작으며, 스택의 총 크기는 몇 메가바이트에 불과하다.무료 매장은 일반적으로 프로그램의 나머지 프로세스 공간 전체를 제공한다.현대의 컴퓨터에서는 수백 기가바이트가 될 수 있으며, 무료 저장소 할당의 크기가 짧은 문자열처럼 몇 바이트에서 메가바이트 또는 심지어 기가바이트의 임의 데이터에 이르기까지 다양해지는 것은 드문 일이 아니다.이는 자유 저장소 할당자가 기본 운영 체제의 가상 메모리 관리를 처리해야 한다는 것을 의미한다.스택 할당은 기본적으로 컴퓨터 하드웨어에 내장되어 있다.

만약 당신이 정말로 무료 매장 할당에 대해 배우고 싶다면, 나는 다양한 만록 구현에 대해 발표된 많은 논문과 기사들 중 몇 가지를 읽거나 코드를 읽는 것을 강력히 추천한다.시작하기 위한 몇 가지 링크:

• dlmalloc - Doug Lea의 malloc, GNU C++에서 한 번에 사용된 과거 참조 malloc 구현
• phkmalloc - FreeB바니쉬 웹 캐시의 Poul-Henning Kamp 저자가 작성한 malloc의 SD 구현
• tcmalloc - 일부 Google 개발자가 구현한 스레드-캐칭 Malloc
• Jemalloc - Jason Evan의 FreeBSD용 malloc 구현(phkmalloc의 프로세서)

TCMalloc 구현에 대한 몇 가지 추가 링크:

• http://jamesgolick.com/2013/5/15/memory-allocators-101.html
• http://jamesgolick.com/2013/5/19/how-tcmalloc-works.html

스택 영역 데이터 생성 : 스택 포인터를 이동하기만 하면 헤드 영역 데이터 생성 : 주어진 요구 사항을 충족하는 메모리 풀(첫 번째 적합, 최적의 적합 또는 최악의 적합)에서 영역을 검색하십시오.해당 지역을 찾은 후 정보 저장(예약 보관)

스택의 삭제 : 스택의 삭제는 쉽다.스택 포인터를 아래로 이동 힙 영역에서 삭제: 요소가 힙에 저장되어 있는 위치를 찾고(책 보관 사용) 필요한 경우 인접한 두 개의 사용 가능한 블록을 병합;

스택과 힙의 주요 차이점은 스택의 항목을 순서대로 제거할 수 없다는 것이다.A, B, C 항목을 스택에 추가하면 C를 먼저 제거하지 않고는 B를 제거할 수 없다.즉, 스택에 새로운 항목을 추가하는 것은 스택의 끝에 항목을 추가하는 것을 의미하는데, 이것은 매우 간단한 작업이다.스택의 끝을 가리키는 포인터를 이동하면 된다.

반면, 당신은 순서가 맞지 않는 항목들을 제거할 수 있다.그리고 나중에 기억 속에서 다른 물건들을 옮기지 않는 한(일부 쓰레기 더미들이 그러하듯이) 당신의 힙은 중간에 "구멍"이 있다.즉, A,B,C를 힙에 추가하고 B를 제거하면 기억에서 A _C가 이렇게 보인다. 여기서 _는 사용되지 않는(자유로운) 메모리의 블록이다.지금 새 항목 D를 추가하면 할당자는 D에 맞도록 충분히 큰 연속적인 여유 공간을 찾아야 한다.기억 속에 계속 여유 공간이 얼마나 있느냐에 따라 이것은 값비싼 작업이 될 수 있다.그리고 그것은 스택의 "마지막 요소" 포인터를 움직이는 것보다 거의 항상 더 비싸다.

참조URL: https://stackoverflow.com/questions/2264969/why-is-memory-allocation-on-heap-much-slower-than-on-stack