매우 빠른 Lexer 구현 전략

• 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 활용, 더 빠른 해싱 알고리듬, 메모리 정렬·프리패치, 입력별 점프 테이블 최적화 등 제시