LZ77에서 C보다 6.6배 빠른 언어를 만든 방법 — Assembly로부터 부트스트랩(Bootstrapped)하기

고지 사항: 이 프로젝트는 AI의 도움(Claude)을 받아 제작되었습니다. 저는 Jda라는 시스템 프로그래밍 언어(Systems programming language)를 처음부터 구축했습니다. 툴체인(Toolchain) 어디에도 C, Rust, Python을 전혀 사용하지 않았습니다. 컴파일러는 순수 x86-64 어셈블리(Assembly)로부터 부트스트랩(Bootstrapped)되었으며, 완전히 셀프 호스팅(Self-hosted)되고, 자기 자신을 바이트 단위로 동일한(Byte-identical) 바이너리로 컴파일합니다.

주요 결과

LZ77 압축(1 MB 데이터)에서 Jda는 다음과 같은 성능을 기록했습니다:

• C (clang -O2): 1,830ms — Jda가 6.6배 더 빠름
• Rust (rustc -O): 2,185ms — Jda가 7.9배 더 빠름
• Go: 2,721ms — Jda가 9.8배 더 빠름

Jda는 Apple Silicon에서 Rosetta 2 x86-64를 통해 실행 중이며, 네이티브 ARM64조차 아닙니다.

전체 벤치마크 표 (Apple Silicon, ms, 낮을수록 좋음)

Jda는 네이티브 ARM64로 컴파일된 언어들과의 5개 벤치마크 중 3개에서 승리했습니다.

왜 LZ77이 C보다 6.6배 더 빠른가?

두 가지 컴파일러 최적화(Compiler optimizations)가 이 역할을 수행합니다:

1. MOD→AND 강도 감소 (Strength reduction)
   LZ77 해시 체인(Hash-chain)은 4096개의 엔트리를 가진 윈도우(Window)를 사용합니다. 모든 반복(Iteration)은 다음을 계산합니다:
   hash % 4096
   Jda의 컴파일러는 이를 다음과 같이 다시 작성합니다:
   hash & 4095
   이를 통해 내부 루프(Inner loop)에서 모든 IDIV 명령어를 제거합니다. C, Rust, Go는 모두 이 패턴에서 더 느린 나눗셈 형태를 유지합니다.

2. 루프 불변 코드 이동 (Loop-Invariant Code Motion, LICM)
   최대 매치 길이(Maximum match length)와 첫 번째 바이트 필터(First-byte filter)는 루프 불변(Loop-invariant) 요소입니다. Jda는 이를 내부 매치 스캔(Inner match scan) 밖으로 끌어올려(Hoists), 반복 횟수를 절반으로 줄입니다.

Sudoku: C와 Rust보다 1.5배 빠름

핫 패스(Hot path)는 후보군에 대한 비트마스크 스캔(Bitmask scan)입니다. Jda의 MOD→AND 핍홀(Peephole) 최적화, 복사 전파(Copy propagation), 그리고 루프 레지스터 승격(Loop register promotion)은 gcc/clang이 메모리에 유지하는 불필요한 작업을 제거합니다.

셀프 호스팅 (Self-Hosting)

컴파일러는 다음과 같이 부트스트랩됩니다:
Assembly → jda0 → jda1.jda 컴파일 → jda1 ↓ jda1.jda 컴파일 → jda1_sh2 ↓ jda1.jda 컴파일 → jda1_sh3 ↑ (sh2와 바이트 단위로 동일)
고정점(Fixed point)에 수렴했습니다.

388개의 적합성 테스트(conformance tests) 통과.

컴파일 속도 (Compile Speed)

Rust보다 33배 빠릅니다. 단일 패스 컴파일러(Single-pass compiler)이며, 링커(linker)와 중간 파일(intermediate files)을 사용하지 않습니다.

특징 (What It Has)

• GC(Garbage Collection) 없음 — alloc_pages를 이용한 수동 메모리 관리
• Goroutine 스타일의 그린 스레드(green threads) + 채널(channels)
• 텐서(Tensors), 자동 미분(autograd), 신경망(neural networks)
• AVX-512 / CUDA / ROCm 가속
• 117개의 표준 라이브러리(stdlib) 패키지
• 풀스택 웹 프레임워크 (Jda Forge)
• VS Code + JetBrains 플러그인

사용해 보기 (Try It)

bash
curl -sSf https://jdalang.org/install.sh | sh

• GitHub: https://github.com/jdalang/jda-lang
• 웹사이트: https://jdalang.org
• 벤치마크: https://jdalang.org/benchmarks/complex-benchmarks/

모든 벤치마크 소스 코드는 저장소(repo)에 포함되어 있습니다. 각 문제에 대해 6가지 구현체(C, Rust, Go, Jda, Ruby, Python)를 나란히 비교할 수 있습니다. 언어 설계, 벤치마크 방법론, 혹은 잘못되었거나 누락된 부분에 대한 피드백을 환영합니다.