Perceus 참조 카운팅 GC 구현하기

Introduction

참조 카운팅(RC)은 지난 수십 년 동안 함수형 프로그래밍에서 다른 가비지 컬렉션(GC) 알고리즘들에 비해 다소 마이너한 위치에 있었다. 예를 들어 OCaml과 Haskell은 비-RC GC를 사용한다. 하지만 Counting Immutable Beans: Reference Counting Optimized for Purely Functional Programming 및 Perceus: Garbage Free Reference Counting with Reuse 같은 최근의 여러 논문은, 순환 참조 같은 일부 언어 기능을 희생하거나 제한하는 대가를 치르는 대신 함수형 언어에서 고도로 최적화된 RC GC가 효율적일 수 있음을 보여주었다. 특히 후자의 논문은 기본적으로 올인원 RC라 할 수 있는 Perceus라는 효율적인 RC GC 알고리즘을 소개했다.

이 글에서는 Perceus RC를 구현하고 그 이점을 얻는 과정에서의 경험과 몇 가지 주의점을 설명한다. 나는 Pen이라는 프로그래밍 언어를 개발해 왔고, 그 안에 Perceus RC의 큰 부분을 구현했다. 이 글이 알고리즘을 구현하고 있는 사람, 혹은 자신의 언어에 구현할 가치가 있는지 고민하는 사람에게 도움이 되길 바란다.

Overview of Perceus

Perceus 참조 카운팅 알고리즘은 스레드 안전한 소유권 기반 참조 카운팅 알고리즘이며, 몇 가지 최적화를 포함한다:

• 데이터 구조 생성 및 해체(패턴 매칭)에서의 힙 재사용
• 힙 재사용 특수화(데이터 구조의 제자리 갱신)
• 여러 스레드가 공유하지 않는 힙 블록에 대해 비원자적 연산 또는 완화된 메모리 순서를 사용하는 원자적 연산
• 참조 카운트 연산을 줄이기 위한 borrow inference

이 모든 최적화를 Koka 프로그래밍 언어에 구현함으로써, 레드-블랙 트리처럼 공통 부분 구조를 자주 유지하는 여러 알고리즘 및 데이터 구조에서 OCaml, Haskell, 심지어 C++을 포함한 다른 언어들보다 GC 오버헤드는 훨씬 작고 실행 시간은 더 빠르다는 결과를 얻었다. 자세한 내용은 논문의 최신 버전을 참고하라.

Implementing the algorithm

현재까지 Pen에서 구현한 Perceus 알고리즘의 핵심 기능은 두 가지다:

• 힙 상의 레코드 제자리 갱신(in-place updates)

  • 이는 위에서 설명한 힙 재사용 특수화에 해당한다.

• 여러 스레드에서 공유되지 않는 참조에 대한 완화된(리랙스드) 원자적 연산

Koka와 Pen의 언어 기능 차이 때문에 알고리즘에 약간의 수정을 가해야 했다. 먼저, Pen은 힙 재사용 특수화를 이용한 제자리 레코드 갱신을 위해 복잡한 알고리즘이 필요 없다. Pen에는 레코드 갱신 문법이 있으며, 이것이 참조 카운팅 알고리즘이 적용되는 중간 수준 중간 표현(MIR)으로 직접 로워링되기 때문이다.

둘째로, 처음에는 함수 내에서 해제(free)와 할당(allocation)을 매칭하는 일반적인 힙 블록 재사용도 구현했지만, 현재는 되돌려 놓았다. Pen에서는 해체를 동반하는 패턴 매칭 문법이 없고, 이후에 구현할 예정인 작은 레코드 언박싱 최적화도 있기 때문에, 당장 성능 향상이 크지 않을 것임을 깨달았기 때문이다. 또한 구현에는 아직 borrow inference가 포함되어 있지 않다. 이전 논문에서 보고된 바에 따르면 성능 기여도가 가장 작았기 때문이다.

알고리즘의 주요 부분은 아래에 나열한 컴파일러 자체의 소스 파일과 Rust로 작성된 FFI 라이브러리에 구현되어 있다:

• https://github.com/pen-lang/pen/blob/d44df6d9cdcbe97fcdd5ac14c4de30f4897664ff/lib/mir-fmm/src/reference_count/pointer.rs
• https://github.com/pen-lang/pen/blob/d44df6d9cdcbe97fcdd5ac14c4de30f4897664ff/lib/ffi/src/arc/arc_block.rs

Counting back synchronized references to 0

이 섹션에서는 "synchronized"라는 용어를 "여러 스레드에 의해 공유됨으로 표시된"이라는 의미로 사용한다. Koka와 Lean 4에서는 같은 의미로 "shared"라는 용어를 쓰지만, 혼동을 줄이기 위해 나는 표현을 바꿨다.

Perceus 참조 카운팅 GC에서 메모리 블록은 주로 양수 카운트와 음수 카운트로 각각 표현되는 두 상태, 즉 _un-synchronized_와 synchronized 상태를 가진다. 힙 블록은 다른 스레드와 공유되기 전에 _synchronized_가 되며, 한 번 synchronized가 되면 다시 un-synchronized 상태로 되돌아가지 않는다. 하지만 이것이 정말 필요한지 의문이 들 수 있다. 참조 카운트가 1인 메모리 블록이 있다면, 이는 더 이상 다른 스레드와 공유되지 않는다는 뜻이기도 하다. 그렇다면 0이라는 공통 카운트 값을 이용해 유일 참조(unique reference)를 표현하고, 일부 원자적 연산의 오버헤드를 잠재적으로 줄일 수 있지 않을까?

답은 아니다. 그렇게 하려면, _un-synchronized_로 되돌아간 참조들에 대한 메모리 연산을 다른 스레드가 해당 참조들을 drop할 때의 연산과 release 메모리 순서로 동기화해야 하기 때문이다. 예를 들어 한 스레드가 다른 스레드와 참조를 공유하는 상황을 생각해 보자:

1. 스레드 A가 스레드 B와 참조를 공유한다.
2. 어떤 계산이 진행된다...
3. 스레드 B가 그 참조를 drop한다.
4. 스레드 A가 그 참조를 drop하고 그리고 내부 메모리 블록을 해제한다. * 또는, 스레드 A가 앞 섹션에서 언급한 힙 재사용 최적화를 위해 그 메모리 블록을 재사용한다.

따라서 참조가 다시 _un-synchronized_로 돌아갈 수 있다면, 위의 (4) 지점에서 항상 acquire 메모리 순서를 갖는 원자적 연산을 사용해야 한다. 그래야 (3) 지점에서 스레드 B가 수행한 모든 부수 효과가 스레드 A에 보이게 된다. 그렇지 않으면 스레드 A가 스레드 B가 읽으려는 메모리 위치를 해제하거나 덮어쓸 수도 있다! 결과적으로 이전에 한 번도 _synchronized_되지 않은 참조들에 대해서도 오히려 원자적 연산 오버헤드를 증가시키게 된다.

Benefitting from the algorithm

일반적으로 Perceus 알고리즘의 힙 재사용을 최대한 활용하려면, 오래된 데이터로 채워진 데이터 구조가 일부의 새로운 데이터로만 갱신되도록 코드를 작성해야 한다. Pen의 컴파일러에는 이전에 성능 버그가 있었는데, 비교적 오래된 데이터 구조가 같은 타입의 새로운 데이터 구조에 병합되는 형태였다. 그 결과, 두 조각의 데이터를 병합하는 코드는 의미론적으로는 올바름에도 불구하고 거의 두 배의 시간이 걸리고 있었다.

Recursive data types

언어에 레코드 타입과 레코드 필드 접근 문법이 있을 때는 상황이 조금 복잡해질 수 있다. 다음의 의사 코드에서 타입 A의 재귀적 데이터 구조를 제자리에서 갱신하고 싶다고 해 보자(코드는 Elm으로 작성되었지만 Perceus로 구현했다고 가정하자):

type alias A =
  { x : Maybe A
  , y : Int
  }

f : A -> A

-- From here, assume that we are in a function scope rather than a module scope.
foo : A
foo = { x = Nothing, y = 42 }

bar : A
bar =
  -- Here, we want to reuse a memory block of `foo`...
  { foo |
    x = case foo.x of
      Nothing -> Nothing
      -- There are two references to `x` on evaluation of `f x` here!
      Just x -> f x
  }

Just x -> f x 라인에서 프로그램은 foo에서 유래한 필드 값 x에 함수 f를 적용한다. 하지만 함수 적용 시점에는 레코드 값 foo 자체를 여전히 유지하고 있으며 x 값에는 참조가 두 개가 있다! 따라서 힙 재사용 특수화(즉, 제자리 레코드 갱신)를 적용할 수 없다. 대신 x 값을 제자리에서 갱신하려면, 다음처럼 먼저 foo를 내부 값들로 해체해야 한다.

bar =
  let { x, y } = foo
  in
    { x =
      case x of
        Nothing -> Nothing
        Just x -> f x
    , y = y
    }

언어가 레코드 해체를 지원하지 않더라도, 자기 자신을 재귀적으로 포함하는 타입의 경우 그 타입 자체를 담는 필드를 drop하는 것은 실무적으로 대부분 가능하다는 점에 유의하라. 그렇지 않으면 그러한 타입의 값은, 그 필드에 함수나 thunk로 동적으로 생성되지 않는 한, 런타임에 존재할 수 없기 때문이다.

the Koka's documentation을 보면 레코드 타입을 지원하는 것으로 보이지만, 이 특정 케이스를 어떻게 처리하는지는 아직 찾지 못했다. 컴파일러의 세부 사항을 노출하고, 최종 사용자에게 제자리 갱신을 강제하는 애너테이션을 허용하는 것도 하나의 선택지지만, 장기적으로 최선의 선택은 아닐 수 있다.

Benchmarking

여기서는 몇 가지 벤치마크 결과와 그 개선을 보여주고 싶다. 설정의 자세한 내용은 뒤 섹션에 있다. Pen은 여전히 힙 할당을 줄이기 위한 몇 가지 기본 최적화(예: 람다 리프팅, 힙에서 작은 값 언박싱)가 부족하다. 따라서 Perceus로 인한 최종적인 성능 개선은 여기 결과보다 낮아질 것이다.

Pen에 대해 mark-and-sweep 같은 다른 GC 방식을 이전에 구현해 본 적이 없기 때문에, 이는 RC GC와 비-RC GC의 비교가 아니다. 오히려 함수형 프로그래밍 언어에서 전통적인 스레드 안전 RC가 Perceus를 채택함으로써 얼마나 성능이 좋아질 수 있는지에 대한 증명에 가깝다.

Configuration

Conway's game of life

구현은 리스트를 사용해 필드와 생명(lives)을 표현하므로, 힙에서 메모리 블록의 할당과 해제를 많이 발생시킨다.

• Field size: 20 x 40
• Iterations: 100
• Implementation

Hash map insertion/update

맵 갱신 벤치마크에는 맵 초기화를 위한 삽입에 걸린 시간도 포함되어 있다.

• A number of entries: 100,000
• Key type: 64-bit floating point number
• Data structure: Hash-Array Mapped Trie (HAMT)
• Implementation
  • Insertion
  • Update

Conclusion

지금까지의 경험으로는, Perceus 알고리즘 구현은 다른 비-RC GC 알고리즘들에 비해 상당히 직관적인 편으로 보인다. 다만 특히 저수준 동시성과 원자적 명령에 익숙하지 않다면 몇 가지 걸림돌이 있다.

간단한 구현임에도 내 언어에 이 알고리즘을 구현해 두고 좋은 성능을 확인할 수 있어 매우 만족스럽다. Perceus RC는 함수형 프로그래밍에서 게임 체인저가 될 수 있는데, 함수형 프로그래밍에서 흔한 여러 패턴에서 전통적인 GC를 능가하기 때문이다. 하지만 이것이 모두에게 맞는 것은 분명 아니며, 대부분의 경우 언어 설계에 영향을 준다.

끝으로 읽어줘서 고맙다! 이 글과 Pen 프로그래밍 언어에 대한 피드백을 주면 감사하겠다. 언어의 새 릴리스는 Homebrew의 LLVM 14 채택 때문에 막혀 있었지만, 지난 몇 주 동안 이슈에 진전이 있었다. 그래서 아마도 v0.4를 곧 릴리스할 수 있을 것 같다...

또한 알고리즘에 대한 질문에 답해 준 Koka 개발자들에게 특별히 감사한다. 정말 큰 도움이 되었다!

Appendix

Raw benchmark results

환경:

> uname -a
Linux xenon 5.13.0-1033-gcp #40~20.04.1-Ubuntu SMP Tue Jun 14 00:44:12 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

> lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         46 bits physical, 48 bits virtual
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Xeon(R) CPU @ 2.20GHz
Virtualization features:
  Hypervisor vendor:     KVM
Caches (sum of all):
  L1d:                   64 KiB (2 instances)
  L1i:                   64 KiB (2 instances)
  L2:                    512 KiB (2 instances)
  L3:                    55 MiB (1 instance)

> lsmem
Memory block size:       128M
Total online memory:       4G

Conway's game of life

> hyperfine -w 3 ./life-old ./life-new
Benchmark 1: ./life-old
  Time (mean ± σ):      2.136 s ±  0.033 s    [User: 1.699 s, System: 0.392 s]
  Range (min … max):    2.097 s …  2.206 s    10 runs

Benchmark 2: ./life-new
  Time (mean ± σ):      1.142 s ±  0.035 s    [User: 1.087 s, System: 0.009 s]
  Range (min … max):    1.102 s …  1.203 s    10 runs

Summary
  './life-new' ran
    1.87 ± 0.06 times faster than './life-old'

Hash map insertion

> hyperfine -w 3 ./insert-old ./insert-new
Benchmark 1: ./insert-old
  Time (mean ± σ):     909.0 ms ±  14.2 ms    [User: 605.7 ms, System: 250.6 ms]
  Range (min … max):   890.7 ms … 932.8 ms    10 runs

Benchmark 2: ./insert-new
  Time (mean ± σ):     254.8 ms ±   5.1 ms    [User: 189.1 ms, System: 15.0 ms]
  Range (min … max):   247.0 ms … 263.4 ms    12 runs

Summary
  './insert-new' ran
    3.57 ± 0.09 times faster than './insert-old'

Hash map update

> hyperfine -w 3 ./update-old ./update-new
Benchmark 1: ./update-old
  Time (mean ± σ):      1.935 s ±  0.032 s    [User: 1.405 s, System: 0.476 s]
  Range (min … max):    1.879 s …  1.976 s    10 runs

Benchmark 2: ./update-new
  Time (mean ± σ):     448.6 ms ±  14.4 ms    [User: 381.5 ms, System: 15.1 ms]
  Range (min … max):   430.9 ms … 484.3 ms    10 runs

Summary
  './update-new' ran
    4.31 ± 0.16 times faster than './update-old'