백만 요소

Part 마지막 probe는 수중에서 가장 무뚝뚝한 물음을 물었다: prelude의 리스트 함수들을 받아, 1만 요소, 다음에 10만, 다음에 100만을 먹이고, 어느 것이 돌아오는지 적는다. 4 backend와 메모리 모델을 가진 언어에는 격 낮게 느껴지는 종류의 측정이고 —— 그래서야말로 한 번도 해지지 않았었다. 답은 두 카테고리로 도착했다: 이차함수적인 함수와, 꼬리 재귀가 아닌 함수. sort는 둘 다였다. prelude의 삽입 정렬 —— 리스트가 열 개의 설정 항목을 갖던 시대의 정직한 플레이스홀더 —— 는 1만 요소에서 몇 분 걸렸고, 10만에서는 느려지기 전에 스택을 날렸다.

네 번째 매복

대체는, 리스트 라이브러리에 배열을 갖지 않는 언어를 위해 설계된 안정 merge sort였다: 포인터 추적이 아니라 길이로 분할, 반전 accumulator를 통한 merge, 모든 함수를 꼬리 재귀로 기술. 그래도 20만 요소에서 떨어졌다. 모든 함수가 꼬리 재귀로 보이고, 생성된 C는 호출이 꼬리 위치에 있음을 확인했고, 그래도 스택은 자랐다. address sanitizer가 밥값을 벌어, 분할 함수를 가리켰다 —— 두 리스트의 tuple을 반환하는, 그 함수다. struct를 값으로 반환하는 함수는 sret 형식으로 컴파일된다: 호출하는 쪽이 자기 프레임 안 영역으로의 숨은 포인터를 넘긴다. 호출자의 프레임에 써 넣어야 하는 호출은 sibling call이 될 수 없고, 최적화기는 말없이 사양한다. 프로젝트의 TCO 매복 카탈로그의 네 번째 —— escape하는 스택 주소, inline화된 asprintf, thread-local 캐시에 이어 —— 이고, 형태는 다른 것들과 같다: 소스는 무죄, 배신은 C 툴체인의 세칙에서 일어난다. 수정은 핫패스의 de-tuple: 분할은 두 개의 단일 리스트 함수가 되었고, sort는 일어섰다.

감사와, Part의 장부

sret이 sort를 매복했다면, 달리 무엇이 기다리는가? 감사는 50여 개의 prelude 함수 전부를 걸으며 두 물음을 물었다 —— 재귀는 스택을 늘리는가, 일은 이차함수적으로 늘어나는가. 열 함수가 떨어졌고, accumulator 형식으로 고쳐 써졌다: length, map, range, take, zip, concat, flat-map, max, min 등. 어느 것도 테스트가 쓰는 리스트 길이에서는 보이지 않았고, 어느 것도 스케일에서는 치명적이었다. 재주행은 다른 라이브러리처럼 읽힌다: 백만 요소의 정렬이 0.65초, 고쳐 쓴 모든 함수가 백만까지 평평. 그리고 이로써 Part의 장부가 닫힌다. 여섯 화, 패턴은 양방향으로 성립한다: 싼 측정은 실제 일을 찾았고(trait 시스템은 단상화에 녹고, 단락 평가는 두 backend에서 빠져 있었고, wasm의 회수, codepoint view, 이 스케일 일순) —— 그리고 두 번, 일이 이미 끝나 있음을 찾았다. 그것대로 데이터다. 방법의 요약은 한 줄에 들어간다: probe가 일을 고른다. 그리고 probe는 싸다. 다음 Part가 무엇을 잴지는 아직 정해지지 않았다. 그것이야말로 요점이다 —— 무언가 작은 것이 언어에 쳐 넣어지고, 언어가 답할 것이다.