08 — Bootstrap (부트스트랩)

현재 위치

7장은 a824a175("Check for stack overflow.", 스택 오버플로 검사), 2023-07-18 15:04:09에서 끝난다 — 컴파일러 자신의 소스는 모듈 단위로 하나씩, 스스로 읽어낼 수 있는 좁은 방언 안으로 압축되어 있다: 타입 클래스도, deriving도, 결합성과 우선순위 선언도 없고, 손으로 짠 Map, Integer 대신 Int를 쓴다. 이 마지막 커밋은 C 런타임의 고정 크기 인터프리터 스택 배열을, 새 -K 플래그로 크기를 정하는 malloc 할당 배열로 바꾼다. 3분 20초 뒤, 456ce17c가 도착한다. 이 두 커밋과 그 이전 모든 커밋이 쌓아 올린 사다리 — GHC가 컴파일러를 컴파일하고, 그 컴파일러가 스스로를 컴파일하고, C 런타임이 그 셀프 컴파일 결과를 실행하고, 바이트 단위 cmp가 두 결과가 일치하는지 확인하는 것 — 은 aux/bootstrapping-a-compiler.md의 주제 전체이며, 먼저 그것부터 읽어야 한다. 이 장은 그 사다리가 제 몫의 make 타깃을 얻고 누군가 실제로 그것을 오르는 순간 벌어지는 일을 서술한다.

무슨 일이 있었나

a824a175..298c9824 범위는 커밋 28개이며, 전부 Lennart Augustsson이 작성했고, 이틀 반에 걸쳐 있다: 07-18에 19개(15:07–23:19), 07-19에 4개(13:11–19:29), 07-20에 5개(11:20–14:58).

`456ce17c`: 이정표

456ce17c("Add bootstrap test.", 부트스트랩 테스트 추가), 15:07:29는 새 Makefile 타깃 하나를 추가한다 — 네 줄이다(456ce17c:Makefile 66–69행, 전문 인용):

bootcombtest:	$(BIN)/uhs uhs.comb
	$(BIN)/uhs -ilib -isrc -omain-uhs.comb  MicroHs.Main
	$(BIN)/eval -H10000000 -K1000000 -ruhs.comb --  -ilib -isrc -omain-comb.comb MicroHs.Main
	cmp main-uhs.comb main-comb.comb

첫 줄은 GHC로 빌드한 bin/uhs가 MicroHs.Main — 컴파일러 자신의 진입점이자, 그것이 임포트하는 src/MicroHs/lib 트리 전체 — 를 곧바로 main-uhs.comb로 컴파일하게 한다. 둘째 줄은 uhs.comb(별도의, 이미 빌드된 타깃: bin/uhs가 스스로를 컴비네이터 파일로 컴파일한 것)를 C 런타임 bin/eval에 넘기고, 그 컴비네이터 파일을 프로그램으로 실행하되 -- 뒤에 동일한 컴파일러 인자(-ilib -isrc -omain-comb.comb MicroHs.Main)를 붙이라고 지시한다. uhs.comb는 uhs를 eval이 이미 실행할 줄 아는 컴비네이터 항으로 옮긴 것 — 2장의 .comb 형식이며, 그 이후로 모양이 바뀌지 않았다. 그러므로 둘째 줄은 인터프리트된 컴파일러가 같은 소스를 두 번째로 컴파일해 main-comb.comb를 쓰는 것이다. 셋째 줄은 오라클이다: 특별 취급 없는 순수한 바이트 동등성 검사다. 네이티브로, GHC로 빌드한 컴파일러와, 컴비네이터로 옮겨져 C 인터프리터가 실행한 바로 그 컴파일러가, 자신의 소스를 컴파일해 같은 출력을 낸다면 그 사다리는 견고하다. cmp가 (어떤 의미론적 검사가 아니라) 왜 옳은 오라클(정답 판별 기준)인지, 그리고 병행하는 "local lib" 단인 bootboottest에 대한 완전한 설명은 aux 문서의 몫이며, 이 장이 할 일은 bootcombtest가 실제로 도는 것을 지켜보는 것이다.

`fc7a2ad7` / `f06bacb7` / `1876f4c1`: 컴파일러가 컴파일러를 컴파일하는 작업 부하의 실상

이전 모든 장의 "직접 해보기"가 하듯 짧은 테스트 파일 몇 개만으로 컴파일러를 돌리는 것과, 컴파일러를 자기 자신에게 돌리는 것 — src/와 lib/ 아래 .hs 파일 30개, 이 커밋 시점 합쳐서 73,856바이트(git ls-tree -r -l 456ce17c -- src lib로 센 값) — 는 서로 다른 작업 부하이며, 그 차이는 한 시간 안에 드러난다.

fc7a2ad7("Add comments.", 주석 추가), 15:36:42는 대체로 제목 그대로다: eval.c의 컴비네이터 case 옆에 붙는 짧은 /* ... */ 주석들(/* K x y = * x */ 같은 것들)이다. 하지만 추가된 줄 중 세 줄은, IO_BIND case 바로 위에 놓여 있는데, 장식이 아니다 — 실제로 예상되는 문제를 겨냥해 적어 둔 TODO 메모다(fc7a2ad7:src/runtime/eval.c 977–979행, 전문 인용):

      /* XXX could use associativity to avoid deep evalio recursion. */
      /* (m >>= g) >>= h    ===  m >>= (\ x -> g x >>= h) */
      /* BIND (BIND m g) h  ===  BIND m (\ x -> BIND (g x) h) == BIND m (C' BIND g h)*/

35분 뒤, f06bacb7("Commented out non-working alternative.", 동작하지 않는 대안을 주석 처리), 16:12:11은 수정을 시도한다 — 런타임이 아니라 라이브러리에서다. lib/System/IO.hs의 hGetContents는 파일 핸들을 한 글자씩 읽으며, 그 재귀 케이스는 평범한 do-바인드 >>=다: 한 글자를 읽을 때마다 파일의 나머지 부분을 감싸는 IO.>>=가 하나씩 더 중첩된다(f06bacb7:lib/System/IO.hs 126–135행, 전문 인용):

-- Strict hGetContents
hGetContents :: Handle -> IO String
hGetContents h = do
  c <- P.primHGetChar h
  case c == negate 1 of
    False ->
      do { cs <- hGetContents h; return (chr c:cs) }
      -- This should use less stack, but it doesn't work. :(
      --return (chr c : P.primPerformIO (hGetContents h))
    True  -> return ""

이곳이 정확히 위의 TODO 주석이 걱정하던 그 지점이다: src/MicroHs/Compile.hs의 readFilePath는 컴파일러가 컴파일하는 모든 모듈을 읽을 때 IO.hGetContents를 호출하므로, 문자 N개짜리 소스 파일은 그중 하나라도 실행되기 전에 N개가 중첩된 >>= 사슬을 만들어낸다. 주석 처리된 줄은 재귀적인 do-바인드 대신 P.primPerformIO로 이를 우회하려 하지만, 주석은 그것이 동작하지 않는다고 솔직히 적어 두었고, 그 시도는 지우지 않은 채 죽은 코드로 그 자리에 남는다.

그로부터 21초 뒤, 1876f4c1("Use associativity of IO.>>= to avoid deep evalio recursion.", IO.>>=의 결합법칙을 이용해 evalio의 깊은 재귀를 피하기), 16:12:32는 실제 메커니즘을 고친다 — TODO 주석이 있어야 한다고 말했던 바로 그 런타임에서다. 이 커밋 이전에는 evalio의 IO_BIND case가 m >>= g를 처리할 때 m에 대해 evalio를 재귀적으로 호출했다 — 그래서 왼쪽으로 중첩된 사슬 (m >>= g) >>= h의 경우, 바깥 바인드를 평가하는 것은 안쪽 것을 평가하기 위한 중첩된 C 함수 호출을 뜻했고, 사슬 안의 바인드 하나당 네이티브 스택 프레임이 하나씩 든다. 문자 하나를 손으로 읽으면 바인드 하나가 생기고, 소스 파일은 문자 수만큼의 중첩된 바인드를 만들어내는데, 이 재귀는 a824a175가 방금 키울 수 있게 만든 인터프리터 자신의 -K 크기 NODEPTR 스택이 아니라 C 프로세스 자신의 콜 스택에서 실행된다 — 그런 플래그가 없는 별개의 스택이다. 1876f4c1의 수정은 fc7a2ad7의 TODO 주석이 이미 이름 붙였던 대수 법칙 — (m >>= g) >>= h === m >>= (\x -> g x >>= h) — 을 이용해 그 항을 재귀로 파고드는 대신 다시 쓰고, 중첩 호출을 만드는 대신 goto top으로 평가기의 맨 위로 되돌아간다(1876f4c1:src/runtime/eval.c 980–998행, 전문 인용):

    case IO_BIND:
      CHECKIO(2);
      {
        /* Use associativity to avoid deep evalio recursion. */
        /* (m >>= g) >>= h      ===  m >>= (\ x -> g x >>= h) */
        /* BIND ((BIND m) g) h  ===  BIND m (\ x -> BIND (g x) h) == (BIND m) (((C' BIND) g) h)*/
        NODEPTR bm;
        NODEPTR bmg = evali(ARG(TOP(1)));
        GCCHECKSAVE(bmg, 4);
        if (TAG(bmg) == AP && TAG(bm = indir(FUN(bmg))) == AP && TAG(indir(FUN(bm))) == IO_BIND) {
          NODEPTR g = ARG(bmg);
          NODEPTR h = ARG(TOP(2));
          n = new_ap(bm, new_ap(new_ap(new_ap(combCC, combIOBIND), g), h));
          POP(3);
          goto top;
        }
      }

      x = evalio(ARG(TOP(1)));  /* first argument, unwrapped */

정확히 짚을 필요가 있다: 이것은 >>=가 틀린 답을 낸다는 보고가 아니며, 어떤 바인드가 계산하는 값도 전혀 바뀌지 않는다 — 모든 m >>= g는 여전히 m의 결과를 가지고 g의 계속(continuation)을 순서대로 실행하는 것으로 끝난다. 바뀌는 것은 왼쪽으로 중첩된 바인드 사슬을 평가하는 데 네이티브 스택 프레임이 몇 개나 드는가다: 이 커밋 이전에는 무한정 늘어나고(사슬이 깊을수록 바인드 하나당 하나씩), 이 커밋 이후에는 인터프리터 루프가 가능할 때마다 재귀 대신 반복하므로 일정하다. 이로써 닫히는 버그는 실제 소스 파일을 대상으로 한 글자씩 읽는 파일 리더 아래에서의 스택 깊이 위험이다 — 컴파일러가 스스로를 컴파일하는 것은, 이 위험을 실체화할 만큼 긴 IO 사슬을 만들어내는 이 프로젝트 역사상 첫 작업 부하다.

`5d58461f`: 정직하게 더 큰 정수로

결합법칙 수정 뒤 6분 48초, 5d58461f("Use bigger ints.", 더 큰 정수 쓰기), 16:19:20은 사용자 프로그램이 보는 하스켈 Int 타입에 관한 것이 아니다 — 그것은 이미 6/7장의 다이어트에서 머신 폭으로 좁혀져 있었다. 대신 런타임 자신의 집계 카운터들을 int에서 int64_t로 넓힌다: num_reductions, num_gc, num_marked, max_num_marked, start_size, 그리고 init_nodes, scan, gc, parse_top 안의 힙 인덱싱 루프 변수 여럿이다(5d58461f:src/runtime/eval.c 121–122행, 인용):

int64_t num_reductions = 0;
int64_t num_gc = 0;

테스트 프로그램의 축약 횟수와 GC 횟수는 32비트 안에 여유 있게 들어간다. 자기 소스 수천 줄을 컴파일하는 컴파일러는 그 여유 안에 오래 머물지 못한다. 프로그램 의미론에서 사용자에게 보이는 것은 아무것도 바뀌지 않는다 — 런타임 자신의 통계가 조용히 오버플로되기 전까지 얼마나 멀리 셀 수 있는가만 바뀔 뿐이다.

`1a84b483`: 힙이 2%까지 줄면 포기하기

6ca78e8a("Cleanup", 정리), 23:16:14, 그리고 8초 뒤 1a84b483 ("Give up when heap is down to 2%", 힙이 2%까지 줄면 포기), 23:16:22가 같은 긴 저녁의 끝자락에 도착한다. GC의 gc() 함수는 이미 마크-스윕 패스마다 몇 개의 셀이 살아남았는지 추적하고 있었다; 이 커밋은 그 수를 알게 된 직후에 검사 하나를 추가한다 (1a84b483:src/runtime/eval.c 334–338행, 전문 인용):

  if (num_marked > max_num_marked)
    max_num_marked = num_marked;
  int64_t free = heap_size - heap_start - num_marked;
  if (free < heap_size / 50)
    ERR("heap exhausted");

heap_size / 50은 정확히 힙의 2%다. 이것은 더 똑똑한 컬렉터도, 더 큰 컬렉터도 아니다 — 힙 크기는 여전히 -H가 말하는 그대로다 — 이것은 정직한 포기다: GC 패스 한 번이 끝난 뒤 힙의 여유가 2% 미만으로 남으면, 런타임은 갈수록 더 자주 모으면서 갈수록 더 적은 이득을 얻는 것을 계속하거나 진단 하나 없이 할당 도중 소진되는 대신, 멈추고 "heap exhausted"를 보고한다. 이는 런타임이 처음으로 그것을 찾아낼 만큼 큰 작업 부하 아래서 자신의 한계와 마주치는 것이다 — 그 한계가 문제가 된다는 것을 발견한 바로 그 커밋에서 정직하게 명시된 상한이다.

`ee853660` / `04a4bbe4` / `8ad7094c`: 실제 작업 부하가 생긴 뒤에야 나온 성능 작업

이틀 뒤 07-20, ee853660("Specialize the Map to StringMap.", Map을 StringMap으로 특수화), 11:20:05는 src/MicroHs/Map.hs — 7장이 매 호출마다 명시적 동등성 인자를 받도록 만든 범용 Map k v — 를 지우고, Compile.hs, Desugar.hs, Main.hs, Translate.hs에서 그것을 쓰던 모든 자리를 src/MicroHs/StringMap.hs로 바꾼다. 이는 String 키에 특화되어, 매 호출 지점에서 넘기는 대신 eqString을 안에 박아 넣은 버전이다: ee853660:src/MicroHs/Compile.hs 79행은 case M.lookup nm ch of로 읽히는데, 바로 앞 커밋의 같은 줄은 case M.lookup eqIdent nm ch of였다. 25분 뒤 04a4bbe4("Sort in frequency order.", 빈도 순으로 정렬), 11:45:47은 컴파일러가 읽거나 쓰는 모든 컴비네이터· 프리미티브 연산 이름에 대해 문자열 단위로 선형 탐색되는 두 조회 테이블의 순서를 바꾼다: .comb 파일의 토큰마다 parse()가 훑는 eval.c의 primops[]와, Translate.hs의 primTable이다. 두 diff 모두 같은 근거를 밝힌 주석을 덧붙인다(04a4bbe4:src/runtime/eval.c 169–190행과 04a4bbe4:src/MicroHs/Translate.hs 36–51행, 전문 인용, ...는 각 컴비네이터 테이블 뒤에 생략된 프리미티브 연산 항목을 나타낸다):

/* We use linear search in this, because almost all lookups
 * are among the combinators.
 */
struct {
  char *name;
  enum node_tag tag;
  NODEPTR node;
} primops[] = {
  /* combinators */
  /* sorted by frequency in a typical program */
  { "B", B },
  { "O", O },
  { "K", K },
  { "C'", CC },
  { "C", C },
  { "T", T },
  { "S'", SS },
  { "P", P },
  { "I", I },
  { "S", S },
  { "Y", Y },
  { "B'", BB },
  ...

-- Use linear search in this table.
-- 99% of the hits are among the combinators.
primTable :: [(String, Any)]
primTable = [
  ("B", primitive "B"),
  ("O", primitive "O"),
  ("K", primitive "K"),
  ("C'", primitive "C'"),
  ("C", primitive "C"),
  ("T", primitive "T"),
  ("S'", primitive "S'"),
  ("P", primitive "P"),
  ("I", primitive "I"),
  ("S", primitive "S"),
  ("Y", primitive "Y"),
  ("B'", primitive "B'"),
  ...

두 테이블 모두 B와 O를 앞으로 옮기고, S, Y, B' — 1장의 브래킷 추상화가 실제로는 가장 드물게 만들어내는 컴비네이터들 — 을 뒤로 미는데, 근거는 인용된 측정치가 아니라 일반적인 빈도에 대한 한 줄짜리 주석이다. 이 둘 사이, 07-18 16:50:16(재귀 수정과 같은 저녁이지, 재정렬과 같은 날은 아니다)에 8ad7094c("Add profiling option.", 프로파일링 옵션 추가)는 Makefile에 PROF 변수를 추가해, bootuhs의 빌드·링크 단계에 연결한다: GHC 자체의 -prof -fprof-auto 코스트 센터 프로파일러를, 컴파일러의 "local lib" GHC 빌드에 적용한 것이다. 아래 이 장 자신의 "직접 해보기"에서 빌드해 돌려 보면, 그 프로파일러 보고서는 Text.ParserComb.(>>=), Data.List.(++), Text.String.eqString이 지배한다 — 컴파일러 자신의 파서와 라이브러리 안, 네이티브 GHC 바이너리인 bootuhs에서 측정한 하스켈 수준 코스트 센터들이다. 어떤 컴비네이터 이름 — S, K, B, O — 이 .comb 파일에 가장 자주 나오는지, 즉 04a4bbe4의 테이블이 정렬 기준으로 삼는 것에 대해서는 아무 말도 해주지 않는다; 그것은 C 런타임 eval과 번역기 Translate.hs의 속성이며, GHC 프로파일러는 둘 중 어느 쪽도 건드리지 않는다. 짐작이 아니라 직접 확인한 결과: 이 범위의 어떤 커밋 메시지도, 코드 주석도, 파일도 둘을 연결 짓지 않는다. 같은 48시간 동안 나온 두 개의 독립적인 성능 개입으로 읽힌다 — 하나는 컴파일러 자신의 하스켈을 계측하고, 다른 하나는 완전히 다른 프로그램 안의 선형 탐색을 손으로 튜닝한다 — 한쪽이 다른 쪽에 재료를 대주는 파이프라인이 아니다.

`db418344`: 타입 파싱, 파싱만

db418344("Add type parsing.", 타입 파싱 추가), 18:46:43는 6장이 type Type = Expr로 납작하게 만든 이래 처음으로 Parse.hs에 진짜 타입 구문을 부여한다. 새로운 EType은 타입 변수, 생성자 적용, 단일화 변수를 구분하며, ETypeScheme은 forall을 더한다 (db418344:src/MicroHs/Parse.hs 99–107행, 전문 인용):

-- No higher order type variables (yet)
data EType
  = TVar Ident
  | TConstr Ident [EType]
  | TUVar Int
  --Xderiving (Show)

data ETypeScheme = ETypeScheme [Ident] EType
  --Xderiving (Show)

Sign :: Ident -> ETypeScheme -> EDef는 이제 타입이 없는 Expr 별칭 대신 실제로 파싱된 타입 스킴을 담는다. 하지만 이 커밋이 이 점에서 손대지 않은 Desugar.hs는 여전히 모든 Sign을 아무것도 아닌 것으로 바꾼다(db418344:src/MicroHs/Desugar.hs 151행, 인용): Sign _ _ -> []. 타입은 파서가 이해하고 EDef AST가 담을 수 있는 구문일 뿐, 그 뒤 어디서도 아직 읽지 않는다 — 검사기도, 추론도, 경고조차도 없다. 3장이 컴파일러의 가장 초기 타입 시그니처에 부여했던 것과 같은 "파싱만" 하는 자세가 한 걸음 더 나아간 것이다; 그렇게 파싱된 타입이 결국 무엇에 쓰이는가는 이 장이 아니라 9장의 주제다.

`298c9824`: `uhs`가 `mhs`가 되다 — 실제로 이름이 바뀌는 것

이 범위의 마지막 커밋, 298c9824("Rename uhs to mhs.", uhs를 mhs로 이름 바꾸기), 14:58:46은 정확히 두 파일만 건드린다: Makefile과 tests/Makefile이다. 어떤 파일도 git mv되지 않고, 어떤 모듈도 이름이 바뀌지 않는다 — MicroHs.Main은 이미 그 이름이었다. 바뀌는 것은, 리터럴 문자열 uhs가 빌드 산출물의 이름으로 쓰이던 모든 곳에 치환되는 새 Makefile 변수 MHS=mhs다: 바이너리($(BIN)/uhs가 $(BIN)/$(MHS)가 된다), GHC로 빌드한 로컬 라이브러리 짝(bootuhs가 boot$(MHS)가 된다), 셀프 컴파일된 컴비네이터 파일(uhs.comb가 $(MHS).comb가 된다), 가짜 테스트 타깃(uhstest가 $(MHS)test가 된다), 그리고 tests/Makefile에서는 UHS 변수 자체가 MHS=../bin/mhs로 이름이 바뀐다. 프로젝트는 자신의 이름 — MicroHs — 을 빌드 어휘 안에서 먼저 얻는다. 모든 곳에서 한 번에 얻는 것은 아니다: 이 커밋 시점에 src//lib//ghc/를 grep -rn uhs로 훑으면 여전히 한 군데가 걸린다. src/MicroHs/Main.hs 자신의 사용법 메시지로, 이 커밋으로도 바뀌지 않는다(298c9824:src/MicroHs/Main.hs 23행, 인용): error "Usage: uhs [-v] [-r] [-iPATH] [-oFILE] ModuleName". 이 커밋으로 이름이 바뀐 컴파일러는 여전히 자기 사용자들 앞에서는 스스로를 uhs라 부른다.

밝히지 않은 부가 사항

커밋 두 개가 제목이 말하는 것보다 더 많은 것을 담고 있다. 787d8842("Add an (unused) Data.Map", (쓰이지 않는) Data.Map 추가), 14:48:47은 약속한 파일 — 177줄, 균형 잡힌 진짜 2-3 트리 구현이며, 빌드는 되지만 어떤 호출 지점에도 연결되지 않는다(Makefile은 이를 bootuhs의 일부로만 컴파일할 뿐, 의미 있는 어느 곳에서도 임포트하지 않는다) — 을 실제로 추가하지만, 같은 커밋은 Parse.hs에 leIdent 헬퍼도 추가하고, StringMap.hs의 타입 시그니처들을 새로 주석 처리된 Data.Map 기반 대안 구현과 나란히 새 꼬리 블록으로 옮기는데, 제목에는 둘 다 언급되지 않는다. 8e2f7109("Change test targets.", 테스트 타깃 바꾸기), 07-18 16:25:51은 대체로 제목 그대로 한다 — alltest/everytest 타깃을 이름 바꾸고 추가한다 — 하지만 그 bootcombtest diff는 456ce17c가 1시간 18분 전에 추가했던 eval 호출에서 -K1000000을 조용히 빼기도 한다(8e2f7109:Makefile 67행, 인용): $(BIN)/eval -H10000000 -ruhs.comb -- -ilib -isrc -omain-comb.comb MicroHs.Main — -K1000000이 없고, 커밋 제목에도 언급이 없다 — 그 이후로 bootcombtest는 eval의 내장 기본값인 인터프리터 스택 셀 10,000개로 돌아가게 된다 — 명시적 안전 여유를 백 분의 일로 줄인 것이, 밝혀지지 않은 채로. 장부의 반대편도 있다: acf40ed4("Remove junk", 쓰레기 제거), 07-19 13:11:39은 A.hs와 Test.hs를 지우는데, 이는 7장 범위에서 59b8b1ab가 무관한 제목 "Fix name"(이름 고치기) 아래 밝히지 않고 추가했던 바로 그 두 파일이다. 두 주 뒤, 같은 프로젝트는 diff가 실제로 하는 일을 정직하게 말하는 제목 아래서 그 파일들을 지운다.

왜 중요한가

456ce17c는 기능 하나가 착지한 것이 아니라 고정점 하나가 닫히는 것이다. bootcombtest가 존재하고 통과하는 순간, 컴파일러 자신의 속도는 부차적인 관심사이기를 멈추고 가장 중요한 벤치마크가 된다: 런타임이나 컴파일러를 더 빠르게 만드는 모든 커밋은 다음 부트스트랩 실행도 더 빠르게 만들며, 부트스트랩 실행은 이제 프로젝트 전체 테스트 스위트에서 가장 무겁고 가장 대표적인 작업 부하다. 이는 커밋 순서 자체에서 드러난다. 이 장의 모든 성능 개입 — int64_t 확장, 힙 2% 포기, StringMap, 빈도순 정렬 조회 테이블 — 은 전부 456ce17c 이후에 오며, 그중 여럿은 몇 시간 안에, 그 이전에는 하나도 없다. 런타임은 이 저장소의 첫 커밋(ccb31388, 2023-05-25)부터 a824a175까지 54일 동안, 카운터도, GC 임계값도, 자료 구조도, 조회 순서도 손보는 커밋이 단 하나도 없었다 — 앞서 "optimiser"라는 제목을 단 커밋들(ae2a1403, d2956ee8 등)은 완전히 다른 관심사로, Exp.hs의 브래킷 추상화 출력에 대한 코드 품질 손질, 즉 aux/bracket-abstraction.md의 주제이지 런타임 엔지니어링이 아니다. 셀프 컴파일이야말로 마침내 런타임에 엔지니어링할 가치가 있는 작업 부하를 준 것이고, 프로젝트는 그것이 존재하게 되자마자 곧바로 엔지니어링했지, 그 전에 하지 않았다.

실험 노트 여백

실제 셀프 컴파일을 돌려서 가장 직접적으로 강제된 세 개의 수정 — 1876f4c1의 결합법칙 재작성, 5d58461f의 더 넓은 카운터, 1a84b483의 힙 포기 — 는 가장 멀리 떨어진 경우(1876f4c1부터 1a84b483까지) 7시간 3분 50초 차이로 도착하며, 가장 가까운 쌍(f06bacb7부터 1876f4c1까지)은 21초 차이다.
StringMap/빈도순 정렬/프로파일링 묶음(8ad7094c, ee853660, 04a4bbe4)은 처음부터 끝까지 42시간 55분 31초에 걸쳐 있다 — 마지막 둘이 처음 것과 다른 날짜에 도착함에도 불구하고, 여전히 456ce17c로부터 이틀 안이다.
d8d8856b("Add version string to compiler binary.", 컴파일러 바이너리에 버전 문자열 추가), 07-20 11:53:35은 모든 .comb 파일에 다섯 바이트짜리 헤더("v1.0\n")를 부여하고, eval의 main에 파일의 나머지를 파싱하기 전에 그 바이트들을 읽어 맞춰 보는 checkversion 검사를 추가한다 — 호환되지 않는 컴파일러 버전이 만든 .comb 파일을 실행하는 상황에서 ERR("version mismatch") 하나만큼 떨어져 있다. 같은 날 오후의 787d8842("Add an (unused) Data.Map")는 이 프로젝트가 허용하는 정직한 종류의 사변적 코드다: 빌드되고, 컴파일되지만, 결코 호출되지 않으며, 제목이 그렇다고 말한다.

직접 해보기

기준점: 456ce17c("Add bootstrap test."), 2023-07-18 15:07:29 — 이 연습이 실행하는 bootcombtest 타깃을 추가하는 커밋이다. 관례(참고: 00-overview.md):

git worktree add /tmp/mhs-456ce17c 456ce17c
cd /tmp/mhs-456ce17c

타깃이 필요로 하는 두 바이너리를 쓰인 그대로 빌드한다. 이 프로젝트의 flake 툴체인(GHC 9.8.4)에는 패치가 필요 없다:

mkdir -p bin
nix develop $MICROHS -c make bin/uhs
nix develop $MICROHS -c make bin/eval

[...]
[12 of 12] Linking bin/uhs

gcc -Wall -O3 src/runtime/eval.c -o bin/eval

(이전 모든 장의 빌드 노트가 이미 짚은 head/tail에 대한 같은 -Wx-partial 경고가 bin/uhs 빌드 중에도 나타난다; 생략.)

이제 핵심 장면 — bootcombtest 자신이 실행하는 그대로 사다리 전체를, 단계별로 시간을 재며 실행한다:

nix develop $MICROHS -c bash -c 'time bin/uhs -ilib -isrc -ouhs.comb MicroHs.Main'

real	0m0.964s

nix develop $MICROHS -c bash -c 'time bin/uhs -ilib -isrc -omain-uhs.comb MicroHs.Main'

real	0m0.942s

nix develop $MICROHS -c bash -c 'time bin/eval -H10000000 -K1000000 -ruhs.comb -- -ilib -isrc -omain-comb.comb MicroHs.Main'

real	0m21.273s

nix develop $MICROHS -c cmp main-uhs.comb main-comb.comb

cmp는 아무것도 출력하지 않고 종료 코드 0으로 끝난다: main-uhs.comb와 main-comb.comb — 각각 68,799바이트 — 는 바이트 단위로 동일하다. GHC로 빌드한 bin/uhs가 자신의 소스를 컴파일했고, 그 같은 소스를 컴비네이터로 옮겨 bin/eval이 인터프리트해 다시 컴파일했으며, 두 실행 모두 정확히 같은 출력을 냈다. 그것이 bootcombtest가, 그것을 추가한 바로 그 커밋에서, 전부 실제로 실행되는 모습이다 — 스택 오버플로도, 패치도 없이. (나는 또한 이 범위의 마지막 커밋 298c9824에서 bin/uhs 대신 bin/mhs로 사다리 전체를 다시 실행해 보았다: 거기서도 main-mhs.comb와 main-comb.comb가 일치했고, 각각 75,052바이트, 인터프리트 단계는 20.715초였다 — 그러니 1876f4c1이 닫은 네이티브 스택 위험이 무엇이든, 이 특정 셀프 컴파일에 대해서는 이 환경의 기본 8MB ulimit -s가 그것을 유발하는 위험이 아니다; 수정은 실재하고 위의 메커니즘은 diff에서 직접 읽어낸 것이지만, 나는 그것이 막는 크래시를 재현해내지는 못했다.)

연습 문제 1: eval로 실행한 셀프 컴파일과 GHC 빌드 버전의 시간 비교

위의 time 실행 세 번이 이미 이 기계에서 이 질문에 답한다: GHC로 빌드한 bin/uhs는 MicroHs.Main을 1초에 한참 못 미치는 시간에 컴파일한다(실행마다 0.942초–0.964초); 같은 컴파일러의 컴비네이터 번역본을 인터프리트하는 bin/eval이 동일한 컴파일을 수행하는 데는 21.273초가 걸린다 — 22.6배의 감속이다(21.273 ÷ 0.942): 네이티브 코드 대 같은 컴비네이터 항을 걷는 그래프 축약 인터프리터의 대결이며, 이전 모든 장의 time 타깃이 측정하던 짧은 테스트 프로그램이 아니라 이 컴파일러 자신의 소스를 상대로 처음 재는 값이다. 소스가 이틀, 커밋 27개만큼 자라난 뒤인 298c9824에서 같은 3단계 타이밍을 재면(여기서는 main-uhs.comb가 68,799바이트, 그쪽은 main-mhs.comb가 75,052바이트로 대략 9% 더 큰 프로그램) 0.926초 / 0.890초 / 20.715초가 나온다 — 바이트당 처리량이 약간 더 낫다(75,052 ÷ 20.715 ≈ 3,624B/s 인터프리트, 여기서는 68,799 ÷ 21.273 ≈ 3,234B/s) — 이 앞뒤 한 쌍만으로 이 범위의 어떤 성능 커밋이 정확히 얼마를 기여했는지 가려낼 수는 없지만, ee853660/04a4bbe4의 조회 테이블 작업이 순수한 오버헤드가 아니라 스스로 값어치를 하고 있다는 것과 부합한다.

연습 문제 2: `uhs.comb`의 바이트 하나 손상시키기

uhs.comb의 텍스트 형식은 모든 컴비네이터를 $로 시작하는 토큰으로 이름 붙인다; 그런 토큰 하나를 찾아 바이트 하나를 뒤집는다:

(python3 역시 devShell의 buildInputs에는 없다 — 1장의 diff와 마찬가지로, nix develop이 넘겨주는 PATH에서 호스트 시스템이 무엇을 제공하든 그것을 쓴다.)

nix develop $MICROHS -c python3 -c "
data = bytearray(open('uhs.comb','rb').read())
assert data[53:54] == b'C'
data[53] = ord('Z')
open('uhs-corrupt.comb','wb').write(bytes(data))
"

바이트 오프셋 53(0부터 셈)은 파일 시작 근처의 \$C 토큰 안에 놓여 있다; 위의 수정은 이를 존재하지 않는 컴비네이터 이름인 \$Z 로 바꾼다. bootcombtest의 가운데 줄이 하듯 eval에게 이를 실행하라고 시킨다:

nix develop $MICROHS -c bin/eval -H10000000 -K1000000 -ruhs-corrupt.comb -- -ilib -isrc -ocorrupt-out.comb MicroHs.Main

eval: bad primop Z
ERR: no primop

종료 코드 1이다. parse()의 프리미티브 연산 테이블 조회(나중에 04a4bbe4가 재정렬하는 바로 그 선형 탐색)는 Z라는 이름의 항목을 찾지 못하고, fprintf/ERR 호출이 약속하는 진단을 정확히 출력하며, 축약이 단 한 번도 일어나기 전에 실행 전체가 중단된다 — 손상된 바이트 하나가, 다음 부트스트랩으로 조용히 잘못 컴파일되어 들어가는 대신, 파싱 시점에 붙잡힌다.

연습 문제 3: 프로파일링 플래그와 빈도 순서 — 짐작이 아니라 확인

8ad7094c의 PROF 플래그는 456ce17c 기준점에서는 아직 존재하지 않고, 04a4bbe4의 재정렬된 primops[] 테이블도 마찬가지다; 이 연습에는 둘 다 필요하므로, 둘이 마지막으로 함께 나타나는 커밋인 04a4bbe4 자신에 두 번째 워크트리를 쓴다:

git worktree add /tmp/mhs-04a4bbe4 04a4bbe4
cd /tmp/mhs-04a4bbe4
mkdir -p bin
nix develop $MICROHS -c make PROF="-prof -fprof-auto" bin/bootuhs

[...]
ghc -prof -fprof-auto -hide-all-packages -o bin/bootuhs ghc-boot/*.o ghc-boot/*/*.o

nix develop $MICROHS -c bin/bootuhs -ilib -isrc -omain-boot.comb +RTS -p -RTS MicroHs.Main

이는 bootuhs.prof, GHC 자신의 코스트 센터 보고서를 쓴다(상위 항목만 추림):

COST CENTRE      MODULE            SRC                                      %time %alloc

>>=.\.xss        Text.ParserComb   src/Text/ParserComb.hs:80:15-69           18.8    7.4
++               Data.List         lib/Data/List.hs:(22,1)-(25,26)           10.1   23.9
>>=.\            Text.ParserComb   src/Text/ParserComb.hs:(78,5)-(82,68)      9.9   17.0
eqString         Text.String       lib/Text/String.hs:(101,1)-(110,44)        8.7   12.9
runP             Text.ParserComb   src/Text/ParserComb.hs:(66,1)-(68,12)      6.3    0.0
foldr.rec        Data.List         lib/Data/List.hs:(57,5)-(60,30)            4.2    2.8
...

이 목록을 있는 그대로 읽으면: Text.ParserComb의 >>=, Data.List.(++), Text.String.eqString이 지배한다 — 컴파일러 자신의 파서와 프렐류드 안에 있는 하스켈 함수들로, "local lib" 빌드를 실행하는 네이티브 GHC 바이너리 bootuhs에서 측정한 값이다. 컴비네이터 이름은 — S, K, B, O, 04a4bbe4의 primops[]/primTable이 재정렬하는 그 이름들은 — 이 보고서 어디에도 단 하나도 나타나지 않는데, 그것들은 완전히 다른 프로그램에 속하기 때문이다: eval.c의 인터프리터와 Translate.hs의 번역기이며, bootuhs의 GHC 프로파일러는 둘 중 어느 쪽도 실행하지 않는다. "프로파일링 플래그를 빈도 순서와 연결 짓고 싶은" 직감은 이 실행 결과 앞에서 살아남지 못한다: 그것들은 같은 48시간 동안 우연히 함께 도착한, 서로 다른 두 프로그램을 겨냥한, 별개의 두 성능 개입이다. 이 보고서가 독립적으로 뒷받침하는 것은 채 이틀도 되지 않은 앞선 시점의 8f361a0a의 "Fix stupid eqString"(멍청한 eqString 고치기)이다 — eqString 하나만으로 이 실행 시간의 8.7%와 할당량의 12.9%를 차지하며, 이만한 크기의 작업 부하가 처음으로 드러내는 딱 그런 종류의 핫패스 비용이다.

두 워크트리를 모두 정리한다:

git worktree remove --force /tmp/mhs-456ce17c
git worktree remove --force /tmp/mhs-04a4bbe4

MicroHs에서 배우기 (Learning from MicroHs)

456ce17c: 이정표

fc7a2ad7 / f06bacb7 / 1876f4c1: 컴파일러가 컴파일러를 컴파일하는 작업 부하의 실상

5d58461f: 정직하게 더 큰 정수로

1a84b483: 힙이 2%까지 줄면 포기하기

ee853660 / 04a4bbe4 / 8ad7094c: 실제 작업 부하가 생긴 뒤에야 나온 성능 작업

db418344: 타입 파싱, 파싱만