jank의 새로운 커스텀 중간 표현(IR)과 이를 활용한 최적화 작업, 그리고 재귀 피보나치 벤치마크를 통해 JVM과 경쟁할 수 있을 만큼 성능을 끌어올린 과정을 살펴봅니다.
좋은 소식입니다, 여러분! jank에 새로운 커스텀 중간 표현(IR)이 생겼고, 우리는 이를 사용해 jank를 최적화하여 JVM과 경쟁할 수 있게 만들고 있습니다. 오늘은 그 이야기를 더 깊이 다뤄보겠지만, 먼저 제 Github sponsors와 올해 내내 저를 후원해 준 Clojurists Together에 감사드리고 싶습니다. 여러분 모두가 큰 힘이 되어 주고 있습니다. 저는 여전히 월세와 식료품비를 감당할 수 있는 수입으로 jank를 풀타임으로 계속 개발할 방법을 찾고 있으니, 아직 후원에 동참하지 않으셨다면 지금이 좋은 때입니다!
컴파일러는 종종 프로그램을 대상 CPU 명령어 집합보다 더 추상적인 명령 집합으로 표현합니다. 이렇게 하면 몇 가지 추가적인 이점이 있습니다. 첫째, 프로그램을 나중에 x86_64나 arm64 같은 서로 다른 CPU 아키텍처로 낮출 수 있는 방식으로 표현할 수 있습니다. 중간 표현은 CPU 아키텍처보다 더 높은 수준인 경우가 많기 때문에 일반적으로 이식성이 더 높습니다. 둘째, IR은 특정 최적화를 더 쉽게 작성할 수 있도록 특별히 설계될 수 있는데, 예를 들어 정적 단일 대입(SSA) 형식이 그렇습니다. 마지막으로, IR 설계자는 표현하려는 의미론에 맞게 IR의 추상화 수준을 선택할 수 있으며, 그 결과 IR을 더 일반적으로 만들 수도 있고 특정 언어에 더 특화되게 만들 수도 있습니다.
JVM의 바이트코드, CLR의 공용 중간 언어(CIL), GCC의 GIMPLE, LLVM의 IR 등 잘 알려진 인기 IR은 많이 있습니다. 어떤 컴파일러는 컴파일 과정에서 프로그램을 여러 IR을 거쳐 이동시키기도 합니다.
역사적으로 jank는 최적화 컴파일러가 아니었습니다. 우리는 생성한 C++ 또는 LLVM IR을 기반으로 사실상 그 모든 작업을 LLVM에 맡겨 왔습니다. 하지만 LLVM IR은 Clojure에 비하면 매우 낮은 수준에서 동작합니다. 거기에는 Clojure의 vars, transients, 영속 자료구조, 지연 시퀀스 같은 개념이 없습니다. Clojure의 동적 특성은 다형성과 간접 참조에 크게 의존해 얻어지지만, 그 때문에 LLVM은 jank에서 넘어온 LLVM IR을 다룰 때 활용할 수 있는 최적화 기회가 매우 적습니다.
이전에 jank에서 진행한 최적화 작업은 런타임과 컴파일러 자체를 최적화하는 데는 도움이 되었지만, 컴파일러가 컴파일하는 코드 자체에는 상대적으로 덜 도움이 되었습니다. 지난 두 달 동안 저는 이것을 바꾸고자 했습니다.
저는 Clojure의 의미론 수준에서 동작하는 IR을 원했습니다. 이것은 LLVM IR보다 훨씬 높은 수준일 것이고 JVM의 바이트코드보다도 훨씬 높은 수준일 것입니다. 저는 범용 가상 머신(VM)이나 컴파일러 플랫폼을 만드는 것이 아니므로, 여러 언어를 위해 IR을 일반화할 필요가 없습니다. jank의 IR을 jank에 딱 맞게 만들 수 있고, 그렇게 하면 최적화 측면에서 더 큰 힘을 얻을 수 있습니다. 제가 알기로는 어떤 Clojure 방언도 아직 이 단계까지 나아가지는 않았습니다.
저는 jank의 IR에 대한 참고 문서를 jank 책에 여기 작성해 두었습니다. 이 문서는 현재 시점에서 jank IR의 안정성에 대해 아무 보장도 하지 않기 때문에, 주로 jank 자체를 개발하는 사람들을 대상으로 합니다. 하지만 앞으로의 내용을 이해하는 데 도움이 되도록, jank의 IR을 보여 주고 머릿속 모델을 잡을 수 있게 그 내용 일부를 여기에도 옮기겠습니다. 먼저 이 간단한 Clojure 함수를 살펴봅시다.
(defn greet [name]
(if (= "jeaye" name)
(println "Are you me?!")
(println (str "Hello, " name "!"))))
jank의 IR은 메모리 안에서 C++ 자료구조로 저장되지만, 디버깅과 테스트를 위해 Clojure 데이터로 렌더링할 수 있습니다. 이것은 완전한 직렬화는 아닙니다. 우리가 보유한 Clang AST 내부 데이터 때문에 IR에서 다시 jank 컴파일러로 되돌리는 왕복 변환은 할 수 없기 때문입니다. 이 함수에 대한 jank IR 모듈을 살펴보겠습니다.
{:name user_greet_82687
:lifted-vars {clojure_core_SLASH_str_82694 clojure.core/str
clojure_core_SLASH_println_82691 clojure.core/println
clojure_core_SLASH__EQ__82689 clojure.core/=}
:lifted-constants {const_82693 "!"
const_82692 "Hello, "
const_82690 "Are you me?!"
const_82688 "jeaye"}
:functions [{:name user_greet_82687_1
:blocks [{:name entry
:instructions [{:name greet :op :parameter :type "jank::runtime::object_ref"}
{:name name :op :parameter :type "jank::runtime::object_ref"}
{:name v3 :op :literal :value "jeaye" :type "jank::runtime::obj::persistent_string_ref"}
{:name v4 :op :var-deref :var clojure_core_SLASH__EQ__82689 :type "jank::runtime::object_ref"}
{:name v5 :op :dynamic-call :fn v4 :args [v3 name] :type "jank::runtime::object_ref"}
{:name v7 :op :truthy :value v5 :type "bool"}
{:name v8 :op :branch :condition v7 :then if0 :else else1 :merge nil :shadow nil :type "void"}]}
{:name if0
:instructions [{:name v9 :op :literal :value "Are you me?!" :type "jank::runtime::obj::persistent_string_ref"}
{:name v10 :op :var-deref :var clojure_core_SLASH_println_82691 :type "jank::runtime::object_ref"}
{:name v11 :op :dynamic-call :fn v10 :args [v9] :type "jank::runtime::object_ref"}
{:name v12 :op :ret :value v11 :type "jank::runtime::object_ref"}]}
{:name else1
:instructions [{:name v13 :op :literal :value "Hello, " :type "jank::runtime::obj::persistent_string_ref"}
{:name v14 :op :literal :value "!" :type "jank::runtime::obj::persistent_string_ref"}
{:name v15 :op :var-deref :var clojure_core_SLASH_str_82694 :type "jank::runtime::object_ref"}
{:name v16 :op :dynamic-call :fn v15 :args [v13 name v14] :type "jank::runtime::object_ref"}
{:name v17 :op :var-deref :var clojure_core_SLASH_println_82691 :type "jank::runtime::object_ref"}
{:name v18 :op :dynamic-call :fn v17 :args [v16] :type "jank::runtime::object_ref"}
{:name v19 :op :ret :value v18 :type "jank::runtime::object_ref"}]}]}]}
jank의 IR은 SSA 기반입니다. 즉, 각 이름은 한 번만 대입됩니다. 이것은 전체 최적화 범주를 훨씬 더 쉽게 추론할 수 있게 해 줍니다. 또한 jank의 IR은 제어 흐름 그래프(CFG)로 표현되며, 하나 이상의 기본 블록으로 이루어지고 각 블록은 정확히 하나의 종료 명령(branch, jump, throw, ret 등)을 가집니다.
IR 모듈에서 볼 수 있듯이, jank는 vars와 상수의 리프팅을 처리하고 있으며, var 역참조, 함수 호출 등 Clojure 의미론 수준의 명령어를 가지고 있습니다. 이제 이 IR에서 생성된 C++를 살펴보겠습니다.
extern "C" jank::runtime::object_ref
user_greet_19_1(jank::runtime::object_ref const greet, jank::runtime::object_ref name)
{
auto const v3(const_33);
auto const v4(clojure_core_SLASH__EQ__34->deref());
auto const v5(jank::runtime::dynamic_call(v4, v3, name));
auto const v7(jank::runtime::truthy(v5));
if(v7)
{
auto const v9(const_35);
auto const v10(clojure_core_SLASH_println_36->deref());
auto const v11(jank::runtime::dynamic_call(v10, v9));
return v11;
}
else
{
auto const v13(const_37);
auto const v14(const_38);
auto const v15(clojure_core_SLASH_str_39->deref());
auto const v16(jank::runtime::dynamic_call(v15, v13, name, v14));
auto const v17(clojure_core_SLASH_println_36->deref());
auto const v18(jank::runtime::dynamic_call(v17, v16));
return v18;
}
}
C++와 IR을 비교해 보면, 둘 사이의 대응 관계를 즉시 확인할 수 있습니다. C++ 변수 이름은 IR 변수 이름과 맞춰져 있습니다. var 역참조는 그 var에 대한 ->deref() 호출이 됩니다. 동적 호출은 단순히 jank::runtime::dynamic_call이 됩니다. 이것은 의도된 설계입니다.
IR을 설계하고 구현하는 데, 그리고 jank의 AST에서 생성하던 기존 C++ 코드 생성을 IR에서 생성하도록 재작업하는 데 약 6주가 걸렸습니다. 이 시점에서 우리는 아직 IR에 대해 어떤 최적화 패스도 실행하고 있지 않습니다. 하지만 이제는 그것을 시작하는 데 필요한 모든 것을 갖추었습니다. 6주라는 기간도 이미 main에서 분기된 채 유지하기에는 긴 시간이기 때문에, 가능한 한 많이 확장하는 것보다 먼저 새로운 IR 파이프라인을 머지하는 일을 우선하고 싶었습니다. 이제 IR이 머지되었으니, 제 접근 방식은 벤치마크를 하나씩 골라 만족할 때까지, 또는 더는 최적화할 수 없을 때까지 필요한 최적화를 진행하는 것입니다. 그 최적화 중 일부는 IR을 직접 다루게 될 것이고, 일부는 그렇지 않을 것입니다.
이 IR의 기술적인 개발 측면에 더 관심이 있다면, 제가 IR 작업을 하면서 진행했던 여러 Twitch 스트림에서 나온 영상 몇 개가 jank TV YouTube channel에 있습니다. 이 영상들은 구현 세부 사항을 정말 아주 깊이 파고듭니다.
새로운 IR이 도입되었으니, 첫 번째 벤치마크인 재귀 피보나치 최적화로 넘어가 봅시다.
계속하기 전에, jank 메일링 리스트 구독을 고려해 주세요. 이것이 jank 릴리스, jank 관련 발표, 워크숍 등 최신 소식을 놓치지 않는 가장 좋은 방법이 될 것입니다. 트래픽은 매우 적습니다.
이번 최적화 라운드의 첫 번째 벤치마크는 재귀 피보나치 구현입니다. 단 5줄짜리입니다. 우리의 목표는 jank가 최소한 Clojure JVM만큼은 빠르고, 가능하다면 더 빠르게 만드는 것이지만, 그 성능은 직접 만들어 내야 합니다.
(defn fibonacci [n]
(if (<= n 1)
n
(+ (fibonacci (- n 1))
(fibonacci (- n 2)))))
이 벤치마크는 최적화하기에 너무 사소해 보일 수도 있습니다. 이것이 왜 실제 애플리케이션을 대표할 수 있는지 의문이 들 수도 있습니다. 하지만 실제로 이 벤치마크는 컴파일러와 런타임의 몇 가지 핵심적인 측면을 포괄합니다.
이 글 전반에 걸쳐 최적화를 살펴보면서, 이 네 가지 범주와 각 최적화가 어디에 속하는지를 함께 생각해 보세요.
기준 벤치마크 수치를 얻기 위해 Clojure JVM을 사용한 다음, jank로 그 수치를 넘어서는 것을 목표로 하겠습니다.
이 글의 모든 수치는 제 5년 된 x86_64 데스크톱, AMD Ryzen Threadripper 2950X, NixOS, OpenJDK 21 환경에서 측정되었습니다. 이 글에서 제가 "JVM"이라고 말하면 OpenJDK 21을 뜻합니다.
❯ clojure -Sdeps '{:deps {criterium/criterium {:mvn/version "0.4.6"}}}'
Clojure 1.12.4
user=> (require '[criterium.core :refer [quick-bench]])
nil
user=> (defn fibonacci [n]
(if (<= n 1)
n
(+ (fibonacci (- n 1))
(fibonacci (- n 2)))))
#'user/fibonacci
user=> (quick-bench (fibonacci 35))
Clojure는 (fibonacci 35)를 계산하는 데 약 200밀리초가 걸립니다. 이것이 우리의 기준선입니다!
lein repl 사용 시 주의참고로 저는 원래 Clojure 벤치마킹을 lein repl에서 했는데, 이 경우 결과가 엄청나게 다르게 나옵니다. 제 시스템에서는 200밀리초가 아니라 무려 2,800밀리초 정도가 걸립니다! 여기에 따르면 lein repl이 일부 JVM 최적화를 비활성화하는데, 여기에서 그것이 핵심적인 역할을 하는 것으로 보입니다. 이것을 지적해 준 Kyle Cesare에게 감사드립니다.
몇 주 전의 jank main에서 시작해서, 같은 fibonacci 정의를 사용하겠습니다. 다만 criterium은 JVM용 라이브러리이므로 사용할 수 없습니다. 대신 jank에는 jank 자체와 함께 제공되는 자체 벤치마킹 라이브러리가 있습니다.
(defn fibonacci [n]
(if (<= n 1)
n
(+ (fibonacci (- n 1))
(fibonacci (- n 2)))))
(require '[jank.perf])
(jank.perf/benchmark {:label "fib"} (fibonacci 35))
최적화를 활성화하고 eager compilation으로 실행하면 초기 수치를 얻을 수 있습니다.
❯ jank run -O3 --eagerness eager fib.jank
jank는 5,522밀리초가 나왔습니다. 이건... 빠르지 않습니다. JVM의 200밀리초와 비교하면 더욱 그렇습니다.
시작으로, 저는 Clojure가 수학 호출을 인라인한다는 것을 알고 있었고 jank에도 예전에 이를 위한 임시방편 같은 해법이 있었지만 제거되었습니다. 이제는 이것을 제대로 할 때입니다. Clojure는 다른 네임스페이스의 함수 본문을 사용할 수 없기 때문에 메타데이터를 통해 인라이닝을 처리합니다. 이것은 Clojure만의 문제가 아니라, C와 C++도 정확히 같은 방식으로 동작합니다. 번역 단위가 다른 곳에 있는 C 또는 C++ 함수 호출은 링크 타임 최적화(LTO)를 사용하지 않으면 인라인되지 않습니다. 다른 선택지는 정의를 헤더 파일로 옮기고 함수에 inline을 표시하여 모든 번역 단위가 자체 복사본을 가지게 하는 것입니다. Clojure에서는 var의 메타데이터를 바꿔 인라이닝 정보를 포함시키면, 누구나 어디서든 var 메타데이터를 읽을 수 있으므로 같은 효과를 낼 수 있습니다. 예를 보겠습니다.
(defn
^{:inline (fn [l r]
(list 'cpp/jank.runtime.max l r))
:inline-arities #{2}}
max
([x]
x)
([l r]
(cpp/jank.runtime.max l r))
([l r & args]
(let [res (cpp/jank.runtime.max l r)]
(if (empty? args)
res
(recur res (first args) (next args))))))
여기에는 clojure.core/max가 있고, 두 개의 키 :inline과 :inline-arities를 포함한 메타데이터를 정의합니다. 후자는 인라인할 arity들의 집합입니다. 여기서는 [l r] arity만 신경 쓰면 됩니다. :inline의 값은 그 arity의 본문을 얻기 위해 호출할 실제 함수입니다. max의 경우에는 그저 jank::runtime::max에 대한 C++ 호출을 인라인하고 싶습니다. 나중에는 Clang이 그 호출마저도 인라인하도록 하겠습니다.
이 인라이닝은 IR 패스가 아니라 분석 과정에서 수행됩니다. var를 통한 함수 호출을 찾으면, var의 메타데이터를 확인하고 해당하는 :inline 함수가 있으면 그것을 호출합니다. 이것은 매크로 확장의 자매 개념이라고 생각해도 좋습니다. 동작 방식이 매우 비슷하기 때문입니다.
이 방식의 인라이닝은 엄청난 장점이 있습니다. 첫째, clojure.core/max의 var intern과 역참조를 제거할 수 있습니다. 둘째, 모든 Clojure 함수는 boxed parameter를 필요로 하므로, 우리가 네이티브 값으로 작업 중이라면 max를 호출하기 전에 그것들을 박싱할 필요가 없습니다. 셋째, max가 unboxed 네이티브 값을 반환한다면, 함수에서 반환하기 위해 그것을 다시 박싱할 필요도 없습니다. 이를 통해 박싱을 피하고 타입 정보를 더 잘 전파할 수 있습니다.
jank 분석기에 inline 지원을 추가하고 모든 산술 함수의 메타데이터를 갱신한 뒤, 새 벤치마크 결과를 확인해 볼 수 있습니다. 이로써 5,522밀리초에서 2,309밀리초로 줄었습니다. 이렇게 큰 승리로 시작하는 건 좋습니다.
다음으로, 피보나치 함수의 IR을 살펴보겠습니다. 저는 이제 jank 함수의 IR을 들여다보는 것을 정말 좋아합니다. jank 컴파일러가 코드를 어떻게 보고 있는지 아주 좋은 시야를 제공하기 때문입니다.
{:name user_fibonacci_82580
:lifted-vars {}
:lifted-constants {const_82598 2
const_82597 1}
:functions [{:name user_fibonacci_82580_1
:blocks [{:name entry
:instructions [{:name fibonacci :op :parameter :type "jank::runtime::object_ref"}
{:name n :op :parameter :type "jank::runtime::object_ref"}
{:name v3 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}
{:name v4 :op :cpp/call :value "jank::runtime::lte" :args [n v3] :type "bool"}
{:name v5 :op :cpp/into-object :value v4 :type "jank::runtime::object_ref"}
{:name v7 :op :truthy :value v5 :type "bool"}
{:name v8 :op :branch :condition v7 :then if0 :else else1 :merge nil :shadow nil :type "void"}]}
{:name if0
:instructions [{:name v9 :op :ret :value n :type "jank::runtime::object_ref"}]}
{:name else1
:instructions [{:name v10 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}
{:name v11 :op :cpp/call :value "jank::runtime::sub" :args [n v10] :type "jank::runtime::object_ref"}
{:name v12 :op :named-recursion :fn fibonacci :args [v11] :type "jank::runtime::object_ref"}
{:name v13 :op :literal :value 2 :type "jank::runtime::obj::integer_ref"}
{:name v14 :op :cpp/call :value "jank::runtime::sub" :args [n v13] :type "jank::runtime::object_ref"}
{:name v15 :op :named-recursion :fn fibonacci :args [v14] :type "jank::runtime::object_ref"}
{:name v16 :op :cpp/call :value "jank::runtime::add" :args [v12 v15] :type "jank::runtime::object_ref"}
{:name v17 :op :ret :value v16 :type "jank::runtime::object_ref"}]}]}]}
함수에는 세 개의 블록이 있습니다. 우리는 entry 블록에서 시작합니다. 파라미터 n과 리터럴 1을 가져오고, 인라인된 cpp/call 명령으로 <= 검사를 수행하며 그 결과는 bool입니다.
{:name n :op :parameter :type "jank::runtime::object_ref"}
{:name v3 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}
{:name v4 :op :cpp/call :value "jank::runtime::lte" :args [n v3] :type "bool"}
그다음 이 bool을 boxed object로 바꾸고, 분기할 수 있도록 그것이 truthy인지 검사합니다.
{:name v5 :op :cpp/into-object :value v4 :type "jank::runtime::object_ref"}
{:name v7 :op :truthy :value v5 :type "bool"}
{:name v8 :op :branch :condition v7 :then if0 :else else1 :merge nil :shadow nil :type "void"}
이 부분은 최적화로 제거할 수 있습니다. <= 검사 결과인 v4가 이미 bool이었기 때문입니다. 다시 bool로 바꾸기 위해 object로 만들었을 뿐입니다. 이상적으로는 branch 조건이 그냥 v4이면 됩니다.
그것을 최적화하기 전에, 먼저 나머지 IR도 마저 살펴보겠습니다. 우리는 if0으로 분기해서 결과를 바로 반환하거나, else1으로 분기해서 재귀를 수행합니다. else1 분기는 세 단계로 이루어집니다.
; 1. `(- n 1)`로 재귀 호출.
{:name v10 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}
{:name v11 :op :cpp/call :value "jank::runtime::sub" :args [n v10] :type "jank::runtime::object_ref"}
{:name v12 :op :named-recursion :fn fibonacci :args [v11] :type "jank::runtime::object_ref"}
; 2. `(- n 2)`로 재귀 호출.
{:name v13 :op :literal :value 2 :type "jank::runtime::obj::integer_ref"}
{:name v14 :op :cpp/call :value "jank::runtime::sub" :args [n v13] :type "jank::runtime::object_ref"}
{:name v15 :op :named-recursion :fn fibonacci :args [v14] :type "jank::runtime::object_ref"}
; 3. 그 둘의 합을 반환.
{:name v16 :op :cpp/call :value "jank::runtime::add" :args [v12 v15] :type "jank::runtime::object_ref"}
{:name v17 :op :ret :value v16 :type "jank::runtime::object_ref"}
이것이 전부입니다! 그러니 이제 여분의 :cpp/into-object와 :truthy 명령을 제거하고, bool 값을 직접 사용할 수 있도록 IR 생성기를 지원해 봅시다. 그 결과 2,309밀리초에서 2,247밀리초로 줄어들었습니다. 전체 규모를 생각하면 꽤 미미합니다. 그래도 이제 IR 안에 불필요한 작업이 없다는 점은 좋습니다. 1에 대한 두 개의 :literal 명령을 리프팅해서 하나만 두도록 만들 수도 있지만, 성능에는 영향을 주지 않을 것이므로 지금은 그냥 두겠습니다.
{:name entry
:instructions [{:name fibonacci :op :parameter :type "jank::runtime::object_ref"}
{:name n :op :parameter :type "jank::runtime::object_ref"}
{:name v3 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}
{:name v4 :op :cpp/call :value "jank::runtime::lte" :args [n v3] :type "bool"}
{:name v6 :op :branch :condition v4 :then if0 :else else1 :merge nil :shadow nil :type "void"}]}
{:name if0
:instructions [{:name v7 :op :ret :value n :type "jank::runtime::object_ref"}]}
{:name else1
:instructions [{:name v8 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}
{:name v9 :op :cpp/call :value "jank::runtime::sub" :args [n v8] :type "jank::runtime::object_ref"}
{:name v10 :op :named-recursion :fn fibonacci :args [v9] :type "jank::runtime::object_ref"}
{:name v11 :op :literal :value 2 :type "jank::runtime::obj::integer_ref"}
{:name v12 :op :cpp/call :value "jank::runtime::sub" :args [n v11] :type "jank::runtime::object_ref"}
{:name v13 :op :named-recursion :fn fibonacci :args [v12] :type "jank::runtime::object_ref"}
{:name v14 :op :cpp/call :value "jank::runtime::add" :args [v10 v13] :type "jank::runtime::object_ref"}
{:name v15 :op :ret :value v14 :type "jank::runtime::object_ref"}]}
nil 사용 최적화이 시점에서 IR은 괜찮아 보이고, 다른 계획된 최적화도 없으니 flamegraph를 보고 시간이 어디에 쓰이는지 살펴봅시다. 원하시면 이 이미지를 클릭해 새 탭에서 자세히 볼 수 있습니다. 여기서는 핵심만 다루겠습니다.
우리는 산술 연산과 fibonacci 호출이 보이기를 기대합니다. 그런데 이상하게도 jank_nil과 jank_const_nil에서 엄청난 시간이 소모되고 있습니다. Clojure 방언으로서 우리는 nil을 매우 자주 접근합니다. 어떤 것이 nil인지 확인해야 하고, 값을 nil로 초기화해야 하며, 많은 식이 nil로 평가되기 때문입니다. 하지만 그게 프로파일러에 드러나서는 안 됩니다! 지금 드러나는 이유는, 아주 깊은 내부 사정 때문에 jank가 현재 nil 값을 함수 뒤에 숨겨 두고 있기 때문입니다. C++는 번역 단위 간 전역 객체의 초기화 순서를 보장하지 않으며, jank가 AOT 컴파일하는 번역 단위들은 값 초기화를 nil로 하려는 전역 객체들(리프팅된 상수)로 가득 차게 됩니다. 만약 nil이 다른 번역 단위, 즉 jank 런타임의 일부로서 전역으로 정의되어 있다면, 초기화되기 전에 그것을 사용하려 할 수도 있습니다. 그래서 우리는 지금까지 jank_nil이라는 함수 뒤에 nil을 숨기는 방식으로 이를 우회해 왔는데, 이것이 꽤 큰 성능 비용을 낳은 것으로 보입니다.
jank의 boxed pointer type은 nullptr로 초기화하는 것을 허용하지 않습니다. 그것은 유효한 값이 아니기 때문입니다. jank는 nil과 nullptr를 분리하는데, Clojure에서는 nil 역참조가 잘 정의되어 있지만 C++에서 nullptr 역참조는 정의되지 않은 동작이기 때문입니다. 우리는 그걸 그냥 할 수 없습니다. 하지만 저는 AOT 컴파일된 코드에 대해 생성하는 전역 객체들의 기본 생성에는 신경 쓰지 않아도 된다는 것을 알고 있습니다. 모듈이 로드될 때 나중에 그것들을 다시 초기화하기 때문입니다. 그러니 boxed pointer type에 커스텀 생성자를 추가해서, 나중에 nil로 다시 초기화할 것을 알고 있으니 실제로는 nullptr로 초기화하도록 합시다. 그러면 jank_nil을 함수가 아니라 전역 값으로 유지할 수 있습니다.
이렇게 하자 2,247밀리초에서 1,400밀리초로 줄었습니다!
큰 승리입니다! 이건 런타임이 벤치마크를 방해하던 사례에 해당하므로, 이것을 정리할 수 있어 좋습니다. 그래도 여전히 Clojure JVM보다 5배 이상 느리니, 이제 더 큰 덩어리를 더 잘라내야 합니다.
add/sub가 느릴까?위에 삽입한 flamegraph의 나머지 부분을 보면, 예상했던 용의자들이 등장합니다. 바로 add와 sub입니다. flamegraph가 말해 주는 이 함수들의 가장 느린 부분은 새 숫자를 위한 GC 할당입니다. 덧셈이나 뺄셈의 모든 정수 결과가 새로운 동적 할당입니다. 이 시점에서는 사실상 거의 모든 시간을 숫자를 할당하는 데 쓰고 있습니다.
왜 여기에 unboxed 숫자를 사용하지 않느냐고 생각할 수도 있습니다. 또는 "타입 힌트만 추가하면 되지 않나? Clojure도 그걸 지원하잖아!"라고 생각할 수도 있습니다. 하지만 그것은 이 벤치마크의 요점을 놓치는 것입니다. 이 벤치마크는 의도적으로 컴파일러와 런타임에 도전하기 위해 작성되었습니다. Clojure 코드를 한 번 더 보고 왜 그런지 설명하겠습니다.
(defn fibonacci [n]
(if (<= n 1)
n
(+ (fibonacci (- n 1))
(fibonacci (- n 2)))))
여기서 n의 타입은 타입이 지워진 object일 뿐입니다. Clojure JVM에서는 Java Object일 것입니다. jank에서는 jank::runtime::object_ref입니다. 어느 쪽이든 그 안에 어떤 종류의 객체가 들어 있는지 전혀 알 수 없습니다. (- n 1)과 (- n 2)를 수행할 때도 여전히 n의 타입을 모릅니다. 그것은 float일 수도 있습니다. integer일 수도 있습니다. ratio일 수도 있습니다. big decimal이나 big integer일 수도 있습니다. 심지어 산술을 전혀 지원하지 않는 무언가일 수도 있습니다. 그래서 우리는 n에 대한 산술을 처리하기 위해 전체 다형적 절차를 거쳐야 합니다. 다행히 1과 2의 타입은 알고 있으니 그 부분은 최적화할 수 있지만, 이것만으로는 이 산술을 unbox할 수 없습니다. 같은 문제는 + 호출에도 적용됩니다. 우리는 fibonacci의 반환 타입을 모릅니다. n을 반환할 수도 있는데 그 타입을 모르고, +의 결과를 반환할 수도 있는데 그 입력 둘 다 fibonacci의 반환값이므로 여전히 타입을 모릅니다. 따라서 이 부분도 정적으로 할 수 있는 것이 없습니다. 이것이 바로 이 벤치마크를 어렵게 만드는 핵심 요소입니다. 현재는 JVM이 우리보다 훨씬 더 잘 처리하고 있습니다.
이 문제를 해결하기 위해, 정수에 대해서는 아예 동적 할당을 피해 봅시다. 언어 런타임이 정확히 이것을 위해 사용하는 잘 알려진 기법들이 있으며, jank는 아직 그 어느 것도 사용하고 있지 않습니다. 먼저 가장 단순한 기법부터 시작하고, 더 복잡한 설계는 이후 벤치마크 글에서 다루겠습니다.
알고 계셨나요? 64비트 시스템에서는 포인터의 하위 3비트가 사실상 사용되지 않습니다. 포인터가 64비트 머신 워드에 정렬되기 때문입니다. 예를 들어, 정렬된 포인터는 주소 0, 8, 16, 24 등에 존재합니다. 하지만 8바이트(64비트)로 나누어떨어지지 않는 주소에는 정렬된 포인터가 존재하지 않습니다. 포인터의 하위 세 비트인 000은 1의 자리(최하위 비트), 2의 자리(가운데 비트), 4의 자리(가장 높은 비트)를 의미합니다. 모든 비트가 켜져 111이면 값은 7(4 + 2 + 1)입니다. 여기에 하나를 더하면 8이 되고, 하위 3비트는 다시 모두 0이 됩니다.
이것은 정말 놀라운 사실입니다. 왜냐하면 포인터 안에 추가 정보를 아주 쉽게 담을 수 있다는 뜻이기 때문입니다. 예를 들어, 최하위 비트를 1로 설정하면 그 포인터가 실제 포인터가 아니라는 것을 나타낼 수 있습니다. 대신 그것은 인코딩된 정수입니다. 그러면 나머지 63비트를 실제 정수 값을 저장하는 데 사용할 수 있습니다. 이렇게 하면 정수가 63비트로 표현 가능한 범위를 넘지 않는 한, 동적 할당 없이 인라인으로 저장할 수 있습니다! 64비트 전체가 필요한 경우에는 기존처럼 할당을 하고, 그러면 boxed integer를 가리키는 정상 포인터(하위 세 비트가 모두 0)를 얻게 됩니다.
이를 시각화하면, 일반적인 64비트 포인터는 이렇게 생깁니다. 상위 61비트는 포인터 데이터를 위해 사용되고 하위 3비트는 0입니다.
pppppppp pppppppp pppppppp pppppppp pppppppp pppppppp pppppppp ppppp000
인코딩된 정수는 이렇게 생깁니다. 최하위 비트는 1이고 나머지는 정수 데이터를 위해 예약됩니다. 실제 63비트 정수를 얻으려면 전체를 한 번 오른쪽으로 시프트하면 됩니다.
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxx1
우리의 피보나치 벤치마크에서는, 그리고 사실상 거의 모든 벤치마크와 실제 애플리케이션에서는, 이것이 정수에 대한 동적 할당을 사실상 전부 제거하게 됩니다. 수치에 어떤 영향을 주는지 봅시다.
63비트 정수에 최적화된 tagged pointer를 적용하자, jank는 1,400밀리초에서 282밀리초로 내려갔습니다. 앞서 말했듯, 우리는 사실상 거의 모든 시간을 정수 할당에 쓰고 있었습니다. 더 좋은 점은 이것으로 Clojure의 200밀리초에 도달할 수 있는 거리까지 왔다는 것입니다.
최신 변경 사항을 적용한 새로운 flamegraph를 보고 남은 군더더기를 어떻게 더 깎아낼 수 있을지 살펴봅시다. 다시 말하지만, 원하시면 이 이미지를 클릭해 새 탭에서 보실 수 있습니다. 아니면 제 말을 믿으셔도 됩니다.
이상적으로는 여기서 fibonacci만 보여야 합니다. 중요한 것은 모두 인라인되어 있어야 하기 때문입니다. 하지만 실제로는 jank::runtime::add, jank::runtime::sub, jank::runtime::lte가 보입니다. 이것은 해당 호출들이 Clang에 의해 인라인되지 않았다는 뜻입니다. 그러니 Clang에게 산술 함수를 항상 인라인하라고 지시해 봅시다. C++의 add, sub 같은 함수에 몇 가지 속성을 붙이면 됩니다. 현대 C++ 문법 덕분에 이것은 쉽습니다.
template <typename L, typename R>
[[gnu::always_inline, gnu::flatten, gnu::hot]]
auto add(L const l, R const r)
{ ... }
산술은 언제나 빨라야 하는 것이므로, 숫자 연산만큼 인라인할 가치가 큰 대상도 없습니다. 이제 다시 시도해 봅시다. 다행히도, 안도의 한숨과 함께 jank는 282밀리초에서 114밀리초로 떨어졌습니다. 이제 Clojure JVM보다 거의 두 배 빠릅니다! 더 나아가, 우리는 5,522밀리초에서 114밀리초로 내려왔고, 사실상 같은 작업을 하고 있습니다.
예전에 전기톱 조각을 하는 예술가의 인터뷰를 본 적이 있습니다. 인터뷰어가 거대한 통나무에서 곰 같은 조각을 어떻게 만들기 시작하느냐고 묻자, 그는 "곰처럼 보이지 않는 부분을 전부 제거할 뿐이다"라고 답했습니다. 그다지 도움이 되는 대답은 아니지만, 최적화도 꽤 비슷합니다. 프로파일링을 하고 시간이 어디에 쓰이는지 들여다볼 때, 가장 핵심적인 작업이 아닌 데 쓰이는 시간을 모두 제거하면 됩니다. 일반적으로는 무엇이 핵심 작업인지 파악하고, 그 외의 것은 어떻게 하지 않을지 알아내는 과정입니다.
하나의 벤치마크를 끝냈고, 아직 더 많은 벤치마크가 남아 있습니다. 다음으로는 제가 몇 년 전에 Clojure로 작성했던 레이 트레이서를 다시 살펴보고, 새로운 IR과 최적화된 런타임을 활용해 jank를 얼마나 빠르게 밀어붙일 수 있는지 볼 예정입니다. 이 글과 첫 번째 벤치마크는 시작에 불과합니다. 저는 앞으로 몇 달 동안 크고 작은 다양한 벤치마크를 계속 다루면서, 실용적인 모든 의미에서 jank가 충분히 빠르도록 만들어 갈 것입니다. 이 모든 작업은 jank의 베타 릴리스를 향해 쌓여 가고 있습니다.
처음 jank를 써 보는 많은 분들이 "jank는 왜 느리죠? C++로 작성된 것 아닌가요?"와 비슷한 말을 합니다. 우선, jank가 느린 이유는 최적화되지 않았기 때문입니다. 여기서 보았듯이 jank는 이 마이크로 벤치마크에서 충분히 JVM과 경쟁할 수 있고, 앞으로의 글들에서는 더 큰 벤치마크에서도 그렇게 할 수 있음을 보여 드릴 것입니다. 둘째, C++로 작성된 또 다른 것이 무엇인지 아시나요? JVM입니다. jank는 실제로 몇 가지 중요한 차이점을 가진 작은 JVM입니다.
JVM에는 JIT 컴파일러뿐 아니라 JIT 최적화기도 있습니다. JVM은 어떤 함수가 호출되는지, 얼마나 자주 호출되는지, 어떤 값들과 함께 호출되는지를 바탕으로 실행 시간에 적응적으로 프로시저 간 최적화를 수행합니다. 이것은 경이로운 공학의 산물입니다.
네이티브 세계에는 현재 JIT 최적화가 없습니다. 존재할 수는 있겠지만, LLVM에도 구현이 없고 주요 C 또는 C++ 컴파일러에도 없습니다. 게다가 네이티브 생태계 전체가 이를 전제로 설계되어 있지 않은 반면, JVM 세계에서는 이것이 완전히 당연한 것으로 받아들여집니다. 이것은 JVM 프로그램이 일정 시점까지는 사용할수록 점점 더 빨라진다는 뜻입니다. 하지만 jank가 Clojure보다 빠르다면, 처음부터 그렇게 빨랐고 계속 그렇게 빠른 것입니다.
마지막으로, jank가 C++로 작성되었다고 해서 Clojure의 의미론에서 벗어날 수 있는 것은 아닙니다. Clojure는 동적 타입 언어이고, 가비지 컬렉션을 사용하며, 극도로 다형적입니다. 컴파일러와 런타임이 어떤 언어로 작성되었든, 진정한 Clojure 방언이라면 이 모든 의미론을 보존해야 합니다. 만약 이 벤치마크를 실제 관용적인 C++로 다시 쓴다면, Clojure와의 경쟁은 아예 성립하지 않을 것입니다. C++는 정적 타입이고, 원시 산술을 사용하며, 런타임이 거의 없고, 특히 Clang은 세계 최고 수준의 AOT 최적화를 제공하기 때문에 그냥 이길 것입니다. 이것은 Clojure 코드에 타입 힌트를 붙여도 마찬가지입니다. 믿기지 않는다면 직접 해 보세요. 글을 쓰면서 저도 해 봤습니다. :)