현대 CPU의 OoO 실행과 분기 예측 등으로 인해 잘 만든 인터프리터를 JIT로 이기기가 왜 어려운지 설명하고, PostgreSQL의 간단한 SELECT 예제를 통해 null 체크 제거와 인라인화, computed goto 같은 최적화가 성능에 미치는 영향을 수치로 분석한다. 마지막에는 인터프리터의 가장 큰 병목을 다음 글에서 다루겠다고 예고한다.
Hi
지난번 PostgreSQL용 JIT 컴파일러에 관한 블로그 글 이후로, 아쉽게도 시간 부족으로 큰 진전은 없었지만 그래도 몇 가지는 진행했습니다(가장 큰 개선은 ARM64 포팅, 약간의 최적화, 더 많은 opcode 구현 등). 그런데 저는 종종 인터프리터를 정말로 어떻게 이길 수 있을지 스스로에게 묻곤 합니다… 그리고 “현대” CPU에서, 잘 작성된 인터프리터를 이기는 일은 많은 사람이 상상하는 것보다 훨씬 더 복잡합니다. 그래서 이를 설명하고 제가 성능을 개선하려는 계획(가능하다면 인터프리터 자체의 성능까지도 함께 개선해, 이 시도가 자승자박이 되게 만들 수도 있습니다)을 보여드리기 위해, 먼저 이런 이야기부터 해보겠습니다…
이 제목에 언급된 내용을 이미 잘 알고 계시다면, 다음 섹션으로 넘어가셔도 됩니다. 참고로, 아래 내용은 개념을 쉽게 전달하기 위해 의도적으로 단순화했습니다.
저는 이 블로그 글을 Zen 2+ CPU에서 작성하고 있습니다. 같은 메인보드, 같은 메모리를 유지한 채 Zen 3로 업그레이드하면, 단일 스레드 벤치마크에서 광고상 25%의 성능 향상이 있다고 합니다. 하지만 CPU 주파수는 겨우 2%만 높아집니다. 왜 이런 차이가 날까요?
90년대 펜티엄급 CPU 이후로, x86은 RISC CPU를 따라 슈퍼스칼라 시대에 들어섰습니다. 조건이 맞으면 사이클당 1개가 아니라 여러 명령을 동시에 실행할 수 있습니다. 다음과 같은 의사코드를 생각해 봅시다.
f(a, b, c, d):
X = a + b
Y = c + d
Z1 = 2 * X
Z2 = 2 * Y
Z = Z1 + Z2
return Z
X와 Y는 동시에 계산할 수 있습니다. CPU는 두 개의 정수 연산 유닛에서 이를 실행하고, 결과를 가져와 저장할 수 있습니다. 유일한 문제는 Z 계산입니다. 이 단계에 오기 전에 모든 것이 끝나야 하므로, CPU는 이전 결과를 기다리지 않고 더 진행할 수 없습니다. 그런데, 코드가 다음과 같이 작성되어 있다면 어떨까요?
f(a, b, c, d):
X = a + b
Z1 = 2 * X
Y = c + d
Z2 = 2 * Y
Z = Z1 + Z2
return Z
매 단계가 이전 단계의 완료를 기다려야 하므로 CPU가 크게 느려집니다. 그래서 슈퍼스칼라 CPU 구현에서 가장 중요한 기술이 등장합니다: Out-of-Order(OoO) 실행입니다. CPU는 명령을 가져온 뒤 여러 명령 큐에 디스패치하고, 의존성을 해소해 Z1을 계산하기 전에 Y를 먼저 계산하여 결과를 더 빨리 준비합니다. CPU가 대기하는 시간이 줄어 전체가 더 빨라지는 것입니다. 하지만, 안타깝게도 다음 함수에서는 어떻게 될까요?
f(a, b, c, d):
X = a + b
Y = c + d
if X > Y:
Z = b + d
else:
Z = a + c
return Z
CPU는 X와 Y를 기다렸다가 어느 Z를 계산할지 결정해야 할까요? 여기서 가장 큰 요령이 등장합니다. CPU는 일단 운에 맡기고 뭔가를 계산해봅니다. 이렇게 하면, 추측이 맞으면 많은 시간을 절약할 수 있고, 틀렸으면 잘못된 결과를 버린 다음 올바른 계산을 다시 합니다. 이것이 바로 분기 예측이며, 이는 많은 재미있는 보안 이슈의 근원이었습니다(안녕, 멜트다운). 하지만 성능 이점이 너무 커서 이를 비활성화하는 선택지는 사실상 없습니다.
대부분의 인터프리터는 AST 등에서 직접 실행하지 않고, opcode를 사용하는 중간 표현 위에서 동작합니다. 그래서 다음과 같은 메인 루프를 사용할 수 있습니다.
step = steps[0]
while 1:
switch step.opcode:
case A:
// code for opcode A
case B:
// code for opcode B
case C:
// code for opcode C
...
step++
많은, 아주 많은 인터프리터가 이렇게 작성되어 왔습니다. 하지만 최소한 이런 식으로 컴파일될 때는 끔찍한 단점이 있습니다. 단일 시작점에서 분기가 사방으로 뻗어나갑니다(최적화 컴파일러 대부분은 디스패치를 최적화하기 위해 점프 테이블을 생성하겠지만, 여전히 같은 지점에서 점프합니다). CPU는 올바른 점프를 예측하기 어려워 많은 성능을 잃습니다. 만약 인터프리터를 작성하는 유일한 방법이 이것뿐이라면, 코드를 이어 붙여 함수 형태로 생성하는 것만으로도 시간을 많이 절약할 수 있어, 아마 10% 이상의 성능 향상이 가능할 것입니다. 파이썬을 보면, 이 switch를 제거하는 것만으로 인터프리터가 15~20% 빨라졌습니다. PostgreSQL을 포함한 많은 프로젝트가 “computed goto”라 불리는 동일한 기법을 사용합니다. 1차 패스로 각 step에 “label” 대상 주소를 채워 넣고 나면, 실행은 다음과 같습니다.
step = steps[0]
goto step->label;
OPCODE_A:
// code for opcode A
step++; goto step->label;
OPCODE_B:
// code for opcode B
step++; goto step->label;
OPCODE_C:
// code for opcode C
step++; goto step->label;
...
짧은 연산 시퀀스를 루프에서 실행할 때 점프가 훨씬 더 예측 가능해져 분기 예측기의 일이 쉬워지고, 그 결과 인터프리터의 속도가 향상됩니다.
이제 현대 CPU의 기본 개념과 이들이 도달한 무시무시한 수준의 최적화를 아주 간단히 이해했으니, PostgreSQL 인터프리터와 성능으로 맞붙는 이야기를 해봅시다.
튜플 디폼(디스크상의 구조를 코드에서 사용하는 C 구조로 바꾸는 과정) 최적화는 여기서 다루지 않겠습니다. 제 컴파일러에 이를 구현하게 되면, 그때 별도의 블로그 글에서 이야기하겠습니다.
아시다시피, PostgreSQL은 연산자 오버로딩을 갖춘 매우 완전한 타입 시스템을 가지고 있습니다. 이렇게 단순해 보이는 쿼리조차도 결국에는 비교를 수행하는 엄격(strict) 함수 int4eq 호출로 귀결됩니다.
#define PG_GETARG_DATUM(n) (fcinfo->args[n].value)
#define PG_GETARG_INT32(n) DatumGetInt32(PG_GETARG_DATUM(n))
static inline int32
DatumGetInt32(Datum X)
{
return (int32) X;..
}
Datum
int4eq(PG_FUNCTION_ARGS)
{
int32 arg1 = PG_GETARG_INT32(0);
int32 arg2 = PG_GETARG_INT32(1);
PG_RETURN_BOOL(arg1 == arg2);
}
이 함수는 strict이므로, PostgreSQL은 인자가 null이 아닌지 확인해야 합니다. 그렇지 않으면 함수를 호출하지 않고 결과는 null이 됩니다.
제목에 있는 아주 기본적인 쿼리를 실행하면, PostgreSQL은 다음과 같은 opcode들을 가집니다.
EEOP_SCAN_FETCHSOME
EEOP_SCAN_VAR
EEOP_FUNCEXPR_STRICT_2
EEOP_QUAL
EEOP_DONE_RETURN
EEOP_FUNCEXPR_STRICT_2는 null 검사를 수행한 다음 함수를 호출합니다.
모든 opcode를 실제 C 코드로 풀어보면 다음과 같습니다.
// SCAN_FETCHSOME
CheckOpSlotCompatibility(op, scanslot);
slot_getsomeattrs(scanslot, op->d.fetch.last_var);
op++; goto op->code;
// SCAN_VAR
int attnum = op->d.var.attnum;
/* See EEOP_INNER_VAR comments */
Assert(attnum >= 0 && attnum < scanslot->tts_nvalid);
*op->resvalue = scanslot->tts_values[attnum];
*op->resnull = scanslot->tts_isnull[attnum];
op++; goto op->code;
// FUNCEXPR_STRICT_2
FunctionCallInfo fcinfo = op->d.func.fcinfo_data;
NullableDatum *args = fcinfo->args;
Assert(op->d.func.nargs == 2);
/* strict function, so check for NULL args */
if (args[0].isnull || args[1].isnull)
*op->resnull = true;
else
{
Datum d;
fcinfo->isnull = false;
d = op->d.func.fn_addr(fcinfo);
*op->resvalue = d;
*op->resnull = fcinfo->isnull;
}
op++; goto op->code;
// QUAL
/* simplified version of BOOL_AND_STEP for use by ExecQual() */
/* If argument (also result) is false or null ... */
if (*op->resnull ||
!DatumGetBool(*op->resvalue))
{
/* ... bail out early, returning FALSE */
*op->resnull = false;
*op->resvalue = BoolGetDatum(false);
EEO_JUMP(op->d.qualexpr.jumpdone);
}
/*
* Otherwise, leave the TRUE value in place, in case this is the
* last qual. Then, TRUE is the correct answer.
*/
op++; goto op->code;
// DONE_RETURN
*isnull = state->resnull;
return state->resvalue;
이미 한 가지 최적화를 찾을 수 있습니다. 왜 두 인자(상수 포함)에 대해 null 검사를 할까요? 상수는 쿼리 전체 실행 동안 변하지 않으므로, 매번 비교 연산이 ALU를 사용하고 그 비교 결과에 따라 분기합니다. 물론 CPU는 대응하는 분기 패턴을 파악해 다른 유닛을 계속 바쁘게 만들 수 있습니다.
그렇다면 이런 무의미한 비교의 실제 비용은 얼마일까요? 이를 알아보기 위해, 저는 PostgreSQL 인스턴스를 일부러 망가뜨려 모든 FUNCEXPR_STRICT에서 한 쪽 인자만 검사하도록 바꾸고, 또 하나는 STRICT 검사를 아예 하지 않도록 바꿨습니다(집에서는 절대 따라 하지 마세요!). 1억 행 테이블에 인덱스 없이 단순한 SELECT * FROM demo WHERE a = 42를 10번 실행했을 때, 두 경우의 perf 결과는 다음과 같습니다.
// non-broken PostgreSQL, the query took about 124ms per run
Performance counter stats for process id '1757113':
1,175.93 msec task-clock:u # 0.133 CPUs utilized
0 context-switches:u # 0.000 /sec
0 cpu-migrations:u # 0.000 /sec
80 page-faults:u # 68.031 /sec
13,377,719,062 instructions:u # 2.92 insn per cycle
# 0.01 stalled cycles per insn
4,583,676,400 cycles:u # 3.898 GHz
87,108,713 stalled-cycles-frontend:u # 1.90% frontend cycles idle
2,322,262,677 branches:u # 1.975 G/sec
1,577,035 branch-misses:u # 0.07% of all branches
// only 1 argument checked, the query took about 117ms per run
Performance counter stats for process id '1760731':
1,137.86 msec task-clock:u # 0.137 CPUs utilized
0 context-switches:u # 0.000 /sec
0 cpu-migrations:u # 0.000 /sec
480 page-faults:u # 421.845 /sec
13,238,656,204 instructions:u # 2.99 insn per cycle
# 0.01 stalled cycles per insn
4,429,234,344 cycles:u # 3.893 GHz
80,398,623 stalled-cycles-frontend:u # 1.82% frontend cycles idle
2,277,385,482 branches:u # 2.001 G/sec
1,513,041 branch-misses:u # 0.07% of all branches
// broken PostgreSQL, the query took about 115ms per run
Performance counter stats for process id '1758298':
1,134.46 msec task-clock:u # 0.132 CPUs utilized
0 context-switches:u # 0.000 /sec
0 cpu-migrations:u # 0.000 /sec
484 page-faults:u # 426.634 /sec
13,199,914,639 instructions:u # 2.99 insn per cycle
# 0.01 stalled cycles per insn
4,416,014,805 cycles:u # 3.893 GHz
80,840,330 stalled-cycles-frontend:u # 1.83% frontend cycles idle
2,248,257,937 branches:u # 1.982 G/sec
1,497,270 branch-misses:u # 0.07% of all branches
세기의 최적화는 아니더라도, 구현 비용이 크지 않으니… 왜 안 하겠습니까? (곧 pgsql-hackers에 패치를 보낼 예정입니다)
하지만 더 나은 최적화는 인라인에 올인하는 것입니다. 사실, int4eq 코드로 점프(이 또한 CPU가 크게 최적화하긴 합니다)하는 대신, 꽤 흔한 이 연산을 위한 특수 opcode를 둘 수 있습니다.
// Code of the opcodes unrolled, merged back and hand-optimized
// SCAN_FETCHSOME
CheckOpSlotCompatibility(op, scanslot);
slot_getsomeattrs(scanslot, op->d.fetch.last_var);
op++;
// SCAN_VAR
int attnum = op->d.var.attnum;
/* See EEOP_INNER_VAR comments */
Assert(attnum >= 0 && attnum < scanslot->tts_nvalid);
*op->resvalue = scanslot->tts_values[attnum];
*op->resnull = scanslot->tts_isnull[attnum];
op++;
// FUNCEXPR_STRICT_INT4EQ
FunctionCallInfo fcinfo = op->d.func.fcinfo_data;
NullableDatum *args = fcinfo->args;
/* strict function, so check for NULL args */
if (args[0].isnull || args[1].isnull)
*op->resnull = true;
else
{
*op->resvalue = ((int32) args[0].value == (int32) args[1].value);
*op->resnull = false;
}
op++;
// QUAL
/* simplified version of BOOL_AND_STEP for use by ExecQual() */
/* If argument (also result) is false or null ... */
if (*op->resnull ||
!DatumGetBool(*op->resvalue))
{
/* ... bail out early, returning FALSE */
*op->resnull = false;
*op->resvalue = BoolGetDatum(false);
EEO_JUMP(op->d.qualexpr.jumpdone);
}
/*
* Otherwise, leave the TRUE value in place, in case this is the
* last qual. Then, TRUE is the correct answer.
*/
op++;
// DONE_RETURN
*isnull = state->resnull;
return state->resvalue;
이 변경만으로도(두 번의 null 검사는 유지했기에 아직도 최적화 여지가 있음) 다음과 같은 perf 결과를 얻었습니다.
// broken PostgreSQL, the query took about 114ms per run
1,125.33 msec task-clock:u # 0.143 CPUs utilized
0 context-switches:u # 0.000 /sec
0 cpu-migrations:u # 0.000 /sec
456 page-faults:u # 405.215 /sec
12,941,745,741 instructions:u # 3.01 insn per cycle
# 0.01 stalled cycles per insn (71.33%)
4,305,023,693 cycles:u # 3.826 GHz (71.38%)
85,985,959 stalled-cycles-frontend:u # 2.00% frontend cycles idle (71.65%)
2,211,080,124 branches:u # 1.965 G/sec (71.71%)
1,596,208 branch-misses:u # 0.07% of all branches (71.27%)
자, 결과를 정리해 봅시다.
PostgreSQL Unpatched Only 1 NULL check No NULL check Two NULL checks, inlined int4eq Average time (ms)127 117 (-7.9%)115 (-9.5%)114 (-10.3%) Instructions 13,377,719,062 13,238,656,204 (-1.1%)13,199,914,639 (-1.4%)12,941,745,741 (-3.3%) Cycles 4,583,676,400 4,429,234,344 (-3.4%)4,416,014,805 (-3.7%)4,305,023,693 (-6.1%) Branches 2,322,262,677 2,277,385,482 (-2%)2,248,257,937 (-3.2%)2,211,080,124 (-4.8%)
세 가지 변경에 따른 성능 요약
가장 큰 변화는 당연히 int4eq 호출을 인라인한 데서 옵니다. 왜 이렇게 좋은 걸까요? 실행해야 할 명령 수를 크게 줄이고, 메모리에 저장된 주소로의 호출을 제거하기 때문입니다. 그리고 이것은 제 JIT 컴파일러에서도 할 수 있는 최적화일 뿐 아니라, 인터프리터에서도 동일한 이점을 얻을 수 있는 최적화입니다. 여기서 가장 큰 문제는 opcode의 개수를 (명시되지 않은) 한계 내에 유지해야 한다는 점입니다. opcode가 너무 많아지면 컴파일러의 일이 훨씬 더 나빠질 수 있습니다.
음. 처음에는 null 검사 제거를 인터프리터에 쉽게 구현할 수 없다고 생각했습니다. 제 컴파일러의 첫 시도는 확실히 올바르지 않았지만, 흥미로운 수치(위에서 본 것처럼 약 5%)를 보여줬고, 계속 진행하고 싶은 마음이 들었습니다. 그리고 깨달았습니다. 이를 인터프리터에 깔끔하게 구현하는 것이 제 JIT 컴파일러에 구현하는 것보다 훨씬 쉽다는 것을…
그 다음으로 흔한 케이스인 int4eq 호출을 최적화했는데, 음… 인터프리터에도 이를 위한 opcode를 추가할 수 있으니, JIT 컴파일러의 성능 이득은 인터프리터에 비해 미미해질 것입니다.
현대 CPU는 여기서 제 일을 쉽게 만들어주지 않습니다. 인터프리터의 비용 대부분이 분기 예측 및 실리콘에 구현된 다른 최적화로 상쇄됩니다. 그렇다면 모든 희망이 사라진 걸까요? 카피-패치 방식이라는 제 JIT에 가능한 방식의 한계 때문에 인터프리터의 승리를 선언해야 할까요?
PostgreSQL Unpatched Only 1 NULL check No NULL check Two NULL checks, inlined int4eqCopyjit, optimization in development Average time (ms)127 117 (-7.9%)115 (-9.5%)114 (-10.3%)98 (-23%) Instructions 13,377,719,062 13,238,656,204 (-1,1%)13,199,914,639 (-1,4%)12,941,745,741 (-3,3%)12,013,081,667 (-11%) Cycles 4,583,676,400 4,429,234,344 (-3,4%)4,416,014,805 (-3,7%)4,305,023,693 (-6,1%)3,701,112,703 (-20%) Branches 2,322,262,677 2,277,385,482 (-2%)2,248,257,937 (-3,2%)2,211,080,124 (-4,8%)2,028,224,528 (-13%)
보시다시피, 재미있어질 것 같습니다!
물론 희망이 사라진 건 아닙니다. 다음 글에서 가장 큰 인터프리터 병목에 대해 이야기하겠습니다!
PS: 도움은 언제나 환영입니다. 작년에 이 작업에 업무 시간 중 일부를 쓸 수 있었지만, 그 후로 이직을 하면서 이 일에 시간을 내기가 쉽지 않았습니다. 또한 이 작업을 계속하고 향후 PostgreSQL 컨퍼런스에서 발표하기 위해 스폰서를 찾아봤지만 아쉽게도 성과가 없었습니다 :/
이 프로젝트에 어떤 형태로든 도움을 주고 싶으시다면 언제든지 연락 주세요(코드 기여, 스폰서십, 용역, 채용 제안 등 눈치 챙김). 지금껏 혼자 해오다 보니 많은 것들이 낙서 같은 메모로 남아 있고, 일상 속 무료한 시간에 머릿속으로 코드와 아이디어를 벤치마크해 보곤 하지만, 실제로 테스트해 보는 것이 훨씬 더 좋습니다. 곧 여행 일정이 있어 내년이 오기 전에 다음 편을 공개할 수 있기를 바라고 있습니다. 제 경험이 예상만큼 성공적으로 진행되어 흥미로운 결과를 보여드리길 바랍니다.