가비지 수집을 위해 마크 비트를 함께 사용하고 분리하는 것의 장점과 단점은 무엇입니까?

Question

영상을 보고 있었는데 Google IO 2008 - Dalvik 가상 머신 내부 Dalvik VM의 작동 방식과 사람들이 Android용 JVM보다 Dalvik VM을 선호하는 이유를 이해합니다.나는 안드로이드가 객체와 함께 마크 비트(객체가 가비지 수집이 가능한지 여부를 알려주는 비트)가 있는 JVM과 달리 객체에 대한 가비지 정보에 대해 별도의 메모리를 사용한다는 것을 발견했습니다.

마크 비트를 위한 별도의 메모리를 갖는 것과 마크 비트를 위한 별도의 메모리를 갖지 않는 것의 장점과 단점이 무엇인지 자세히 말해 줄 수 있는 사람이 있습니까?

동영상을 볼 때는 이 차이를 알 수 없었습니다.

Answer 1

별도의 비트맵의 장점:

• 훨씬 더 조밀합니다.일반적인 GC에는 8비트의 GC 메타데이터가 필요하지만 정렬로 인해 객체 내 헤더가 이 메모리를 최대 32비트로 반올림할 수 있습니다.
• 특히 청소와 관련된 일부 작업이 더 빨라졌습니다.이는 부분적으로 비트맵의 밀도가 높을수록(위 참조) 메모리 트래픽이 적고 캐시 사용이 더 좋아지기 때문일 뿐만 아니라 일부 작업(예:모든 표시 비트를 제로화)는 이 형식일 때 벡터화될 수 있습니다.(GC의 다른 부분은 해당 기능을 활용하도록 설계되어야 합니다.)
• 만약 너라면 fork() Unix 시스템에서는 별도의 비트마크를 사용하면 쓰기 중 복사를 더 잘 사용할 수 있습니다.개체가 포함된 페이지는 계속 공유될 수 있습니다.

객체 내 마크 비트의 장점:

• 개체를 비트맵과 연결하는 데 사용되는 구성표에 따라 개체에 대한 표시 비트를 가져오거나 그 반대로 가져오는 것은 상당히 복잡하거나 느릴 수 있습니다.반면에 객체 내 헤더는 액세스하기가 쉽지 않습니다.
• 더 쉬워진 메모리 관리:적절한 크기의 별도 할당을 생성하고 동기화를 유지할 필요가 없습니다.
• 객체에 대한 비트맵을 찾는 빠른 방법(또는 그 반대의 경우)은 다른 측면에서 매우 제한적입니다.예를 들어, 모든 페이지에 대해 비트맵을 만들고 페이지 시작 부분에 비트맵 포인터를 저장하는 경우 페이지보다 큰 개체를 저장하는 데 문제가 있습니다.

Answer 2

별도의 표시 비트는 각 비트가 개체를 시작할 수 있는 힙의 주소를 나타내는 비트 배열을 가짐으로써 작동합니다.예를 들어 힙이 65536바이트이고 모든 개체가 16바이트 경계에 정렬되어 있다고 가정하면 힙에 개체의 시작이 될 수 있는 주소가 4096개 있습니다.이는 배열이 4096비트를 포함해야 함을 의미하며, 이는 512바이트 또는 64개의 64비트 크기의 부호 없는 정수로 효율적으로 저장할 수 있습니다.

객체 내 표시 비트는 객체가 표시되면 각 객체의 각 헤더에 있는 한 비트가 1로 설정되고 그렇지 않으면 0으로 설정되는 방식으로 작동합니다.이를 위해서는 각 개체에 전용 헤더 영역이 있어야 합니다.JVM 및 .NET과 같은 런타임은 모두 객체에 헤더를 추가하므로 기본적으로 마크 비트를 위한 공간을 무료로 얻을 수 있습니다.

그러나 이는 실행 중인 환경을 완전히 제어할 수 없는 보수적인 수집가에게는 작동하지 않습니다. 뵘GC.정수를 포인터로 잘못 식별할 수 있으므로 mutator 데이터 힙의 모든 항목을 수정하는 것은 위험합니다.

마크 앤 스윕 가비지 수집은 두 단계로 나뉩니다.표시 및 청소.객체 내 표시 비트를 사용하여 표시하는 것은 간단합니다(의사 코드).

if not obj.is_marked():
    obj.mark()
    mark_stack.append(obj)

마크 비트를 저장하기 위해 별도의 배열을 사용하여 객체 주소와 크기를 비트 배열의 인덱스로 변환하고 해당 비트를 1로 설정해야 합니다.

obj_bits = obj.size_in_bytes() / 16
bit_idx = (obj - heap.start_address()) / 16
if not bitarr.bit_set(bit_idx):
    bitarr.set_range(bit_idx, obj_bits)
    mark_stack.append(obj)

따라서 이 예에서는 객체의 길이가 128바이트인 경우 비트 배열에 8비트가 설정됩니다.분명히 객체 내 표시 비트를 사용하는 것이 훨씬 간단합니다.

그러나 별도의 표시 비트는 스위핑할 때 어느 정도 추진력을 얻습니다.스위핑에는 전체 힙을 검색하고 표시되지 않았으므로 회수할 수 있는 연속적인 메모리 영역을 찾는 작업이 포함됩니다.객체 내 표시 비트를 사용하면 대략 다음과 같습니다.

iter = heap.start_address()
while iter < heap.end_address():
    # Scan til the next unmarked object
    while iter.is_marked():
        iter.unmark()
        iter += iter.size()
        if iter == heap.end_address():
            return
    # At an unmarked block
    start = iter
    # Scan til the next marked object
    while iter < heap.end_address() and not iter.is_marked():
        iter += iter.size()
    size = iter - start
    # Reclaim the block
    heap.reclaim(start, size)

반복이 객체에서 객체로 어떻게 이동하는지 확인하세요. iter += iter.size() 윤곽.이는 스윕 단계 실행 시간이 라이브 개체와 가비지 개체의 총 개수에 비례한다는 것을 의미합니다.

별도의 표시 비트를 사용하면 가비지 개체의 큰 덩어리가 각각에서 "중지"되지 않고 날아간다는 점을 제외하면 대략 동일한 루프를 수행하게 됩니다.

65536 힙을 다시 고려해보세요.모두 가비지인 4096개의 개체가 포함되어 있다고 가정합니다.마크 비트 배열에서 64개의 64비트 정수를 반복하고 모두 0임을 확인하는 것은 확실히 매우 빠릅니다.따라서 별도의 마크 비트를 사용하면 스위핑 단계가 훨씬 더 빨라질 수 있습니다.

하지만 또 다른 주름이 있습니다!모든 마크 및 스윕 컬렉터에서 실행 시간은 일반적으로 매우 빠른 스윕 단계가 아닌 마크 단계에 의해 지배됩니다.그래서 아직 판결이 나오지 않은 상태입니다.일부는 별도의 마크 비트를 선호하고 다른 일부는 객체 내 비트를 선호합니다.내가 아는 한, 아직까지 어떤 접근 방식이 다른 접근 방식보다 우월한지 보여줄 수 있는 사람은 아무도 없습니다.