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

• AST 직접 순회 인터프리터도 값 표현, 인라인 캐시, 객체 모델, watchpoint, 반복적인 세부 최적화만으로 큰 성능 향상 가능
• 성능을 거의 고려하지 않은 Zef 베이스라인은 CPython 3.10보다 35배, Lua 5.4.7보다 80배, QuickJS-ng 0.14.0보다 23배 느렸지만, 21단계 최적화 뒤 16.646배 가속 달성
• 가장 큰 도약은 객체 모델 재설계와 인라인 캐시 결합에서 발생했고, Storage와 Offsets 기반 접근, 캐시된 AST 특수화, 이름 오버라이드 감시용 watchpoint 적용으로 4.55배 향상 이어짐
• 추가 개선으로 문자열 기반 디스패치 제거, Symbol 도입, 인자 전달 구조 변경, getter와 setter 특수화, 해시테이블 단축 경로, 배열 리터럴과 sqrt·toString 특수화까지 누적 적용
• Yolo-C++ 이식까지 포함하면 베이스라인 대비 66.962배 빠름 기록, CPython 3.10보다 1.889배 빠르고 QuickJS-ng 0.14.0보다 2.968배 빠르지만 메모리 해제가 없어 장기 실행 워크로드에는 부적합함

---

도입과 평가 방법론

• 최적화 대상은 AST 직접 순회 인터프리터이며, 재미로 만든 동적 언어 Zef를 Lua, QuickJS, CPython과 경쟁 가능한 수준까지 끌어올리는 목표
  • JIT 컴파일러나 성숙한 GC의 미세 조정보다, 기초가 없는 출발점에서도 적용 가능한 최적화에 집중
  • 다루는 기법은 값 표현, 인라인 캐싱, 객체 모델, watchpoint, 상식적인 최적화의 반복 적용
• 본문 기법만으로 SSA, GC, 바이트코드, 머신 코드 없이도 큰 성능 향상 달성
  • 본문 기준 16배 가속
  • 미완성 Yolo-C++ 이식 포함 시 67배 가속
• 성능 평가는 ScriptBench1 벤치마크 스위트 사용
  • 포함 벤치마크는 Richards OS scheduler, DeltaBlue constraint solver, N-Body physics simulation, Splay binary tree test
  • 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은 GitHub releases 바이너리 사용
  • CPython 3.10은 Ubuntu 기본 제공 버전 사용
• 모든 실험은 무작위로 섞은 30회 실행 평균값 사용
• 대부분 비교는 Fil-C++로 컴파일한 Zef 인터프리터와 Yolo-C 컴파일러로 빌드한 다른 인터프리터들 사이에서 수행

원래 Zef 인터프리터

• 성능을 거의 고려하지 않고 작성됐으며, 성능을 의식한 선택은 두 가지만 있었다고 명시

• 값 표현

  • 64비트 tagged value 사용
    • 담을 수 있는 값은 double, 32비트 정수, Object*
  • double은 0x1000000000000 오프셋 방식으로 표현
    • JavaScriptCore에서 배운 기법으로 소개
    • 문헌에서는 NuN tagging으로 지칭
  • 정수와 포인터는 네이티브 표현 사용
    • 포인터 값이 0x100000000보다 작지 않다는 가정에 의존
    • 위험한 선택이라고 직접 명시
    • 대안으로 정수에 0xffff000000000000 상위 비트 태그를 둘 수 있었다고 언급
  • 이 표현으로 숫자 연산에서 비트 테스트 기반 빠른 경로 구현 가능
  • 더 중요한 이점은 숫자에 대한 힙 할당 회피
  • 인터프리터를 새로 만들 때는 기본 값 표현을 초기에 잘 선택하는 일이 중요하며, 이후 변경은 매우 어려움
  • 동적 타입 언어 구현 출발점으로 32비트 또는 64비트 tagged value 제시

• 구현 언어 선택

  • 최적화를 충분히 담아낼 수 있는 언어로 C++ 계열 선택
  • Java는 저수준 최적화 상한 때문에 선택하지 않겠다고 명시
  • Rust는 GC 언어 구현에 필요한 전역 가변 상태와 순환 참조를 갖는 힙 표현 때문에 선택하지 않겠다고 밝힘
    • 다중 언어 구성을 감수하거나 많은 unsafe 코드를 허용하면 일부 또는 전체에 Rust 사용 가능성 언급

• 성능 엔지니어링 관점의 잘못된 선택

  • Fil-C++ 사용
    • 빠르게 개발 가능했고 GC를 공짜로 제공
    • 메모리 안전성 위반을 진단 정보와 스택 트레이스로 보고
    • 정의되지 않은 동작이 없음
    • 성능 비용은 보통 약 4배
  • 재귀적 AST 워킹 인터프리터
    • 여러 곳에서 오버라이드되는 virtual Node::evaluate 메서드 구조
  • 문자열 남용
    • Get AST 노드가 변수 이름을 설명하는 std::string 저장
    • 변수 접근마다 그 문자열 사용
  • 해시테이블 남용
    • Get 실행 시 문자열 키로 std::unordered_map 조회
  • 재귀 호출 체인 기반 스코프 탐색
    • 거의 모든 구조의 중첩과 클로저 허용
    • 함수 F 안의 클래스 A, 클래스 B 안의 함수 G 같은 중첩에서 A의 메서드는 A 필드, F 지역 변수, B 필드, G 지역 변수를 볼 수 있음
    • 원래 구현은 이를 서로 다른 스코프 객체를 질의하는 C++ 재귀 함수들로 처리

• 원래 구현의 특성

  • 잘못된 선택에도 불구하고 적은 코드로 꽤 복잡한 언어 인터프리터 구현 가능
  • 가장 큰 모듈은 parser
  • 나머지는 단순하고 명확한 편

• 초기 성능

  • 원래 인터프리터는 CPython 3.10보다 35배 느림

  • Lua 5.4.7보다 80배 느림

    • QuickJS-ng 0.14.0보다 23배 느림

전체 최적화 진행표

• 표는 Zef Baseline부터 Zef Change #21: No Asserts, 그리고 Zef in Yolo-C++ 까지 성능 변화를 정리
  • 비교 열은 vs Zef Baseline, vs Python 3.10, vs Lua 5.4.7, vs QuickJS-ng 0.14.0
• 최종 행 기준 Zef Change #21: No Asserts는 베이스라인 대비 16.646배 빠름

  • Python 3.10보다 2.13배 느림

  • Lua 5.4.7보다 4.781배 느림

    • QuickJS-ng 0.14.0보다 1.355배 느림

• Zef in Yolo-C++는 베이스라인 대비66.962배 빠름

  • Python 3.10보다 1.889배 빠름

  • Lua 5.4.7보다 1.189배 느림

    • QuickJS-ng 0.14.0보다 2.968배 빠름

초기 최적화 단계

• 최적화 #1: 연산자 직접 호출

  • 파서가 더 이상 연산자를 연산자 이름을 가진 DotCall 노드로 만들지 않고, 각 연산자별 별도 AST 노드 생성
  • Zef에서는 a + b와 a.add(b)가 동일
    • 원래는 a + b를 DotCall(a, "add")와 인자 b 로 파싱
    • 모든 산술 연산마다 연산자 메서드 이름 문자열 조회 발생
    • DotCall은 문자열을 Value::callMethod로 전달
    • Value::callMethod는 다중 문자열 비교 수행
  • 변경 후 파서는 Binary<>, Unary<> 노드 생성
    • 템플릿과 람다를 활용해 연산자별 서로 다른 Node::evaluate 오버라이드 제공
    • 각 노드는 해당 연산자의 Value 빠른 경로 직접 호출
    • 예시로 a + b는 Binary<lambda for add>::evaluate 호출 뒤 Value::add 호출
  • 성능 효과는 17.5% 향상
    • 이 시점 성능은 CPython 3.10보다 30배 느림
    • Lua 5.4.7보다 67배 느림
    • QuickJS-ng 0.14.0보다 19배 느림

• 최적화 #2: RMW 연산자 직접 호출

  • 일반 연산자는 빨라졌지만, a += b 같은 RMW 형태는 여전히 문자열 기반 디스패치 사용
  • 파서가 각 RMW 케이스용 별도 노드를 생성하도록 변경
  • 파서는 LValue 노드가 makeRMW 가상 호출을 통해 자신을 RMW로 대체하도록 요청
  • RMW로 바뀌는 LValue는 Get, Dot, Subscript
    • Get은 변수 읽기 id 대응
    • Dot은 expr.id 대응
    • Subscript는 expr[index] 대응
  • 각 가상 호출은 SPECIALIZE_NEW_RMW 매크로 사용
    • SetRMW는 id += value
    • DotSetRMW는 expr.id += value
    • SubscriptRMW는 expr[index] += value
  • 변경 #1의 연산자 특수화는 람다 디스패치 사용
  • RMW는 enum 사용
    • get, dot, subscript 세 경로를 모두 처리하며 enum을 여러 위치에 전달해야 해서 선택
    • 최종적으로 Value::callRMW<> 템플릿 함수가 실제 RMW 연산자 호출 디스패치 수행
  • 성능 효과는 3.7% 향상
    • 이 시점 성능은 CPython 3.10보다 29배 느림
    • Lua 5.4.7보다 65배 느림
    • QuickJS-ng 0.14.0보다 18.5배 느림
    • 시작점 대비 1.22배 빠름

• 최적화 #3: IntObject 검사 회피

  • Value의 빠른 경로가 isInt() 를 사용하고, 그 내부 isIntSlow() 가 Object::isInt() 가상 호출을 수행하는 점이 병목
  • 원래 값 표현에는 네 가지 경우 존재
    • tagged int32
    • tagged double
    • int32로 표현 불가능한 int64용 IntObject
    • 그 외 모든 객체
  • IntObject 경우에도 정수 메서드 디스패치를 Value가 담당
    • 모든 산술 연산 구현을 한 곳, 즉 Value에 두기 위함
  • 최적화 후 Value 빠른 경로는 int32와 double만 고려
    • IntObject 처리 로직은 IntObject 자신으로 이동
    • 메서드 디스패치마다 발생하던 isInt() 호출 회피
  • 성능 효과는 1% 향상
    • 이 시점 성능은 CPython 3.10보다 29배 느림
    • Lua 5.4.7보다 65배 느림
    • QuickJS-ng 0.14.0보다 18배 느림
    • 시작점 대비 1.23배 빠름

• 최적화 #4: Symbol

  • 원래 인터프리터는 std::string을 거의 모든 곳에 사용
  • 비용이 큰 문자열 사용 위치는 Context::get, Context::set, Context::callFunction, Value::callMethod, Value::dot, Value::setDot, Value::callOperator<>, Object::callMethod 계열
  • 이런 구조에서는 단순 해시테이블 조회가 아니라 문자열 키 해시테이블 조회가 되어 실행 중 문자열 해싱과 비교 반복
  • 최적화는 문자열 기반 조회를 hash-consed Symbol 객체 포인터로 대체
  • 새 Symbol 클래스 추가
    • symbol.h, symbol.cpp에 구현
    • Symbol과 문자열은 상호 변환 가능
    • 문자열을 Symbol로 바꿀 때 전역 해시테이블로 hash consing 수행
    • 결과적으로 Symbol* 포인터 동일성 비교만으로 같은 심볼 여부 판별
  • 문자열 리터럴 대신 미리 준비된 심볼 사용
    • 예시로 "subscript" 대신 Symbol::subscript
  • 함수 시그니처 다수가 const std::string& 대신 Symbol* 사용으로 변경
  • 성능 효과는 18% 향상
    • 이 시점 성능은 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% 향상
    • 이 시점 성능은 CPython 3.10보다 24배 느림
    • Lua 5.4.7보다 53배 느림
    • QuickJS-ng 0.14.0보다 15배 느림
    • 시작점 대비 1.5배 빠름

객체 모델과 캐시 구조 재설계

• 최적화 #6: 객체 모델, 인라인 캐시, Watchpoint

  • Object, ClassObject, Context 작동 방식을 대규모 재구성해 객체 할당 비용을 낮추고 접근 시 해시테이블 조회 회피
  • 이 변경은 객체 모델, 인라인 캐시, watchpoint 세 기능 결합

• 객체 모델

  • 이전에는 각 렉시컬 스코프마다 Context 객체 할당
    • 각 Context는 그 스코프 변수들을 담는 해시테이블 보유
  • 객체는 더 복잡한 구조
    • 각 객체가 자신이 인스턴스인 클래스들을 Context에 매핑하는 해시테이블 보유
  • 이런 구조가 필요했던 이유는 상속과 중첩 스코프 때문
    • Bar가 Foo를 상속할 때 Bar와 Foo가 서로 다른 스코프를 클로즈오버
    • 같은 이름의 서로 다른 private 필드도 가질 수 있음
  • 새 구조는 Storage 개념 도입
    • 데이터는 Offsets에 따라 저장
    • offset은 어떤 Context 가 결정
  • Context는 여전히 존재하지만 객체나 스코프 생성 시점이 아니라 AST의 resolve 패스에서 미리 생성
  • 실제 객체나 스코프 생성 시에는 해당 Context가 계산한 크기에 맞춰 Storage만 할당

• 인라인 캐시

  • expr.name 같은 코드 위치에서 마지막으로 본 expr의 동적 타입과 name이 해석된 마지막 offset을 기억하는 기법
  • JIT 문맥에서 주로 설명되는 고전적 기법이지만, 여기서는 인터프리터에 적용
  • 기억한 정보는 일반 AST 노드 위에 특수화된 AST 노드를 placement construct하는 방식으로 구현

• 인라인 캐시 구성 요소

  • CacheRecipe
    • 특정 접근이 무엇을 했는지, 캐시 가능한지 추적
  • Context, ClassObject, Package 곳곳에 CacheRecipe 호출 삽입
    • 접근 과정의 정보 수집
  • Dot::evaluate 같은 AST 평가 함수는 자신이 수행한 다형적 연산에서 얻은 CacheRecipe 를 this와 함께 constructCache<> 에 전달
  • constructCache
    • CacheRecipe에 따라 새 AST 노드 특수화 컴파일
    • 템플릿 기계로 다양한 특수화 AST 노드 생성
    • 지역 변수 접근이면 전달받은 storage에 대한 직접 로드
    • 마지막으로 본 클래스와 동일한지 확인하는 class check
    • 그 뒤 마지막으로 본 함수에 대한 직접 함수 호출
    • 필요하면 chain step과 watchpoint 조합
  • 캐싱 대상 AST 노드는 각각 cached variant 보유
    • 먼저 cache 객체로 빠른 호출 시도
    • cache 객체 타입은 constructCache<>가 결정

• watchpoint

  • 렉시컬 스코프에 변수 x가 있고 그 안에 클래스 Foo가 있으며, Foo 메서드가 x에 접근하는 예시 제시
  • Foo 내부에 x라는 함수나 변수가 없다면 바로 바깥 x 를 읽을 수 있을 것처럼 보임
  • 그러나 서브클래스가 getter x를 추가할 수 있음
  • 그 경우 접근 결과는 바깥 x가 아니라 getter가 되어야 함
  • 인라인 캐시는 이런 변경 가능성을 처리하기 위해 런타임에 Watchpoint 설정
  • 예시에서는 이 이름이 오버라이드되었는지 감시하는 watchpoint 사용

• 세 기능을 동시에 구현한 이유

  • 새 객체 모델만으로는 인라인 캐시가 잘 작동하지 않으면 의미 있는 개선이 어려움
  • 인라인 캐시도 watchpoint가 없으면 많은 캐시 조건을 안전하게 다루기 어려워 실익이 작음
  • 새 객체 모델과 watchpoint는 함께 잘 작동해야 함

• 구현 진행과 어려운 부분

  • 시작은 단순한 CacheRecipe 버전 작성과, 최종 형태에 가까운 Storage, Offsets 설계부터 진행
  • 가장 어려운 작업 중 하나는 intrinsic class 구현 방식 교체
  • 배열 예시
    • 이전에는 ArrayObject::tryCallMethod가 Object::tryCallMethod 가상 호출을 가로채는 방식으로 모든 메서드 구현
    • 새 객체 모델에서는 Object에 vtable도 없고 가상 메서드도 없음
    • 대신 Object::tryCallMethod는 object->classObject()->tryCallMethod(object, ...) 로 위임
    • 따라서 Array 메서드를 제공하려면 그 메서드를 가진 Array용 클래스 자체 생성 필요
  • 결과적으로 intrinsic 기능 상당 부분이 구현 전역에 흩어져 있던 구조에서 makerootcontext.cpp 중심으로 이동
  • 긍정적인 결과로 평가한 이유는 객체의 native/intrinsic 함수에도 인라인 캐시가 그대로 적용되기 때문
  • 성능 효과는 4.55배 향상
    • 이 시점 성능은 CPython 3.10보다 5.2배 느림
    • Lua 5.4.7보다 11.7배 느림
    • QuickJS-ng 0.14.0보다 3.3배 느림
    • 시작점 대비 6.8배 빠름
    • Fil-C++의 손실 폭이 다른 인터프리터 대비 대체로 Fil-C 비용 수준까지 좁혀졌다고 평가

호출과 접근 경로 최적화

• 최적화 #7: 인자 전달 구조 개선

  • 변경 전 Zef 인터프리터는 함수 인자를 const std::optional<std::vector<Value>>& 로 전달
  • optional이 필요했던 이유는 일부 모서리 케이스에서 다음 둘을 구분해야 했기 때문
    • o.getter
    • o.function()
  • Zef에서는 대체로 둘 다 함수 호출이지만, 예외로 다음 코드 존재
    • o.NestedClass
    • o.NestedClass()
  • 첫 번째는 NestedClass 객체 자체 반환
  • 두 번째는 인스턴스 생성
  • 따라서 인자가 없는 함수 호출과 getter류 호출로서 인자 배열이 비어 있는 경우를 구분해야 함
  • 그러나 기존 구조는 비효율적
    • 호출자가 vector 할당
    • 피호출자가 그 벡터를 복사한 arguments scope를 다시 할당
  • 변경은 Arguments 타입 도입
    • 모양이 피호출자가 만들던 arguments scope와 정확히 동일
    • 이제 호출자가 직접 그 형태로 할당
  • Yolo-C++에서도 vector backing store malloc 제거로 할당 수 감소
  • Fil-C++에서는 std::optional 자체가 힙 할당
    • std::optional이 없어도 const std::vector<>& 전달 역시 할당
    • 스택 할당되는 것은 힙 할당된다고 명시
    • 호출자 쪽이 벡터를 미리 크기 지정하지 않아 여러 번 재할당하던 점도 언급
  • 변경의 상당 부분은 함수 시그니처를 Arguments* 로 교체하는 작업
  • 성능 효과는 1.33배 향상
    • 이 시점 성능은 CPython 3.10보다 3.9배 느림
    • Lua 5.4.7보다 8.8배 느림
    • QuickJS-ng 0.14.0보다 2.5배 느림
    • 시작점 대비 9.05배 빠름

• 최적화 #8: Getter 특수화

  • Zef는 Ruby와 유사하게 인스턴스 필드가 기본적으로 private
  • 예시 class Foo { my f fn (inF) f = inF }
    • 생성자에서 받은 값을 인스턴스에만 보이는 지역 변수 f 에 저장
  • 같은 타입 인스턴스라도 다른 객체의 f에는 접근할 수 없음
    • 예시 fn nope(o) o.f
    • println(Foo(42).nope(Foo(666)))
    • nope 안의 o.f는 o의 f에 접근하지 못함
  • 이유는 필드가 클래스 멤버의 스코프 체인에 나타나는 방식으로 작동하기 때문
    • o.f는 필드 읽기가 아니라 f라는 이름의 메서드 호출 요청
  • 그래서 다음 패턴이 자주 등장
    • my f
    • fn f f
    • 즉 지역 변수 f를 반환하는 이름 f의 메서드
  • 더 짧은 문법으로 readable f
    • my f와 fn f f의 축약형
  • 많은 메서드 호출이 실질적으로 getter 호출
  • 모든 getter가 AST를 평가하며 동작하는 것은 낭비
  • 최적화는 getter 특수화
    • 중심은 UserFunction
    • 새 Node::inferGetter 메서드로 함수 본문이 단순 getter인지 추론
  • 추론 규칙
    • Block::inferGetter 는 자신이 담은 것이 전부 getter로 추론 가능하면 getter로 추론
    • Get::inferGetter 는 자신을 getter로 추론하고 로드할 offset 반환
    • Context::tryGetFieldOffsets 는 getter가 실행될 렉시컬 스코프에 그 필드가 확실히 존재할 때만 비어 있지 않은 Offsets 반환
    • UserFunction 은 함수 본문이 getter로 추론 가능하면 알려진 offset에서 바로 읽기만 수행하는 특수 Function 서브클래스로 resolve
  • 성능 효과는 5.6% 향상
    • 이 시점 성능은 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에 대한 쓰기 아님을 확인해야 하며, 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: 해시테이블

  • 메서드 호출의 inline cache 미스가 발생하면 ClassObject::tryCallMethod와 ClassObject::TryCallMethodDirect를 따라 내려가야 했고, 두 경로 모두 크고 복잡
  • 기존 탐색 비용은 계층 깊이에 비례하는 O(hierarchy depth)
    • 계층의 각 클래스마다 호출이 멤버 함수로 해석되는지 확인하는 해시테이블 조회 수행
    • 계층의 각 클래스마다 호출이 중첩 클래스로 해석되는지 확인하는 해시테이블 조회도 수행
  • 새 변경으로 receiver class와 symbol을 키로 사용하는 전역 해시테이블 도입
    • 한 번의 조회로 callee 직접 반환
    • 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이 보수적으로 동작하도록 intrinsics 삽입
  • 이후 FilPizlonator 패스가 자체 escape analysis를 수행해 union 타입 지역 변수를 레지스터 할당 가능하게 만들려 시도
    • 다만 이 분석은 일반 LLVM의 SROA 분석만큼 완전하지 않음
  • 결과적으로 std::optional처럼 union을 포함한 클래스 전달이 Fil-C++에서 메모리 할당으로 이어지는 경우가 많음
  • 이번 변경은 hot path에서 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의 모든 built-in 함수는 1개 또는 2개의 인자를 받으며, 네이티브 구현에서는 이를 담기 위한 Arguments 객체 할당 불필요
  • setter도 항상 한 개의 인자를 받으며, setter 추론이 이뤄진 경우 specialized setter 구현 역시 Arguments 객체 없이 값 인자만 직접 받으면 충분
  • 이번 변경으로 ZeroArguments, OneArgument, TwoArguments 특수화 인자 타입 도입
    • callee가 필요로 하지 않는 경우 caller가 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배 빠름

Fil-C 병리 우회와 세부 특수화

• 최적화 #14: 개선된 Value slow path

  • 또 다른 Fil-C 병리 현상 우회로 큰 속도 향상 확보
  • 변경 전 Value의 out-of-line slow path는 Value의 멤버 함수였고, 암묵적인 const Value* 인자 필요
  • 이 구조에서는 caller가 Value를 스택에 할당해야 함
  • Fil-C++에서는 모든 스택 할당이 힙 할당
    • 따라서 slow path를 호출하는 코드는 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 특수화

  • inline cache는 원하는 함수로 호출을 잘 라우팅하지만 객체에 대해서만 동작
  • 비객체에서는 Binary<>, Unary<>, Value::callRMW<> fast path가 receiver가 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이므로 새 배열 할당 필요
  • 변경 전에는 실행 때마다 AST를 따라 내려가며 1, 2, 3을 매번 재귀 평가
  • 이번 변경은 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 slow path에도 적용
  • 성능 효과는 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배 속도 향상 확보
• 다만 이 방식은 sound하지 않고 suboptimal
  • sound하지 않은 이유는 기존 Fil-C++ GC 호출이 calloc 호출로 바뀌기 때문
  • 그 결과 메모리가 해제되지 않으며, 충분히 오래 실행되는 워크로드에서는 인터프리터가 메모리 고갈에 도달
  • ScriptBench1에서는 테스트 시간이 짧아 메모리 고갈 발생 없음
• suboptimal한 이유는 실제 GC 할당기가 glibc 2.35의 calloc보다 빠르기 때문
• 따라서 Yolo-C++ 포트에 실제 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배 빠름

원시 벤치마크 데이터

• 벤치마크 실행 시간 단위는 초
• 표에는 각 인터프리터별 nbody, splay, richards, deltablue, geomean 포함

• Python 3.10

  • nbody 0.0364
  • splay 0.8326
  • richards 0.0822
  • deltablue 0.1135
  • geomean 0.1296

• Lua 5.4.7

  • nbody 0.0142
  • splay 0.4393
  • richards 0.0217
  • deltablue 0.0832
  • geomean 0.0577

• QuickJS-ng 0.14.0

  • nbody 0.0214
  • splay 0.7090
  • richards 0.7193
  • deltablue 0.1585
  • geomean 0.2036

• Zef Baseline

  • nbody 2.9573
  • splay 13.0286
  • richards 1.9251
  • deltablue 5.9997
  • geomean 4.5927

• Zef Change #1: Direct Operators

  • nbody 2.1891
  • splay 12.0233
  • richards 1.6935
  • deltablue 5.2331
  • geomean 3.9076

• Zef Change #2: Direct RMWs

  • nbody 2.0130
  • splay 11.9987
  • richards 1.6367
  • deltablue 5.0994
  • geomean 3.7677

• Zef Change #3: Avoid IntObject

  • nbody 1.9922
  • splay 11.8824
  • richards 1.6220
  • deltablue 5.0646
  • geomean 3.7339

• Zef Change #4: Symbols

  • nbody 1.5782
  • splay 9.9577
  • richards 1.4116
  • deltablue 4.4593
  • geomean 3.1533

• Zef Change #5: Value Inline

  • nbody 1.4982
  • splay 9.7723
  • richards 1.3890
  • deltablue 4.3536
  • geomean 3.0671

• Zef Change #6: Object Model and Inline Caches

  • nbody 0.3884
  • splay 3.3609
  • richards 0.2321
  • deltablue 0.6805
  • geomean 0.6736

• Zef Change #7: Arguments

  • nbody 0.3160
  • splay 2.6890
  • richards 0.1653
  • deltablue 0.4738
  • geomean 0.5077

• Zef Change #8: Getters

  • nbody 0.2988
  • splay 2.6919
  • richards 0.1564
  • deltablue 0.4260
  • geomean 0.4809

• Zef Change #9: Setters

  • nbody 0.2850
  • splay 2.6690
  • richards 0.1514
  • deltablue 0.4072
  • geomean 0.4651

• Zef Change #10: callMethod inline

  • nbody 0.2533
  • splay 2.6711
  • richards 0.1513
  • deltablue 0.4032
  • geomean 0.4506

• Zef Change #11: Hashtable

  • nbody 0.1796
  • splay 2.6528
  • richards 0.1379
  • deltablue 0.3551
  • geomean 0.3906

• Zef Change #12: Avoid std::optional

  • nbody 0.1689
  • splay 2.6563
  • richards 0.1379
  • deltablue 0.3518
  • geomean 0.3839

• Zef Change #13: Specialized Arguments

  • nbody 0.1610
  • splay 2.5823
  • richards 0.1350
  • deltablue 0.3372
  • geomean 0.3707

• Zef Change #14: Improved Value Slow Paths

  • nbody 0.1348
  • splay 2.5062
  • richards 0.1241
  • deltablue 0.3076
  • geomean 0.3367

• Zef Change #15: Deduplicated DotSetRMW::evaluate

  • nbody 0.1342
  • splay 2.5047
  • richards 0.1256
  • deltablue 0.3079
  • geomean 0.3375

• Zef Change #16: Fast sqrt

  • nbody 0.1274
  • splay 2.5045
  • richards 0.1251
  • deltablue 0.3060
  • geomean 0.3322

• Zef Change #17: Fast toString

  • nbody 0.1282
  • splay 2.2664
  • richards 0.1275
  • deltablue 0.2964
  • geomean 0.3235

• Zef Change #18: Array Literal Specialization

  • nbody 0.1295
  • splay 1.6661
  • richards 0.1250
  • deltablue 0.2979
  • geomean 0.2992

• Zef Change #19: Value callOperator Optimization

  • nbody 0.1208
  • splay 1.6698
  • richards 0.1143
  • deltablue 0.2713
  • geomean 0.2810

• Zef Change #20: Better C++ Configuration

  • nbody 0.1186
  • splay 1.6521
  • richards 0.1127
  • deltablue 0.2635
  • geomean 0.2760

• Zef Change #21: No Asserts

  • nbody 0.1194
  • splay 1.6504
  • richards 0.1127
  • deltablue 0.2619
  • geomean 0.2759

• Zef in Yolo-C++

  • nbody 0.0233
  • splay 0.3992
  • richards 0.0309
  • deltablue 0.0784
  • geomean 0.0686

[GN⁺]

Hacker News 의견들

• 비슷한 맥락으로, Wren 인터프리터 성능을 다룬 이 페이지가 꽤 흥미로웠음
  Zef 글이 구현 기법 중심이라면, Wren 쪽은 언어 설계 자체가 성능에 어떻게 기여하는지도 보여준다고 느꼈음
  특히 Wren은 dynamic object shapes를 포기해서 copy-down inheritance가 가능해지고 메서드 조회가 훨씬 단순해진 점이 좋아 보였음
  개인적으로는 꽤 괜찮은 트레이드오프라고 봄. 클래스가 만들어진 뒤에 메서드를 덧붙여야 할 일이 실제로 얼마나 자주 있나 싶은 생각임

  • 인터프리터나 JIT 속도는 언어 설계가 엄청 크게 좌우한다고 봄
    동적 언어용으로 매우 최적화된 VM은 많지만, LuaJIT가 강한 이유는 Lua가 워낙 작고 최적화에 잘 맞는 언어이기 때문이라고 느낌
    최적화하기 까다로운 기능도 조금 있긴 하지만, 수가 적어서 공을 들일 만하다는 점이 큼
    반면 Python은 전혀 다르다고 느낌. 과장 조금 보태면 빠른 JIT 가능성을 최소화하도록 설계된 수준이고, 여러 겹의 동적성이 겹쳐 최적화가 정말 어려워 보임
    그렇게 오랜 기간 작업한 뒤에도 CPython 3.15 JIT가 x86_64에서 기본 인터프리터보다 약 5% 빠른 정도라는 점이 이를 잘 보여준다고 느낌
  • 이런 접근은 monkey patching이 관용적으로 받아들여지는 언어들, 특히 Ruby에서 늘 하는 일과 비슷하다고 봄
    물론 Ruby는 속도 최우선 성향으로 알려진 언어는 아니라는 점도 같이 떠오름
    반대로, 어떤 타입이 적용 가능한 함수 집합을 닫힌 형태로 가진다는 발상은 조금 의문스럽게 느껴지기도 함
    세상에는 임의 함수를 정의해 두고 첫 번째 인자 타입이 맞는 변수에 점 표기 메서드처럼 붙여 쓸 수 있는 언어가 꽤 있음
    예를 들면 Nim의 매크로, Scala의 implicit classes와 type classes, Kotlin의 extension functions, Rust의 traits 같은 방식임
  • 제 경험상 대체로 어떤 표현식에 정적 타입을 붙일 수 있으면 꽤 효율적으로 컴파일할 수 있음
    복잡한 동적 언어들은 여러 방식으로 그 가능성을 적극적으로 깨뜨리기 때문에 최적화가 어려워지는 편이라고 느낌
    돌이켜보면 꽤 당연한 이야기처럼 보임

• 변경 #5에서 #6으로 넘어가며 inline caches와 hidden-class object model이 대부분의 성능 향상을 만든다는 점이, 역사적으로 V8이나 JSC가 빨라진 방식과 정말 비슷하게 느껴졌음
  순진한 인터프리터가 죽는 지점은 결국 프로퍼티 접근의 동적 디스패치이고, 나머지는 비교적 rounding error에 가깝다는 인상임
  각 단계가 얼마나 기여했는지를 따로 볼 수 있게 정리된 점도 좋았음. 보통 성능 글은 최종 수치만 던지고 끝나는 경우가 많음

  • #6에서 특히 흥미로운 구현 디테일은, AST를 직접 걷는 인터프리터에서 inline caching을 어떻게 하느냐는 점이었음
    바이트코드 인터프리터에서는 바이트코드 스트림의 안정된 오프셋을 패치하면 되니 IC 재작성 위치가 자연스러움
    그런데 여기서는 캐시 위치가 AST 노드라서, @pizlonator가 constructCache<>를 통해 generic 노드 위에 specialized AST 노드를 in-place로 세우는 방식을 썼다는 점이 인상적이었음
    결국 AST 레벨의 self-modifying code처럼 보였음
    대신 이 방식은 mutable AST nodes를 요구해서, 서브트리 공유나 병렬 컴파일처럼 많은 컴파일러가 기대하는 immutable AST 가정과 충돌함
    단일 스레드 인터프리터라면 깔끔하지만, 같은 AST를 백그라운드 스레드에서 JIT 컴파일하는 동안 인터프리터가 노드를 바꾸는 상황이라면 문제가 될 것 같음
  • 전반적인 방향엔 동의하지만, 이건 어디까지나 특정 벤치마크 하나에 대한 결과라는 작은 단서는 있다고 봄
    제 생각엔 실제 현업 코드의 대부분을 잘 대변하진 않을 수도 있음
    그렇게 느낀 이유는 sqrt 최적화로 1.6% 개선이 나왔다는 대목 때문이었음
    그 정도 개선이 나오려면 애초에 벤치마크 시간이 1.6% 이상은 거기에 쓰이고 있어야 해서 꽤 놀라웠음
    git repo를 보니 실제로 nbody 시뮬레이션에서 그런 일이 벌어진 듯했음

• 저도 최근에 제 AST-walking interpreter 첫 버전을 공개한 직후라서 더 흥미롭게 읽었음
  제 목표는 인터프리터 언어를 만드는 데 무엇이 필요한지 기초 수준에서 이해하는 것이었음
  최적화 복잡성은 넣고 싶지 않았고, 그냥 제 Rust 코드를 스스로 이해할 수 있게 만드는 데 집중했음
  그런데 좋아하는 언어인 Rust를 썼다는 이유만으로도 성능이 꽤 잘 나와서 놀랐음
  게다가 Rust가 ownership과 lifetimes를 챙겨주니 garbage collector가 따로 필요 없다는 점도 보너스처럼 느껴졌음
  물론 지금은 closure 같은 부분에서 lifetime 지옥을 피하려고 clone에 꽤 보수적으로 의존하고 있지만, 그래도 속도와 메모리 프로파일은 충분히 괜찮다고 느낌
  단순하고 이해하기 쉬운 Rust 기반 tree-walking interpreter에 관심 있다면 제 인터프리터 gluonscript를 보면 됨

• 글이 정말 좋았음
  특히 Arguments 아크, 즉 #7에서 #13으로 가는 흐름이 제 경험과 아주 비슷하게 닿았음
  예전에 Rust로 async step evaluator를 만들면서, 평소엔 borrow가 이득을 줄 거라 믿고 Cow<'_, Input>에 깊게 들어간 적이 있었음
  마이크로벤치에서는 좋아 보였지만, 실제 워크로드에서는 Cow의 discriminant와 lifetime 관련 복잡성이 첫 await 이후 모든 combinator로 번졌고, 인라이닝이 크게 무너지면서 Cow를 쓴 이유 자체가 사라졌음
  결국 evaluator 경계에서 NoInput / OneInput / MultiInput(Vec)로 갈아탔는데, 보기엔 투박해도 결과적으로 여기의 ZeroArguments / OneArgument / TwoArguments 분리와 거의 같은 지점에 도달했음
  한 가지 계속 궁금한 점은, native 경로에서 arity specialization 위에 type specialization까지 쌓아봤는지 여부임
  예를 들어 binary 스타일로 가면 isInt 검사 자체를 없앨 수도 있을 것 같음
  제 추측으로는 코드 크기 계산이 안 맞았거나, 객체 쪽은 IC가 뜨거운 경로를 이미 충분히 먹어버려서 native fast path 영향이 크지 않았던 것 같기도 함
  어느 쪽인지 궁금했음

• 이건 정말 흥미롭고 잘된 작업이라고 느낌
  저도 비슷한 일을 해봤는데, 좀 더 함수형에 가까운 언어인 Scheme 쪽이었음
  여기서는 객체 최적화가 가장 큰 이득을 줬지만, 제 경우엔 closures 최적화가 제일 큰 승부처였음
  재미있게도 최적화 방식 자체는 꽤 비슷했음
  Scheme를 충분히 빠르게 만드는 답은 Three implementation models for scheme에 거의 다 들어 있다고 봄
  다만 이쪽은 어느 정도 컴파일 단계를 거치기 때문에 원래 AST를 그대로 인터프리팅하는 모델은 아니라는 차이가 있음

• 흥미로웠고 공유해줘서 고맙다는 느낌임
  저도 언젠가 이 주제를 자세히 파보고 싶다는 생각이 들었음
  그리고 Github 기준으로 repo가 99.7% HTML에 0.3% C++라는 점도 꽤 웃기고 인상적이었음
  인터프리터 크기가 정말 작다는 증거 같았음

  • 정적 생성한 사이트를 커밋해둬서 그렇게 보이는 것임
    브라우저용 코드를 생성하는 방식 때문에 사이트 쪽이 쓸데없이 커진 면이 있음
    그래도 인터프리터 자체는 정말 아주 작음

• 이 작업을 하면서 fil c 자체를 더 좋게 만들 만한 걸 배웠는지 궁금했음

  • 확실히 unions를 다루는 방식은 더 나은 해법이 필요하다는 걸 느꼈음
    그리고 value object의 메서드를 outline call로 처리하는 비용이 꽤 크다는 점도 배움

• Lua가 포함된 건 봤는데, LuaJIT도 같이 있었으면 좋겠다는 생각이 들었음

  • 제 예상으로는 LuaJIT가 Zef를 완전히 이길 것 같음
    아니, 그 정도 엔지니어링이 들어갔다는 점을 생각하면 오히려 그래야 한다는 기대임
    넣을 수 있었던 런타임은 많았지만 다 포함하진 않았음
    그리고 PUC Lua가 QuickJS나 Python보다 꽤 빠르다는 점도 상당히 인상적이었음

• Fil-C를 실제로 써본 경험이 어떤지, 실전에서 실질적 유용성이 있는지 궁금했음

  • 제가 Fil 본인이니 편향은 있음을 먼저 말해둠
    그래도 이 프로젝트에서는 꽤 실질적으로 도움이 됐음
    메모리 안전성 문제를 여러 개 결정론적으로 잡아줘서, 객체 모델 설계가 그렇지 않았을 때보다 훨씬 쉬워졌음
    또 정확한 GC가 붙은 C++은 정말 좋은 프로그래밍 모델처럼 느껴졌음
    일반 C++ 대비 생산성이 1.5배쯤 올라가는 기분이었고, 다른 GC 언어와 비교해도 1.2배쯤은 빠르게 개발되는 느낌이었음
    이유는 C++의 API 생태계가 풍부하고 lambdas, templates, class system이 매우 성숙했기 때문이라고 봄
    물론 여러 면에서 편향이 있다는 점도 인정함
    Fil-C++를 직접 만들었고, C++도 한 35년쯤 써왔음

• 글에서 언급된 YOLO-C/C++ 컴파일러가 뭔지 궁금했음
  검색해도 잘 안 나오고 chatgpt도 모르는 듯했음

  • Fil-C의 작성자이자 이 언어의 작성자가 Yolo-C/C++ 라는 표현으로 Fil-C가 없는 일반적인 C/C++을 뜻해 쓴 것임