트리 순회와 바이트코드

같은 AST를 실행하는 방법은 크게 둘이다. 트리를 재귀적으로 순회하며 노드마다 값을 계산하거나, 트리를 한 번 훑어 바이트코드로 바꿔 놓고 평평한 루프로 돌리거나.

파싱까지는 완전히 같다. 갈라지는 것은 AST를 손에 쥔 다음부터다.

소스 → 렉서 → 파서 → AST ─┬─ 트리 순회        : AST를 그대로 재귀 순회
                          └─ 컴파일 → VM      : AST → 바이트코드 → 루프

트리 순회

노드 타입으로 분기해 자식을 재귀 호출하고 결과를 합친다.

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    case *ast.Program:
        return evalProgram(node, env)
    case *ast.ExpressionStatement:
        return Eval(node.Expression, env)
    case *ast.IntegerLiteral:
        return &object.Integer{Value: node.Value}
    case *ast.Identifier:
        return evalIdentifier(node, env)
    // ...
    }
}

컴파일 단계가 없다. 파싱이 끝나면 바로 실행할 수 있고, 구현이 언어의 의미 정의를 거의 그대로 옮긴 모양이라 읽기 쉽다.

변수는 환경에서 이름으로 찾는다. 스코프마다 해시맵을 하나 두고, 없으면 바깥 환경으로 올라간다.

type Environment struct {
    store map[string]Object
    outer *Environment
}

func (e *Environment) Get(name string) (Object, bool) {
    obj, ok := e.store[name]
    if !ok && e.outer != nil {
        obj, ok = e.outer.Get(name)      // 바깥으로 올라간다
    }
    return obj, ok
}

함수를 호출할 때마다 새 환경을 만들어야 하므로 호출마다 맵이 하나씩 생긴다.

바이트코드

AST를 한 번 훑어 명령어 열로 바꾼 뒤, 그 열을 순회하는 루프를 돈다.

for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
    vm.currentFrame().ip++
    ip = vm.currentFrame().ip
    ins = vm.currentFrame().Instructions()
    op = code.Opcode(ins[ip])

    switch op {
    case code.OpConstant:
        constIndex := code.ReadUint16(ins[ip+1:])
        vm.currentFrame().ip += 2
        vm.push(vm.constants[constIndex])
    // ...
    }
}

여기서도 switch를 돌지만 성격이 다르다. 트리 순회의 switch는 재귀 호출로 내려갔다 올라오는 구조인 반면, 이쪽은 평평한 배열을 앞으로 훑는다.

변수 접근이 결정적으로 다르다. 컴파일 시점에 이름을 슬롯 번호로 바꿔 두므로, 실행 중에는 배열 인덱스 한 번이다.

case code.OpGetLocal:
    localIndex := code.ReadUint8(ins[ip+1:])
    vm.currentFrame().ip += 1
    frame := vm.currentFrame()
    vm.push(vm.stack[frame.basePointer+int(localIndex)])

이름 조회가 컴파일 시점으로 옮겨간 것이다. 해시도, 문자열 비교도, 바깥 환경 추적도 실행 중에는 없다.

실측

같은 언어를 두 방식으로 구현한 코드에서 같은 프로그램을 돌려 비교할 수 있다. 재귀 피보나치 fib(35), Go 1.26.2, Apple A18 Pro 기준이다.

engine=eval  duration=9.884s
engine=eval  duration=9.991s
engine=eval  duration=9.990s

engine=vm    duration=3.443s
engine=vm    duration=3.421s
engine=vm    duration=3.441s

약 2.9배 차이다. 컴파일 시간은 제외한 순수 실행 시간이고, 편차는 1% 안쪽이다.

fib(30)으로 할당량을 재면 차이가 어디서 오는지 드러난다. 이 계산은 함수 호출이 정확히 2,692,537번 일어난다.

	트리 순회	바이트코드
실행 시간	909 ms	316 ms
총 할당 횟수	24,551,553	6,731,854
총 할당 바이트	1,110 MB	99 MB
호출당 할당	9.12회	2.50회
호출당 바이트	412 B	37 B

할당 횟수는 3.6배, 할당 바이트는 11배 차이다. 시간 차이(2.9배)보다 훨씬 크다.

가장 큰 몫이 환경이다. 트리 순회는 함수 호출마다 NewEnclosedEnvironment로 해시맵을 새로 만든다. 맵 하나가 그 자체로 여러 번의 할당이고, 인자를 넣을 때마다 또 든다. 바이트코드 쪽은 이미 잡아 둔 스택에 base pointer만 옮긴다. 호출 프레임을 만드는 비용이 맵 생성에서 정수 하나 갱신으로 바뀐 것이다.

프로파일에도 그대로 나타난다.

트리 순회                              바이트코드
─────────────────────                  ─────────────────────
extendFunctionEnv     6.25%            NewFrame          10.34%
Environment.Set       5.21%            currentFrame      13.79%
Environment.Get       3.12%            push               6.90%
maps.getWithoutKey…   3.12%

트리 순회 쪽에는 해시맵 조회(maps.getWithoutKeySmallFastStr)가 프로파일에 올라오지만 바이트코드 쪽에는 아예 없다.

호출당 할당 412 B 대 37 B라는 숫자가 왜 이 프로그램에서 2.9배가 나왔는지를 설명하므로, 프로그램이 달라지면 비율도 달라진다. 위 숫자는 함수 호출이 지배적인 재귀 프로그램 기준이고, 호출이 적고 루프가 긴 프로그램이면 환경 생성 비용이 줄어 격차가 좁아진다.

GC 때문이 아니다

할당이 많으면 GC 탓이라고 생각하기 쉽다. GC를 꺼 보면 그렇지 않다.

GOGC=100 (기본)    eval  9.78s / 9.63s     vm  3.48s / 3.48s
GOGC=off           eval 10.21s / 10.26s    vm  3.40s / 3.36s

GC를 껐는데 트리 순회가 오히려 조금 느려졌다. 힙이 계속 커지면서 지역성이 나빠지기 때문이다. 즉 비용은 수집이 아니라 할당 그 자체에 있다. 객체를 하나 만들 때마다 드는 mallocgc 비용이 누적된 것이고, 이건 GC 설정으로 없앨 수 없다.

노드 디스패치

환경 다음으로는 순회 구조 자체다. 트리 순회는 fib(x-1) + fib(x-2) 하나를 평가하려고 Eval → evalIfExpression → Eval → evalInfixExpression → Eval → applyFunction → …으로 Go 스택을 깊게 오르내린다. 노드마다 타입 스위치를 다시 돌고, 인터페이스 값을 다시 언박싱한다.

바이트코드는 그 구조가 컴파일 시점에 이미 평평해졌다. 조건 분기는 OpJumpNotTruthy와 오프셋으로 바뀌어 있고, VM은 명령어 포인터를 옮길 뿐이다. AST를 매번 다시 해석하지 않는 것이 이 방식의 정의다.

그래도 명령어 하나마다 드는 디스패치 비용은 남는다. 2.9배는 실행 모델을 바꿔 얻은 것이고, 그 위의 차수는 특수화와 JIT에서 온다.

트리 순회가 나은 경우

느리다고 쓸모없는 것은 아니다.

• 구현이 짧고 명확하다. 컴파일러와 VM을 따로 만들 필요가 없다. 언어 의미를 그대로 코드로 옮긴 형태라 새 문법을 붙이기 쉽다.
• 한 번만 실행되는 코드에는 컴파일이 손해다. 설정 파일 평가식, 템플릿, 규칙 엔진처럼 짧은 코드를 한 번 돌리는 용도라면 컴파일 시간이 실행 시간보다 클 수 있다.
• AST가 그대로 남아 있다. 소스 위치, 노드 구조를 실행 중에 참조할 수 있어 오류 메시지와 디버깅이 유리하다. 바이트코드는 위치 정보를 별도 테이블로 유지해야 한다.
• 프로토타입에 적합하다. 실제로 언어를 만들 때 트리 순회로 의미를 먼저 확정하고 나중에 바이트코드로 옮기는 순서가 흔하다.

Ruby는 1.8까지 트리 순회였다가 1.9에서 YARV 바이트코드 VM으로 바꿨고, CPython은 처음부터 컴파일한다. 반대로 많은 DSL과 설정 언어, 정규식 이외의 규칙 평가기는 지금도 트리 순회다.

---

참고

• opcode
• 중간언어
• 인라인 캐싱과 특수화
• 클로저와 셀
• Python VM
• pprof
• https://craftinginterpreters.com/a-virtual-machine.html
• https://interpreterbook.com/
• https://compilerbook.com/