가비지 컬렉터 압축은 실제 개체를 수집해야하기 때문에 기존의 메모리 관리보다 빠르며 모든 것을 하나의 연속 된 블록으로 메모리에 재 배열하면 힙 조각화가 발생하지 않습니다. 그러나 어떻게 그렇게 빨리 할 수 있습니까? 그것은 저의 것으로 짐 패킹 문제, 즉 NP-hard과 같으며 계산에 대한 우리 지식의 현재 한계 내에서 큰 데이터 세트에 적당한 시간 내에 완료 될 수 없습니다. 내가 뭘 놓치고 있니?힙 압축은 어떻게 신속하게 작동합니까?
압축은 RAM에있는 개체를 이동하여 일부 개체가 제거되고 (죽은 개체, GC가 회수해야 함) 나머지 모든 개체가 RAM에서 연속되도록합니다.
대부분의 압축 GC 작업은 내에서 개체를 할당하여 운영 체제에서 가져온 연속 영역입니다. 압축은 죽은 물체를 제거한 다음 남아있는 모든 살아있는 물체를 "왼쪽으로"밀면서 구멍을 짜내는 것과 같습니다. GC가 압축에 의해 작동하면 할당은 "할당 된 영역의 끝"포인터 위로 이동하는 문제입니다. 종합적으로, 할당 영역 내에는 빈 영역이 그 포인터 다음의 바이트로 구성되는 포인터가 있습니다. 오브젝트에 대한 공간을 할당하기 위해 포인터는 새 오브젝트 크기만큼 간단히 위로 이동합니다. 때로는 GC가 실행될 시간이고, 죽은 객체를 감지하고, 구멍을 쥐어 짜기 때문에 할당 포인터를 낮추는 경우가 있습니다. 압축 GC에서
성능 향상은 여러 소스에서 온 : 건설하여, 하나의 여유 공간이 항상있다 : 할당
는 경우 운영 체제 대신 다음 GC를 압축하기 때문에 여러 블록이 다음 상황이 조금 더 복잡하고, 빈 포장 문제처럼 보이기 시작할 수 항복, 하나의 할당 영역을 제공 거부 어떤 블록이 각각의 살아있는 객체로가는지를 결정해야한다. 그러나 빈 포장의 복잡성은 일반적인 경우에 "완벽한"일치를 찾는 것입니다. 대략적인 해결책은 메모리 할당자를 위해 이미 충분하다.
압축 알고리즘의 알고리즘 난이도는 모든 포인터를 업데이트하여 새 개체 위치를 가리키는 것입니다. 엄격한 입력을 통해 .NET 가상 컴퓨터는 RAM의 각 단어가 포인터인지 아닌지를 명확하게 결정할 수 있지만 지나치게 많은 RAM을 사용하지 않고 모든 포인터를 효율적으로 업데이트하는 것은 까다로운 작업 일 수 있습니다. H.B.M. Jonkers는 "A Fast Garbage Compaction Algorithm"(Information Processing Letters, Volume 9, Number 1, 1979, pp. 26-30)에서이를위한 멋지고 똑똑한 알고리즘을 설명했습니다. 광대 한 인터넷에서이 논문의 사본을 찾을 수는 없지만 알고리즘은 Jones and Lins (5.6 절)의 "Garbage Collection" 서적에 설명되어 있습니다. 가비지 콜렉터를 이해하는 데 관심이있는 모든 사람에게이 책을 권하고 싶습니다. Jonkers의 알고리즘은 실제 객체에 대해 두 번의 선형 패스가 필요하며 쉽게 구현할 수 있습니다 (몇 줄의 코드가 더 이상 필요하지 않으며 가장 어려운 부분은 왜 작동하는지 이해하는 것입니다).
추가적인 복잡도는 세대 콜렉터에서 발생합니다. 대부분의 경우 개체의 대부분을 그대로두고 젊은 개체 만 우선적으로 사용합니다. 여기서 이것은 힙의 끝만 압축하는 것을 의미합니다. 전체 압축은 드물게 적용됩니다. 여기에서 요점은 완전한 압축은 선형이지만 여전히 눈에 띄는 일시 정지를 유도 할 수 있다는 것입니다. 세대 별 GC는 그러한 일시 중지를 더 드물게 시도합니다. 다시 Jones와 Lins의 책은 반드시 읽어야합니다.
언어의 참조를 포인터 테이블에 대한 포인터로 구현함으로써 순진한 압축 GC를 구현할 수 있다고 생각합니다. 압축 후에 GC가 테이블을 업데이트하면됩니다. 이것은 모든 역 참조를 이중 역 참조로 만들고 테이블을위한 여분의 공간을 요구합니다. –
Joseph : 실제로 이것은 종종 소위 리소스, 커널 측 할당으로 수행됩니다. 적어도 고전적인 맥 OS는 그렇게했다. –
종이에 대한 링크 : http://oai.cwi.nl/oai/asset/9391/9391A.pdf –
나는 종종 이것을 궁금해했습니다. 모노에는 힙을 압축하는 조각 모음 가비지 수집기가 없지만 Microsoft의 .NET은 않습니다. 그들은 그걸 어떻게 햇어? –
압축은 빈 포장이 아닙니다. 빈 포장에서 "이 공간을 정확하게 채울 수 있습니까?"라는 질문에 답해야합니다. 압축 GC에는 이러한 문제가 없으며 압축은 일반적으로 실제 메모리 크기에서 선형입니다. –
@Callum Rogers 한 가지 방법은 다음과 같습니다. 1 단계 - 모든 포인터를 그 자리에서 반전시켜 어린이가 부모를 가리 키도록합니다. 2 단계 - 가장 낮은 주소의 라이브 블록을 힙의 맨 처음으로 이동합니다. 거꾸로 포인터를 사용하여 모든 부모를 업데이트하십시오. 첫 번째 블록 바로 뒤에서 가장 낮은 주소의 두 번째 라이브 블록을 이동하십시오 .... 3 단계 - 모든 포인터를 다시 반전하십시오. –