바이트코드 인터프리터의 거대한 스위치 디스패치에서 벗어나, 스레드형 디스패치와 특수화된 꼬리 호출 규약으로 성능을 개선한 이야기.
20분 읽기
7시간 전
바이트코드 인터프리터에 관한 실화
전체 크기 이미지를 보려면 Enter를 누르거나 클릭하세요
작년, 유일한 Graal의 보유자인 Thomas가 우리에게 다음 과제를 가져왔다.
「 /goal make the GraalPy interpreter faster than CPython 」
Thomas가 무엇을 요청했는지 이해하려면 두 인터프리터가 무엇으로 만들어졌는지 알면 도움이 된다. GraalPy 인터프리터는 Java로 작성되었다. CPython은 C로 작성되었다. 따라서 실제 과제는 고수준 Java 프로그래밍 모델을 포기하지 않고 Java 인터프리터가 C 인터프리터를 앞지르게 만드는 것이었다.
좋은 소식은 컴파일러를 우리가 제어한다는 것이었다.
나쁜 소식도 컴파일러를 우리가 제어한다는 것이었다.
전체 스택을 소유하면 어려운 한계는 거의 없다. 변명도 거의 없다.
분기 예측기가 불만이라면, 그것은 우리의 문제였다.
레지스터 할당기가 불만이라면, 그것은 우리의 문제였다.
그래서 최적화하기 위험한 무언가를 찾기 시작했다.
가장 명백한 용의자는 인터프리터 디스패치 루프였다. 논의를 구체적으로 하기 위해 작은 프로그램부터 시작하자.
static int plus1(int x) {
return x + 1;
} 스택 기반 가상 머신에서는 이것이 다음과 같은 바이트코드 시퀀스로 컴파일될 수 있다.
iload_0
iconst_1
iadd
ireturn Java 바이트코드를 한 번도 본 적이 없더라도 명령어는 꽤 자명하다. 첫 번째 지역 변수(이 예에서는 메서드 매개변수)를 불러오고, 상수 1을 푸시하고, 두 값을 더한 뒤 결과를 반환한다.
이러한 바이트코드 인터프리터를 구현하는 자연스러운 방법 중 하나는 큰 디스패치 루프다.
while (true) {
int opcode = bytecodes[pc];
switch (opcode) {
case ILOAD_0:
stack[sp++] = locals[0];
pc++;
break;
case ICONST_1:
stack[sp++] = 1;
pc++;
break;
case IADD:
int b = stack[--sp];
int a = stack[--sp];
stack[sp++] = a + b;
pc++;
break;
case IRETURN:
return stack[--sp];
}
} 계속하기 전에, 이것이 바이트코드 인터프리터를 구현하는 유일한 방법은 아니라는 점을 인정할 만하다. 예를 들어 HotSpot의 템플릿 인터프리터는 매우 효율적인 것으로 유명하다. 거대한 switch 루프에 의존하는 대신 바이트코드를 실행하는 플랫폼별 네이티브 코드를 생성한다.
그 선택지는 강력하지만, 수작업으로 작성하거나 명시적으로 생성한 저수준 장치에 부담을 옮기기도 한다. 우리의 과제는 달랐다. 인터프리터를 Java 객체와 메서드로 표현한 채로 유지하면서, 컴파일러가 유사한 효율성의 일부를 자동으로 되찾기에 충분한 정보를 제공하는 것이었다.
실제 디스패치 루프는 당연히 이 장난감 예제보다 훨씬 컸으며, 수백 개의 바이트코드 핸들러가 있었다.
그럼에도 실행 패턴은 동일하다. 모든 바이트코드 핸들러는 결국 다음 opcode를 가져와 해당 핸들러로 점프하는 같은 디스패치 루프로 돌아온다.
이 구조에는 많은 장점이 있다. 잘 이해되어 있고, 유지보수가 쉬우며, 놀랄 만큼 효과적이다. 또한 상태를 축적하는 경향이 있다. 프로그램 카운터가 այնտեղ 있다. 피연산자 스택이 այնտեղ 있다. 지역 변수가 այնտեղ 있다. 프로파일링 정보가 այնտեղ 있다. 머지않아 인터프리터 상태의 모든 조각이 같은 컴파일 단위를 통해 흐르게 된다.
이 마지막 세부 사항은 결국 매우 중요해진다.
당장은 가장 뜨거운 실행 경로 중 하나의 한가운데에 놓인 거대한 스위치만 보였다.
당연히 성능 차이의 원인으로 그것을 지목했다.
첫 번째 가설은 분기 예측이었다.
종료하지 않는 각 바이트코드 핸들러의 끝에서 제어는 switch로 돌아간다. 인터프리터는 다음 opcode를 읽고 같은 디스패치 분기를 사용해 다음 핸들러를 선택한다. 따라서 plus1 예제의 모든 전이는 같은 기계어 분기를 통과한다.
현대 프로세서는 모든 분기가 해결될 때까지 얌전히 기다리지 않는다. 추측 실행한다. 프로세서는 분기가 어디로 갈지 예측하고, 분기가 실제로 완료되기 전 그 경로를 따라 실행을 시작한다.
예측이 맞으면 그 작업의 상당 부분은 사실상 공짜다. 예측이 틀리면 추측 작업은 버려지고 올바른 대상으로 실행을 다시 시작한다. 이상적으로는 프로세서가 iload_0 다음에는 iconst_1, iconst_1 다음에는 iadd, iadd 다음에는 ireturn이 온다는 것을 학습해야 한다.
안타깝게도 예측기는 바이트코드를 보지 않는다. 기계어 명령을 본다.
프로세서의 관점에서 이 모든 전이는 같은 디스패치 분기에서 시작한다.
직관을 만들기 위해 각 분기 명령이 표지판이라고 상상해 보자. 분기가 해결될 때마다 표지판은 방금 택한 목적지를 가리키도록 돌아간다. 다음에 실행이 그 표지판에 도달하면 프로세서는 현재 방향을 따라가며 추측한다. 이 단순한 모델에서는 공유 디스패치 표지판이 예제의 모든 전이를 잘못 예측한다.
실제 분기 예측기는 훨씬 더 풍부한 이력을 사용하지만, 분기가 실행될 때마다 예측기는 여전히 하나의 구체적 대상을 선택해 그 경로를 따라 추측 실행을 시작해야 한다.
이것이 스레드형 디스패치의 고전적인 동기다. 요령은 표지판을 복제하는 것이다.
전체 크기 이미지를 보려면 Enter를 누르거나 클릭하세요
바이트코드 시퀀스는 그대로지만, 각 핸들러는 서로 다른 기계어 코드 위치에 있는 디스패치 분기의 자체 복사본을 얻는다.
분명한 질문은 이러한 배치를 어떻게 생성하느냐이다. 다행히 재생 자체는 놀랄 만큼 간단하다.
우리는 이를 Truffle Bytecode DSL의 기능으로 제공한다. 디스패치 시퀀스는 특별한 처리를 위해 표시된다.
while (true) {
int opcode = bytecodes[pc];
switch (markThreadedSwitch(opcode)) {
}
} 컴파일러를 우리가 제어하므로, 그 표시는 후반 코드 생성 단계를 유발할 수 있다. 코드 생성 중에는 루프 헤더부터 switch를 위해 생성된 테이블 점프까지 디스패치 경로의 기계어 코드를 기록한다. 컴파일 마지막 단계에서 컴파일러는 각 인터프리터 역방향 간선을 그 정확한 기계어 바이트의 복사본으로 교체한다.
전체 크기 이미지를 보려면 Enter를 누르거나 클릭하세요
재최적화는 필요 없다. 새 레지스터 할당도 필요 없다.
그 결과 모든 레지스터, 메모리 피연산자, 주소 지정 모드는 원래 디스패치 시퀀스와 정확히 동일하게 유지된다. 중요한 차이는 분기 명령이 더는 모든 바이트코드 전이에서 공유되지 않는다는 점이다.
여전히 약간의 패칭이 필요하다. 복사된 영역을 벗어나는 분기, 메타데이터 참조, 그 밖의 관리 세부 사항은 조정해야 한다. 이 세부 사항들은 중요하지만 기본 발상은 바꾸지 않는다. 생성된 디스패치 경로를 각 역방향 간선에 복사하는 것이다.
예측 불가능한 하나의 디스패치 분기가 더 예측 가능한 여러 분기가 된다.
적어도 이론은 그랬다.
예상대로 스레드형 디스패치는 도움이 되었지만, 그 크기는 결코 맞는 느낌이 아니었다.
솔직히 분기 예측이 이야기의 전부라고는 한 번도 믿지 않았다.
그래서 컴파일러가 내보내는 중간 표현을 열어 보았다.
컴파일러 엔지니어에게 이는 대개 새 연구 프로젝트 대신 작고 국소적인 실수를 찾기를 바라는 시점이다.
다행히 그런 것이 하나 있었다.
공유 디스패치 루프 헤더가 놀랄 만큼 많은 레지스터 압박을 안고 있었다.
왜 이것이 중요한지 이해하려면, 가용 레지스터 수를 넘을 만큼 충분한 상태를 라이브로 유지하는 인터프리터를 생각해 보자. x86–64에서 이는 들리는 만큼 어렵지 않다. 컴퓨팅의 다른 영역에서 수십 년간 진보가 있었음에도, 우리 대부분은 여전히 범용 레지스터 16개인 기계에서 개발한다. Intel APX는 완화를 약속하지만, 우리의 경영 현황 차트를 생성하는 기계에는 아직 등장하지 않았다.
결국 일부 값은 메모리로 스필되어야 한다. 우리의 경우 스케줄링 휴리스틱은 인터프리터 상태를 공유 디스패치 루프 헤더로 끌어오는 경향이 있었다.
불행한 부분은 그 상태 중 다수가 모든 바이트코드 핸들러에 필요한 것은 아니라는 점이다. 소수의 바이트코드에만 관련된 인터프리터 상태도 모두가 실행하는 공유 디스패치 경로에서 레지스터를 두고 경쟁할 수 있었다. 핸들러가 로컬로 더 많은 레지스터를 필요로 할수록 공유 루프 헤더 주변에서 라이브인 값에 남는 좋은 선택지는 줄었다.
간단한 완화책은 더 적은 인터프리터 상태가 루프 헤더로 스케줄되도록 휴리스틱을 조정하는 것이었다.
이것이 레지스터 압박을 사라지게 하지는 않았다. 비용을 지불하는 위치를 바꿨다. 한 핸들러에 필요한 인터프리터 상태는 이상적으로 모든 바이트코드가 실행하는 공유 디스패치 경로가 아니라 그 핸들러에서 레지스터를 두고 경쟁해야 한다. 훨씬 더 나은 절충이다.
보통은 코드 크기 증가가 우려 사항일 것이다.
이 시점에 우리는 이미 모든 인터프리터 역방향 간선에 디스패치 루프를 복제하고 있었다. 몇 개의 명령을 더 걱정하는 것은 다소 학술적으로 느껴졌다.
최적화는 놀랄 만큼 잘 작동했다.
불행히도 바로 여기서 토끼굴로 빠졌다.
공유 디스패치 경로의 비용은 줄였지만, 컴파일러는 여전히 근본적으로 같은 거대한 프로그램을 추론하고 있었다.
거대한 switch는 거대한 컴파일 단위가 되었다. 거대한 컴파일 단위는 거대한 라이브 범위 문제가 되었다.
전체 크기 이미지를 보려면 Enter를 누르거나 클릭하세요
관련 없는 바이트코드 핸들러의 값들은 여전히 같은 제한된 레지스터 예산을 두고 경쟁했다. 인터프리터에서 모든 값이 동등하지는 않다. 드물게 사용하는 핸들러 로컬 임시값을 스필하는 것은 성가시다. 프로그램 카운터, 스택 포인터, 바이트코드 배열 또는 자주 접근하는 프레임 상태를 스필하면 거의 모든 바이트코드 전이에 메모리 트래픽을 추가할 수 있다.
레지스터 할당기는 종종 훌륭한 해법을 찾을 수 있지만, 큰 컴파일 단위의 최적화 공간을 합리적인 시간 안에 완전 탐색할 수는 없다.
따라서 더 많은 휴리스틱 결정을 내려야 하며, 휴리스틱 결정은 필연적으로 일부 성능을 놓친다.
레지스터 할당은 문제가 처음 분명해진 지점일 뿐이었다. 인터프리터를 하나의 거대한 본문으로 추론해야 하는 모든 최적화가 같은 형태의 영향을 받았다.
휴리스틱을 계속 조정하고 컴파일러에 새 묘기를 가르칠 수도 있었다.
아니면 더 불편한 질문을 할 수도 있었다.
애초에 왜 인터프리터 전체를 하나의 거대한 컴파일 단위로 최적화하고 있었을까?
문제를 거대한 컴파일 단위로 규정하자, 해법도 똑같이 자명해 보였다.
나눈다.
결국 컴파일러는 이미 여러 메서드를 독립적으로 컴파일하는 법을 안다. 왜 인터프리터 전체를 하나의 거대한 최적화 문제로 밀어 넣어야 하는가?
실제로 정확히 그렇게 하는 놀랄 만큼 간단한 방법이 있다. 각 바이트코드 핸들러를 자체 메서드로 만들면 된다.
@DontInline
static void iload0(...) { ... } @DontInline
static void iconst1(...) { ... }
@DontInline
static void iadd(...) { ... }
이제 모든 핸들러는 독립적으로 컴파일된다. 거대한 컴파일 단위가 사라진다. 거대한 라이브 범위 문제도 사라진다. 레지스터 할당기는 한 번에 하나의 바이트코드 핸들러에 집중할 수 있다.
문제는 사라졌다. 안타깝게도 성능 대부분도 사라졌다.
문제는 컴파일 경계가 공짜가 아니라는 것이다.
인터프리터에는 전달할 상태가 상당히 많다. 바이트코드 스트림, 프로그램 카운터, 피연산자 스택, 스택 포인터, 프로파일링 정보, 예외 상태, 수년간 진화하며 축적된 여러 관리 정보가 있다.
하나의 컴파일 단위 안에서는 이 값들 중 다수가 가상 상태로 남을 수 있다. 컴파일러는 자유롭게 레지스터에 유지하고 적절하다고 판단하는 대로 이동할 수 있다.
메서드 경계를 넘으면 그 환상이 깨진다. 값은 호출 규약을 건너야 하며, 가상 상태는 구체화되어야 할 수 있다.
Java 같은 언어에서 원시 인터프리터 상태는 특히 까다롭다. 한 가지 선택지는 모든 것을 객체에 저장하고 핸들러에서 핸들러로 그 객체를 전달하는 것이다. 레지스터 할당기는 분명 더 작은 컴파일 단위를 좋아할 것이다.
메모리 하위 시스템은 그렇지 않다.
레지스터 할당 문제를 메모리 트래픽 문제로 바꾸게 된다. 우리가 정말 원한 것은 모순적으로 들리는 것이었다.
각 바이트코드 핸들러가 자체 컴파일 단위인 것처럼 독립적으로 컴파일되기를 원했다.
동시에 컴파일 경계가 전혀 존재하지 않는 것처럼 인터프리터 상태가 핸들러 사이를 흐르기를 원했다.
다시 말해 컴파일 단위 간 최적화를 원했다.
보통 이 말들은 같은 문장에 들어가지 않는다.
명백한 질문은 우리가 그토록 힘들게 되찾은 최적화 기회를 희생하지 않고 어떻게 인터프리터 상태를 컴파일 경계 너머로 옮기느냐였다.
Medium에 무료로 가입하여 이 작성자의 업데이트를 받으세요.
더 빠른 로그인을 위해 나를 기억하기
발상 자체가 완전히 새로운 것은 아니었다.
Project Valhalla는 이미 수년간 유사한 관찰을 탐구해 왔다. 프로그래머는 객체를 좋아하지만, 컴파일러는 종종 그 내용을 선호한다.
계속되는 예제를 보자.
class State {
int pc;
int sp;
} static void iadd(State state, int[] stack) {
int b = stack[state.sp--];
int a = stack[state.sp--];
stack[++state.sp] = a + b;
state.pc++;
} 인터프리터 작성자의 관점에서 이것은 정확히 그래야 한다. 인터프리터 상태를 한 바이트코드 핸들러에서 다음으로 전달하는 작고 변경 가능한 객체다. 하지만 컴파일러 관점에서 흥미로운 부분은 객체 자체가 드문 경우다. 흥미로운 부분은 객체가 담은 값이다.
개념적으로 컴파일러는 State state를 추론하는 대신 <pc, sp>를 추론하는 편을 훨씬 선호한다.
그래서 이 발상을 가져와 인터프리터 상태를 위해 더 발전시켰다. 인터프리터 객체를 컴파일 경계 너머로 전달하는 대신, 선택한 필드를 값의 튜플로 확장한다. 기존 핸들러 인수와 함께 이는 컴파일러가 실제로 최적화하고자 하는 경계 튜플을 제공한다. 원래 프로그래밍 모델을 보존하기 위해 컴파일러는 원래 핸들러 시그니처를 바꾸지 않고 작은 스텁을 합성한다.
static void __stub_iadd(int pc, int sp, int[] stack) {
State state = new State(pc, sp);
iadd(state, stack);
} 인라이닝 후 이스케이프 분석은 재구성된 상태 객체를 최적화된 표현에서 제거하고 그 필드를 컴파일러 값으로 대체할 수 있는 경우가 많다. 전역적으로 그렇게 할 수 없을 때도, Graal의 제어 흐름 인식 부분 이스케이프 분석은 객체 구체화가 불필요한 빠른 경로에 같은 최적화를 적용할 수 있다.
인터프리터 상태를 튜플로 확장하는 것은 문제의 절반만 해결한다. 튜플은 다시 돌아와야 하지만, Java 메서드는 많은 입력을 받는 것보다 많은 출력을 반환하는 데 훨씬 덜 적합하다. 그래서 생성된 스텁은 튜플 반환값을 얻는다.
static <int, int, int[]> __stub_iadd(int pc, int sp, int[] stack) {
State state = new State(pc, sp);
iadd(state, stack);
return <state.pc, state.sp, stack>
}
처음 보면 튜플 객체를 구성해 반환하는 것처럼 보일 수 있다. 중요한 세부 사항은 갱신된 값이 도착하는 위치다. 생성된 호출 규약은 튜플을 들어올 때 사용한 바로 그 위치를 통해 반환한다. pc가 한 레지스터에서 스텁에 들어가면, 갱신된 pc'는 같은 레지스터로 돌아온다. 그러면 호출자 측 되쓰기는 기계적으로 삽입할 수 있다.
<pc', sp', stack> =
__stub_iadd(state.pc, state.sp, stack);
state.pc = pc';
state.sp = sp'; 인터프리터 상태는 이제 왕복 경로를 따른다.
전체 크기 이미지를 보려면 Enter를 누르거나 클릭하세요
상태 객체는 경계 양쪽에서 Java 프로그래밍 모델을 보존한다. 인터프리터 작성자는 객체, 필드, 일반적인 메서드 시그니처로 계속 작업하고, 컴파일러는 튜플을 사용해 선택한 상태를 고정된 레지스터 값으로 컴파일 간 전달한다.
이스케이프 분석도 호출자에서 독립적으로 실행되며, 원래 상태 객체를 가상으로 유지할 수 있다.
되쓰기 자체가 반드시 메모리 트래픽이 되는 것은 아니다. 두 상태 객체가 모두 가상으로 남는다면 갱신된 값은 전체 왕복 과정에서 컴파일러 값으로 계속 흐를 수 있다. 실제로 이는 두 컴파일이 하나가 될 필요 없이, 컴파일 경계 간 이스케이프 분석에서 원했던 것의 상당 부분을 제공한다.
레지스터 할당기는 또 다른 관점을 제공한다. 이전에는 디스패치 루프와 모든 바이트코드 핸들러가 하나의 거대한 레지스터 할당 문제를 이뤘다. 이제 호출자와 각 핸들러는 독립적으로 할당되며, 고정된 인수 위치가 이들을 하나의 연속 실행으로 연결한다.
이 인터페이스가 표현할 수 있는 것에는 여전히 한계가 있다. 원칙적으로는 모든 인터프리터 상태를 호출 경계 너머로 전달할 수 있다. 실제로는 각 핸들러의 로컬 작업을 위해 레지스터 예산 일부를 남겨야 한다. iadd처럼 단순한 바이트코드도 로컬 계산용 스크래치 레지스터가 필요하므로, 경계 튜플이 쓸모 있는 모든 레지스터를 차지할 수는 없다.
이전의 거대한 컴파일 단위에서는 선택되지 않은 값도 인라인된 핸들러 본문에 계속 보일 수 있었고 스칼라 대체를 통해 레지스터 상주 상태로 남을 수 있었다. 아웃라이닝 후 경계 튜플에 포함되지 않은 값은 더는 컴파일러 값으로 핸들러에 전달되지 않는다. 핸들러가 필요로 한다면, 일반적인 메모리 접근을 통해 구체화된 인터프리터 상태에서 값을 복구해야 한다.
대개 이것은 여전히 허용 가능하다. 가장 중요한 상태를 선택하고, 통계적으로 무시할 수 있는 상태는 핸들러가 실제로 필요할 때 메모리에서 복구하도록 남겨 둘 수 있다.
더 피할 수 없는 문제는 호출 자체다.
반환 주소 관리와 프레임 설정 같은 일반 호출 기계 동작 외에도, Native Image 같은 관리형 런타임은 호출을 위해 라이브 참조의 위치를 설명하는 세이프포인트 메타데이터를 내보내야 한다. 비호출 연산과 달리 호출은 컴파일러가 피호출자를 블랙박스로 취급하도록 강제한다. 특수 호출 규약이 호출 후 이를 복원하더라도, 레지스터에 있는 라이브 참조는 호출 중 훼손될 수 있다. 이는 참조에 GC가 볼 수 있는 보금자리가 필요함을 뜻하며, 흔히 스택 슬롯을 의미한다.
따라서 아웃라인된 호출 경계는 원래 레지스터 압박 문제의 일부를 스텁 호출 주변의 백업 및 복원 문제로 바꾼다.
하지만 호출은 그 비용에서 벗어날 실마리도 준다. 핸들러가 반환할 때 갱신된 튜플은 이미 다음 핸들러가 입력을 기대하는 위치를 차지한다. 이 시점에서 명백한 질문은 단지 호출을 더 저렴하게 만드는 방법이 아니다. 애초에 왜 호출자로 돌아가는가?
물론 답은 돌아가지 않는다는 것이다.
대신 각 핸들러 스텁이 디스패치를 직접 수행한다. 이 최적화는 흔히 꼬리 호출 스레딩이라고 한다. 바이트코드 구현을 실행한 뒤 다음 opcode를 가져오고 해당 핸들러 스텁을 찾아 직접 점프한다. 그러므로 바이트코드 스트림은 핸들러 인터페이스의 일급 부분이 되어 튜플을 <pc, sp, stack, bytecodes>로 확장한다.
생성된 코드는 이제 대략 다음과 같다.
static <int, int, int[], short[]>
__stub_iadd(int pc, int sp, int[] stack, short[] bytecodes) {
State state = new State(pc, sp);
iadd(state, stack);
int nextOpcode = bytecodes[state.pc];
jump handlerTable[nextOpcode]
with <state.pc, state.sp, stack, bytecodes>
} 특수화된 호출 규약이 이를 자연스럽게 만든다. 점프에는 재배치가 필요 없으며 현재 인터프리터 상태를 직접 전달한다.
멀리서 보면 핸들러는 LEGO 블록을 닮았다. 공유 튜플 인터페이스는 이들을 서로 직접 맞물리게 하는 돌기다.
전체 크기 이미지를 보려면 Enter를 누르거나 클릭하세요
디스패치 루프는 여전히 존재한다. 단지 모든 바이트코드에 초대받지 않을 뿐이다.
이제 이 모험 전체를 이끈 벤치마크로 돌아가야 할 것 같다.
되짚어 보면 첫 번째 용의자는 디스패치 루프의 분기 예측이었고, 이를 공략하기 위해 스위치를 스레드화했다. 스필은 나중에 나타났다. 스케줄링 휴리스틱을 조정해 스필 비용을 개별 핸들러로 밀어 넣었다. 결국 컴파일 단위 자체가 의심스러워졌다. 핸들러를 아웃라인한 뒤, 그 사이의 꼬리 호출을 스레드화했다.
최종적인 스레드형 꼬리 호출 구성은 출시된 GraalVM 25.1이다. 다른 구성은 관련 최적화를 선택적으로 비활성화한 같은 릴리스를 사용하므로 여정의 각 단계를 재구성할 수 있다. 모든 측정은 GraalPy의 JIT 컴파일을 비활성화한 인터프리터 전용이다.
위에서 논의한 인터프리터 최적화를 대표하는 산술 중심 벤치마크 몇 가지를 선택했다. 다른 워크로드는 게스트 언어 호출이나 속성 접근 같은 다른 비용이 지배적이므로, Python 런타임 자체의 구현에 더 크게 의존한다.
전체 크기 이미지를 보려면 Enter를 누르거나 클릭하세요
bytecode-benchmark는 이야기에 가장 명확하게 들어맞는다. 기준선은 CPython보다 낮게 시작한다. 스위치 스레딩은 이를 대략 동등한 수준으로 올리고, 스케줄링 조정은 이를 앞서게 한다.
그다음 우리는 욕심을 냈다. 한 핸들러에서 다음 핸들러로 실행을 직접 스레드화하기 위해 먼저 핸들러를 별도 컴파일 단위로 아웃라인했고, 경계 비용을 맞닥뜨렸다. 핸들러는 더 작아졌지만, 모든 호출은 관리용 메모리 접근에 둘러싸였다.
꼬리 호출 스레딩이 이 구조의 대가를 치르게 한다. 갱신된 튜플이 특수화된 호출 규약을 통해 한 핸들러에서 다음으로 직접 흐를 수 있게 되자, bytecode-benchmark는 CPython을 여유 있게 앞선다.
arith-binop과 sieve는 더 강한 기준선에서 시작하지만 같은 큰 흐름을 따른다.
전반적으로 벤치마크 결과는 단순히 스레딩이 이긴다는 것이 아니다. 더 구체적으로, 스레딩은 핸들러 경계를 충분히 저렴하게 만들어 아웃라이닝이 구조적으로 치명적이지 않게 한다.
그러면 더 흥미로운 질문이 남는다. 호출자와 핸들러 사이의 컴파일 경계가 더는 최적화 경계일 필요가 없다면, 한 핸들러와 다음 핸들러 사이의 경계는 어떨까?
스택 인터프리터에서 가장 자주 접근하는 값은 당연하게도 스택 최상단의 값이다. 전형적인 산술 바이트코드는 피연산자 스택에서 값을 불러오고, 연산을 수행한 뒤, 즉시 결과를 다시 푸시한다. 거대한 스위치에서 탈출한 뒤에도 이 스택 접근은 뜨거운 경로에 단단히 남아 있었다.
이는 새로운 관찰이 아니다. 스택 최상단 캐싱은 잘 확립된 인터프리터 최적화다. 문제는 일반 Java 코드로 표현 가능하게 하면서도 컴파일러에 최적화할 레지스터 수준 표현을 제공하는 방법이었다. 답은 다시 튜플이었다.
이 시점에 인터프리터 상태는 이미 레지스터 상주 값의 튜플로 핸들러 사이를 흐르고 있었다. 그 튜플을 프로그램 카운터나 스택 포인터 같은 기존 인터프리터 상태로 제한할 이유는 없었다. 최근 피연산자 스택 값도 담아 핸들러 경계를 넘어 레지스터에 유지할 수 있었다.
개념적으로 핸들러 튜플은 <pc, sp, stack, bytecodes>에서 <pc, sp, stack, bytecodes, tos1, tos2, tosDepth>로 커진다.
여기서 tosDepth는 현재 유효한 캐시 값이 몇 개인지 말한다. tosDepth가 1이면 tos1은 현재 스택 최상단이다. tosDepth가 2이면 tos2가 현재 스택 최상단이고, tos1은 그 아래 값이다.
이 시점에서 일부 독자는 레지스터를 세며 점점 불편해질 수 있다. 전통적인 호출 규약 아래라면 그들이 옳다. 조만간 추가 인수는 스택으로 스필되어 우리가 얻으려던 이점의 상당 부분을 되돌릴 것이다.
다행히 컴파일러를 우리가 제어한다.
플랫폼 ABI가 제공하는 여섯 개 정수 인수 레지스터에서 멈출 이유는 없다. 핸들러 스텁은 언어 경계를 절대 넘지 않으므로 훨씬 더 과감한 호출 규약을 사용하고, 인터프리터 상태를 위해 사실상 할당 가능한 레지스터 파일 전체를 사용할 수 있다. 튜플은 커질 수 있지만, 여전히 레지스터에 머무르도록 의도되어 있다.
계속되는 예제에서 iload_0은 지역 값을 tos1에 푸시한다. 그러면 iconst_1은 상수를 tos2에 푸시한다. 마지막으로 iadd는 tos2와 tos1을 소비하고 결과를 tos1에 남긴다.
전체 크기 이미지를 보려면 Enter를 누르거나 클릭하세요
중요한 부분은 단지 tos1과 tos2가 하나의 핸들러 내부에서 메모리 접근을 피한다는 것이 아니다. iload_0이 불러온 값은 피연산자 스택을 전혀 건드리지 않고 iconst_1을 지나 iadd까지 레지스터에 남는다.
스택 로드 없음.
스택 저장 없음.
적어도 당장은 그렇다.
물론 현실은 약간 덜 편리하다. 레지스터 두 개에는 스택 값 두 개만 담을 수 있다. 언젠가는 바이트코드 시퀀스가 세 번째 값, 네 번째 값을 푸시하고, 결국 캐시는 뒷받침 피연산자 스택으로 스필되어야 한다. 마찬가지로 어떤 핸들러는 피연산자 스택이 메모리에 있다고 기대하는 코드와 상호작용하기 전에 캐시 값을 구체화해야 할 수 있다. 그러므로 인터프리터는 상태의 일부로 tosDepth를 들고 다니며, 개별 핸들러가 값이 레지스터에 남아야 할 때와 뒷받침 스택 배열과 동기화해야 할 때를 결정하게 한다.
추가 도움 없이는 이제 모든 푸시와 팝이 가능한 모든 캐시 상태를 고려해야 한다. 푸시는 더는 단순히 stack[++sp] = value;가 아니다. 다음과 같이 보이기 시작한다.
switch (tosDepth) {
case 0:
tos1 = value;
tosDepth = 1;
break;
case 1:
tos2 = value;
tosDepth = 2;
break;
case 2:
stack[++sp] = tos1;
tos1 = tos2;
tos2 = value;
break;
} 팝도 반대로 같은 문제가 있다.
여러 절에 걸쳐 인터프리터 상태를 레지스터로 옮긴 뒤, 실수로 새로운 런타임 상태 기계를 도입했다.
tosDepth가 캐시된 스택의 모양만 설명한다면, 아예 튜플로 전달되지 않아야 할지도 모른다. 대신 런타임 상태 기계를 컴파일 시간 상태 기계로 바꾸고, 모든 바이트코드 실행에서 핸들러 생성으로 그 결정을 시간 뒤편으로 보낼 수 있다.
가장 평범한 방식으로 작성한 iadd를 보자.
static void iadd(...) {
int b = stack.pop();
int a = stack.pop();
stack.push(a + b);
state.pc++;
}
특수화가 없다면 각 팝과 푸시는 위의 푸시 예제처럼 런타임에 tosDepth를 검사해야 한다.
가능한 모든 캐시 상태를 추론해야 하는 단일 핸들러를 생성하는 대신, 여러 핸들러 변형을 생성한다. 각 변형에는 상수 tosDepth가 할당되며, 이는 일반적인 컴파일러 최적화가 push와 pop의 관련 없는 분기를 접어 제거하기에 충분하다. 그 분기가 사라진 뒤에는 갱신된 tosDepth도 흔히 결정적이 된다. 그러면 디스패치는 이 값을 사용해 다음 변형을 선택할 수 있다.
LEGO 예제로 돌아가, 이제 각 바이트코드 블록이 가능한 각 입력 tosDepth에 하나씩 여러 핸들러 변형을 묶는다고 상상해 보자. 이 복합 블록을 수직으로 쌓고, 한 핸들러가 생성한 tosDepth가 다음 핸들러로 향하는 경로를 선택한다.
전체 크기 이미지를 보려면 Enter를 누르거나 클릭하세요
상태 기계는 여전히 존재하지만, 더는 모든 핸들러 내부의 제어 흐름으로 존재하지 않는다. 핸들러 변형 사이의 전이에 존재한다.
이제 iadd<2> 특수화를 생각해 보자. 컴파일러는 두 피연산자가 이미 레지스터에 있음을 안다. 첫 번째 팝은 int b = tos2;가 된다. 두 번째 팝은 int a = tos1;가 된다. 그리고 푸시는 tos1 = a + b;가 된다.
상수 접기와 죽은 코드 제거 후 핸들러는 본질적으로 tos1 = tos1 + tos2;로 축소된다.
그 결과 tosDepth는 더는 튜플에서 런타임 슬롯을 차지할 필요가 없다.
전체 크기 이미지를 보려면 Enter를 누르거나 클릭하세요
열은 런타임 분기가 아니라 별도로 생성된 핸들러 변형이다. 강조된 경로는 iload_0<0>에서 iconst_1<1>로, 이어 iadd<2>와 ireturn<1>로 향한다. 각 핸들러의 출력 캐시 모양이 다음 변형을 결정하므로, 그 경로에는 런타임 tosDepth 값이나 이에 대한 테스트가 나타나지 않는다.
런타임 상태 전달을 명령 바이트와 교환했다. 여러 핸들러 변형은 런타임 값과 그 제어 흐름을 제거하여 실제 인터프리터 상태를 위한 레지스터를 하나 확보한다. 이전 절들은 인터프리터가 컴파일 경계를 넘어 상태를 효율적으로 전달하는 법을 가르쳤다. 이 절은 어떤 상태는 애초에 전달될 필요가 없었다는 것을 가르쳤다.
남은 우려는 레지스터 압박이다. 이 메커니즘이 잘 작동하려면 핸들러 인터페이스는 기존 인터프리터 상태 외에 캐시된 스택 최상단 값 두 개 이상을 전달할 충분한 레지스터가 필요하다. 이미 빠듯한 예산이다. GraalPy의 꼬리 호출 스레드형 핸들러는 현재 꽤 무거운 인수 튜플을 전달하며, 최상단 스택 값을 더 추가하면 레지스터가 고갈되어 다른 상태가 메모리로 밀려날 수 있다.
Python 스택은 원시값과 객체 참조를 모두 담을 수 있으므로 상황은 더 까다롭다. 이들은 특별한 처리, 또는 별도의 캐시된 스택 최상단 값까지 필요할 수 있으며, 그러면 인터페이스는 다시 넓어진다. 그 시점에서 이 최적화는 피하려 했던 바로 그 레지스터 압박 문제와 싸우기 시작한다.
우리는 이 레지스터 비용을 완화할 방법, 또는 최소한 핸들러 인터페이스가 지나치게 넓어질 때 인터프리터 작성자에게 경고할 방법을 계속 탐구하고 있다.
이 글은 거대한 스위치에서 시작했다.
거대한 스위치는 스필로 이어졌다.
스필은 거대한 컴파일 단위로 이어졌다.
그리고 거대한 컴파일 단위는 몇 개의 잘못 배치된 레지스터보다 훨씬 많은 것을 숨기고 있었다.
먼저 스위치를 스레드화하여 각 바이트코드 핸들러에 자체 디스패치 분기를 부여했다. 이어 핸들러 로컬 상태가 전체 디스패치 루프에 걸쳐서가 아니라 필요한 곳에서만 스필되도록 스케줄링을 조정했다. 마지막으로 핸들러를 별도 컴파일 단위로 아웃라인하고 특수화된 꼬리 호출 규약으로 연결했다. 인터프리터 상태는 고정된 레지스터 위치에 있는 값의 튜플로 이 컴파일 경계를 넘으므로, 핸들러는 별도 컴파일 단위로 남으면서도 그 경계가 최적화 경계가 되지 않는다.
스레드형 핸들러 구현은 GraalVM 25.1.3에 포함되어 출시되었으며 GraalPy에서 기본으로 활성화된다. 위에 제시한 인터프리터 전용 산술 중심 워크로드에서 이는 bytecode-benchmark를 CPython보다 낮은 수준에서 여유 있게 높은 수준으로 끌어올리고, arith-binop은 CPython의 약 세 배에 이른다.
이것이 모든 Python 워크로드를 세 배 빠르게 만드는 것은 아니다. 호출, 속성 접근, 그 밖의 런타임 연산은 GraalPy 구현의 다른 부분이 지배한다. 핸들러 인터페이스 내부에서도 레지스터는 유한한 자원으로 남는다. 더 많은 인터프리터 상태를 전달하면 결국 기존 값이 메모리로 밀려날 위험이 있다.
그 지점에서 다음 실험도 시작된다. 컴파일 경계가 더는 값이 최적화기에 보이는 상태로 남는 것을 막지 않는다면, 같은 인터페이스가 캐시된 피연산자 스택 값을 한 핸들러에서 다음으로 직접 전달할 수 있다. 메커니즘은 작동한다. 올바른 레지스터 예산을 찾는 일은 여전히 진행 중이다.
지금으로서는 거대한 스위치는 사라졌다.
다음 토끼굴이 나타날 때까지는.
