빠른 동적 언어 인터프리터를 만드는 방법

빠른 동적 언어 인터프리터를 만드는 방법

이 글은 내가 재미로 만든 Zef라는 동적 언어를 위한 극도로 단순한 AST 워킹 인터프리터를 최적화해서 Lua, QuickJS, CPython 같은 구현들과 경쟁할 수 있을 정도까지 끌어올리는 과정에 관한 것이다.

왜?

언어 구현을 빠르게 만드는 방법에 관한 글 대부분은 이미 안정적인 기반이 있는 상태에서 하는 작업, 예를 들면 또 하나의 JIT(just in time) 컴파일러를 쓰거나 이미 꽤 괜찮은 가비지 컬렉터를 미세 조정하는 일에 초점을 맞춘다. 나는 성숙한 JS 런타임의미친최적화들에관해많은 글을써 왔다. 이 글은 다르다. 처음부터 시작하는 경우, 아직 JIT를 쓸 단계는 한참 멀었고 GC가 최우선 문제가 아닌 경우에 대한 이야기다.

이 글의 기법들은 이해하기 쉽다. SSA도 없고, GC도 없고, 바이트코드도 없고, 머신 코드도 없다. 그런데도 무려 16배의 속도 향상을 달성한다(Yolo-C++로의 미완성 포팅까지 포함하면 67배). 그리고 내 작은 인터프리터를 QuickJS, CPython, Lua와 비슷한 급으로 끌어올린다.

이 글에서 집중할 기법은 다음과 같다.

• 값 표현.
• 인라인 캐싱.
• 객체 모델.
• 워치포인트.
• 상식적인 최적화를 끝까지 밀어붙이기.

평가 방법론

진행 상황을 평가하기 위해 나는 ScriptBench1이라는 벤치마크 모음을 만들었다. 여기에는 고전적인 언어 벤치마크들을 Zef로 포팅한 것이 들어 있다.

• Richards (OS 스케줄러)
• DeltaBlue (제약 해결기)
• N-Body (물리 시뮬레이션)
• Splay (이진 트리 테스트)

이 벤치마크들은 다른 다양한 언어에서도 구할 수 있다. 나는 이 벤치마크들의 JavaScript, Python, Lua 포트를 찾아냈다. Splay는 기존 Python 및 Lua 포트가 없어서 Claude를 사용해 포팅했다.

모든 실험은 Ubuntu 22.04.5, Intel Core Ultra 5 135U, 32GB RAM, Fil-C++ 버전 0.677 환경에서 수행했다. Lua 5.4.7은 GCC 11.4.0으로 컴파일했다. QuickJS-ng 0.14.0은 QuickJS의 GitHub releases 페이지에 있는 바이너리다. CPython 3.10은 Ubuntu에 기본으로 포함된 것을 사용했다.

모든 실험은 무작위로 교차 배치한 30회 실행의 평균값을 사용한다.

분명히 해두자면, 이 글의 대부분에서는 Fil-C++로 컴파일한 내 인터프리터를 Yolo-C 컴파일러로 컴파일된 다른 사람들의 인터프리터와 비교한다.

목차

이 글은 원래의 AST 워킹, 해시테이블 위주 Zef 인터프리터에 대한 상위 수준 설명으로 시작하고, 이후 16.6배 속도 향상에 도달하기까지의 여정에서 적용한 각 최적화를 섹션별로 다룬다.

원래의 Zef 인터프리터

원래의 Zef 인터프리터는 성능을 거의 고려하지 않고 작성되었다. 성능을 의식한 선택은 두 가지뿐이었다.

• 값 표현은 64비트 태그드 값으로, double, 32비트 정수, 또는 Object*를 담을 수 있다. double은 0x1000000000000만큼 오프셋해서 표현한다(이 기법은 JavaScriptCore에서 배웠고, 문헌에서는 이를 NuN tagging이라고 부르게 되었다). 정수와 포인터는 네이티브하게 표현하며, 어떤 포인터도 0x100000000보다 작은 값을 갖지 않는다는 사실에 의존한다(위험한 선택이지만 강제로 참이 되게 만들 수는 있다. 이 점이 걱정되었다면 정수를 0xffff000000000000라는 상위 비트 태그를 주어 표현할 수도 있었다). 이렇게 하면 숫자 연산에 대한 빠른 경로를 만들기 쉽다(숫자인지, 어떤 종류의 숫자인지를 비트 테스트로 판별할 수 있기 때문이다). 더 중요한 점은 숫자에 대해 힙 할당을 피할 수 있다는 것이다. 처음부터 인터프리터를 만든다면, 가장 근본적인 값 표현에 대해 좋은 선택을 하는 것에서 시작하는 것이 좋다. 나중에 바꾸기가 엄청 어렵기 때문이다! 동적 타입 언어를 구현한다면 32비트 또는 64비트 태그드 값은 표준적인 출발점이다.
• 나는 일종의 C++를 사용했다. 언어 구현이 결국 필요로 하게 되는 모든 최적화를 할 수 있는 언어를 고르는 것이 중요하고, C++는 그런 언어다. 특히 Java 같은 것은 고르지 않을 것이다. 그렇게 낮은 수준의 최적화를 얼마나 많이 할 수 있는지에 상한이 있기 때문이다. Rust도 고르지 않을 것이다. 가비지 컬렉션 언어는 전역 가변 상태와 순환 참조를 가진 힙 표현이 필요하기 때문이다(물론 다국어 구성을 받아들일 수 있다면 인터프리터의 일부는 Rust로 작성할 수 있다. 또는 많은 unsafe 코드를 감수할 수 있다면 Rust를 쓸 수도 있다).

하지만 성능 공학 관점에서는 잘못된 임시방편 선택도 엄청 많이 했다.

• Fil-C++를 사용했다. 덕분에 아주 빠르게 개발할 수 있었다. 예를 들면 GC를 공짜로 얻는다. 또한 메모리 안전성 문제를 디버깅하는 데 시간을 전혀 쓰지 않았다(Fil-C++는 메모리 안전성 위반을 보기 좋은 스택 트레이스와 많은 진단 정보와 함께 보고한다). 정의되지 않은 동작도 없었다(Fil-C++에는 undefined behavior가 없다). Fil-C++는 보통 성능이 약 4배 정도 손해이므로, 나는 다른 모든 비최적 선택 위에 그 4배 핸디캡을 안고 시작한 셈이다.
• 재귀적인 AST 워킹 인터프리터. 인터프리터는 가상 Node::evaluate 메서드로 구현되어 있고 여러 곳에서 이를 오버라이드한다.
• 어디에나 문자열. 예를 들어 Get AST 노드는 가져올 변수 이름을 설명하기 위해 std::string을 들고 있고, 변수에 접근할 때마다 그 문자열을 사용한다.
• 어디에나 해시테이블. 그 Get이 실행되면, 그 문자열은 변수 값을 담고 있는 std::unordered_map의 키로 사용된다.
• 스코프 체인을 기어 올라가기 위한 재귀 호출들의연쇄. Zef는 거의 모든 구문이 중첩될 수 있고, 중첩은 클로저를 낳는다. 예를 들어 함수 F 안의 클래스 A, 그 바깥의 클래스 B, 그 바깥의 함수 G라는 구조라면 클래스 A의 멤버 함수는 A의 필드, F의 로컬, B의 필드, G의 로컬을 모두 볼 수 있다. 원래의 인터프리터는 서로 다른 스코프 객체를 질의할 수 있는 함수들 위를 C++ 재귀로 내려가며 이를 구현했다.

그럼에도 불구하고, 그런 좋지 않은 선택들 덕분에 비교적 정교한 언어를 아주 적은 코드로 구현할 수 있었다. 가장 큰 모듈은 단연 파서다. 나머지는 모두 단순하고 깔끔하다.

이 인터프리터는 CPython 3.10보다 35배 느렸고, Lua 5.4.7보다 80배 느렸으며, QuickJS-ng 0.14.0보다 23배 느렸다. 이제 여러 최적화를 구현해서 어디까지 갈 수 있는지 보자!

최적화 #1: 연산자를 직접 호출하기

첫 번째 최적화는 연산자 이름을 가진 DotCall 노드를 사용하는 대신, 파서가 각 연산자별로 구별되는 AST 노드를 생성하도록 하는 것이다.

Zef에서 이것은:

a + b

이것과 동일하다.

a.add(b)

그래서 원래 인터프리터는 a + b를 b를 인자로 가지는 DotCall(a, "add")로 파싱했다. 그 결과 실행이 느렸는데, 모든 수학 연산마다 연산자 메서드 이름에 대한 문자열 조회가 필요했기 때문이다.

• DotCall은 문자열을 Value::callMethod에 전달했다.
• Value::callMethod는 여러 문자열 비교를 연쇄적으로 수행했다.

이 최적화에서는 파서가Binary<> 및 Unary<> 노드를 생성하게 한다. 약간의 템플릿과 람다 마법 덕분에, 이 노드들은 연산자별로 따로 Node::evaluate를 가상 오버라이드한다. 그리고 이들은 해당 연산자에 대한 Value의 빠른 경로를 직접 호출한다. 따라서 이제 a + b는 Binary<lambda for add>::evaluate를 호출하고, 이는 다시 Value::add를 호출한다.

이 변경은 17.5%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 30배 느리고, Lua 5.4.7보다 67배 느리며, QuickJS-ng 0.14.0보다 19배 느리다.

최적화 #2: RMW(Read Modify Write) 연산자를 직접 호출하기

이전 최적화에서는 문자열 비교 기반 디스패치를 피함으로써 연산자를 빠르게 만들었다. 하지만 그 변경은 모든 연산자에 영향을 주지는 않았다! 다음과 같은 RMW 형태 연산자들은:

a += b

여전히 문자열 기반 디스패치를 사용했다. 그래서 두 번째 최적화는 파서가 각 RMW 경우마다 별도의 노드를 생성하도록 하는 것이다. 각 RMW 경우에 대해 말이다. 여기서 일어나는 일은 파서가 makeRMW 가상 호출을 통해 LValue 노드에게 자신을 RMW로 대체해 달라고 요청하는 것이다.

• Get - 변수 읽기에 해당, 즉 그냥 id
• Dot - expr.id에 해당
• Subscript - 첨자 접근, 즉 expr[index]에 해당

이 각각의 가상 호출은 SPECIALIZE_NEW_RMW 매크로를 사용해 다음의 템플릿 특수화 형태를 만든다.

• SetRMW - id += value에 해당
• DotSetRMW - expr.id += value에 해당
• SubscriptRMW - expr[index] += value에 해당

나머지 연산자 특수화(변경 #1)가 적절한 연산자 함수 Value로 디스패치하기 위해 람다를 사용하는 반면, RMW에서는 열거형을 사용한다는 점에 주목하라. 이는 실용적인 선택인데, RMW에 도달하는 방법이 세 가지(get, dot, subscript)라는 사실을 처리하기 위해 그 enum을 여러 곳으로 전달해야 하기 때문이다. 이 모든 마법은 결국 실제 RMW 연산자 호출을 디스패치하는 Value::callRMW<> 템플릿 함수로 귀결된다.

이 변경은 3.7%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 29배 느리고, Lua 5.4.7보다 65배 느리며, QuickJS-ng 0.14.0보다 18.5배 느리다. 이제 시작점보다 1.22배 빨라졌다.

최적화 #3: IntObject 검사 피하기

Value의 빠른 경로에는 작은 문제가 있다. 이들은 isInt()를 사용하는데, 이는 다시 isIntSlow()를 사용하고, 그것은 우리가 정말 int를 다루는지 확인하기 위해 Object::isInt()에 대한 가상 호출을 수행한다.

이런 일이 벌어지는 이유는 원래 인터프리터의 Zef 값 표현이 네 가지 구별된 경우를 가졌기 때문이다.

1. 태그된 int32 값.
2. 태그된 double 값.
3. int32로 표현할 수 없는 int64를 위한 IntObject.
4. 그 외의 모든 객체.

IntObject의 경우에도 Value가 모든 정수 메서드의 디스패치를 계속 담당했는데, 그러면 인터프리터가 모든 수학 연산자에 대해 구현을 하나만 가지면 되었기 때문이다(그리고 그 구현은 항상 Value 안에 있었다).

이 단순한 최적화는 Value의 빠른 경로가 오직 int32와 double만 고려하게 하고, 모든 IntObject 처리를 IntObject 자체로 옮긴다. 추가로 이 변경은 모든 메서드 디스패치마다 발생하던 isInt() 호출도 피한다.

이는 1%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 29배 느리고, Lua 5.4.7보다 65배 느리며, QuickJS-ng 0.14.0보다 18배 느리다. 이제 시작점보다 1.23배 빨라졌다.

최적화 #4: 심볼

원래의 Zef 인터프리터는 std::string을 어디에나 사용한다. 특히 잔인한 경우는 다음과 같다.

• Context::get, Context::set, 그리고 Context::callFunction - 로컬 변수 및 로컬 함수 접근에 사용된다.
• Value::callMethod, Value::dot, 그리고 Value::setDot - 모든 expr.something 연산에 사용된다.
• Value::callOperator<> - primitive에 대한 이름 기반 호출이 해석되는 방식이다.
• Object::callMethod와 그 관련 함수들 - 메서드 호출이 해석되는 방식이다.

이것이 불행한 이유는 이런 조회들이 단지 해시테이블만 수반하는 것이 아니라, 문자열을 키로 하는 해시테이블을 수반한다는 뜻이기 때문이다! 따라서 Zef 실행 중에는 문자열을 계속 해싱하고 비교하게 된다.

다음 최적화는 이런 모든 조회에 문자열 대신 해시-컨싱된 Symbol 객체에 대한 포인터를 사용한다. 파일 영향 범위는 큰 변경이지만, 실제로는 아주 단순하다.

• symbol.h와 symbol.cpp에 새로운 Symbol 클래스가 있다. Symbol은 문자열로 바꿀 수 있고 그 반대도 가능하다. 문자열을 symbol로 바꾸는 과정에는 해시 컨싱을 수행하는 전역 해시테이블이 사용된다. 이 덕분에 Symbol*에 대한 포인터 동일성 비교가 두 심볼이 같은지 확인하는 올바른 방법이 된다.
• 이제 문자열 리터럴 대신 미리 준비된 심볼을 참조하는 곳이 많다. 예를 들어 "subscript" 문자열 대신 Symbol::subscript를 사용하는 것 같은 식이다.
• 함수 시그니처를 const std::string& 대신 Symbol*를 사용하도록 바꾸는 곳도 많다.

이는 18%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 24배 느리고, Lua 5.4.7보다 54배 느리며, QuickJS-ng 0.14.0보다 15배 느리다. 이제 시작점보다 1.46배 빨라졌다.

최적화 #5: Value 인라인

이 변경은 중요한 함수들의 인라이닝을 가능하게 함으로써 꽤 큰 이득을 준다..

이 변경의 거의 모든 핵심은 새로운 valueinlines.h 헤더를 도입한 데 있다. 이는 value.h와는 별개의 헤더인데, value.h를 포함해야 하는 헤더들을 사용하기 때문이다.

이는 2.8%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 24배 느리고, Lua 5.4.7보다 53배 느리며, QuickJS-ng 0.14.0보다 15배 느리다. 이제 시작점보다 1.5배 빨라졌다.

최적화 #6: 객체 모델, 인라인 캐시, 그리고 워치포인트

때로는 언어 구현을 더 좋게 만드는 유일한 방법이 거대한 패치를 넣는 것이다. 좋은 엔지니어링은 작고 소화하기 쉬운 변경에서만 나온다고 누가 말하든 믿지 마라. 항상 그런 것은 아니다! 빠른 동적 언어 구현을 원한다면 더더욱 아니다!

Object, ClassObject, Context가 동작하는 방식을 다시 설계해서 객체 할당을 더 싸게 만들고 접근 시 해시테이블 조회를 피할 수 있게 하는 거대한 변경이다. 이 변경은 세 가지 변화를 하나로 묶는다.

객체 모델

이전에는 각 렉시컬 스코프가 Context 객체를 하나 할당했고, 각 Context 객체는 그 스코프의 변수들, 즉 필드들의 해시테이블을 담고 있었다. 객체는 더 심했다. 각 객체는 그 객체가 인스턴스인 클래스들로부터 Context 객체로의 매핑을 담은 해시테이블이었다. 이것이 필요했던 이유는 Foo를 상속한 Bar의 인스턴스가 있을 때 Bar와 Foo가 서로 다른 스코프를 클로즈오버할 수 있고, 별개의 필드에 대해 같은 이름을 공유할 수도 있기 때문이다(Zef에서는 필드가 기본적으로 private이기 때문이다). 분명 이것은 엄청 비효율적이다! 이 변경은 Storage라는 개념을 도입한다. 이 Storage는 어떤 Context가 결정한 Offsets에 따라 데이터를 담는다. 즉, Context는 여전히 존재하지만, AST의 resolve 패스 일부로 미리 생성되고, 객체나 스코프가 생성될 때는 그에 해당하는 Context가 계산한 크기에 맞춰 storage를 할당만 하면 된다.

인라인 캐시

이것은 고전적인 기법이며 현대의 고성능 동적 언어 구현의 기반을 형성한다. 하지만 이 기법은 전통적으로 JIT 컴파일러 맥락에서 논의되지만, 이번 변경에서는 인터프리터에서 사용한다. 인라인 캐시의 아이디어는 expr.name을 수행하는 코드 위치가 있으면, expr이 마지막으로 동적으로 가졌던 타입과 name이 마지막으로 해석된 오프셋을 기억하는 것이다. 이번 변경에서 그 기억은 일반 AST 노드 위에 특수화된 AST 노드를 placement construct하는 방식으로 구현된다. 여기에는 다섯 가지 요소가 있다.

1. CacheRecipe 객체는 특정 접근이 무엇을 했는지, 그리고 그것이 캐시 가능한지 추적하는 데 사용된다.
2. Context, ClassObject, Package 전반에 CacheRecipe 호출이 흩어져 있다.
3. Dot::evaluate 같은 AST 평가 함수는 자신이 수행한 다형적 연산에서 얻은 CacheRecipe를 this와 함께 constructCache<>에 전달한다.
4. constructCache는 CacheRecipe에 따라 새 AST 노드 특수화를 컴파일한다. 그렇다, 컴파일한다. constructcache.h에는 다양한 종류의 특수화된 AST 노드를 생성할 수 있는 템플릿 기계가 있다. 예를 들어 AST 노드에 전달된 storage에 대한 직접 로드로 특수화할 수도 있다(로컬 변수 접근의 경우처럼). 또는 클래스 검사 (이 객체가 여전히 내가 마지막으로 본 클래스를 가지고 있는가?)를 내보낸 다음, 마지막으로 본 함수에 대한 직접 함수 호출을 내보낼 수도 있다. 캐시되는 접근이 스코프 체인을 따라가는 과정이 포함되었다면, 이런 것들은 체인 단계 및 워치포인트와 조합될 수 있다.
5. 캐싱 대상이 되는 각 AST 노드는 먼저 constructCache<>가 타입을 결정하는 cache 객체에 대한 빠른 호출을 시도하는 캐시된 변종을 가진다.

워치포인트

렉시컬 스코프 안에 변수 x를 가진 클래스 Foo가 있고, Foo의 한 메서드가 x에 접근하려고 한다고 하자. 그리고 Foo 안에는 x라는 함수나 변수가 없다고 하자. 그렇다면 아무 검사 없이 x에 접근할 수 있어야 하지 않을까? 그런데 완전히 그렇지는 않다. 누군가 Foo를 상속해서 x라는 getter를 추가할 수 있기 때문이다. 그 경우 그 접근은 바깥쪽 x가 아니라 getter로 해석되어야 한다. 인라인 캐시는 이를 처리하기 위해 런타임 내부에 Watchpoint를 설정한다. 이 예에서는 이름이 override되었는가라는 워치포인트다.

모두 합치기

이 세 기능은 각각 규모가 크다. 내가 이를 한꺼번에 구현하기로 한 이유는 다음과 같다.

• 새로운 객체 모델은 인라인 캐싱이 잘 동작하도록 하지 않으면 의미 있게 좋아지지 않는다. 그래서 객체 모델과 인라인 캐시를 함께 개발했다.
• 인라인 캐시는 워치포인트도 함께 갖추지 않으면 의미 있는 이득을 주지 못한다. 캐시 가능한 조건들 중 워치포인트를 필요로 하는 것이 너무 많기 때문이다.
• 새로운 객체 모델과 워치포인트는 서로 아주 잘 맞물려 동작해야 한다.

나는 이 변경을 시작하면서, 최종 형태에 거의 가까운 Storage와 Offsets와 함께, 단순한 버전의 CacheRecipe를 먼저 작성했다.

가장 어려운 작업 중 일부는 예전 스타일의 intrinsic class를 새로운 스타일로 바꾸는 일이었다. 배열을 예로 들어 보자. 이전에는 ArrayObject::tryCallMethod가 가상 Object::tryCallMethod 호출을 가로채는 방식으로 모든 ArrayObject 메서드를 구현했다. 하지만 새로운 객체 모델에서는 Object에 vtable도, 가상 메서드도 없다. 대신 Object::tryCallMethod가 object->classObject()->tryCallMethod(object, ...)로 전달한다. 따라서 Array가 메서드를 가지려면 그 메서드들을 가진 Array용 클래스를 생성해야 한다. 결국 이 변경은 구현 전반에 흩어져 있던 많은 intrinsic 기능을 makerootcontext.cpp 안으로 모아 놓는다. 이것은 좋은 결과인데, 객체의 네이티브/intrinsic 함수들에 대해서도 모든 인라인 캐싱 기계가 그대로 작동하게 되기 때문이다!

이 거대한 변경은 거대한 이득을 낸다. 4.55배 더 빠르다! 이 시점에서 Zef는 CPython 3.10보다 5.2배 느리고, Lua 5.4.7보다 11.7배 느리며, QuickJS-ng 0.14.0보다 3.3배 느리다. 다시 말해 Fil-C++로 컴파일된 Zef가 다른 인터프리터들에 비해 뒤처지는 폭은 거의 Fil-C의 손실폭 정도와 비슷한 수준이 되었다(그 다른 인터프리터들은 Yolo-C로 컴파일된다).

이제 시작점보다 6.8배 빨라졌다.

최적화 #7: 인자

이 변경 전에는 Zef 인터프리터가 함수에 인자를 const std::optional<std::vector<Value>>& 형태로 전달했다. optional이 필요했던 이유는 어떤 구석진 경우에는 다음을 구분해야 하기 때문이다.

o.getter

그리고:

o.function()

대부분의 경우 Zef에서는 이 둘이 같다. 둘 다 함수 호출이다. 하지만 예외가 있다.

o.NestedClass

대:

o.NestedClass()

첫 번째 경우는 NestedClass 객체를 가져오고, 두 번째 경우는 그것을 인스턴스화한다.

따라서 비어 있는 인자 배열을 전달하는 것이 인자가 0개인 함수 호출이라서인지, 아니면 getter 같은 호출이어서인지 구분할 필요가 있다.

어쨌든 이것은 엄청 비효율적이다. 호출자가 vector를 할당하고, 그 다음 피호출자가 그 벡터의 복사본인 인자 스코프를 다시 할당해야 하기 때문이다.

이 변경은 Arguments 타입을 도입하는데, 이 타입은 피호출자가 원래 할당했을 인자 스코프와 정확히 같은 모양을 가진다. 이제 호출자가 이것을 직접 할당한다. 그 결과 호출 한 번에 필요한 할당 횟수가 절반 이하로 줄어든다.

• Yolo-C++에서도 할당을 절반으로 줄였을 것이다. 더 이상 vector의 backing store를 malloc할 필요가 없기 때문이다.
• Fil-C++에서는 std::optional 자체가 힙 할당되어야 한다. std::optional이 없더라도 const std::vector<>&를 전달하면 그것도 할당이 된다. 스택에 할당되는 것은 모두 힙에 할당되기 때문이다.
• 마침 호출자 쪽 코드는 벡터를 미리 크기 지정하지 않고 여러 번 재할당하고 있었다.

이 변경의 상당 부분은 함수 시그니처를 optional vector 대신 Arguments*를 받도록 바꾸는 작업일 뿐이다.

이는 1.33배의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 3.9배 느리고, Lua 5.4.7보다 8.8배 느리며, QuickJS-ng 0.14.0보다 2.5배 느리다. 이제 시작점보다 9.05배 빨라졌다.

최적화 #8: Getter 특수화

Ruby와 다른 많은 객체 지향 언어처럼, Zef는 인스턴스 필드가 기본적으로 private이다. private라는 뜻은 그 인스턴스 자신만 그것을 볼 수 있다는 뜻이다. 다음 코드를 보자.

class Foo {
    my f
    fn (inF) f = inF
}

이것은 생성자에서 f에 대한 값을 받아 인스턴스에만 국한된 로컬 변수 에 저장하는 클래스 Foo다. 예를 들어 다음은 동작하지 않는다.

class Foo {
    my f
    fn (inF) f = inF
    fn nope(o) o.f
}
println(Foo(42).nope(Foo(666)))

nope 안의 o.f 식은 o가 같은 타입이라 하더라도 o의 f에 접근할 수 없다. 이는 필드가 클래스 멤버의 스코프 체인 안에 나타나는 방식으로 동작한다는 사실의 결과일 뿐이다. o.f 같은 것을 할 때, 우리는 f라는 메서드를 호출하려는 것이다. 그래서 이런 코드가 많이 나온다.

class Foo {
    my f
    fn (inF) f = inF
    fn f f # local variable f를 반환하는 f라는 메서드
}

또는 더 간단히:

class Foo {
    readable f # `my f`와 `fn f f`의 축약형
    fn (inF) f = inF
}

결국 많은 메서드 호출이 getter 호출이 된다. 그런데 이런 호출들 모두가 getter의 AST를 평가하고 그에 수반되는 모든 일을 하게 두는 것은 엄청난 낭비다!

그래서 다음 변경은 getter를 특수화한다.

이 변경의 핵심은 UserFunction 안에 있다. 여기서 새로운 Node::inferGetter 메서드를 사용해 함수 본문이 단순한 getter인지 추론한다. 중요한 부분은 다음과 같다.

• Block::inferGetter는 자신이 담고 있는 것이 전부 getter로 추론 가능한 것이라면 자신도 getter라고 추론한다.
• Get::inferGetter는 자신을 getter로 추론하고, 자신이 로드할 오프셋을 반환한다.
• Context::tryGetFieldOffsets는 getter가 실행되는 렉시컬 스코프에 그 필드가 확실히 존재하는 경우에만 비어 있지 않은 Offsets를 반환한다.
• UserFunction은 본문이 getter로 추론될 수 있으면 자기 자신을 알려진 오프셋에서 바로 get을 수행하는 특별한 Function 서브클래스로 resolve한다.

이는 5.6%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 3.7배 느리고, Lua 5.4.7보다 8.3배 느리며, QuickJS-ng 0.14.0보다 2.4배 느리다. 이제 시작점보다 9.55배 빨라졌다.

최적화 #9: Setter 특수화

이제 setter에도 같은 일을 해 보자!

이번에는 추론이 조금 더 복잡하다. 다음 패턴을 매칭해야 하기 때문이다.

fn set_fieldName(newValue) fieldName = newValue

이것이 뜻하는 바는 다음과 같다.

• UserFunction의 추론은 setter의 매개변수 이름을 아래로 전달해야 한다.
• Set의 추론은 ClassObject에 대한 쓰기를 하고 있지 않은지(그 필드들은 immutable이다), 그리고 setter의 매개변수를 set의 소스로 사용하고 있는지 확인해야 한다.

이는 3.4%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 3.6배 느리고, Lua 5.4.7보다 8배 느리며, QuickJS-ng 0.14.0보다 2.3배 느리다. 이제 시작점보다 9.87배 빨라졌다.

최적화 #10: callMethod 인라이닝

이것은 중요한 함수를 인라인하기 위한 한 줄짜리 변경이다..

이는 3.2%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 3.5배 느리고, Lua 5.4.7보다 7.8배 느리며, QuickJS-ng 0.14.0보다 2.2배 느리다. 이제 시작점보다 10.2배 빨라졌다.

최적화 #11: 해시테이블

이 변경 전에는 메서드 호출에 대한 인라인 캐시가 미스하면 ClassObject::tryCallMethod와 ClassObject::TryCallMethodDirect를 따라 내려가야 했는데, 이 둘은 꽤 크고 복잡하다.

게다가 이것은 O(계층 깊이)다. 더 정확히 말하면 계층의 각 레벨마다 해시테이블 조회 두 번이다.

• 계층의 각 클래스마다 호출이 멤버 함수로 해석되는지 확인한다.
• 계층의 각 클래스마다 호출이 중첩 클래스에 해석되는지 확인한다.

다음 변경은 수신자 클래스와 심볼을 키로 하여 피호출자를 한 번의 조회로 직접 주는 전역 해시테이블을 도입한다..

classobject.h에서는 전체 tryCallMethodSlow로 내려가기 전에 이 전역 테이블을 조회한다.

classobject.cpp에서는 성공적인 조회를 이 전역 테이블에 기록한다..

전역 해시테이블 자체는 꽤 단순하다.

이는 15%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 3배 느리고, Lua 5.4.7보다 6.8배 느리며, QuickJS-ng 0.14.0보다 1.9배 느리다. 이제 시작점보다 11.8배 빨라졌다.

최적화 #12: std::optional 피하기

Fil-C++에서는 union과 관련된 컴파일러 병리 때문에 std::optional이 힙 할당되어야 한다.

보통 LLVM은 union에 사용되는 메모리 접근 타입을 아주 느슨하게 다루지만, 이것은 invisicaps에서 문제가 된다. union 안의 포인터는 때때로, 프로그래머가 보기에는 꽤 예측 불가능하게, capability를 잃는다. 그러면 Fil-C는 프로그래머가 잘못한 것이 없는데도 null capability를 가진 객체를 역참조하고 있다는 패닉을 낸다. 이를 완화하기 위해 Fil-C++ 컴파일러는 union 타입의 로컬 변수를 LLVM이 보수적으로 다루도록 강제하는 intrinsic을 삽입한다. 이후 FilPizlonator 패스가 자체적인 escape analysis를 수행해 union 타입 로컬이 레지스터 할당되도록 허용하려고 시도하지만, 이 분석은 일반적인 LLVM의 SROA 분석만큼 완전하지는 않다.

그 결과는 이렇다. std::optional처럼 내부에 union이 있는 클래스를 전달하는 것은 Fil-C++에서 종종 메모리 할당으로 이어진다!

그래서 이 변경은 핫 패스에서 std::optional로 이어지는 코드 경로를 피한다..

이는 1.7%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 3배 느리고, Lua 5.4.7보다 6.65배 느리며, QuickJS-ng 0.14.0보다 1.9배 느리다. 이제 시작점보다 12배 빨라졌다.

최적화 #13: 특수화된 인자

Zef의 모든 내장 함수는 인자를 하나 또는 둘 받는데, 네이티브 구현은 그것들을 담기 위해 Arguments 객체를 할당할 필요가 없다. 그냥 그 인자들을 직접 받을 수 있다.

setter는 모두 인자를 하나 받는다. 그리고 setter를 추론할 수 있다면 특수화된 setter 구현 역시 Arguments 객체를 할당할 필요가 없다. 마찬가지로 그 코드는 값 인자를 직접 받으면 된다.

다음 변경은 ZeroArguments, OneArgument, TwoArguments라는 특수화된 인자 타입을 도입하여, 피호출자가 Arguments 객체를 필요로 하지 않는 경우 호출자가 그 객체를 할당하지 않도록 한다.

이 변경의 핵심은 새로운 특수화 인자 타입들이다. ZeroArguments가 필요한 이유는 (Arguments*)nullptr 전달과 구분해야 하기 때문이다. 우리는 이미 (Arguments*)nullptr를 getter 호출이라는 뜻으로 사용하고 있었고, 그 로직은 그대로 둔다. 따라서 이제 ZeroArguments는 인자가 없는 함수 호출을 뜻한다.

이 변경의 상당 부분은 인자를 받는 함수들을 템플릿화하는 것에 관한 것이고, 이어서 ZeroArguments, OneArgument, TwoArguments, Arguments*에 대해 명시적으로 인스턴스화한다. 많은 코드가 이미 인자를 꺼내는 헬퍼로 Value::getArg를 사용하고 있었기 때문에, 이 변경은 인자 특수화에 대한 오버로드만 추가하면 된다. 그 결과 인자를 사용하는 네이티브 코드의 변경도 꽤 직선적이다.

이는 3.8%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 2.9배 느리고, Lua 5.4.7보다 6.4배 느리며, QuickJS-ng 0.14.0보다 1.8배 느리다. 이제 시작점보다 12.4배 빨라졌다.

최적화 #14: 개선된 Value 느린 경로

(다음 변경은 또 다른 Fil-C 병리를 우회함으로써 큰 속도 향상을 얻는다.](diff-viewers/14-valueslowpaths.html)

이 변경 전에는 Value의 out-of-line 느린 경로가 Value의 멤버 함수였다. 즉 암묵적인 const Value* 인자를 받았다. 이는 호출자가 Value를 스택에 할당해야 함을 뜻한다.

Fil-C++에서는 모든 스택 할당이 힙 할당이다. 따라서 느린 경로를 호출하는 코드는 Value를 힙에 할당하게 된다!

이 변경은 그 메서드들을 static으로 바꾸고 Value를 값으로 받게 하여, 어떤 할당도 필요 없게 만든다.

10%의 속도 향상. 이 시점에서 Zef는 CPython 3.10보다 2.6배 느리고, Lua 5.4.7보다 5.8배 느리며, QuickJS-ng 0.14.0보다 1.65배 느리다. 이제 시작점보다 13.6배 빨라졌다.

최적화 #15: DotSetRMW 중복 제거

이 변경은 중복된 코드를 일부 제거한다.

기계 코드가 적을수록 좋으니 속도 향상이 있기를 바랐다. 특히 constructCache<>에 의해 특수화되는 템플릿 함수에서는 더더욱 그렇다.

하지만 속도 향상은 없었다. 성능에는 아무 영향이 없다.

최적화 #16: sqrt 특수화

인라인 캐시는 호출을 원하는 정확한 함수로 라우팅하는 데 뛰어나지만, 객체에 대해서만 작동한다. 비객체의 경우에는 Binary<>, Unary<>, Value::callRMW<>가 빠른 경로로 가서 수신자가 int인지 double인지 검사한다는 사실에 의존하고 있다.

하지만 이것은 파서가 인식하는 연산자에 대해서만 작동한다. 예를 들어 value.sqrt를 하는 경우에는 작동하지 않는다.

그래서 다음 변경은 Dot이 value.sqrt에 대해 특수화하도록 가르친다..

이는 1.6%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 2.6배 느리고, Lua 5.4.7보다 5.75배 느리며, QuickJS-ng 0.14.0보다 1.6배 느리다. 이제 시작점보다 13.8배 빨라졌다.

최적화 #17: toString 특수화

이것은 거의 바로 이전 최적화와 같지만, toString에 대한 것이다.

이 변경에는 int를 문자열로 변환할 때 발생하는 할당 수를 줄이기 위한 약간의 추가 로직이 있다.

이는 2.7%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 2.5배 느리고, Lua 5.4.7보다 5.6배 느리며, QuickJS-ng 0.14.0보다 1.6배 느리다. 이제 시작점보다 14.2배 빨라졌다.

최적화 #18: 배열 리터럴 특수화

다음을 수행한다고 하자.

my whatever = [1, 2, 3]

Zef에서 배열은 alias 가능하고 mutable이므로 새 배열을 할당해야 한다. 하지만 더 나쁜 점은, 이 변경 전에는 매번 1, 2, 3을 평가하기 위해 AST를 재귀적으로 내려가야 했다는 것이다.

이 변경은 ArrayLiteral 노드가 상수 배열을 할당하는 경우를 특수화한다..

이는 8.1%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 2.3배 느리고, Lua 5.4.7보다 5.2배 느리며, QuickJS-ng 0.14.0보다 1.5배 느리다. 이제 시작점보다 15.35배 빨라졌다.

최적화 #19: Value::callOperator 개선

이전에 Value를 참조로 전달하지 않는 것에서 약간의 속도 향상을 얻었다. 이것은 같은 최적화를 callOperator 느린 경로에 적용한 것이다.

이는 6.5%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 2.2배 느리고, Lua 5.4.7보다 4.9배 느리며, QuickJS-ng 0.14.0보다 1.4배 느리다. 이제 시작점보다 16.3배 빨라졌다.

최적화 #20: 더 나은 C++ 옵션

이 변경은 Fil-C++에서는 불필요하므로 RTTI와 libc++ hardening을 비활성화한다.

여기에는 C++ 코드 변경은 없고, 빌드 시스템 설정 변경만 있다.

이는 1.8%의 속도 향상이다. 이 시점에서 Zef는 CPython 3.10보다 2.1배 느리고, Lua 5.4.7보다 4.8배 느리며, QuickJS-ng 0.14.0보다 1.35배 느리다. 이제 시작점보다 16.6배 빨라졌다.

최적화 #21: Assert 없음

마지막 최적화는 기본적으로 assertion을 끈다.

이전에는 코드가 Fil-C 전용 ZASSERT 매크로를 사용했는데, 이것은 항상 assert한다는 뜻이다. 이제 코드는 내부 ASSERT 매크로를 사용하며, 이는 ASSERTS_ENABLED가 설정되어 있을 때만 assert한다는 뜻이다.

이 변경에는 코드가 Yolo-C++에서도 빌드되도록 하기 위한 다른 변경도 일부 포함되어 있다.

속도 향상이 있기를 바랐지만, 없었다.

Yolo-C++는 어떤가?

마지막으로 코드를 Yolo-C++로 컴파일해 보았다. 그 결과 4배의 속도 향상이 나왔다. 다만 이것은 건전하지도 않고 최적도 아니다.

• 건전하지 않은 이유는, 원래 Fil-C++ GC 호출이던 것을 calloc 호출로 바꾸고 있기 때문이다. 즉 메모리가 전혀 해제되지 않는다. 충분히 오래 실행되는 워크로드에서는 이 인터프리터가 메모리를 다 써 버릴 것이다. ScriptBench1에서는 테스트가 짧게만 실행되므로 우연히 메모리 부족이 나지 않을 뿐이다.
• 최적이 아닌 이유는, 실제 GC allocator가 glibc 2.35에 포함된 calloc보다 더 빠르기 때문이다.

따라서 Yolo-C++ 포트의 일부로 Zef에 실제 GC를 추가한다면, 아마 4배보다 더 큰 속도 향상을 얻을 것이다.

이 실험에는 GCC 11.4.0을 사용했다.

이 시점에서 Zef는 CPython 3.10보다 1.9배 빠르고, Lua 5.4.7보다 1.2배 느리며, QuickJS-ng 0.14.0보다 3배 빠르다. 이제 시작점보다 67배 빨라졌다!

원시 데이터

다음은 각 인터프리터에서 모든 벤치마크의 실행 시간(초)과 그 기하평균을 보여 주는 원시 데이터다.