TL;DR

  • 이진 트리로 1+1+1을 계산하는 자료구조 과제에서 출발해, C로 클로저(closure)와 가비지 컬렉터(garbage collector), 메모리 할당기, REPL, FFI 등을 갖춘 그래프 평가 언어 graphLang을 구축함.
  • 연산자를 각각 별도 표현으로 두는 대신 함수와 값으로 표현해, 평가기가 연산의 의미가 아니라 함수 적용 방식만 알도록 구성함.
  • 변수와 함수 이름을 노드에 연결하는 환경 테이블을 만들고, 사용자 정의 함수를 AST 기반 클로저로 표현해 그래프에서 전달하고 반환할 수 있게 함.
  • 노드 포인터가 깨지는 동적 재할당 문제는 청크 할당기로 해결하고, fib(40)에서 12GB 이상 쓰던 메모리를 마크 앤 스윕 가비지 컬렉터로 약 1.7MB까지 줄임.
  • 메모리 문제는 해결했지만 fib(40) 계산에 6분이 걸리는 성능 문제가 남아 있으며, 후속 작업으로 꼬리 호출 최적화(TCO)와 평가 개선 등을 다룰 예정임.

시작점

  • 자료구조 과제는 이진 트리를 사용해 산술식 1+1+1을 3으로 평가하는 문제임.
  • 먼저 식을 트리로 구성하고, 가장 안쪽의 (+ 1 1)을 2로 줄인 뒤 바깥쪽 덧셈을 계산하는 방식임.
  • 평가기가 알아야 할 것은 +의 의미 자체라는 점에서 출발해, Add, Sub, Mul, Div를 각각 다른 식 유형으로 둘 필요가 있는지 검토함.
  • 네 연산 모두 두 개의 식을 입력받아 하나의 식을 반환하므로, 평가기는 연산 종류가 아니라 함수를 적용하는 방법만 알면 된다는 결론에 도달함.
  • 이에 따라 식을 Func Expr Expr 또는 Val로 표현하고, 변수 Var를 추가함. 변수는 해시 테이블에서 식을 조회하는 방식으로 처리할 수 있다고 봤지만, C에는 내장 해시 테이블이 없어 직접 구현함.

C에서 실제로 구현하기

  • 노드는 태그가 붙은 공용체(tagged union)로 구성함. 초기 노드 유형은 리터럴, 변수, 함수이며, 왼쪽·오른쪽 포인터와 데이터, 유형 태그를 포함함.
  • 64비트 시스템에서 노드 자체는 32바이트이며, malloc() 메타데이터 16바이트를 더하면 노드 하나에 48바이트가 듦.
  • 1+1을 계산하려면 연산자 노드 하나와 피연산자 노드 두 개가 필요해 총 144바이트를 사용함. 작은 노드를 개별적으로 많이 할당하는 방식은 비효율적이므로 사용자 정의 할당기를 구현하기로 함.
  • 초기에는 노드 1,024개를 담는 고정 크기 아레나 할당기(arena allocator)를 만들고, 할당 위치를 나타내는 top을 증가시켜 노드를 제공함.

환경 테이블 만들기

  • 변수와 함수를 같은 환경에 저장하면 함수도 값처럼 다룰 수 있다는 점을 확인함.
  • 환경 테이블의 함수는 인수를 받아 결과를 내는 대상으로 취급함. 처음에는 C 함수 포인터를 저장하려 했지만, 사용자가 언어 안에서 함수를 정의할 수 없고 함수 포인터는 평가기가 내부를 탐색할 수 없는 불투명한 값이라는 문제가 있음.
  • 함수가 다른 함수를 반환하는 경우에도 반환된 함수를 그래프에 넣어 나중에 평가할 수 있어야 하므로, 함수 본문을 트리로 저장하는 클로저 표현을 도입함.
  • 클로저는 한쪽에 매개변수, 다른 쪽에 연산 본문 트리를 담는 그래프 노드임. 이를 통해 사용자 정의 함수를 C 코드에 손대지 않고 만들고, 전달하거나 반환한 뒤 단계별로 평가할 수 있음.
  • 클로저에는 기술적으로 환경도 포함되지만, 이 시점에는 지역 변수를 아직 다루지 않음.
  • 환경 테이블은 이름을 Node * 값에 연결하며, 노드 유형에 클로저와 네이티브 함수도 포함함. 네이티브 함수는 C로 구현된 불투명한 함수이고, 클로저는 언어 수준의 그래프 표현임.
  • 이 단계에서 구성한 요소는 메모리 할당기, 변수·C 함수·사용자 정의 함수를 담는 환경 테이블, 환경을 조회하며 프로그램을 순회하고 함수를 적용하는 평가기임.
  • 렉서와 파서는 아직 없어 AST를 직접 구성해 피보나치 프로그램을 실행했지만, 초기 아레나가 총 1,024개 노드만 담을 수 있어 fib(5)에서 충돌함.

메모리 할당기 업그레이드

  • fib(5)는 약 1만 3천 개의 노드를 생성해 고정 크기 아레나 용량을 초과함.
  • 단일 메모리 블록을 동적 배열처럼 확장하면 realloc() 과정에서 블록이 다른 주소로 이동할 수 있음. 노드끼리 블록 내부 주소를 가리키므로 이동 시 포인터가 깨져 세그멘테이션 오류가 발생할 수 있음.
  • 기존 블록을 이동하는 대신 새 블록을 할당해 연결하는 청크 할당기(chunk allocator)를 구현함. 각 청크는 노드 배열과 다음 청크를 가리키는 포인터를 가지며, 현재 청크가 가득 차면 새 청크로 이동함.
  • 변경 후 fib(5)는 정상적으로 5를 반환함. 그러나 메모리 사용량은 약 1.32MB였고, fib(10)에서는 약 40MB까지 증가함.
  • fib(40)은 약 13억 개의 노드를 생성함. 노드당 48바이트로 계산하면 약 62.4GB 규모의 할당량이며, 실제 실행은 메모리 부족(OOM)으로 중단되기 전 12GB 이상을 사용함.
  • 사용이 끝난 노드를 해제하지 않는 문제가 원인이므로 가비지 컬렉터를 구현함.

가비지 컬렉터 만들기

  • 가비지 컬렉션은 프로그램이 더 이상 도달할 수 없는 노드를 회수하는 작업임.
  • 1+1+1을 평가하면 내부의 (+ 1 1)이 2로 줄어들지만, 이전 피연산자 노드 두 개는 할당 영역에 계속 남아 프로그램 종료 때까지 회수되지 않음.
  • 평가 중 노드를 리터럴로 변경할 때 양쪽 자식 포인터를 null로 설정하면 이전 자식 노드는 해당 그래프 부분에서 더 이상 도달할 수 없음.
  • 마크 단계에서는 루트에서 시작해 도달 가능한 노드를 표시함. 이후 청크를 순회해 표시되지 않은 노드를 freeList라는 연결 리스트에 넣음.
  • 새 노드가 필요할 때 freeList가 비어 있지 않으면 첫 노드를 꺼내 재사용하고, 비어 있을 때만 현재 청크에서 새 노드를 할당함.
  • 가비지 컬렉터 적용 후 fib(40)의 메모리 사용량은 12GB 이상에서 약 1.7MB로 감소함.
  • 하지만 fib(40) 계산에는 6분이 걸림. 구현한 마크 앤 스윕(mark-and-sweep) 방식은 정지형(stop-the-world) 가비지 컬렉터이며, 피보나치 평가 알고리즘 자체도 지수적이므로 메모리 문제 뒤에 성능 문제가 남음.
  • 동시 가비지 컬렉터 구현과 피보나치 평가 방식 개선을 두 문제의 대응 방향으로 제시함.

다음 편에서 다룰 내용

  • 꼬리 호출 최적화(TCO)와 개선된 평가 방식으로 속도 문제를 다룬 내용
  • 렉서와 파서 구현
  • 외부 함수 인터페이스(FFI) 구현
  • REPL 구현
  • 포인터 역참조 방식의 전환
  • C에서 어설픈 캡슐화(scuffed encapsulation) 도입
  • 람다 함수 구현
  • 지역 변수 추가
  • Cheney 복사 수집기(Cheney’s copying collector)를 위한 준비

지금까지 이룬 것

  • 식 유형을 대수적 데이터 유형(Algebraic Data Type)으로 볼 수 있음을 확인함.
  • 실제 변형이 함수, 변수, 리터럴 같은 데이터 종류임을 확인함.
  • 변수와 함수가 서로 다른 종류라기보다 모두 데이터라는 점을 확인함.
  • 평가 후 현재 노드를 변경하는 그래프 평가기를 구현함.
  • 사용자 정의 해시 테이블을 사용하는 환경 테이블을 구현함.
  • 노드 할당을 위한 사용자 정의 청크 할당기를 구현함.
  • 사용이 끝난 노드가 계속 남는 문제를 확인하고 마크 앤 스윕 가비지 컬렉터를 구현함.
  • 전체적으로 그래프 축약(graph reduction) 엔진을 구축함.

그래도 1+1을 계산할 수 있는가

  • 이제 graphLang은 1+1을 계산해 2를 반환함.
  • 다루지 않은 내용도 더 있으며, 관련 내용은 저장소에 있음.