# 매우 빠른 Lexer 구현 전략

> Clean Markdown view of GeekNews topic #22140. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=22140](https://news.hada.io/topic?id=22140)
- GeekNews Markdown: [https://news.hada.io/topic/22140.md](https://news.hada.io/topic/22140.md)
- Type: news
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-07-24T10:12:01+09:00
- Updated: 2025-07-24T10:12:01+09:00
- Original source: [xnacly.me](https://xnacly.me/posts/2025/fast-lexer-strategies/)
- Points: 8
- Comments: 0

## Summary

**점프 테이블 기반의 분기(threaded lexing)**, **0복사 윈도우 문자열**, 그리고 **bump allocator**와 같은 다양한 **로우레벨 최적화** 기법을 적용해 purple-garden 언어의 **Lexer 구현 성능**을 극한까지 끌어올린 사례를 설명합니다. **토큰 해싱** 및 **사전 해시 키워드 비교** 등으로 파싱 속도를 극대화했으며, **mmap**을 통한 대용량 파일 처리로 메모리 및 IO 비용까지 획기적으로 낮추었습니다. 실제 벤치마크에서 기존 유명 lexer들보다 **최대 10배 이상 빠른 처리 속도**를 기록해, 대규모 코드/데이터 파이프라인 구축이나 자체 언어 구현에 관심 있는 개발자에게 의미 있는 구현 전략과 성능 수치를 제시합니다.

## Topic Body

- **purple-garden 언어**를 위해 **초고속 Lexer**를 직접 설계·구현한 전략과 실측 성능 데이터 공유  
- **Threaded Lexing(점프 테이블 기반)**, **0복사·윈도우 문자열**, **인터닝**, **bump allocator** 등 다양한 **최적화 기법** 적용  
- **토큰 해싱**·** 키워드 사전 해시 비교**를 통해 파싱 속도 극대화, 단순 switch문보다 **점프 테이블**이 CPU 캐시 효율에서 우수함  
- **파일 전체 mmap**, **동적 할당 최소화**로 대용량 입력에서 IO·메모리 관리 비용을 대폭 절감  
- 기존 유명 lexer(예: flex, handcoded)와 비교해 **최대 10배 이상 빠른 처리 속도** 입증, 파싱/런타임 각 단계별 마이크로 벤치마크 수치 제시  
  
---  
  
### Lexing 및 컴파일 파이프라인 개요  
  
- **Lexer(토크나이저)** 는 입력 문자열을 의미 있는 **토큰 목록**으로 변환, 이후 **파서**가 이를 받아 AST(추상 구문 트리) 생성  
- purple-garden 언어에서의 토큰 설계는 **TokenType** 열거형과 문자열·타입 정보만 보관하는 **최소 구조** 유지  
  
### 최소 Lexer 설계와 코드 예시  
  
- Lexer 구조체는 **입력 문자열**, **현재 위치**만 저장  
- switch문으로 각 문자에 따라 토큰 생성  
- **디버깅**을 위해 타입-문자열 매핑 배열 및 타입별 초기화 활용  
  
### Threaded Lexing (점프 테이블 기반)  
  
- **switch문** 대신 **점프 테이블**(jump table)로 토큰 구분 처리(Computed goto)  
  - 256 바이트 배열에 문자값을 인덱스로 각 처리 라벨 매핑  
  - 실제 코드 분기에서 JUMP_TARGET 매크로로 즉시 분기 실행  
- 장점:  
  - **캐시 미스 감소**·** 분기 예측 최적화** 등으로 더 빠른 실행  
- 단점:  
  - **MSVC 지원 불가(Clang, GCC만)**, 디버깅 어려움  
  
### 메모리 관리와 Allocator 추상화  
  
- **bump allocator** 등 다양한 메모리 할당 전략을 위한 인터페이스 정의(Allocator 구조체)  
- CALL 매크로로 verbose 로그와 context 전달 간소화  
- 실제 할당·해제·통계 구조 및 코드 예시 제시  
  
### 0 복사, 윈도우 기반 문자열 처리  
  
- C에서 효율적 처리를 위해 **Str** 구조체(포인터, 길이, 해시) 도입  
- **슬라이스, concat, eq, 해싱, 숫자 변환** 등 직접 구현  
- 문자열 슬라이스는 포인터 이동만으로 즉시 생성, 메모리 할당 없음  
- 숫자 변환도 문자-정수 변환 알고리듬 직접 구현  
  
### 토큰 해싱 및 사전 해시 키워드 비교  
  
- **토큰 생성 시 해시**(FNV-1a) 계산하여 중복 비교·인터닝 최적화  
- true/false 등 **상수 키워드는 해시값으로 즉시 비교**하여 분기(성능 개선)  
- is_alphanum(알파벳/숫자/특수문자 판별)도 **bit 연산**·루프업 방식 등 최적화  
  
### 숫자 파싱의 효율화 및 컴파일 단계로 이관  
  
- Lexer에서 숫자 토큰의 **윈도우·해시**만 저장, 실제 정수/실수 변환은 **컴파일 단계**에서 중복 없이 1회만 수행  
- 중복 수치 값 파싱 시 전체 처리량의 64% 이상 속도 개선 확인  
  
### 대용량 파일 IO 가속  
  
- 기존 fread 방식 대신 **mmap**으로 전체 파일을 **메모리에 직접 매핑**  
- IO_read_file_to_string 함수로 입력 전체를 mmap, 대용량에서 6~35배 성능 개선 확인  
  
### 실전 벤치마크 및 성능 비교  
  
- Laptop 기준: 1,000,000+ 라인, 25MB 입력에서 **44ms**(토큰화만)  
- Desktop 기준: 동일 입력에서 **30ms** 달성(최대 848MB/s)  
- 타 lexer와 비교해 **최대 10배 이상**(0.3초 vs 2~13초)  
- 마이크로 벤치마크에서 각 최적화별 효과 수치화(예: bump allocator 도입 1.58배, 문자열 0 alloc 1.4~1.5배, 숫자 파싱 컴파일단계로 이관 2.8배 등)  
  
### 구현 전략 요약  
  
- **점프 테이블 기반 직접 분기**(threaded lexing)  
- **0 복사 윈도우 토큰 구조**  
- **상수 토큰 인터닝**  
- **bump allocator 기반 메모리 관리**  
- **토큰 해싱 및 사전 해시 비교**  
- **숫자·문자열 토큰 지연 파싱 및 인터닝**  
- **대용량 파일 mmap 처리**  
- 향후 과제로 **SIMD 활용**, **더 빠른 해싱 알고리듬**, **메모리 정렬·프리패치**, **입력별 점프 테이블 최적화** 등 제시

## Comments



_No public comments on this page._