128-arm 패턴 디스패치 문제와 11ns에서 1.1ns로 어떻게 도달했는가

Source: Dev.to

The Problem

리터럴 값들의 대규모 집합에 대한 패턴 매칭은 코드상에서는 깔끔해 보이지만, 런타임에서는 벽에 부딪힙니다. on() 호출마다 모든 팔에 대해 case 객체를 생성합니다.

팔이 128개라면, 매치 호출당 128개의 객체가 생성되는 것입니다. 호출당 약 11 ns 정도라면 일회성 사용에는 문제가 없지만, 뜨거운 루프 안에서는 재앙이 됩니다.

// Clean syntax, 128 case objects constructed per call
return match(x) | on(
    lit(0) >> handle_0,
    lit(1) >> handle_1,
    // … 126 more arms
    _   >> default_handler
);

case들은 컴파일 타임 상수이며 값이 변하지 않습니다. 하지만 on() 호출이 이들을 함수 인자로 받기 때문에 라이브러리는 매번 객체를 생성해야 합니다. C++는 최적화 단계가 개입하기 전에 호출 지점에서 인자를 평가합니다.

이는 라이브러리 설계상의 버그가 아니라 파이프라인 구문 match(x) | on(...)의 구조적 비용입니다. 이 구문은 가독성이 좋고 조합 가능한 매칭을 제공하지만, 그 대가로 case 리스트가 런타임 객체가 됩니다.

하지만 우리는 이를 해결할 방법을 찾을 때까지는 그랬습니다.

첫 번째 시도: is_constant_evaluated()를 이용한 정적 캐싱

아이디어는 간단했습니다. 매치 표현식이 constexpr 컨텍스트에 나타나면, 컴파일러는 이미 피연산자 값과 모든 case 값을 알고 있습니다. 우리는 전체 매치를 컴파일 타임에 전개하고 런타임 메커니즘을 완전히 우회할 수 있습니다.

C++20은 std::is_constant_evaluated()를 제공했습니다. 이 함수가 true를 반환하면, 컴파일러가 이 코드를 constexpr 컨텍스트에서 평가하고 있다는 뜻입니다. 우리는 정적 경로를 선택할 수 있습니다:

template <typename Subject, typename CasesTuple>
constexpr auto dispatch(Subject& subject, CasesTuple&& cases) {
    if (std::is_constant_evaluated()) {
        // Compile‑time path: unfold cases statically
        return static_dispatch(subject, std::forward<CasesTuple>(cases));
    }
    // Runtime path: use the normal evaluation engine
    return runtime_dispatch(subject, std::forward<CasesTuple>(cases));
}

이론적으로는 멋지지만, 실제로는 전체 호출 지점이 constexpr일 때만 도움이 됩니다. 컴파일 타임에 알려진 case 값을 가진 런타임 매치의 경우, case들은 여전히 생성됩니다. constexpr 분기는 실행되지 않습니다.

우리는 더 공격적인 방법이 필요했습니다: 리스트의 모든 case가 정적 리터럴임을 컴파일 타임에 감지하고, 런타임 평가자가 O(1) 조회에 사용할 수 있는 밀집 디스패치 테이블을 구축하는 것이었습니다.

함정: [[no_unique_address]]와 std::is_empty

Static literal patterns look like empty types:

template <auto V, typename Cmp>
struct static_literal_pattern {
    static constexpr auto value = V;
    [[no_unique_address]] Cmp cmp{};
};

std::equal_to<>는 빈 타입이다. [[no_unique_address]]는 컴파일러가 cmp를 크기 0으로 최적화하도록 허용해야 하며, 전체 패턴을 매우 작게 만든다.

우리는 std::is_empty를 정적‑캐싱 적격성의 게이트로 사용했다:

// Naïve check: if the pattern is empty, we can cache it
if constexpr (std::is_empty_v<T>) {
    // … static cache path
}

이것이 GCC에서 깨졌다. 이유: [[no_unique_address]]는 허가일 뿐, 요구사항이 아니다. GCC는 비‑빈 베이스 클래스에 이를 적용하지 않으며, 멤버가 베이스 클래스가 아니더라도 마찬가지다. Cmp 멤버가 빈 타입임에도 불구하고, 패턴이 std::is_empty를 만족하지 못한다.

정적‑캐시 경로가 조용히 건너뛰어졌다. 조밀한 디스패치 테이블은 절대 구축되지 않았다. 128‑case 매치는 약 11 ns 수준을 유지했다.

수정: sizeof<T>‑기반 트레이트

우리는 [[no_unique_address]] 처리와 관계없이 작동하는 크기 기반 트레이트로 전환했습니다:

template <typename T>
constexpr bool is_cacheable_pattern_v = sizeof(T) == 1;

(실제 구현 세부 사항은 간결성을 위해 생략되었습니다.)

이 변경으로 라이브러리는 정적 리터럴 패턴을 올바르게 식별하고 조밀한 테이블을 구축합니다.

Source: …

숫자

Intel i7‑13700K, GCC 13.2, -O3 -march=native 환경에서 벤치마크했습니다. 대상 타입: int, 128개의 리터럴 팔, 균등 무작위 입력.

자동 캐시 방식은 이전 최적 관행(PTN_ON 매크로)과 동일한 성능을 보이며, 손으로 작성한 switch보다 0.04 ns 정도만 느립니다. 이 차이는 경계 검사에서 발생하는 분기 예측 실패 때문이며, 라이브러리 차원에서 제어할 수 없습니다.

참고로, 원래 구현은 손으로 작성한 switch보다 9.9배 느렸습니다. 이번 수정으로 1.04배 수준으로 개선되었습니다. 10배 이상의 성능 향상은 타입 트레이트의 단일 조건을 변경함으로써 달성되었습니다.

라이브러리 설계에 대한 시사점

• 작은 구현 세부 사항도 중요합니다. std::is_empty 한 번의 검사만으로도 주요 컴파일러에서 10배 느려지는 현상이 발생했습니다.
• 컴파일러 확장([[no_unique_address]])에 의존하는 것은 취약할 수 있습니다. 컴파일러마다 속성을 다르게 처리하므로, 휴대 가능한 대체 구현이 필수적입니다.
• 패턴에 대한 정적 분석이 효과적일 수 있습니다. 모든 경우가 컴파일‑타임 리터럴이라는 것을 감지하면, 일반적인 런타임 루프를 조밀한 O(1) 테이블로 교체할 수 있습니다.
• 성능이 중요한 라이브러리는 “정적‑캐시” 경로를 제공해야 합니다—주변 코드가 constexpr가 아니더라도 동작하도록 설계합니다.

캐시 적용 여부 테스트를 sizeof(T) 로 조정함으로써 숨겨진 성능 버그를 측정 가능한 개선으로 바꿀 수 있었습니다.

패턴: 성능 작업에서는 깔끔한 이론적 특성보다 실제 경험적 임계값이 더 중요합니다.

사용해 보기

구현은 github.com/sentomk/patternia 에서 오픈 소스로 제공됩니다.

• 디스패치 플래너: include/ptn/core/common/optimize.hpp
• 정적 리터럴 캐시 로직: include/ptn/core/common/eval.hpp

헤더‑전용, C++17, 표준 라이브러리 외 의존성 없음.