네 backend에서 병행을 돌리기

타입 시스템은 끝났다: 병행 처리는 종이 위에서 안전하다. 이제 그것은 돌아야 한다. spawn은 진짜 스레드가, channel은 진짜 공유 메모리가 되어야 한다 —— 그리고, 코드 생성을 처음부터 다스려 온 규칙에 따라, 그것은 네 번, backend마다 한 번, 어느 둘도 다른 출력을 내지 않고 일어나야 한다. 두드러지는 것은, 같은 primitive가 네 가지 진짜 다른 방식으로 나오고, 그 저마다가 자기 backend가 무엇인가에 빚어지며, 그리고 코드 생성 Part에서 세워진 클로저 표현이야말로 넷 모두를 돌린다는 것이다.

왜 클로저가 스레드를 만드는가

스레드는, 벗겨 내면, “이 클로저를 어딘가 다른 데서 돌린다”이다. 그리고 클로저는, Mere의 어느 backend에서도, 정신에서는 늘 같게 표현되었다: 엔트리 포인트와, 그 포획된 환경. C에서는 함수 포인터와 환경 포인터의 struct; Wasm에서는 함수 테이블의 인덱스와 메모리 offset. 그 표현이 backend 간에 형태에서 일률적이기에, 클로저를 새 스레드에 건네는 것은 어디서나 기계적으로 자연스럽다 —— 스레드가 요하는 두 가지, 돌릴 코드와, 그것이 닫아 넣은 데이터를, 이미 가지고 있다. 병행 처리 feature는, Part IV의 클로저 일을, 재발명이 아니라 잇는다.

하나의 primitive의 네 맞춤

인터프리터가 가장 쉽고, 가장 빠르게 보답한다. 거기서의 클로저는 진짜 환경을 가진 진짜 호스트 언어 클로저이므로, spawn은 그저 호스트 자신의 스레드 생성이고, channel은 락과 조건 변수를 가진 큐다. 호스트의 런타임이 공유된 환경과 스레드를 돌본다. 수십 줄로, 원래의 pain point —— 하나의 프로세스 안의 두 영구 loop —— 가 풀린다. 왜 OCaml인가의 내기가 다시 한 번 보답받는다: 호스트의 병행성이 Mere의 것이 된다.

C backend는, 병행 처리가 이론적이기를 그치는 곳이다. spawn은 클로저를 heap에 복사하고, 그것을 부르는 trampoline으로 POSIX 스레드를 기동한다; channel은 요소 타입마다 단형화된다 —— 구체 타입마다 하나의 channel 구현, 언어가 이미 그 벡터를 특수화하는 것에 맞추어 —— 저마다 mutex와 조건 변수를 가진 링 버퍼다. 여기서는 환경이 공유된 heap 포인터이므로, 진짜 데이터 경쟁이 이제 가능하고, 그것은 세 회 전의 Send와 Sync의 검사가, 처음으로, 프로그래머와 진짜 버그 사이에 서 있음을 뜻한다. 스레드 새니타이저 아래에서 돌리면, channel은 경쟁 제로를 보인다 —— 타입 시스템의 일이, 경쟁 검출기가 아무것도 찾지 못함으로써 검증된다.

그 backend는 이름 붙일 가치가 있는 위험을 떠올렸다. default region —— 클로저의 환경이 확보되는 —— 은 공유 범프 할당자이고, 그 포인터를 범프하는 것은 아토믹이 아니어서, 두 스레드가 동시에 확보하면 경쟁할 것이다. 수정은 언뜻보다 가벼웠다: 그 region은 결코 해제되지 않는 불사의 arena이므로, 풀 lifetime 문제는 없고, 있는 것은 범프의 경쟁뿐 —— 그리고 공유 arena의 확보로의 단일 락이 그것을 닫고, per-block region은 thread-local한 stack 값이므로 lock-free인 채다. 설계는 한때 각 자식 스레드에 자기 region을 주기를 제안했다; 근본 원인 규명이 그것은 올바름에는 불필요하다고 보이고, 가능한 미래의 최적화로만 남겼다.

LLVM backend는 C와 같은 스레드지만, 다른 channel이다. C가 타입마다 하나의 channel을 단형화하는 곳에서, LLVM은 단일한 총칭적 i64-slot channel을 쓴다 —— 그 스칼라 값이 모두 여덟 바이트에 들어 가므로, 요소를 i64 slot으로/에서 cast할 수 있고, 하나의 channel이 모든 타입에 봉사한다. 그 지름길 에는 구멍이 있었다: 집합 —— 튜플과 레코드 —— 은 레지스터에 들어가지 않고, 하나로 넓혀지지 않으며, 컴파일러는 그 시도를 거부했다. 수정은 집합을 heap에 box하고, 대신 slot에 포인터를 통과시킨다. backend 고유의 최적화의, backend 고유의 엣지 케이스, 찾아 닫혔다.

Wasm backend는, 설계 노트가 비관적이던 하나다: 자식에서 Mere의 클로저를 돌릴 길이 전혀 없다고 우려했다. 그 우려는 녹았다. 공유 메모리 스레드로, worker는 같은 모듈을 하나의 공유 메모리와 하나의 공유 함수 테이블 위에 재 instantiate하고, 클로저 표현 —— 테이블 인덱스와 메모리 offset —— 은 worker에서 변하지 않고 유효하다, 둘 다 두 instance가 공유하는 메모리를 가리키기에. spawn은 host import를 통해 worker를 기동한다; channel은, 호스트의 아토믹 primitive로 조작되는 공유 메모리의 작은 영역으로, 섬세한 락과 대기의 논리를 손으로 쓴 Wasm 밖에 둔다. 옛 비관은 그저 틀렸다, 이전의 클로저 설계가 이미 자식을 닿을 수 있게 했기에.

확보하는 worker만이 낳는 버그

Wasm은 하나 더 미묘한 실패를 가지고 있었다. 공유 데이터를 그저 읽는 worker는 괜찮지만, 확보하는 worker —— 커리된 호출이 중간 클로저를 지을 때 암묵적으로 그러듯 —— 는 instance마다의 확보 포인터를 범프하고, 두 worker가 같은 공유 메모리로 자기 포인터를 범프하면 충돌하여 deadlock한다. 수정은 범프를 아토믹으로 하는 것이 아니라, 각 worker에 확보할 공유 메모리의 서로소인 영역을 건네는 것이었다: 호스트가 각 worker의 확보 포인터를, 기동 후에, 별개의 겹치지 않는 고위 offset으로 설정한다. 생성된 코드로의 변경 없음, 아토믹 없음 —— 그저 분할된 공간. 이전 deadlock한 프로그램, 네 worker가 저마다 커리된 일을 하는, 이 완주했다.

하나의 동작, 네 기구

마지막에, spawn은 네 backend에서 돌고, channel은 그것들을 넘어 돌며, 데이터 병렬 프로그램 —— 일을 여러 worker로 fan-out하고, 부분 결과를 channel로 fan-in하는 —— 이 그 어느 것에서도 같은 수를 낳는다: 인터프리터, C, LLVM, Wasm. 기구는 이보다 더 다를 수 없다 —— 호스트 스레드, per-type channel의 pthreads, box된 i64 slot의 pthreads, 호스트 구동의 아토믹과 분할된 확보를 동반한 공유 메모리의 worker —— 그리고 그것이야말로, 코드 생성의 규율 전체가 만들기 위해 세워진 점이다. parity는 관측되는 출력에 살고, 구현에 살지 않는다; 각 backend는 그것에 맞는 실현을 받고, 그럼에도 여전히 일치하도록 유지된다.

병행 처리는 이제, 안전하게, 어디서나 존재한다. 하지만 spawn과 channel은 생 primitive —— 병렬성의 어셈블리 언어이지, 대부분의 코드가 그것으로 표현하고 싶어야 할 형태가 아니다. 다음 단계는, 흔한 경우를 인간적으로 하는 것이다: 사람이 실제로 손을 뻗는 형태, 병렬 맵을 주고, 그것을 네 번 쓰지 않고 네 backend에서 얻는 것. 다음 회: par_map.