diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/design/022-arrays-and-registers.md | 41 |
1 files changed, 40 insertions, 1 deletions
diff --git a/docs/design/022-arrays-and-registers.md b/docs/design/022-arrays-and-registers.md index 7786640..53a75f6 100644 --- a/docs/design/022-arrays-and-registers.md +++ b/docs/design/022-arrays-and-registers.md @@ -1,6 +1,7 @@ # 022 — 배열과 레지스터로 C를 넘기 -작성일: 2026-10-05. 상태: 설계와 착수 기준. 1–4단계를 처음으로 만들었다(아래 "만들며 정한 것"). +작성일: 2026-10-05. 상태: 1–4단계를 만들었다(아래 "만들며 정한 것"). 코어 BFS는 C보다 빠르지만 미리 읽기 덕이고, 깡연산으로는 +C의 1.6배 느리다. 기준은 [023](023-optimizing-tier.md)의 묶음으로 옮긴다(아래 "3단계를 마치며"). [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보다 빠르게. @@ -151,6 +152,44 @@ 3. 바뀌는 장부를 레지스터에: 안쪽 루프의 프레임은 C를 부를 때만 쓰고 돌아오면 거둔다. 덧붙이기의 개수와 여분, 판, 바이트, 메모리 몫은 레지스터에서 세고 C를 부르기 전과 루프를 나갈 때 쓴다(걷기의 자리처럼). +### 3단계를 마치며 (2026-10-05 오후) + +위의 셋 중 1, 2와 3의 장부 몫을 만들었다. 단계마다 코어 BFS(`bfs-run`, 탐색 하나의 중앙값)와 탐색 하나의 명령·사이클 +(`perf_event`, 사용자 공간): + +| 커밋 | 바꾼 것 | 시간 | 명령 | 사이클 | +|---|---|---:|---:|---:| +| `ddc8ba0` | 정수 가정, `pure_run_rest` | 14.6 ms | 5,780만 | 3,520만 | +| `e8d213b` | 장부를 레지스터에 | 12.5 ms | 4,620만 | 3,030만 | +| `4537289` | 작업량을 레지스터에, x30, 산술 다듬기 | 12.2 ms | 4,300만 | 3,030만 | +| `1aa334d` | 정수로 미리 읽기, 칸의 마지막 셀도 | 8.6 ms | 4,170만 | 2,070만 | +| `e9e0d22` | 간선 루프에서 확인 셋을 덜기 | 7.4 ms | 3,840만 | 1,790만 | + +- **장부.** 묶음이 덧붙이는 FLAT 리스트의 개수(LIVE), DENSE 리스트에 더한 항목 수(PENDING), 이벤트가 더 자랄 수 있는 바이트 + (HEADROOM, 예산과 여분 중 작은 쪽), 이벤트가 더 할 수 있는 일(WORK)을 레지스터에 둔다. C를 부르기 전(`write_back`), 결함에서, + 묶음을 나갈 때(`join`, 묶음 밖으로 가는 `JZ`) 리스트와 앱에 쓴다. 장부는 읽혀 있을 때만 바뀌므로, 읽혀 있지 않은 장부는 쓸 것이 + 없다(그래서 줄 밖 길은 명령이 시작할 때 읽혀 있던 것만 쓴다). 개수를 읽는 곳(개수, 항목의 경계, 위치 옮기기, 걷기의 끝, 미리 + 읽기)은 장부의 개수를 본다. 레지스터가 모자라 장부를 다 두지 못하는 리스트는 예전처럼 메모리에 쓴다. +- **안쪽 루프의 프레임은 레지스터에 두지 않았다**(위 3의 앞 절반). 미스를 겹친 뒤로는 명령이 아니라 미스와 분기 예측이 시간을 + 쥐어서 미뤘다. +- **C를 넘은 것은 미리 읽기 덕이다. 깡연산으로는 아직 C보다 느리다.** 프로파일에서 사이클의 21%가 간선 열을 읽은 바로 뒤에 + 있었다. 노드의 간선(약 10개, 40바이트)은 64바이트 줄을 넘는 일이 잦은데(약 60%) 바닥도 JIT도 첫 셀만 읽었다. 칸의 끝 + (`first[b + 1]`)을 이미 읽으니 마지막 셀도 미리 읽는다. 사이클이 3,030만에서 2,070만이 됐다. 그러나 이것은 C가 하지 않는 일을 + 한 것이다: C에 같은 미리 읽기를 하면 7.1 ms다(`c_ahead`, 위의 바닥 표). 미리 읽기를 끄면 `e9e0d22`의 BFS는 16.1 ms, 같은 + 프로세스의 C는 9.8 ms다(검사가 함께 돌던 때라 둘 다 조금 길다). **기계어의 체급은 C의 1.6배 느리다.** +- **그래서 BFS 하나로 C를 넘었다고 하지 않는다**(2026-10-05, 사용자의 지적). BFS는 예였다. 기준을 여러 종류의 일로 바꾸고(실수와 + 정수의 루프, 정렬, 해시 조인, 텍스트, 그리드, BFS, TPC-C와 질의), 바이트코드를 SSA로 올려 타입을 추론하고 검사를 루프 밖으로 + 끌어내고 레지스터를 할당하는 계층을 모든 블록에 두는 설계를 [023](023-optimizing-tier.md)으로 한다. 이 설계의 BFS 통과 조건으로 + 잴 계열은 023의 묶음에 들어간다. +- **간선 루프.** 정수의 코드에서, 편 리스트의 조각을 코드로 연 걷기 안에서는 그 리스트의 열이 늘 있다(편 리스트는 FLAT이다). 그래서 + step이 연 같은 걷기는 실행기에 넘긴다(`pure_run_rest`). 키 비트가 없는 리스트는 비트가 닿는 키의 수(LIMIT)를 0으로 둬서, 키와 + 견주기 하나가 "비트가 있나"도 겸한다. `has`의 드문 길(1, 8바이트 칸, 비트 밖의 키)은 줄 밖에 둔다. 본 간선 하나에 명령 14개가 + 11개가 됐다. +- **고친 것.** 정수 산술의 결과 레지스터가 피연산자의 것과 같을 수 있는데, 범위 검사가 포기하면 실행기는 덮인 피연산자로 그 명령을 + 다시 했다. 2의 거듭제곱 곱을 시프트로 바꾸며 그 검사가 자주 포기하게 되자 aup의 검사(`PURE_JIT=all`, routes.aup의 깊이 우선 + 탐색)가 잡았다. 포기할 수 있는 산술은 결과를 x16에 만들고 검사 뒤에 옮긴다. `module_assumptions`에 그 꼴(`LOCALS_SOURCE`)을 + 더했다: 고치기 전 빌드에서 틀리고 고친 빌드에서 맞는다. + ## 단계 1. 저장된 리스트를 배열로 펴기와 칸의 색인. |