OxCaml의 기능, 다른 언어들이 훔쳐야 할 것

대부분의 언어에서는 프로파일러를 사용하여 메모리 할당(allocation)을 추적하지만, 실제 핵심 로직(hot path)에 손을 대는 순간 다시 발생합니다.

Jane Street의 OCaml 슈퍼셋인 OxCaml은 이 상황을 뒤집을 수 있게 해줍니다. 함수에 [@zero_alloc] 어노테이션을 추가하면 컴파일러가 해당 호출 트리 내에서 힙(heap) 메모리를 건드리는 것을 거부합니다.

OxCaml은 전체 함수가 할당하지 않도록(on the heap) 단언할 수 있게 합니다. 만약 그 호출 트리 내부에서 할당하기 시작하면, 컴파일러는 실패하며 할당했다는 사실을 알려줍니다. 정적 분석(static analysis)으로도 이 목표를 달성할 수는 있겠지만, 이렇게 컴파일러 자체에서 가능하게 하는 주류 언어는 거의 없습니다. 제가 아는 예외적인 경우는 Swift와 Clang뿐입니다.¹

대부분의 언어(Java, Go, C#, Rust, Zig, OCaml 등)에서는 과정이 반대입니다. 프로파일러를 사용하여 할당을 찾아내려고 합니다 (보통 수백만 번 발생하는 루프 내부에서). 그런 다음 그 할당을 제거하거나 최소화합니다. 하지만 핵심 로직의 코드 한 줄이라도 수정하는 순간, 문맥(context)을 잊고 다시 할당하기 시작할 수 있고, 결국 프로파일러를 들고 처음부터 다시 시작해야 합니다.

D 언어에서는 함수에 @nogc로 표시할 수 있지만, 이는 가비지 컬렉터(garbage collector) 없이도 힙 메모리를 할당하는 것을 막지는 못합니다. Zig (그리고 아마도 더 최신 버전의 Rust)에서는 아키텍처를 따르는 것만으로 회귀(regression)를 최소화할 수도 있습니다 (예: 함수에 할당자(allocator)를 전달하지 않는 방식). 하지만 관습은 무시되거나 우회될 수 있습니다. 왜 컴파일러가 이 작업을 수행하도록 두지 않을까요?

이 글에서는 OxCaml의 [@zero_alloc] 단언이 어떻게 작동하는지 살펴보겠습니다.

전제 조건#

먼저 OxCaml을 설치해야 합니다 (시간이 좀 걸릴 것입니다).

sudo apt-get -y install unzip bubblewrap hyperfine build-essential autoconf
bash -c 

우선, CSV의 행들을 합산하는 단순한 OCaml 프로그램을 작성해 보겠습니다 (아직 OxCaml 기능은 사용하지 않습니다). 관용적이지 않을 수 있지만, 핵심은 이 제로 할당(zero allocation) 단언 기능을 보여주는 것입니다.

먼저 첫 번째 명령줄 인수로 주어진 경로에서 파일을 엽니다. 그런 다음 `sum_column`을 호출하고 열 합산할 열을 나타내기 위해 두 번째 명령줄 인수를 전달합니다.

let () =
let path = Sys.argv.(1) in
let col = int_of_string Sys.argv.(2) in
...

main_alloc.ml

OCaml에서 함수 호출에 괄호가 필요하지 않다는 점을 기억하세요. `.(X)` 구문은 배열 접근입니다. 그리고 `open_in_bin`과 `close_in`은 파일용 표준 라이브러리 함수입니다.

다음으로 파일을 64KB 청크 단위로 반복 처리할 것입니다.

let chunk = 1 lsl 16
let sum_column (ic: in_channel) (col: int) =
let buf = Bytes.create chunk in
...

main_alloc.ml

`ref`는 OCaml에서 가변 값(mutable values)을 위한 래퍼입니다. `!`는 `ref` 타입의 역참조 연산자이며, `:=`는 `ref` 타입에 대한 할당 연산자입니다.

이제 `sum_column_incremental` 내부에서는 버퍼를 문자 단위로 반복 처리할 것입니다. 사용자가 합산하라고 요청한 열을 파싱한 후 문자열로 변환할 수 있도록 필드 문자를 버퍼에 단순하게 누적합니다.

type state = { mutable column : int; field : Buffer.t; mutable sum : int }
let sum_column_incremental (st: state) (buf: Bytes.t) (len: int) (col: int): unit =
for i = 0 to len - 1 do
...

main_alloc.ml

`<-`는 OCaml의 레코드 필드 할당입니다.

이것은 좋은 CSV 파서가 아닙니다. 따옴표나 다른 것은 처리하려고 하지 않습니다.

실행을 위해 대용량 CSV 데이터셋(2개 열, 1억 행)을 생성해 보겠습니다.

awk -v n=100000000 'BEGIN { srand(1); for (i = 1; i <= n; i++) print i "," int(rand() * 1000) }' > data.csv

그리고 두 번째 열을 합산해 보겠습니다.

$ ocamlopt main_alloc.ml -o main_alloc
$ ./main_alloc data.csv 1
sum=49947827758

나쁘지 않다! 하지만 성능이 마음에 들지 않는다. Hyperfine에 따르면 이 Digital Ocean 가상 머신(4vCPU, 8GB RAM)에서 완료하는 데 보통 약 13초가 걸린다고 한다.

$ hyperfine './main_alloc data.csv 1'
Benchmark 1: ./main_alloc data.csv 1
Time (mean ± σ): 13.637 s ± 0.572 s [User: 13.263 s, System: 0.373 s]
...

## 프로그램 디버깅하기#

이 시점에서는 실제로 프로파일러(profiler)를 사용해서 어느 부분에서 시간을 소비하는지 찾아봐야 한다. 디버그 심볼(debug symbols)을 포함하여 프로그램을 다시 컴파일하고 `perf`로 분석해 보자.

$ ocamlopt -g main_alloc.ml -o main_alloc
$ perf record -g --call-graph dwarf ./main_alloc data.csv 1
$ perf report
...

perf 리포트 내부에서 `sum_column_incremental` 부분에 많은 시간이 소비된 것을 발견하는데, 이는 당연한 일이다. 하지만 문자열을 할당하는 데 예상외로 큰 시간 부분이 있다는 것도 알게 된다. 이걸... 멈출 수 있을까?

## 어설션 기반 최적화(Assertion-guided optimizing)#

다른 언어라면 `perf`를 사용하고 코드에 면밀히 살펴보면서 메모리 할당을 발견하는 과정을 계속해야 했을 것이다. 하지만 OxCaml을 사용하면 함수에 단순히 `[@zero_alloc]` 레이블을 붙여주기만 하면 컴파일러가 실패하며 우리가 어느 곳에서 할당했는지 모든 장소를 알려준다.

정말 놀랍다.

`main_alloc.ml` 파일을 `main_noalloc.ml`로 복사하고, `sum_column` 함수에 `[@zero_alloc]`을 표시해 보자.

let[@zero_alloc] sum_column (ic: in_channel) (col: int) =
let buf = Bytes.create chunk in
let st = { column = 0; field = Buffer.create 16; sum = 0 } in
...

main_noalloc.ml

그리고 OxCaml 컴파일러를 실행한다.

$ File

⚠️ [IMG:N] 형식 토큰은 이미지 placeholder 입니다. 번역하지 말고 원래 위치에 그대로 유지하세요.

let[@zero_alloc] sum_column (ic: in_channel) (col: int) (buf: Bytes.t) =
let st = { column = 0; field = Buffer.create 16; sum = 0 } in
let continue = ref true in
...

main_noalloc.ml

The main function은 sum_column에 buf를 전달합니다.

다시 컴파일을 시도해 봅시다.

$ ocamlopt main_noalloc.ml -o main_noalloc
File "main_noalloc.ml", line 23, characters 5-15:
23 | let[@zero_alloc] sum_column (ic: in_channel) (col: int) (buf: Bytes.t) =
...

main_noalloc.ml

좋아요! 하나 끝냈고, 몇 개만 더 남았네요.

다음 문제는 우리가 열(column)을 저장하기 위해 사용하는 이 Buffer입니다. 이를 통해 int_of_string으로 정수형 변환이 가능합니다. 하지만 합계를 구하려는 열을 전달한 후 문자들을 복제하고 문자를 정수로 변환하는 대신, 우리 스스로 한 글자씩 정수 변환을 할 수 있습니다.

type state = { mutable column : int; mutable value : int; mutable sum : int }
let sum_column_incremental (st: state) (buf: Bytes.t) (len: int) (col: int): unit = 
for i = 0 to len - 1 do
...

main_noalloc.ml

컴파일러가 뭐라고 하는지 봅시다.

$ ocamlopt main_noalloc.ml -o main_noalloc
File "main_noalloc.ml", line 22, characters 5-15:
22 | let[@zero_alloc] sum_column (ic: in_channel) (col: int) (buf: Bytes.t) =
...

거의 다 왔습니다!

다음 과제는 히프(heap)에 할당되는 이 state 레코드입니다. 하지만 OxCaml도 이를 위한 도구를 제공합니다. 우리는 값을 stack_로 표시하여 스택(stack)에 할당되도록 하고, 이 값이 스택을 벗어나지 않을 것임을 단언할 수 있습니다 (만약 반환하거나 전역 가변 변수에 할당하려고 시도하는 경우 등에는 그렇지 않을 수 있음).

let[@zero_alloc] sum_column (ic: in_channel) (col: int) (buf: Bytes.t) = 
let st = stack_ { column = 0; value = 0; sum = 0 } in
let continue = ref true in
...

main_noalloc.ml

우리는 등가적으로 st를 local_로 표시할 수도 있었고, OxCaml의 타입 추론은 st가 스택에 할당될 수 있음을 추론했을 것입니다.

let[@zero_alloc] sum_column (ic: in_channel) (col: int) (buf: Bytes.t) =
let local_ st = { column = 0; value = 0; sum = 0 } in
let continue = ref true in
...

main_noalloc.ml

이제 컴파일러가 어떻게 생각하는지 봅시다.

$ ocamlopt main_noalloc.ml -o main_noalloc
File "main_noalloc.ml", line 22, characters 5-15:
22 | let[@zero_alloc] sum_column (ic: in_channel) (col: int) (buf: Bytes.t) =
...

이제 우리는 표준 라이브러리 함수 input을 제외한 모든 할당(allocation)을 제거했습니다.
이것은 디스크에서 파일의 바이트를 우리의 버퍼로 복사할 때 발생합니다.

몇 가지 옵션이 있습니다. 첫째, 파일을 증분적으로 읽는 것을 포기하고, 처음부터 전체를 한 번에 읽은 다음 그 내용을 전부 처리할 수 있습니다.

둘째, input을 우리 자신의 함수로 감싸고 (assert 즉 lie) 이것이 zero_alloc임을 단언하는 것입니다.

let[@zero_alloc assume] input_unsafe ic buf pos len = input ic buf pos len

main_noalloc.ml

input이 할당을 일으킬 수 있는 한 영역은 예외 처리 경로(exception path)입니다. 예외는 변형 생성자(variant constructors)이기 때문에, int보다 큰 무언가(예: 문자열 오류 메시지)를 포함하는 경우 힙에서 할당해야 할 수도 있습니다. 따라서 파일에 접근할 때 문제가 발생한다면 할당이 일어날 수 있습니다. 이 예제 프로그램에서는 확실히 괜찮습니다. 실패할 것이라고 예상하지 않습니다. 그리고 설령 실패하더라도, 다시 실행하면 괜찮을 것입니다.

셋째, C FFI를 사용하여 input의 버전을 만들어 바이트를 우리의 버퍼로 복사하지만 절대로 예외를 발생시키지 않도록 할 수 있습니다.

#include <unistd.h>
#include <caml/mlvalues.h>
#include <caml/io.h>
...

read_noalloc.c

그리고 OCaml 스텁에서는 이를 [@@noalloc]으로 표시하여 [@zero_alloc]을 만족시킬 수 있습니다.

external read_noalloc : in_channel -> bytes -> int -> int -> int
= "caml_read_noalloc" [@@noalloc]

read_noalloc.ml

넷째, 별도의 리더 스레드와 공유 버퍼 풀을 가질 수 있습니다. noalloc Atomics와 spinlocks를 사용하여 리더 및 프로세스 스레드가 언제 버퍼를 수정하고 읽는 것이 안전한지 알 수 있게 합니다.

그리고 아마도 다른 선택지들도 있을 겁니다.

우리는 [@zero_alloc assume] 경로를 따르겠습니다. 여기 전체 main_noalloc.ml가 있습니다.

type state = { mutable column : int; mutable value : int; mutable sum : int }
let sum_column_incremental (st: state) (buf: Bytes.t) (len: int) (col: int): unit = 
for i = 0 to len - 1 do
...

main_noalloc.ml

한번 실행해 봅시다.

$ ocamlopt main_noalloc.ml -o main_noalloc
$ ./main_noalloc data.csv 1
sum=49947827758

훌륭합니다! 이제 Hyperfine과 비교해 봅시다.

$ hyperfine --warmup 3 './main_alloc data.csv 1' './main_noalloc data.csv 1'
Benchmark 1: ./main_alloc data.csv 1
Time (mean ± σ): 12.626 s ± 0.564 s [User: 12.287 s, System: 0.337 s]
...

나쁘지 않습니다!

호출 트리를 할당하지 않음(not allocating)으로 표시할 수 있는 이 기능은 엄청나게 유용합니다. Jane Street 팀이 추가한 멋진 기능이며, 다른 언어들의 컴파일러에서도 이런 기능을 구현하는 것을 보고 싶습니다. 이전 버전의 기사에서는 할당 제로(zero allocations)를 주석 처리할 수 있는 주류 언어가 없다고 했었습니다. Hacker News의 weissi는 Swift가 비슷한 기능을 가지고 있다고 지적했습니다. 이 Swift 기능을 살펴보던 중, Clang에도 OxCaml의 기능과 유사하게 작동하는 nonallocating 속성이 있다는 것을 발견했습니다. 두 경우 모두 매우 좋은 소식입니다. 더 많은 언어들이 이 방향을 계속 따르기를 바랍니다.↩@_noAllocation

속성은 유사하게 작동합니다. 이 플래그는 Swift 프로그램을 -experimental-performance-annotations 플래그로 컴파일해야 합니다.[@zero_alloc]

. C/C++ 프로그램은 컴파일러가 경고하도록 -Wfunction-effects로 컴파일해야 합니다.