c - 확인 - 힙 메모리 란




힙의 메모리 할당이 스택보다 느린 이유는 무엇입니까? (2)

나는 이것을 여러 번 들었다. 하지만 난 모르겠어 ... 힙에서 메모리를 할당 할 때 추가 비용은 얼마나 들까 요? 하드웨어와 관련이 있습니까? CPU주기와 관련이 있습니까? 너무 많은 추측이지만 정확한 답은 없습니다 ... 누군가가 내게 정교함을 줄 수 있습니까?

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


unwind의 답변을 수정 한 편집에서 "힙 데이터 구조"를 언급합니다. heap 알려진 데이터 구조는 동적 메모리 할당과 관계가 없으므로 매우주의하십시오. 매우 명확하게 말하면 무료 스토어 의 언어 변호사 용어를 더 많이 사용하겠습니다.

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

반대로 무료 스토어는 훨씬 더 복잡합니다. 가비지 컬렉션 시스템을 다루기 시작하지는 않을 것입니다.이 주제는 완전히 다른 주제이기 때문에이 질문은 C 언어에 대한 질문이었습니다. 일반적으로 무료 저장소의 할당 및 할당 해제에는 사용 가능한 목록 또는 블록 풀과 같은 여러 가지 데이터 구조가 포함됩니다. 이러한 데이터 구조와 부기는 메모리를 필요로하므로 공간이 낭비됩니다. 또한 부기 기록은 종종 할당과 섞여서 다른 할당의 데이터 지역성을 해친다. 무료 저장소의 할당은 일반적으로 슬래브 할당 자의 형태로보다 많은 프로세스 메모리를 기본 운영 체제에 요청하는 것과 관련 될 수 있습니다.

간단한 비교를 위해 jemalloc-2.2.5와 sloccount의 숫자를 참조로 사용하여 jemalloc 구현은 C 언어로 8,800 개가 넘는 소스 코드와 700 개가 넘는 테스트 코드 라인을 포함합니다. 이것은 자유 저장소 할당과 스택 할당 간의 복잡성의 차이에 대한 좋은 아이디어를 제공합니다 : 수천 줄의 C 코드 대 단일 명령.

또한 무료 저장소 할당은 하나의 어휘 범위에만 국한되지 않으므로 모든 할당의 수명을 추적해야합니다. 마찬가지로 이러한 할당은 스레드를 통해 전달 될 수 있으므로 스레드 동기화 문제가 문제 공간에 입력됩니다. 무료 저장소 할당에 대한 또 다른 큰 문제는 단편화입니다. 단편화로 인해 많은 문제가 발생합니다.

  • 단편화는 데이터 지역을 아프게합니다.
  • 단편화는 메모리를 낭비합니다.
  • 단편화 (Fragmentation)는 큰 할당을위한 여유 공간을 찾기 어렵게 만듭니다.

현대 시스템에서 스택은 무료 저장소와 비교할 때 상대적으로 작기 때문에 궁극적으로 무료 저장소는 더 많은 공간을 관리하므로 더 어려운 문제를 해결합니다. 또한 스택 크기의 제한으로 인해 일반적으로 무료 저장소가 대용량 할당에 사용되므로 매우 큰 할당과 매우 작은 할당을 모두 처리해야하는 불일치로 인해 무료 저장소 작업이 어려워집니다. 일반적으로 스택 할당은 수 킬로바이트 또는 그 이하의 작은 크기이며 스택의 총 크기는 단지 몇 메가 바이트입니다. 무료 저장소는 일반적으로 프로그램의 전체 프로세스 공간 에 제공됩니다. 현대의 컴퓨터에서 이것은 수백 기가 바이트가 될 수 있으며 무료 저장 할당이 문자의 짧은 문자열과 같은 몇 바이트에서 메가 바이트 또는 심지어 임의의 기가 바이트의 데이터까지 크기가 다양하다는 것은 드문 일이 아닙니다. 즉, 무료 저장소 할당자는 기본 운영 체제의 가상 메모리 관리를 처리해야합니다. 스택 할당은 본질적으로 컴퓨터 하드웨어에 내장되어 있습니다.

무료 스토어 할당에 대해 정말로 배우고 싶다면 다양한 malloc 구현에 대해 발표 된 많은 논문과 기사를 읽거나 코드를 읽는 것이 좋습니다. 다음은 시작하기위한 몇 가지 링크입니다.

  • dlmalloc - Doug Lea의 malloc, 한 시점에서 GNU C ++에서 사용 된 역사적인 참조 malloc 구현
  • phkmalloc - phkmalloc -Henning Kamp가 phkmalloc 웹 캐시 저자가 작성한 malloc의 FreeBSD 구현
  • tcmalloc - 일부 Google 개발자가 구현 한 스레드 캐싱 Malloc
  • jemalloc - FreeBSD에 대한 Jason Evan의 malloc 구현 (phkmalloc의 후속 버전)

다음은 tcmalloc 구현에 대한 설명과 함께 추가 링크입니다.


스택과 힙의 주요 차이점은 스택의 항목을 순서가 벗어나 제거 할 수 없다는 것입니다. 항목 A, B, C를 스택에 추가하면 C를 먼저 제거하지 않고 B를 제거 할 수 없습니다. 즉, 새 항목을 스택에 추가한다는 것은 스택의 끝에 추가하는 것을 의미합니다. 이는 매우 간단한 작업입니다. 스택의 끝을 가리키는 포인터를 이동하기 만하면됩니다.

반면에 힙에서는 순서가 맞지 않는 항목을 제거 할 수 있습니다 . 그리고 나중에 다른 항목을 메모리에서 이동하지 않는 한 (일부 가비지 수집 힙처럼) 힙에 중간에 "구멍"이 있습니다. 즉, A, B, C를 힙에 추가하고 B를 제거하면 힙이 메모리에서 다음과 같이 보입니다. _ _ C는 _ 사용되지 않는 (사용 가능한) 메모리 블록입니다. D 항목을 새로 추가하면 할당자는 연속적인 여유 공간을 찾아 D에 맞출 수 있어야합니다. 메모리에 연속되는 여유 공간의 수에 따라 값 비싼 작업이 될 수 있습니다. 그리고 스택의 "마지막 요소"포인터를 움직이는 것보다 거의 항상 비쌉니다.





stack