Spinel: Ruby AOT 네이티브 컴파일러

• Ruby 코드를 독립 실행형 네이티브 바이너리로 바꾸고, 전체 프로그램 단위 타입 추론과 C 코드 생성을 통해 최신 CRuby miniruby 대비 기하평균 약 11.6배 빠른 실행을 노림
• 컴파일 파이프라인은 Prism 기반 파서로 Ruby를 AST 텍스트로 바꾼 뒤 self-hosting 백엔드가 타입 추론과 C 코드 생성을 수행하고, 표준 C 컴파일러로 standalone 바이너리를 만듦
• 컴파일러 백엔드는 Ruby로 작성된 self-hosting 구조를 갖고 있으며, 부트스트랩 과정을 거쳐 gen2.c == gen3.c가 성립해 자기 자신을 다시 컴파일하는 루프가 닫힘
• 문자열 연결 평탄화, value-type promotion, loop-invariant length hoisting, static symbol interning, bigint 자동 승격 같은 컴파일 타임 최적화를 넣고, 내장 regexp 엔진과 bigint, 단일 헤더 런타임으로 외부 런타임 의존성을 줄임
• eval, 메타프로그래밍, Thread, 일반적인 인코딩 처리는 지원하지 않지만, Ruby 없이 실행되는 배포 형태와 계산 집약적 워크로드에서의 큰 성능 차이로 Ruby AOT 컴파일의 실용성이 드러남

동작 방식

• 컴파일 파이프라인은 Ruby 파일을 파싱해 AST 텍스트 파일로 직렬화한 뒤, 타입 추론과 C 코드 생성을 거쳐 표준 C 컴파일러로 네이티브 바이너리를 만드는 흐름으로 이루어짐
• spinel_parse는 Prism과 libprism을 사용해 Ruby를 파싱하며, C 바이너리가 없을 때는 CRuby와 Prism gem을 사용하는 대체 경로를 사용함
• spinel_codegen은 self-hosted 네이티브 바이너리로 동작하며, AST를 받아 타입 추론 + C 코드 생성을 수행함
• 최종 단계는 cc -O2 -Ilib -lm으로 C 소스와 런타임 헤더를 함께 컴파일하며, 결과 바이너리는 standalone 형태로 만들어짐

Self-Hosting

• 부트스트랩 체인은 CRuby + spinel_parse.rb로 AST를 만들고, CRuby + spinel_codegen.rb로 gen1.c와 bin1을 만든 뒤, 다시 생성된 바이너리로 gen2.c, gen3.c를 만드는 방식으로 닫힘
• gen2.c == gen3.c가 성립해 bootstrap loop가 닫혔음을 명시함
• 백엔드인 spinel_codegen.rb는 Spinel이 직접 컴파일 가능한 Ruby 부분집합으로 작성됨
  • classes, def, attr_accessor
  • if/case/while
  • each/map/select, yield
  • begin/rescue
  • String, Array, Hash 연산과 File I/O
• 백엔드에는 metaprogramming, eval, require를 넣지 않음

성능과 벤치마크

• 테스트는 74개 통과, 벤치마크는 55개 통과 상태임
• 28개 벤치마크 기준 기하평균은 최신 CRuby miniruby 대비 약 11.6배 빠름
• 비교 기준은 번들 gem이 없는 최신 CRuby miniruby 빌드이며, 시스템 ruby 3.2.3보다 더 빠른 기준과 비교했어도 계산 집약적 워크로드에서 우위가 큼

• 계산 성능

  • life는 20ms 대 1,733ms로 86.7배 빠름
  • ackermann은 5ms 대 374ms로 74.8배 빠름
  • mandelbrot는 25ms 대 1,453ms로 58.1배 빠름
  • fib 재귀 버전은 17ms 대 581ms로 34.2배 빠름
  • nqueens는 10ms 대 304ms로 30.4배 빠름
  • tarai는 16ms 대 461ms로 28.8배 빠름
  • tak는 22ms 대 532ms로 24.2배 빠름
  • matmul은 13ms 대 313ms로 24.1배 빠름
  • sudoku는 6ms 대 102ms로 17.0배 빠름
  • partial_sums는 93ms 대 1,498ms로 16.1배 빠름
  • fannkuch는 2ms 대 19ms로 9.5배 빠름
  • sieve는 39ms 대 332ms로 8.5배 빠름
  • fasta는 3ms 대 21ms로 7.0배 빠름

• 데이터 구조와 GC

  • rbtree는 24ms 대 543ms로 22.6배 빠름
  • splay tree는 14ms 대 195ms로 13.9배 빠름
  • huffman은 6ms 대 59ms로 9.8배 빠름
  • so_lists는 76ms 대 410ms로 5.4배 빠름
  • binary_trees는 11ms 대 40ms로 3.6배 빠름
  • linked_list는 136ms 대 388ms로 2.9배 빠름
  • gcbench는 1,845ms 대 3,641ms로 2.0배 빠름

• 실제 프로그램

  • json_parse는 39ms 대 394ms로 10.1배 빠름
  • bigint_fib 1000자리 계산은 2ms 대 16ms로 8.0배 빠름
  • ao_render는 417ms 대 3,334ms로 8.0배 빠름
  • pidigits는 2ms 대 13ms로 6.5배 빠름
  • str_concat는 2ms 대 13ms로 6.5배 빠름
  • template engine은 152ms 대 936ms로 6.2배 빠름
  • csv_process는 234ms 대 860ms로 3.7배 빠름
  • io_wordcount는 33ms 대 97ms로 2.9배 빠름

지원하는 Ruby 기능

• Core 기능으로 classes, inheritance, super, include 믹스인, attr_accessor, Struct.new, alias, module constants, 내장 타입에 대한 open classes를 지원함
• Control Flow로 if/elsif/else, unless, case/when, case/in 패턴 매칭, while, until, loop, for..in, break, next, return, catch/throw, &.를 지원함
• Blocks로 yield, block_given?, &block, proc {}, Proc.new, -> x { }, method(:name)를 지원하며, each, map, select, reduce, sort_by, times, upto, downto 같은 블록 메서드도 포함함
• Exceptions로 begin/rescue/ensure/retry, raise, 사용자 정의 예외 클래스를 지원함
• Types는 Integer, Float, String, Array, Hash, Range, Time, StringIO, File, Regexp, Bigint, Fiber를 포함함
  • 다형성 값은 tagged unions로 처리함
  • 자기 참조 데이터 구조를 위해 nullable object types T?를 둠
• Global Variables는 $name을 정적 C 변수로 컴파일하며, 타입 불일치는 컴파일 시점에 검출함
• I/O는 puts, print, printf, p, gets, ARGV, ENV[], File.read/write/open, system(), 백틱을 지원함

문자열, 정규식, 심볼, Bigint, Fiber

• Strings는 불변과 가변 문자열을 모두 다루며, <<는 자동으로 가변 문자열 sp_String으로 승격되어 O(n) 제자리 append를 수행함
• +, interpolation, tr, ljust/rjust/center와 표준 메서드가 두 문자열 표현 모두에서 동작함
• s[i] == "c" 같은 비교는 char 배열에 직접 접근하도록 최적화되어 할당 없이 처리됨
• a + b + c + d 같은 연결은 sp_str_concat4 또는 sp_str_concat_arr 한 번으로 평탄화되어 N-1개 적은 할당으로 바뀜
• 루프 안의 str.split(sep)는 같은 sp_StrArray를 반복 재사용하며, csv_process에서 400만 개 할당 제거가 일어남
• Regexp는 외부 의존성 없는 내장 NFA regexp engine을 사용함
  • =~, $1-$9, match?, gsub, sub, scan, split를 지원함
• Bigint는 mruby-bigint 기반 임의 정밀도 정수를 사용함
  • q = q * k 같은 루프 곱셈 패턴에서 자동 승격됨
  • 정적 라이브러리로 링크되며 실제 사용할 때만 포함됨
• Fiber는 ucontext_t 기반 협력적 동시성을 제공함
  • Fiber.new, Fiber#resume, Fiber.yield와 값 전달을 지원함
  • 자유 변수는 heap-promoted cells로 캡처함
• Symbols는 문자열과 분리된 sp_sym 타입으로 구현됨
  • :a != "a"를 유지함
  • 심볼 리터럴은 컴파일 시점에 intern되어 SPS_name 상수가 됨
  • String#to_sym은 필요할 때만 동적 풀을 사용함
  • 심볼 키 해시는 sp_SymIntHash를 사용해 문자열 대신 정수 키를 직접 저장하므로 strcmp와 동적 문자열 할당이 사라짐

메모리 관리와 값 타입

• 메모리 관리는 mark-and-sweep GC를 사용하며, size-segregated free lists, non-recursive marking, sticky mark bits를 포함함
• 작고 단순한 클래스는 자동으로 value types로 승격되어 스택에 배치됨
  • 조건은 스칼라 필드 8개 이하
  • 상속 없음
  • 파라미터를 통한 변경 없음
• 필드 5개짜리 클래스 100만 회 할당은 85ms에서 2ms로 줄어듦
• 값 타입만 사용하는 프로그램은 GC 런타임 자체를 전혀 내보내지 않음

최적화

• 전체 프로그램 단위 타입 추론을 바탕으로 여러 컴파일 타임 최적화를 수행함
• Value-type promotion으로 작은 불변 클래스는 C struct 스택 객체가 되어 GC 오버헤드를 없앰
• Constant propagation으로 N = 100 같은 단순 리터럴 상수는 cst_N 조회 없이 사용 지점에 직접 인라인됨
• Loop-invariant length hoisting으로 while i < arr.length는 루프 전에 길이를 한 번만 계산함
  • 본문에서 arr.push처럼 수신 객체를 바꾸면 이 hoist는 비활성화됨
• Method inlining은 짧고 재귀가 아닌 메서드 3문장 이하에 static inline을 붙여 gcc 인라이닝을 유도함
• String concat chain flattening은 연결 체인을 단일 호출로 줄여 중간 문자열 생성을 없앰
• Bigint auto-promotion은 자기 참조 덧셈이나 반복 곱셈 패턴을 bigint로 자동 승격함
• Bigint to_s 는 mruby-bigint의 mpz_get_str을 써서 divide-and-conquer O(n log²n) 으로 처리함
• Static symbol interning은 "literal".to_sym을 컴파일 타임 SPS_<name> 상수로 바꾸며, 동적 interning을 쓸 때만 런타임 풀을 넣음
• sub_range에서 길이가 hoist된 문자열은 sp_str_sub_range_len을 사용해 내부 strlen 호출을 건너뜀
• 루프 내부 line.split(",")는 기존 sp_StrArray를 재사용함
• Dead-code elimination은 -ffunction-sections -fdata-sections와 --gc-sections를 사용해 쓰이지 않는 런타임 함수를 최종 바이너리에서 제거함
• Iterative inference early exit는 param, return, ivar의 서명 배열 3개가 더 이상 바뀌지 않으면 고정점 루프를 즉시 중단함
  • 대부분 프로그램은 4회 전체 반복 대신 1~2회에 수렴함
  • bootstrap 시간은 약 14% 줄어듦
• parse_id_list byte walk는 self-compile 동안 약 12만 회 호출되는 AST 필드 리스트 파서를 s.split(",") 대신 s.bytes[i] 수동 순회로 바꿔 호출당 할당을 N+1개에서 2개로 낮춤
• 생성된 C 코드는 기본 경고 수준에서 warning-free build를 유지하며, 하니스는 -Werror를 사용해 회귀를 즉시 드러내게 함

아키텍처

• 저장소 구조는 다음 요소로 나뉨
  • spinel: POSIX shell 기반 원커맨드 래퍼 스크립트
  • spinel_parse.c: libprism에서 텍스트 AST로 가는 C 프런트엔드 1,061줄
  • spinel_codegen.rb: AST에서 C 코드로 가는 컴파일러 백엔드 21,109줄
  • lib/sp_runtime.h: 런타임 라이브러리 헤더 581줄
  • lib/sp_bigint.c: 임의 정밀도 정수 5,394줄
  • lib/regexp/: 내장 regexp 엔진 1,759줄
  • test/: 기능 테스트 74개
  • benchmark/: 벤치마크 55개
  • Makefile: 빌드 자동화
• 런타임 lib/sp_runtime.h는 GC, array/hash/string 구현과 기타 런타임 지원을 하나의 헤더 파일에 담음
• 생성된 C 코드는 이 헤더를 include하며, 링커는 libspinel_rt.a에서 필요한 부분만 가져옴
  • bigint
  • regexp engine
• 파서는 두 구현을 가짐
  • spinel_parse.c는 libprism을 직접 링크해 CRuby 없이 동작함
  • spinel_parse.rb는 Prism gem을 사용하는 CRuby fallback임
• 두 파서는 동일한 AST 출력을 만들며, spinel 래퍼는 가능하면 C 바이너리를 우선 사용함
• require_relative는 파싱 시점에 해결되어 참조된 파일이 인라인됨

제약 사항

• No eval: eval, instance_eval, class_eval은 지원하지 않음
• No metaprogramming: send, method_missing, 동적 define_method는 지원하지 않음
• No threads: Thread, Mutex는 지원하지 않으며 Fiber만 지원함
• No encoding: UTF-8과 ASCII를 가정함
• No general lambda calculus: 깊게 중첩된 -> x { }와 [] 호출은 다루지 않음

의존성과 실행 모델

• 빌드 시 의존성은 libprism C 라이브러리와 초기 부트스트랩용 CRuby임
• 런타임 의존성은 없으며, 생성된 바이너리는 libc + libm만 필요함
• 정규식은 내장 엔진을 써서 외부 라이브러리가 필요 없음
• Bigint는 내장되어 있지만 실제 사용할 때만 링크됨
• Prism은 spinel_parse가 사용하는 Ruby 파서임
  • make deps는 rubygems.org의 prism gem tarball을 내려받아 C 소스를 vendor/prism에 풂
  • 이미 prism gem이 설치되어 있으면 자동 감지함
  • PRISM_DIR=/path/to/prism으로 사용자 경로를 지정할 수도 있음
• CRuby는 초기 bootstrap에만 필요하며, make 이후에는 전체 파이프라인이 Ruby 없이 실행됨

프로젝트 이력

• Spinel은 처음에 C로 구현되었고, 규모는 18K lines였으며 c-version 브랜치에 남아 있음
• 이후 Ruby로 다시 작성한 ruby-v1 브랜치를 거쳤음
• 현재 master는 self-hosting 가능한 Ruby 부분집합으로 다시 작성된 버전임

라이선스

• MIT License를 사용함
• LICENSE 파일을 따름