▲

Fil의 믿기 힘든 가비지 컬렉터

 (fil-c.org)
1P by GN⁺ 3일전 | ★ favorite | 댓글 1개
  • Fil-C 언어의 FUGC는 병렬 및 동시성 처리를 지원하는 첨단 가비지 컬렉터임
  • 전체 프로그램 중단 없이 on-the-fly(즉시 실행) 및 grey-stack Dijkstra 방식을 사용함
  • 정확한 메모리 추적과 객체 이동 없이 처리하는 설계를 구현함
  • Safepoint 활용으로 멀티스레드 환경에서도 안전하고 효율적인 메모리 관리 가능함
  • freed 객체 접근/중복 해제시 예외 처리 등 C/Java/JavaScript 스타일의 다양한 메모리 관리 기능을 제공함

Fil의 FUGC(믿기 힘든 가비지 컬렉터) 개요

Fil-C는 병렬 동시 on-the-fly grey-stack Dijkstra 정확 비이동 가비지 컬렉터인 FUGC(Fil's Unbelievable Garbage Collector)를 사용함
FUGC 소스코드는 fugc.c에서 확인 가능하지만, 런타임 및 컴파일러의 다양한 지원 로직 없이는 동작 불가임

FUGC의 주요 특징

  • 병렬 처리: 마킹 및 스윕 작업을 여러 스레드에서 동시에 수행, CPU 코어가 많을수록 수집 속도 증가
  • 동시성 지원: 가비지 컬렉터 스레드는 mutator(즉, 사용자 프로그램 스레드)와 별도로 작업하며, 애플리케이션 스레드는 정지 없이 동작 가능
  • on-the-fly(즉시 실행) : 글로벌 스톱-더-월드 없이 "소프트 핸드쉐이크(=ragged safepoint)"로 각 스레드가 비동기적으로 스택 스캔 등의 특정 작업을 처리함
  • grey-stack 방식: 스레드 스택을 여러번 고정점까지 재검사하여 마킹 반복, 이 과정에서 추가 객체가 나오면 다시 마킹 작업 진행
  • 단순한 store barrier를 활용하고, load barrier는 필요 없음
  • Dijkstra barrier: 마킹 중에 힙이나 글로벌 변수에 포인터를 저장하면 동시에 대상 객체도 마킹
  • 정확 수집: 모든 포인터 위치를 런타임이 정확히 추적하여, GC는 실제 객체만 탐색
  • 객체 비이동 처리: 객체의 메모리 위치가 변하지 않아 멀티스레드 동시수집과 동기화가 쉬움
  • advancing wavefront 설계: mutator가 수집기 작업량 증가시킬 수 없음, 마킹된 객체는 그 수집 사이클에서 계속 유지됨
  • 증분 수집: 일부 객체는 수집 시작 당시 생존 객체여도 사이클 도중 해제될 수 있음

Safepoint(안전 지점) 및 스레드 관리

  • Pollcheck: 컴파일러가 주기적으로 pollcheck 삽입, 빠른 경로에서는 단순 분기, 느린 경로에서는 GC 관련 콜백 실행
  • 소프트 핸드쉐이크: 모든 스레드에 pollcheck 콜백 실행 요청 후 완료까지 대기
  • enter/exit 상태 관리: 장기간 블록킹 함수/시스템 콜 등에서 pollcheck 생략 시 collector가 직접 해당 콜백 실행
  • 멀티스레드를 지원하는 환경에서 경쟁 조건 방지 및 안전한 포인터 접근 보장
  • stop-the-world 모드를 이용해 디버깅이나 fork 등 특수 작업 지원, signal 처리도 안정적으로 구현

FUGC 수집기 루프

  1. GC 트리거 대기
  2. store barrier 활성화 후 소프트 핸드쉐이크(no-op 콜백)
  3. 블랙 할당(신규 객체 선마킹) 활성화, 캐시 리셋 콜백 수행
  4. 글로벌 루트 마킹
  5. 소프트 핸드쉐이크(스택 스캔 및 캐시 리셋 콜백), 마크 스택 비면 7로 이동
  6. 트레이싱(마크 스택의 각 객체에 대해 참조 마킹, 마크 스택이 빌 때까지 반복 후 5로 이동)
  7. store barrier 해제, 스윕 준비, 캐시 재리셋 소프트 핸드쉐이크
  8. 스윕(아직 스윕되지 않은 페이지는 black, 이미 된 곳은 white로 할당)
  9. 루프 재진입

기존 연구와의 차별점 및 최적화

  • FUGC는 DLG(Doligez-Leroy-Gonthier) collector와 유사하지만 간단한 Dijkstra barrier 및 grey stack 활용으로 store barrier 구현이 직관적이고 성능이 뛰어남
  • 고정점 방식으로 빠르게 수렴하고, 비용이 적게 듬
  • bitvector SIMD 기반 스윕을 통해 매우 빠른 해제 처리, 전체 GC 시간의 5% 미만 소모
  • Verse heap config 활용 등으로 성능 최적화

보너스 기능 (메모리 관리 확장성)

객체 해제

  • C의 free 호출 시 객체를 즉시 free로 플래그 처리, 이후 접근 시 트랩 발생
  • dangling pointer(휘청거리는 포인터)로 인한 GC 오작동을 방지
  • 해제된 객체의 참조는 singleton free 객체로 리디렉션되어, 메모리 재할당 이후에도 확실한 검출 가능
  • 사용하지 않는 포인터로 인한 GC 유발 메모리 누수 방지

파이널라이저

  • Java 스타일의 finalizer 큐를 사용자 지정 큐 및 스레드 처리를 통해 유연하게 구현 가능

약한 참조

  • Java의 weak reference와 동일하게 동작, 별도의 reference queue는 없음 (phantom, soft reference 미지원)

약한 맵

  • JavaScript WeakMap과 유사, 단, 모든 요소 반복 및 요소 개수 확인 가능

결론 및 의미

FUGC를 통해 Fil-C는 free 오용에 대해 강력한 안전성 및 직관적인 예외 처리를 제공함

  • 해제된 객체 접근 또는 이중 해제 시 반드시 트랩 발생하도록 설계
  • 객체를 해제하지 않으면 GC가 책임지고 잘 회수해줌
  • 다양한 메모리 관리 패턴을 지원, 기존 C/Java/JavaScript 개발자에게도 친숙한 환경 제공
▲
GN⁺ 3일전  [-]
Hacker News 의견

  • 음, Fil-C가 정말 중요한 의미를 가질 수 있을 것 같음. 오직 C 코드로만 존재하는 소프트웨어가 많아서, 이를 유지하는 접근법이 필요하다고 생각함. 기존 C 컴파일러들은 단일 코어 성능 극대화를 위해 큰 보안 위험을 감수하는데, 이런 트레이드오프는 이미 시대에 뒤떨어진 느낌임. CPython, SQLite, OpenSSH, ICU, CMake, Perl5, Bash 등 지원 리스트가 정말 대단함. 저 소프트웨어들 중 누구도 Rust로 다시 작성될 가능성은 낮다고 봄. Fil-C를 MMU 없는 환경에서 상호 신뢰할 수 없는 프로세스 간 멀티태스킹에도 활용 가능한지 궁금함. 권한 기반 보안, 논블로킹 동기화 등 적절하게 방향을 잡고 있는 것 같음. 누가 실제로 써본 경험 있는지 알고 싶음. 실제로는 최악의 경우에도 4배 정도 속도가 감소한다는 보고가 있는데, 이름이 정말 재밌음. 필쓰웨이! 필쓰웨이!

    • Fil-C로 MMU 없는 컴퓨터에서 신뢰할 수 없는 프로세스 간 멀티태스킹이 가능한지 궁금하다는 질문에 대해, 기본적으로 FUGC가 OS의 MMU 의존적 기능에 기반하긴 하지만, 이런 의존성을 제거한 버전도 만들 수 있을 거라고 봄. 성능 관련해선, 4배 느려지는 것은 최악의 상황이고 그 수치를 직접 보고했음. 항상 현실적으로 성능을 측정하고, 집요하게 성능 문제를 개선해야 하는 성향이 있음. 실제로 Fil-C 버전 소프트웨어로도 평소에 즐겨 사용하는 프로그램을 무리 없이 쓸 수 있음

    • 지원 소프트웨어 리스트가 인상적이라 하셨는데, 일반론에는 동의하지만 예시로 든 소프트웨어는 약간 다르게 봄. CPython, Perl5 등은 원래 GC가 느리기로 유명한 언어의 런타임이라 여기에 GC를 하나 더 얹는 게 우아한 설계는 아닌 듯하고, 오히려 속도 저하가 클 수 있음. 그리고 Rust나 Go 등으로 다시 구현하거나 대체하려는 시도가 이미 일부 있고, 예를 들어 SQLite는 Turso가 있음. 또 이런 소프트웨어는 워낙 활발히 관리되는 근본적인 프로젝트라서 언젠가 자체적으로 리팩터링이나 Rust로의 포팅을 할 수도 있다고 봄. 오히려 Fil-C가 더 적합한 곳은 관리가 덜 되고, 성능에 덜 민감하면서도 계속 사용하는, 50년 전 C 프로그램처럼 누군가 종종 꺼내 쓰는 코드라 생각함

    • SQLite가 C로 작성된 강점은 비표준 OS로의 이식성이 큼임. 예를 들어 임베디드용 RTOS인 μC/OS-II에서 직접 사용한 경험 있음. 임베디드 환경 설계는 PC/서버와 꽤 달라서, 성능과 메모리 단편화 방지 목적으로 메모리 해제를 아예 하지 않고 오브젝트/구조체를 재사용하게 표시함. 커스텀 힙 할당이나 풀링 같은 개념임. SQLite의 VFS 문서, Micro-Controller OS 소개

    • 예시로 든 리스트의 C 소프트웨어를 Rust로 다시 쓸 일은 없다고 하셨는데, 인공지능 기반 정적 분석 도구가 발전해서 C 코드의 문제점을 정확하게 찾아내고, “이 부분은 오류가 생긴다, 이렇게 고치면 된다”라는 피드백을 줄 수 있을 정도가 되기까지 앞으로 얼마나 남았는지 궁금함. 그런 도구가 진짜 나오면 그냥 계속 C를 써도 괜찮아질 수 있음

    • Fil-C가 아직 32비트(혹은 그 이하) 시스템을 지원하지 않는 점 참고해달라는 의견임. Fil-C에서 Invisicaps 관련 문서

  • 이런 프로젝트는 연구와 실용을 동시에 따라가는 드문 사례인 느낌임. 이런 일은 보통 대형 IT 기업에서 팀을 두고 광고 수익으로 운영되는 경우가 많은데, Fil-C는 무슨 배경에서 출발했는지 궁금함. 단순한 개인 열정 프로젝트가 아니라면, 누가 자금을 댔고 몇 년의 인력 투입이 있었는지, 그리고 최종 목표가 무엇인지 궁금함

    • 개인적으로 봤을 때 이건 열정 프로젝트 같음

    • 최종 목표를 묻는 질문에 대해, 프로젝트 저작권이 2024-2025 Epic Games, Inc.라고 명시됨

  • Fil-C의 존재 자체가 반가움. 이런 기술이 실제 프로그램에 효과적임에도 개발자들이 “그런 거 안 된다”고 믿는 경우가 많은데, 직접 구현이 가능하다는 사실만으로도 숱한 논쟁을 단숨에 끊어주는 역할이 있음

    • 벤치마크 결과가 궁금함. 이런 접근법의 가장 큰 우려는 C/C++이 여전히 인기 있는 특정 용례에서 성능이 어마어마하게 떨어지는 게 아닐까 하는 점임. 처리량이나 레이턴시, 메모리 사용량이 Go 같은 언어와 너무 비슷해져버리면, 결국 선택할 이유가 별로 남지 않을 것 같음

    • 프로그래밍 언어에서는 어셈블리 시절부터 성능 대 담론이 항상 존재했음. 다만 대부분의 개발자들은 Ivan Suntherland, Alan Kay, Steve Jobs, Bret Victor 같은 비범한 비전을 가진 사람이 아니고, 눈앞에서 직접 작동하는 것을 보고 신뢰하는 보통 사람임. 그래서 지금도 UNIX와 C의 복제판이 넘쳐나고, 새로운 것을 창조하기보다 과거의 비전을 그대로 답습하며 살아가는 경우가 많은 듯함. 물론 1970년대 당시 UNIX와 C를 만든 두 명도 대단한 비전가였음

  • advancing wavefront 방식 대신 왜 retreating wavefront 전략을 쓰지 않았는지 궁금함

  • 기존 C 프로그램의 free(...) 호출들이 이미 적절하게 들어있고, 모든 포인터에 대해 별도 범위 정보까지 관리하고 있다면, 왜 전체 GC를 선택했는지 궁금함. 대신 lock-and-key 방식의 temporal checking 기법(참고자료: 논문 링크)이 메모리 사용량 예측이나 성능, 스케줄링 면에서 더 나을 수도 있다고 생각함. 아마도 key 저장 공간이 너무 크거나, 확인 시간이 오래 걸리거나, 멀티스레딩 환경에서 레이스 컨디션 문제가 생길 수도 있다고 추정함

    • lock and key 방식엔 Fil-C만의 똑똑한 특징이 없음. Fil-C의 capability 모델은 완전히 스레드 세이프하고, 대부분의 경우 특수한 atomics나 locking이 필요 없다는 점이 강점임

    • 또 포인터 역참조가 없는 범위 밖 포인터 연산을 허용하는 점이 흥미로움. 컴파일러들이 종종 이런 부분의 UB를 노려 최적화를 하기도 하는데(Stack Overflow 관련 질문), Fil-C 내부 LLVM에서는 이런 최적화를 끄는지, 혹은 포인터를 “베이스 + 오프셋” 조합으로 관리해 아예 그런 가능성을 차단하는 것인지 궁금함. 혹시 그러면 일반 포인터에 적용되는 특정 최적화를 놓치게 되는 건 아닌지도 궁금함

  • 정말 멋진 프로젝트로 보임. pollcheck의 fast path가 그냥 load-and-branch라는 것에 주목함. 이런 브랜치 대신 사용하는 흥미로운 기술이 있는데, 안드로이드 공식 블로그의 "암시적 suspend 체크" 문서에 잘 정리되어 있음

    • poll check에서는 저런 최적화를 흔히 씀. 실제로 대부분의 production JVM에서 이미 적용하고 있음. 하지만 나는 아직 저런 저수준 최적화까지 신경쓸 단계는 아님. 현재 남아있는 고수준의 기본적인 최적화들부터 해야 하는 상황임

  • GC가 붙은 동시성 지원 C, 그것도 non-moving GC라는 점이 정말 신기함. 만약 중형급 C 프로젝트를 2~3배의 런타임 성능 손해와 맞바꾸고 메모리 버그를 줄일 수 있다면, 충분히 감수할 의향이 있음. 점진적 도입이 얼마나 쉬운지 궁금함. 각 대상마다 가능한지, 아니면 전체 툴체인을 다 바꿔야 하는지 궁금함

  • 나는 C와 성능, 그리고 보안을 모두 중요하게 여김. 이 GC와 capability 구조는 매력적임. “더 안전한 C”는 어떤 모습일지 여러 번 생각해 봤는데, capability 개념을 몇 번씩 검토하긴 했지만 난 컴파일러 코드는 잘 다루지 못함. Windows 지원이 힘든지 궁금함

    • 사담이지만, 첫 문장에 Oxford comma가 없어서 무슨 뜻인지 이해하는데 꽤 오래 걸림. 이렇게 명확한 예시는 흔하지 않음

  • GC에서 루트 오브젝트를 어떻게 추적하는지 궁금함. GC가 스캔할 루트를 미리 표시하는 컴파일 단계라도 있는지, 혹시 아는 사람이 설명해줄 수 있는지 문의함

    • LLVM이 stack map을 채우기 위한 명령어를 삽입해서 해결하고 있음

  • 이 프로젝트 정말 놀라움. 여태까지 들어본 적이 없던 게 이상할 정도임. 한번 직접 써보는 게 기대됨. 성능 한계로 실서비스에는 힘들 수 있지만, 일부 프로그램의 안전성을 직접 검증해볼 방법으로는 정말 유용해 보임. 평소에 사용하는 sanitizer보다는 더 포괄적인 느낌임

답변달기