diff options
Diffstat (limited to 'docs/design/022-arrays-and-registers.md')
| -rw-r--r-- | docs/design/022-arrays-and-registers.md | 37 |
1 files changed, 36 insertions, 1 deletions
diff --git a/docs/design/022-arrays-and-registers.md b/docs/design/022-arrays-and-registers.md index 12f0870..7786640 100644 --- a/docs/design/022-arrays-and-registers.md +++ b/docs/design/022-arrays-and-registers.md @@ -1,6 +1,6 @@ # 022 — 배열과 레지스터로 C를 넘기 -작성일: 2026-10-05. 상태: 설계와 착수 기준. +작성일: 2026-10-05. 상태: 설계와 착수 기준. 1–4단계를 처음으로 만들었다(아래 "만들며 정한 것"). [021](021-past-c.md)은 BFS(노드 10만, 간선 100만) 한 번을 190 ms에서 90 ms로 줄였지만 C(9.1 ms)를 넘지 못했다 ([123](../research/123-past-c.md)). 123의 바닥은 길이 있다고 말한다: Pure의 표현대로 손으로 쓴 C가 C를 넘는 것은 저장된 리스트가 배열이고, 열이 값만큼 좁고, 다음 노드를 미리 읽을 때뿐이다. 목표는 그대로다. 같은 aup 코드, 같은 뜻, 같은 기계에서 C보다 빠르게. @@ -116,6 +116,41 @@ 번 뒤의 A의 값으로 같은 계산을 해 B의 칸과 첫 항목을 미리 읽는다(prefetch). A가 아직 그만큼 길지 않으면 하지 않는다. 미리 읽기는 결과를 바꾸지 않는다. 간접 접근의 소프트웨어 미리 읽기는 컴파일러의 일반적인 기법이다(Ainsworth와 Jones, CGO 2017). +## 만들며 정한 것 (2026-10-05) + +1–4단계를 처음으로 만든 판(`1e8c168`, 코어 BFS 14.9 ms)까지 정한 것과 달라진 것. + +- **펴기는 이벤트가 끝난 뒤에만.** 이벤트 도중에 펴면 도는 fold의 런이 쥔 잎이 풀린다. 그래서 소유자 스레드가 이벤트를 끝낼 때 + (`dispatch`) 판(version)에서 많이 찾은 리스트를 편다(`pure_list_settle`). 첫 이벤트는 트리로 돌고 끝에서 펴진다. 펴기와 트리로 + 돌리기 모두 판을 올린다(손가락, 런 캐시, fold의 패스, 스냅숏이 판으로 무효가 된다). 트리는 잎부터 지어 O(n)이다. 사본만 찾는 + 리스트(보기만 찾는)는 펴지지 않는다(다음 일). +- 문턱: 항목 4,096 이상, 판 하나에서 키로 찾기가 항목의 8분의 1(`PACK_SEARCHES`). 칸 하나에 항목 여덟을 기준으로, 찾은 키의 끝 0 + 비트 수가 허락하면 그 폭으로 좁힌다. 색인은 항목 수보다 칸이 많지 않다. 키가 모두 2^53 아래의 정수면 색인을 정수로도 둔다 + (`whole`, 시프트, 원점): 찾기와 JIT의 조각 열기가 정수로 한다. +- **좁은 열의 폭은 1, 4, 8바이트**다(설계의 u16은 두지 않았다: 폭을 고르는 분기가 짧다). 수와 bool만 좁히고 −0은 좁히지 않는다. + FLAT 리스트의 키 열은 늘 8바이트(수로 찾는다), DENSE 리스트는 키 열을 두지 않고 −0은 DENSE의 키가 되지 않는다(그 칸은 키 그 + 자체라 +0으로 읽힌다). 비운 리스트가 DENSE였으면 배열을 놓는다(키 열이 없다). 런(`PureRun`)은 좁은 칸을 넓혀 담을 자리(4 KiB)를 + 갖는다. +- **JIT은 열의 주소 윗바이트에 폭을 적는다**(비트 56, 58, 59). AArch64 리눅스는 사용자 공간 주소의 윗바이트를 읽을 때 보지 않는다 + (Documentation/arch/arm64/tagged-pointers.rst, TBI). 그래서 폭마다 레지스터를 더 쓰지 않는다. 리눅스 AArch64에서만 JIT이 있으니 + 이 가정은 그 안에 있다. +- 가둔 값은 루프 묶음(가장 바깥 루프와 그 안의 루프)마다 레지스터 하나씩이고, 묶음의 모든 레이블에서 다 읽혀 있다. C를 부르면 + 다시 읽는다. 편 리스트의 조각 루프는 코드로 연다(정수 칸). `ITEM_GET` 바로 뒤의 `has`는 하나로 한다(칸을 키로 곧장). +- 미리 읽기: 루프 몸체를 처음부터 기호로 따라가, 안쪽 조각 루프의 아래 경계가 루프의 셈에서 나오면(리스트의 항목, 그리고 산술) + 16회 뒤의 칸과 8회 뒤의 첫 칸을 읽는다(`AHEAD_FAR`, `AHEAD_NEAR`, 바닥에서 잰 거리). 칸은 범위를 보지 않는다(PRFM은 결함을 + 내지 않는다). 첫 칸을 읽을 때만 칸 번호를 확인한다. +- **남은 몫**(덤프로 센 것, 탐색 하나 5,780만 명령, 3,965만 사이클): 노드 하나에 약 280명령(미리 읽기 45, 몸체 50, 조각 열기 + 130, 나가기와 바깥 반복 35, ...), 넣기 하나에 약 150, 간선 하나에 약 10. 바닥은 노드 93, 넣기 12다. 정수 가정만으로는 넣기에서 + 약 33, 노드에서 약 55가 줄어 4,900만이다(사이클로 C를 넘지 못한다). 나머지는 장부다: 노드마다 안쪽 루프의 프레임(루프 구조체, + 이벤트의 행과 걷기, 프레임의 끝과 깊이)을 쓰는 약 40, 덧붙이기마다 개수·판·바이트·메모리 몫과 그 검사 약 25. +- **그래서 3단계를 이렇게 마친다.** + 1. 정수 가정: 좁은 열(1, 4바이트)에서 읽은 값, 행 번호, 개수, 정수인 루프의 셈, 그것들의 정수 산술(결과가 2^53 안이고 −0이 + 생기지 않을 때)은 정수 레지스터에 둔다. 열이 8바이트이거나 산술이 범위를 넘으면 가정이 깨진다. + 2. 가정이 깨지면 그 루프 회차의 남은 부분을 실행기가 한다(`pure_run_rest`): 스택을 수로 내리고, 걷기의 자리를 쓰고, 그 명령부터 + 루프의 끝까지 실행기가 돈 뒤 돌아와 다음 회차를 코드로 한다(BREAK면 루프 밖으로). 모든 길이 끝까지 간다는 원칙이 그대로다. + 3. 바뀌는 장부를 레지스터에: 안쪽 루프의 프레임은 C를 부를 때만 쓰고 돌아오면 거둔다. 덧붙이기의 개수와 여분, 판, 바이트, + 메모리 몫은 레지스터에서 세고 C를 부르기 전과 루프를 나갈 때 쓴다(걷기의 자리처럼). + ## 단계 1. 저장된 리스트를 배열로 펴기와 칸의 색인. |