[Lecture 17] Automatic Memory Management, Performance

# Performence of Automatic Memory Management

• 실제 garbage collector들은 그들이 만드는 절충안에 매우 다양하다. 개발자들은 수십 년 동안 그것들을 설계하는 데 소비되어 왔다.
  • 예를 들어, 자바 10은 4개의 다른 컬렉터와 함께 사용된다. ZGC는 2018년에 추가된 5번째 컬렉터이다
• 프로그램 처리량, 메모리 오버헤드, GC 처리량, 확장성 등 많은 특성이 다르다
•  garbage collector의 정책을 적절히 조정하고 성능에 미치는 영향을 이해하려면 작업 부하를 잘 이해해야 한다

#Modeling the Cost of GC

Compacting Collectors: Garbage collector는 객체 그래프, 특히 다른 객체에 대한 포인터가 저장되는 위치에 대해 거의 모든 것을 알고 있다. 따라서 객체를 이동(그리고 포인터를 업데이트)할 수 있어 압축이 가능하다. 라이브 객체는 힙의 한 영역에서 "대피 (evacuated)"되거나 "파기 (scavenged)" 되어 도달할 수 없는 객체만 남으므로 결국 해당 영역을 한 번에 회수할 수 있다

 

• 따라서 GC 비용은 다음과 같다:
  • 표시 (marking) 비용 + 대피 (evacuated) 비용은 표시된 영역의 실제 개체 크기에 비례
  • 스위프 비용 - 이론적으로는 constant / O(1)이다. 실제로, 할당자는 대부분의 언어에서 재사용할 수 있도록 메모리를 비워내야 하며, 따라서 생성된 쓰레기의 양에 비례하다

#Memory Allocation Time Profile

Memory Allocation vs Time in the absence of GC. Amax denotes the heap limit. Garbage increases monotonically

Simplified version:

Simplified memory allocation profile, showing one GC

#Performance of Allocator

The performance index, P, a weighted sum of the space utilization and throughput

U는 공간 활용도, T는 처리량, Topt는 default traces에서 시스템에 malloc의 최적화된 구현의 처리량이다. 성능 지수는 처리량보다 공간 활용도를 선호하며, 값은 w = 0.6이다. 메모리와 CPU 사이클이 모두 값비싼 시스템 리소스라는 것을 관찰하면서, 우리는 메모리 활용도와 처리량 모두의 균형 잡힌 최적화를 위해 이 공식을 사용한다. 이상적으로 성능 지수는 P = w + (1 - w) = 1 또는 100%에 도달한다. 각 메트릭은 성능 지수에 각각 최대 w와 1 - w를 기여하므로 메모리 활용도 또는 처리량만 최적화를 극단적으로 해서는 안 된다.

#Synthetic Example

public class LargeLiveHeap
{
    public static void main(String []av) {
    int numLive = Integer.parseInt(av[0]);
    int numAllocations = Integer.parseInt(av[1]);
    byte[][] l = new byte[numLive][];
    for (int i = 0; i < numAllocations; i++){
    l[i % numLive] = new byte[100000];
    }
  }
}

numLive = 3, numAllocations = 12

#Heap Size vs GC Frequency

• 라이브 힙 크기가 크면 JVM이 힙 limit에 가까워질 때 가비지 수집 빈도가 증가하는 경향이 있다(Java-Xmx 스위치)
• 그렇다면 JVM은 OS에 얼마나 더 많은 메모리를 요청해야 할까?
• JVM이 사용하려는 메모리 양과 달성 가능한 처리량 간의 일반적인 균형이 잡혀야 한다
• 명시적 할당에 비해 허용 가능한 성능 오버헤드 내에서 유지하려면 라이브 힙의 1.5배 – 2.5배 크기를 예산해야 한다
• Hertz 2005:
  • GC는 5배 이상으로 malloc의 성능을 능가한다
  • GC는 17%의 성능 저하를 위해 3배 필요
  • 2배만 사용하는 경우 최대 70% 더 느려질 수 있다
• 실시간 힙 크기가 최대 힙 크기에 가까워짐에 따라 성능 저하("gc thrashing")

#The Generational Hypothesis

• 오브젝트가 살아있을 가능성은 시간이 지남에 따라 증가하며, "most objects die young" 이라고 불린다
• 작은 컬렉션에서 더 자주 수집되는 "어린이집" 또는 "에덴" 공간이라는 특수 영역에 개체를 할당한다
• 생존한 개체를 주요 컬렉션에서 덜 자주 수집되는 이전 세대로 대피한다
• 이를 위해서는 write barrier를 통한 mutator(사용자 프로그램)와 collector 간의 조정이 필요하다
  • 뮤테이터는 Eden Space에 대한 포인터의 수집기를 알려야 한다. old.field = young은 young을 위한 루트를 추가해야 한다

Generational Hypothesis

#Garbage Collection vs Mutators

GC가 진행되는 동안 도달 가능성 그래프가 변경되면 어떻게 될까? 개체를 계속 사용할 수 있는 개체의 마지막 포인터를 실수로 놓치는 일이 없도록 해야 한다

• "Stop-the-World" 접근법. 수집하는 동안 모든 mutator를 중지한다. "GC Pauses" 상태로 됨
• Incremental collection: 개체를 할당하는 동안 GC의 작은 부분들이 작동할까?
• Concurrent/Parallel collection: GC는 어떤 방식으로든 뮤테이터 스레드와 동기화하는 별도의 스레드에서 실행된다. 일반적으로 뮤테이터는 생성된 새 에지를 수집기에 알리며, 수집기는 포인터가 변경되면 뮤테이터에게 알린다

#G1GC and ZGC

• 현재 기본 collector: G1 GC
  • GC를 지원하기 위해 유휴 코어를 사용할 수 있는 멀티 코어 시스템을 위해 설계됨
• ZGC (2018)
  • 대기 시간이 짧은 단일 세대 수집기(루트 검색 중에만 뮤테이터 중지)
  • Use load barriers를 사용하여 뮤테이터를 멈추지 않고 오브첵트를 이동할 수 있다

#Programmer’s Perspective

• 프로그램의 메모리가 부족하다고 가정해보자 (Java에서는 Out Of MemoryError가 발생한다). 이 문제는 라이브 힙 크기가 메모리 제한을 초과할 때 발생한다. 일반적으로 다음 세 가지 이유 중 하나로 인해 발생한다.
  • 힙 크기 제한이 너무 낮음
  • Leaks
  • Bloat
• GC에 많은 시간이 소요되면 프로그램 성능이 저하된다
  • Churn
  • 헤드룸 (headroom) 부족

#Leak vs Bloat vs Churn

• leak: 라이브 힙에 프로그램이 나중에 액세스할 수 없는 도달 가능한 개체가 포함되어 있다
  • 예: 조회되지 않는 해시 맵에 있는 항목
  • 이벤트 핸들러 및/또는 콜백이 등록되었거나 등록되지 않은 경우
• Weak references로 인해 가비지 컬렉터가 다시 만들 수 있는 개체를 free 할 수 있다
  • 예: 캐싱할 때
• Bloat: 힙에는 프로그램이 액세스할 개체만 포함되어 있지만 이러한 개체가 너무 많은 공간을 차지할때
  • 예: 자바의 Boxed integer
  • 해시맵에 저장된 항목들
• 메모리 분석 도구는 leak 및 bloat에 도움이 된다
• Churn: 프로그램이 많은 short-lived, 즉 단명 객체(높은 할당률)를 할당할때, 특히 Android와 같은 리소스가 제한된 장치에서 중요하다

#Conservative Garbage Collection

• 정확한 가비지 컬렉터는 모든 힙 객체와 스택 프레임의 구조에 대한 정확한 정보를 가지고 있으며, 따라서 포인터를 저장하는 모든 위치에 대한 정확한 지식을 가지고 있다
• managed 언어들에서 실행된다: Java, C#, JavaScript, Python, Go, 그러나 (일반적으로) C/C++에서는 실행 가능하지 않다
• Conservative Garbage Collection들은 힙을 스캔하고 포인터가 될 수 있는 모든 것을 하나라고 가정한다
• 연결할 수 없는 일부 개체를 계속 사용할 수 있음
• Boehm's GC는 C/C++용으로 잘 알려진 collector이다
• GC Safety는 다음과 같은 코드를 생성하는 것을 피하기 위한 컴파일러의 속성이다
• Valgrind의 leak detection은 동일한 접근 방식을 사용한다