[cpython] gh-124951: base64 인코딩/디코딩 2~3배 속도 향상 — CPU 파이프라이닝 최적화

PR 링크: python/cpython#143262 상태: Merged | 변경: +134 / -23

들어가며

Python의 base64, binascii 모듈은 이메일 첨부, JWT 토큰, 바이너리 데이터 전송 등 다양한 곳에서 사용됩니다. 하지만 기존 CPython의 base64 구현은 바이트 단위 루프와 비트 시프트 상태 머신(leftchar/leftbits) 방식으로 동작하여, 현대 CPU의 파이프라인 최적화를 전혀 활용하지 못하고 있었습니다.

이 PR은 loop-carried dependency를 제거하고, lookup table을 캐시 라인에 정렬하며, fast path/slow path를 분리하여 인코딩 2배, 디코딩 3배의 속도 향상을 달성합니다.

핵심 코드 분석

1. Lookup Table의 L1 캐시 라인 정렬

Before:

static const unsigned char table_a2b_base64[] = {
    -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
    // ...
};

static const unsigned char table_b2a_base64[] =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

After:

/* Align to 64 bytes for L1 cache line friendliness */
static const unsigned char table_a2b_base64[] Py_ALIGNED(64) = {
    -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1, -1,-1,-1,-1,
    // ...
    52,53,54,55, 56,57,58,59, 60,61,-1,-1, -1,64,-1,-1, /* PAD->64 detected by fast path */
    // ...
};

static const unsigned char table_b2a_base64[] Py_ALIGNED(64) =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

Py_ALIGNED(64) 지시어로 lookup table이 64바이트 L1 캐시 라인 경계에 정렬됩니다. 이렇게 하면 테이블 접근 시 캐시 미스가 줄어들어, 반복적인 테이블 참조가 일어나는 인코딩/디코딩 루프에서 체감 성능이 향상됩니다.

2. base64_encode_trio() — 3바이트를 한번에 처리

Before:

for( ; bin_len > 0 ; bin_len--, bin_data++ ) {
    leftchar = (leftchar << 8) | *bin_data;
    leftbits += 8;
    while ( leftbits >= 6 ) {
        this_ch = (leftchar >> (leftbits-6)) & 0x3f;
        leftbits -= 6;
        *ascii_data++ = table_b2a_base64[this_ch];
    }
}

After:

static inline void
base64_encode_trio(const unsigned char *in, unsigned char *out,
                   const unsigned char *table)
{
    unsigned int combined = ((unsigned int)in[0] << 16) |
                            ((unsigned int)in[1] << 8) |
                            (unsigned int)in[2];
    out[0] = table[(combined >> 18) & 0x3f];
    out[1] = table[(combined >> 12) & 0x3f];
    out[2] = table[(combined >> 6) & 0x3f];
    out[3] = table[combined & 0x3f];
}

기존 코드는 1바이트씩 처리하면서 leftchar와 leftbits 상태를 유지해야 했습니다. 각 반복이 이전 반복의 결과에 의존하는 loop-carried dependency가 존재하여 CPU 파이프라인이 stall됩니다. 새 코드는 3바이트를 하나의 unsigned int로 합친 뒤, 독립적인 4번의 비트 시프트로 변환합니다. 각 출력이 서로 독립적이므로 CPU가 병렬로 실행할 수 있습니다.

3. base64_decode_quad() — 병렬 유효성 검사

After:

static inline int
base64_decode_quad(const unsigned char *in, unsigned char *out,
                   const unsigned char *table)
{
    unsigned char v0 = table[in[0]];
    unsigned char v1 = table[in[1]];
    unsigned char v2 = table[in[2]];
    unsigned char v3 = table[in[3]];

    if ((v0 | v1 | v2 | v3) & 0xc0) {
        return 0;
    }

    out[0] = (v0 << 2) | (v1 >> 4);
    out[1] = (v1 << 4) | (v2 >> 2);
    out[2] = (v2 << 6) | v3;
    return 1;
}

4개의 lookup을 먼저 수행한 뒤, (v0|v1|v2|v3) & 0xc0이라는 단일 비트 연산으로 유효성을 검사합니다. 유효한 base64 값은 0~63(6비트)이므로 상위 2비트(0xc0)가 설정되어 있으면 잘못된 문자입니다. 분기 예측이 쉬운 단일 조건문으로 4개의 개별 검사를 대체한 것이 핵심입니다.

4. Fast Path / Slow Path 분리

/* Fast path: use optimized decoder for complete quads */
if (ascii_len >= 4) {
    Py_ssize_t fast_chars = base64_decode_fast(ascii_data, (Py_ssize_t)ascii_len,
                                               bin_data, table_a2b_base64);
    if (fast_chars > 0) {
        i = (size_t)fast_chars;
        bin_data += (fast_chars / 4) * 3;
    }
}

/* Slow path: handle remaining input (padding, invalid chars, partial groups) */

완전한 4문자 그룹은 fast path에서 벌크 처리하고, 패딩이나 잘못된 문자가 포함된 나머지만 기존 slow path로 처리합니다. 대부분의 입력은 fast path에서 끝나므로 전체 성능이 크게 향상됩니다.

왜 이게 좋은가

CPython의 공식 벤치마크에 따르면 인코딩 2배, 디코딩 3배 속도 향상이 모든 플랫폼에서 확인되었습니다. 핵심 원리는 간단합니다:

1. Loop-carried dependency 제거: CPU의 superscalar 실행 엔진이 독립적인 연산을 병렬 처리 가능
2. 캐시 친화적 메모리 레이아웃: 64바이트 정렬로 lookup table이 하나의 캐시 라인에 들어감
3. 분기 최소화: 단일 비트마스크 검사로 4개의 유효성 검증을 대체

이 최적화는 SIMD나 플랫폼별 intrinsic 없이 순수 C 코드 수준의 구조 변경만으로 이루어졌다는 점이 인상적입니다.

정리

• 상태 머신보다 벌크 처리: 바이트 단위 상태 추적 대신 고정 크기 블록(3바이트/4문자) 단위로 처리하면 CPU 파이프라인 활용도가 극적으로 향상됩니다.
• 캐시 라인 정렬은 무료 성능: Py_ALIGNED(64) 한 줄로 lookup table 성능을 높일 수 있습니다.
• Fast path/slow path 패턴: 일반적인 경우를 최적화하고 예외적인 경우만 느린 경로로 보내는 패턴은 다양한 파서/인코더에 적용 가능합니다.

참고 자료

• CPython Issue #124951 — base64 성능 개선 트래킹 이슈
• CPython PR #143262 — 전체 diff 및 벤치마크 결과

⚠️ 알림: 이 분석은 AI가 실제 코드 diff를 기반으로 작성했습니다.