메타프로그래밍으로 정규식 매처를 컴파일 타임에 특수화하고 인라인해 재귀 해석기 오버헤드를 없애며, 손으로 짠 코드에 근접한(때론 능가할 수도 있는) 10배 성능을 얻는 과정을 단계별로 설명합니다.
2025년 10월 27일—
가끔은 너무나도 기묘해서 마치 다른 차원을 들여다보는 듯한 최적화를 마주칠 때가 있습니다.
얼마 전까지만 해도 저는 메타프로그래밍이란 게 기본적으로 C++ 템플릿에 constexpr 같은 몇 가지 멋진 기능이 얹힌 정도라고 믿었습니다. PHP로 예전부터 해 오던, 이른바 "코드를 쓰는 코드" 정도라고 생각했죠. 간단한 일이잖아요?
저처럼 생각했다면, 안전벨트를 매세요! 메타프로그래밍으로 제가 불가능한 최적화라고 부르는 것을 어떻게 열어젖힐 수 있는지 보여드리겠습니다.
여기서 말하는 건 5% 미세 최적화가 아닙니다. 코드를 10배 빠르게 만드는, 미친 듯한 최적화입니다.
Zig 라이브러리인 Alexandros Naskos의 ctregex에 큰 감사를 전합니다. 메타프로그래밍으로 무엇을 할 수 있는지 훌륭히 보여주고, 이 글의 예시들에 영감을 주었습니다.
불가능한 최적화, 그리고 그것을 실현하는 메타프로그래밍
간단한 정규식 함수를 쓰는 프로그램이 있고, 이를 이메일 검증에 쓰고 싶다고 상상해봅시다: 0
fn main():
email_regex =
Regex("\w+(\+\w*)?@(\d+\.\d+\.\d+\.\d+|\w+\.\w+)")
print(matches(email_regex, "user@example.com")) # True 출력
print(matches(email_regex, "uexample.com")) # False 출력
print(matches(email_regex, "user@ecom")) # False 출력
print(matches(email_regex, "user+tag@example.com")) # True 출력
print(matches(email_regex, "user@100")) # False 출력
print(matches(email_regex, "howdy123@1.2.3.4")) # True 출력
print(matches(email_regex, "howdy1231.2.3.4")) # False 출력
print(matches(email_regex, "howdy123@1/2/3/4")) # False 출력
우리는 모두 정규식이 꽤 느리다는 걸 압니다. 사실상 전체 인터프리터를 돌려야 하기 때문이죠. 혹은 Regex를 "사전 컴파일"한다 해도, 여전히 AST(혹은 DFA)를 해석하는 셈이어서 느립니다. 1
정말 속도가 필요할 땐, 정규식을 아예 건너뛰고 아래처럼 직접 손으로 matches 함수를 작성하곤 합니다:
fn matches(text: String) -> Bool:
var total_consumed = 0
var pos = 0
var text_len = len(text)
var word_matches = 0
var word_total_consumed = 0
while True:
if pos >= text_len:
break
var ch = text[pos]
alias char_class = "word"
var char_matches = False
char_matches = (
(ord("a") <= ord(ch) <= ord("z"))
or (ord("A") <= ord(ch) <= ord("Z"))
or (ord("0") <= ord(ch) <= ord("9"))
or ch == "_"
)
if not char_matches:
break
var chars_consumed = 1
if chars_consumed == 0:
break
word_matches += 1
word_total_consumed += chars_consumed
pos += chars_consumed
if word_matches < 1:
return False
total_consumed += word_total_consumed
... # 패턴의 나머지에 대한 훨씬 더 많은 코드가 이어집니다
제 벤치마크에서는 이것이 약 10.5배 더 빠릅니다. 2
그러면 문득 궁금해집니다. 최적화기가 이걸 우리 대신 somehow 해줄 수는 없을까요?
안타깝게도, 없습니다. 그 길에는 많은 난관이 있습니다. 아래에서 설명하겠습니다.
0
...그건 아주 끔찍한 아이디어이니 절대 그러지 마세요(자세한 내용은 이 페이지 참고). 하지만 약간의 정규식 관련 죄악 없이 인생이 무슨 재미가 있겠습니까!
1
실제 정규식 엔진은 보통 먼저 패턴을 AST로 파싱한 뒤, 이를 상태 전이로 입력을 처리하는 상태 기계(DFA/NFA)로 컴파일합니다. 이 글의 장난감 구현은 대신 재귀적 AST 인터프리터를 사용합니다. 이는 각 노드마다 함수 호출 오버헤드가 있지만, 이 기법의 힘을 훨씬 더 잘 보여줍니다: 모든 오버헤드가 제거되기 때문이죠.
2
M2 맥북 프로에서 2억 회 실행해 테스트했습니다. 자세한 내용은 아래를 참고하세요.
문제는 matches가 일종의 인터프리터 같다는 점입니다. 다음과 같이, 이런 형태의 노드 트리(상수)를 입력으로 받습니다:
- \w+에 대한 RepeatNode
- \w에 대한 CharClassNode
- (\+\w*)?에 대한 RepeatNode
- \+\w*에 대한 SequenceNode
- \+에 대한 LiteralNode
- \w*에 대한 RepeatNode
- \w에 대한 CharClassNode
- @에 대한 LiteralNode
- (\d+\.\d+\.\d+\.\d+|\w+\.\w+)에 대한 OrNode
- \d+\.\d+\.\d+\.\d+에 대한 SequenceNode
- \d+에 대한 RepeatNode
- \d에 대한 CharClassNode
- \.에 대한 LiteralNode
- \d+에 대한 RepeatNode
- \d에 대한 CharClassNode
- \.에 대한 LiteralNode
- \d+에 대한 RepeatNode
- \d에 대한 CharClassNode
- \.에 대한 LiteralNode
- \d+에 대한 RepeatNode
- \d에 대한 CharClassNode
- \w+\.\w+에 대한 SequenceNode
- \w+에 대한 RepeatNode
- \w에 대한 CharClassNode
- \.에 대한 LiteralNode
- \w+에 대한 RepeatNode
- \w에 대한 CharClassNode
...그리고 실행 시점에만 알 수 있는 사용자 문자열도 함께 받습니다.
그런 다음 사용자 문자열의 다음 문자가 무엇인지에 따라 트리를 위아래로 탐색합니다.
실제 정규식 구현은 이보다 훨씬 더 정교하며, 이런 AST 대신 상태 기계를 사용합니다. 이 글의 구현은 이 글만을 위해 만든 단순한 정규식 부분집합입니다. 3
이를 보여주기 위해, 최상위 matches 함수는 다음과 같습니다:
@no_inline
fn matches(regex: Regex, text: String) -> Bool:
var result = _match_node(regex.nodes, regex.root_idx, text, 0)
return result.matched and result.chars_consumed == len(text)
...이는 실제로 (재귀적인) _match_node 함수를 호출할 뿐입니다:
fn _match_node(
nodes: List[RegexNode], node_idx: Int, text: String, start_pos: Int
) -> MatchResult:
var node = nodes[node_idx]
if node.isa[LiteralNode]():
ref literal_node = node[LiteralNode]
return _match_literal(nodes, literal_node, text, start_pos)
elif node.isa[RepeatNode]():
ref repeat_node = node[RepeatNode]
return _match_repeat(nodes, repeat_node, text, start_pos)
elif ...
...그리고 아래의 _match_repeat 같은 다양한 함수를 호출합니다. 이 함수는 정규식에서 반복되는 부분을 검사합니다. 예를 들어 이메일 정규식의 \w+ 에서 +는 \w를 반복하라는 뜻이죠.
fn _match_repeat(
nodes: List[RegexNode], # 모든 정규식 노드
node: LiteralNode, # 현재 보고 있는 노드
text: String, # 사용자의 문자열
start_pos: Int # 문자열에서 현재 위치
) -> MatchResult:
var matches = 0
var total_consumed = 0
var pos = start_pos
while True:
if node.maximum_times >= 0 and matches >= node.maximum_times:
break
var result = _match_node(nodes, node.repeated, text, pos)
if not result.matched:
break
if result.chars_consumed == 0:
break
matches += 1
total_consumed += result.chars_consumed
pos += result.chars_consumed
if matches >= node.minimum_times:
return MatchResult(True, total_consumed)
else:
return MatchResult(False, 0)
재귀 접근의 장점 중 하나는 매우 유연하다는 점입니다. 임의의 노드 트리를 실행할 수 있고, 즉 임의의 정규식을 실행할 수 있습니다. 손으로 짠 버전은 그런 유연성이 없고, 미리 고정되어 있습니다.
하지만 물론, 유연성에는 비용이 따릅니다. 재귀는 손으로 짠 버전보다 더 많은 함수 호출을 필요로 하며, 함수 호출에는 오버헤드가 있습니다. 함수를 호출할 때마다 스택에 푸시/팝이 발생합니다. 손으로 짠 버전이 더 빠른 이유는 그 문제가 없기 때문입니다.
또 다른 문제는, 이 일반적인 정규식 코드는 손으로 짠 버전이 필요로 하지 않는 여분의 유연성을 갖고 있다는 점입니다. 위의 조건을 보세요:
if node.maximum_times >= 0 and matches >= node.maximum_times:
break
이 코드는 \w{,7}처럼 최대 7번 매칭 같은 상한을 원할 때만 의미가 있습니다. 하지만 우리의 이메일 정규식에는 \w+처럼 상한이 없는 것들이 있으며, 임의 개수의 \w 문자에 매칭합니다. 따라서 이 무의미한 코드가 여기 있어 성능을 떨어뜨리는 것은 아쉽습니다. 손으로 짠 버전이 더 빠른 이유는 이 문제가 없기 때문입니다.
손으로 짠 버전은 이론적으로도 더 최적화하기 쉽습니다. 모든 것이 하나의 함수 안에 있기 때문이며, 마치 이 재귀적 _match_node, _match_repeat 등의 호출을 모두 인라인한 것과 같습니다. 최적화기는 일반적으로 모든 것이 하나의 함수 안에 있을 때 더 잘 작동합니다.
우리의 일반 Regex 코드에도 이런 이점을 가져올 수 있을까요?
3
SIMD 같은 더 흥미로운 기능을 넣고 싶은 유혹을 겨우 참았습니다. 이 구현은 또한 실제 정규식 엔진이 더 복잡한 패턴에 필요로 하는 백트래킹을 지원하지 않습니다.
위에서 손으로 짠 함수는 마치 이 재귀적 _match_node 호출들을 모두 인라인한 것과 같다고 했습니다.
그렇다면 질문은 자명합니다: _match_node를 인라인할 수 있을까요?
@always_inline을 얹어 시도해 봅시다:
@always_inline
fn _match_node(
nodes: List[RegexNode], node_idx: Int, text: String, start_pos: Int
) -> MatchResult:
...
하지만 물론, 재귀 호출을 인라인하려 하면 컴파일 오류가 납니다:
main_rt_inlined.mojo:19:4: error: function has recursive call to 'always_inline' function
fn _match_node(
^
main_rt_inlined.mojo:28:29: note: through call here
return _match_repeat(nodes, repeat_node, text, start_pos)
^
main_rt_inlined.mojo:119:4: note: to function marked 'always_inline' here
fn _match_repeat(
^
main_rt_inlined.mojo:128:33: note: call here recurses
var result = _match_node(nodes, node.repeated, text, pos)
^
main_rt_inlined.mojo:19:4: note: back to function here
fn _match_node(
^
그러니 이 생각은 일단 접어두죠. 나중에 다시 돌아올지도 모릅니다.
마음이 날아갈 만큼 이상한 걸 약속했으니, 이제 진짜 이상하게 만들어 봅시다.
다단계 프로그래밍을 조금 사용해 첫 번째 후타무라 사영과 유사한 효과를 얻겠습니다. 4 어떤 이들에게는 "후타무라 마법의 세 단계"로 알려져 있죠. 5
우리는 다음을 수행합니다:
...그리고 놀라운 일이 벌어집니다.
4
구체적으로는, 인터프리터를 특정 프로그램에 특수화(specialize)하는 것입니다. 다만 자동 부분 평가 대신 몇 가지 명시적 스테이징 주석(alias와 대괄호)을 사용합니다.
5
"어떤 이들"이란, 대략 세 사람 정도를 말합니다. 저를 빼면 두 사람요.
대부분의 Regex 구현은 먼저 정규식을 파싱해 노드 목록으로 만듭니다. 만약 이 파싱을 컴파일 타임으로 옮길 수 있다면, 런타임을 절약할 수 있습니다.
Regex를 컴파일 타임에 노드로 파싱하려면, var regex를 alias regex로 바꾸기만 하면 됩니다.
변경 전:
# 정규식 파싱(런타임)
var regex = Regex("w+(+w*)?@(d+.d+.d+.d+|w+.w+)")
regex.match(regex.nodes, regex.root_node, user_string, 0)
변경 후:
# 정규식 파싱(컴파일 타임)
alias regex = Regex("w+(+w*)?@(d+.d+.d+.d+|w+.w+")
_match_node[regex.nodes, regex.root_node](user_string, 0)
alias는 Mojo에서 "컴파일 타임 변수"를 뜻합니다. 6
"잠깐만요 Evan, 컴파일 타임에 실행하기엔 코드가 너무 많은데, 컴파일러가 정말 일반 코드를 컴파일 타임에 실행할 수 있나요?"
그렇습니다! Mojo(그리고 D, Nim, Zig 같은 몇몇 언어)의 좋은 기능 중 하나입니다. 간단한 키워드(alias) 하나로 거의 모든 계산을 7 컴파일 타임으로 끌어올릴 수 있고, 동일한 코드를 var와 alias처럼 사용 방식에 따라 컴파일 타임 또는 런타임에 실행할 수 있습니다.
이 경우, 컴파일러는 자체 재귀, 힙 할당 등 모든 것을 포함한 작은 파서를 통째로 실행합니다. 그리고 이제 그 일이 컴파일 타임에 일어납니다.
"잠깐, 힙 할당이라고 하셨나요? 컴파일 타임에 힙 할당은 불가능하지 않나요?"
드물지만, 불가능하지 않습니다! Mojo, D, Nim, Zig, 그리고 C++ C++20부터 가능합니다. 이 외에도 몇몇 언어가 더 있을 수 있지만, 다른 방언을 요구하지 않고 일반 런타임 코드를 그대로 컴파일 타임에 실행할 수 있는 언어는 이 정도입니다. 물론, 일부 Lisp는 60~70년대에도 이미 이런 걸 하고 있었을 게 분명하지만요!
Mojo 컴파일러 내부 깊은 곳에는 컴파일 타임 인터프리터가 있으며, 인스턴시에이터(모든 제네릭을 모노모픽으로 만드는 "정교화기")와 긴밀히 협력해 제네릭 인자([...])와 alias 문 안의 모든 표현식을 실행합니다. 이 컴파일 타임 인터프리터는 malloc과 free를 포함해 일반 CPU가 실행할 수 있는 거의 모든 연산을 실행할 수 있습니다.
6
Mojo에도 Zig의 comptime 같은 키워드가 있으면 좋겠다는 생각을 좀 했습니다만, 아쉽네요!
7
거의 모든 것이라고 말한 이유는, stdin에서 읽기 같은 건 언어 차원에서 컴파일 타임에 허용하면 안 되기 때문입니다.
우리는 방금 Regex를 컴파일 타임에 생성했습니다.
이걸 런타임에 읽을까요? 전역 변수에라도 넣을까요?
아니요! 우리는 컴파일 타임에만 읽을 겁니다.
"하지만 Evan, 런타임에 Regex를 읽어야 하잖아요! 그렇지 않으면 런타임 프로그램이 뭘 해야 하는지 어떻게 알죠? 어떤 함수를 호출하고 어떤 분기를 타야 하는지요?"
좋은 질문입니다! 답은 그 모든 결정을 컴파일 타임에 내릴 수 있다는 것입니다.
이해가 안 되실 수 있지만, 잠시만 기다려 주세요.
프로그램을 이렇게 바꿉니다.
변경 전:
fn _match_node(
nodes: List[RegexNode],
node_idx: Int,
text: String,
start_pos: Int
) -> MatchResult:
var node = nodes[node_idx]
if node.isa[LiteralNode]():
ref literal_node = node[LiteralNode]
return _match_literal(nodes, literal_node, text, start_pos)
elif node.isa[RepeatNode]():
ref repeat_node = node[RepeatNode]
return _match_repeat(nodes, repeat_node, text, start_pos)
elif ...
변경 후:
fn _match_node[nodes: List[RegexNode], node_idx: Int](
text: String,
start_pos: Int
) -> MatchResult:
alias node = nodes[node_idx]
@parameter
if node.isa[LiteralNode]():
alias literal_node = node[LiteralNode]
return _match_literal[nodes, literal_node](text, start_pos)
elif node.isa[RepeatNode]():
alias repeat_node = node[RepeatNode]
return _match_repeat[nodes, repeat_node](text, start_pos)
elif ...
두 가지 주요 변경점이 있습니다:
즉 _match_node는 이제 제네릭 함수, 템플릿입니다.
nodes 값은 Regex에서 하나뿐이지만, 이 Regex에는 서로 다른 node_idx가 28개 있습니다. 따라서 이 _match_node의 인스턴스화가 28개 생깁니다. node_idx마다 하나씩이죠.
이전에는 아주 단순한 호출 트리 하나가 있었고, 오직 하나의 _match_node가 재귀적이었습니다. 호출 트리는 다음과 같았습니다:
main
match
_match_node
_match_node
_match_node
_match_node
_match_node
이제는 _match_node가 28개 버전이 있고, 호출 트리는 다음과 같습니다:
main
match[Regex instance]
_match_node[List(...), 0] (전체 표현식)
_match_node[List(...), 1] (첫 번째 \w+)
_match_node[List(...), 3] ((+\w*)?)
_match_node[List(...), 4] (+\w*)
_match_node[List(...), 5] (+)
_match_node[List(...), 6] (\w*)
_match_node[List(...), 8] (@)
_match_node[List(...), 9] ((\d+.\d+.\d+.\d+|\w+.\w+))
_match_node[List(...), 10] (\d+.\d+.\d+.\d+)
_match_node[List(...), 11] (\d+)
_match_node[List(...), 13] (.)
_match_node[List(...), 14] (\d+)
_match_node[List(...), 16] (.)
_match_node[List(...), 17] (\d+)
_match_node[List(...), 19] (.)
_match_node[List(...), 20] (\d+)
_match_node[List(...), 22] (\w+.\w+)
_match_node[List(...), 23] (\w+)
_match_node[List(...), 25] (.)
_match_node[List(...), 26] (\w+)
28개 버전은 각기 node_idx 컴파일 타임 매개변수만 다릅니다.
이를 더 잘 이해하기 위해, 첫 번째 \w+에 해당하는 _match_node[List(...), 1]을 보겠습니다.
컴파일러가 이를 _match_node[List(...), 1]로 인스턴스화하면 아래처럼 보일 것입니다. @parameter if는 컴파일 타임에 평가되어 그 분기 중 하나만 포함됩니다. 설명을 위해 주석으로 남겨두겠습니다:
fn _match_node[List(...), 1]( # 노드 1은 RepeatNode
text: String,
start_pos: Int
) -> MatchResult:
# alias node = nodes[node_idx]
# @parameter
# if node.isa[LiteralNode]():
# alias literal_node = node[LiteralNode]
# return _match_literal[nodes, literal_node](text, start_pos)
# elif node.isa[RepeatNode]():
# alias repeat_node = node[RepeatNode]
return _match_repeat[List(...), RepeatNode(2, 1, 0)](text, start_pos)
# elif ...
여기서의 이점은 런타임에 node.isa[LiteralNode], node.isa[RepeatNode] 등을 수행할 필요가 없다는 것입니다. 이는 약간의 오버헤드를 제거합니다.
또한 alias 문들도 실행되어, 런타임에 그 조회(및 경계 검사)를 수행할 필요가 없습니다. 또 다른 성능 향상이죠!
가장 큰 이점은 다음 섹션에서 보게 됩니다.
호출 트리를 다시 봅시다:
main
match[Regex instance]
_match_node[List(...), 0] (전체 표현식)
_match_node[List(...), 1] (첫 번째 \w+)
_match_node[List(...), 3] ((+\w*)?)
_match_node[List(...), 4] (+\w*)
_match_node[List(...), 5] (+)
_match_node[List(...), 6] (\w*)
_match_node[List(...), 8] (@)
_match_node[List(...), 9] ((\d+.\d+.\d+.\d+|\w+.\w+))
_match_node[List(...), 10] (\d+.\d+.\d+.\d+)
_match_node[List(...), 11] (\d+)
_match_node[List(...), 13] (.)
_match_node[List(...), 14] (\d+)
_match_node[List(...), 16] (.)
_match_node[List(...), 17] (\d+)
_match_node[List(...), 19] (.)
_match_node[List(...), 20] (\d+)
_match_node[List(...), 22] (\w+.\w+)
_match_node[List(...), 23] (\w+)
_match_node[List(...), 25] (.)
_match_node[List(...), 26] (\w+)
이제 이들은 더 이상 실제로 재귀 호출이 아닙니다. 컴파일러가 보기에는 전혀 다른 함수들입니다. 실제로 그렇기도 하고요.
컴파일러 입장에서 이는 정상적인(유한한) 호출 트리이지, 잠재적으로 무한한 호출 트리가 아닙니다.
그렇다면... 인라인할 수 있을까요? 이 함수들에 @always_inline을 붙일 수 있을까요?
가능합니다!
_match_repeat 함수부터 인라인해 봅시다. fn _match_repeat에 @always_inline을 붙이면 됩니다:
@always_inline
fn _match_repeat[
nodes: List[RegexNode], repeat_node: RepeatNode
](text: String, start_pos: Int) -> MatchResult:
var matches = 0
var total_consumed = 0
var pos = start_pos
while True:
if node.maximum_times >= 0 and matches >= node.maximum_times:
break
var result = _match_node[nodes, node.repeated](text, pos)
...
이제 호출자 쪽으로 인라인될 것입니다.
우리의 _match_node[List(...), 1] 함수를 기억하시나요?
fn _match_node[List(...), 5]( # 노드 5는 RepeatNode
text: String,
start_pos: Int
) -> MatchResult:
alias node = nodes[node_idx]
alias repeat_node = node[RepeatNode]
# 먼저 이 _match_repeat 호출을 인라인합시다!
return _match_repeat[nodes, repeat_node](text, start_pos)
_match_repeat가 인라인되면, _match_node는 아래처럼 보입니다:
fn _match_node[List(...), 1]( # 노드 1은 RepeatNode
text: String,
start_pos: Int
) -> MatchResult:
alias node = nodes[node_idx]
alias repeat_node = node[RepeatNode]
# 인라인된 _match_repeat 호출
var matches = 0
var total_consumed = 0
while True:
if node.maximum_times >= 0 and matches >= node.maximum_times:
break
var result = _match_node[nodes, node.repeated](text, pos)
...
...
그리고 컴파일러는 alias 문도 컴파일 타임에 실행하고 그 결과를 인라인합니다.
이 부분:
if node.maximum_times >= 0 and matches >= node.maximum_times:
break
은 실제로 다음처럼 됩니다:
if RepeatNode(2, 1, -1)_times >= 0 and matches >= RepeatNode(2, 1, 0).maximum_times:
break
그 다음 이렇게 됩니다:
if -1 >= 0 and matches >= -1:
break
그 다음 이렇게 됩니다:
if False and matches >= -1:
break
이는 불가능한 조건이므로 완전히 제거됩니다.
결국 우리의 _match_node[List(...), 1] 함수는 훨씬 더 단순해지고, 이 특정 RepeatNode에 더 잘 특화됩니다.
fn _match_node[List(...), 1]( # 노드 1은 RepeatNode
text: String,
start_pos: Int
) -> MatchResult:
# node 조회 없음!
var matches = 0
var total_consumed = 0
while True:
# 쓸모없는 maximum_times 검사 없음!
var result = _match_node[nodes, node.repeated](text, pos)
...
...
우리는 _match_repeat 하나의 함수에 @always_inline만 붙였을 뿐인데도 이렇게 많은 이득을 얻었습니다!
이제 모든 함수에 @always_inline을 걸어봅시다:
갑자기, 위의 거대한 호출 트리는 단순히 이렇게 됩니다:
main, 그리고 다음을 호출:
생성된 IR을 보면, 모두 하나의 함수로 접혀 손으로 짠 버전과 유사한 구조가 되었습니다.
최종 결과(M2 맥북 프로에서 2억 회 실행):
메타프로그래밍 버전은 일반 재귀 버전보다 10배 빠르며, 손으로 짠 버전 대비 약 3% 이내입니다.
상당히 인상적이죠!
그럴 수도 있습니다!
정규식 라이브러리는 종종 사용자 문자열에 매칭하기 전에 AST에 대해 자체 맞춤 최적화를 수행합니다.
예를 들어, (catastrophe|catapult|category) 패턴은 'cat' 접두사를 공유합니다. 컴파일 타임에 이를 감지해 cat(astrophe|apult|egory)처럼 더 적은 비교를 하도록 코드를 생성할 수 있습니다.
또는 \b(GET|POST|PUT|DELETE)\b 같은 패턴의 경우, 컴파일 타임에 완벽 해시 테이블이나 트라이를 만들어 4번의 문자열 비교를 하나의 해시 조회/문자열 비교로 대체할 수 있습니다.
이런 기법은 손으로 짠 코드에서는 잘 보이지 않지만, 일반적인 정규식 엔진에서는 흔합니다.
이것들을 이 기법과 결합하면, 손으로 짠 성능 위에 이런 최적화까지 얹을 수 있습니다.
가장 큰 단점에 대해 이야기합시다: 컴파일 시간!
컴파일러가 훨씬 더 많은 코드를 생성하므로 컴파일 시간이 훨씬 오래 걸립니다. 이 예시에서 우리는 _match_node[...] 함수를 28개 만들었고, 각 함수는 원래 런타임 재귀 _match_node의 약 1/5 크기였습니다. 즉, 이 기법은 _match_node 코드만 해도 약 5배 더 생성했습니다.
그리고 앞 절에서 언급한 사용자 정의 최적화를 도입하면, 더 많은 컴파일 시간을 대가로 성능을 더 얻을 수 있습니다.
이 기법은 현명하게, 빠르게 돌아가야 하는 코드에만 사용해야 합니다.
덧붙이자면, 이 단점은 완화하거나 아예 피할 수 있을 것 같습니다. 이론적으로 사용자는 MaybeComptime와 몇 가지 보조 도구를 사용해 개발/테스트 모드에서는 이러한 계산을 런타임에 수행하도록 만들 수 있다고 생각합니다. 검증되지는 않았지만, 제 촉은 가능합니다라고 말합니다.
이게 바로 _메타프로그래밍_입니다. 템플릿과 constexpr에 그치지 않습니다. 프로그램의 전체 측면을 컴파일 타임으로 옮겨, 맞춤형 최적화를 수행해 손으로 짠 코드보다 더 잘 돌아가게 만드는 것입니다.
메타프로그래밍이라는 용어를 수년 동안 들어왔지만, 여기서 볼 수 있듯이 그것이 가진 힘과 함의를 진정으로 이해하게 된 것은 이번이 처음이라 고백합니다.
이 정규식 예시는 대부분이 공감할 수 있는 주제일 뿐이고, 이 기법은 훨씬 더 많은 곳에 사용할 수 있다고 생각합니다.
그냥 상상에 불과하지만, 이런 곳에 쓸 수 있을 것 같습니다:
일반화하자면:
여기서 더 탐구하고 싶은 방향이 몇 가지 있습니다:
이 기법이 어디까지 갈 수 있을지 의견이 있다면 알려주세요!
알고 보니, 불가능해 보였던 최적화는 충분히 가능합니다!
필요한 건 약간의 메타프로그래밍 마법뿐이었죠.
코드를 보고 싶다면 여기에서 확인할 수 있습니다.
이 기법에 대해 더 읽고 싶다면 첫 번째 후타무라 사영이나 유사한 개념인 "staged programming"을 검색해 보세요.
즐겁게 읽으셨길 바랍니다! RSS 피드, twitter를 구독하고, Mojo 디스코드에서 놀거나 Vale 디스코드에서 저를 찾아주세요.
감사합니다!