diff options
Diffstat (limited to 'docs/research')
| -rw-r--r-- | docs/research/124-against-c.md | 89 |
1 files changed, 89 insertions, 0 deletions
diff --git a/docs/research/124-against-c.md b/docs/research/124-against-c.md new file mode 100644 index 0000000..e11b695 --- /dev/null +++ b/docs/research/124-against-c.md @@ -0,0 +1,89 @@ +# 124 — C와 여러 일로 견주기: 022가 남긴 것과 묶음, 뜻의 값 + +2026-10-05. [022](../design/022-arrays-and-registers.md)를 마치며 잰 것, 그리고 기준을 BFS 하나에서 여러 종류의 일로 옮기며 잰 것. +코드와 원시 결과는 [040-against-c](../../research/experiments/040-against-c/)에 있다. + +## 쉬운 말로 + +- **BFS는 C보다 빨라졌지만 깡연산으로가 아니다.** 022의 3단계를 마쳐 코어 BFS가 14.6 ms에서 7.4 ms가 됐고, 같은 프로세스의 C(`bfs.c`)는 + 9.9 ms다. 그런데 가장 큰 한 걸음(12.2 → 8.6 ms)은 미리 읽기를 칸의 마지막 셀까지 넓힌 것이었고, C에 같은 미리 읽기를 하면 7.3 ms다. + 미리 읽기를 끄면 Pure는 15.7 ms로 C의 1.57배다. 사용자가 짚은 대로 이것은 BFS에 맞춘 이김이다. +- **여러 일로 재니 지금의 Pure는 C보다 3–300배 느리다.** 실수 루프 3.3배, 정렬 4.8배, 텍스트 12배, 해시 조인 22배, 배낭 DP 300배, + 행렬 곱 304배. 루프 묶음만 기계어로 돌고, 나머지는 실행기다. 배낭의 시간 절반은 키로 둔 표를 찾는 데 쓴다. +- **뜻의 값은 0에 가깝게 만들 수 있다.** 같은 일을 Pure의 표현과 뜻대로 손으로 C로 썼다. 검사를 뜻이 놓는 자리마다 두면 1.2–12배 느리고, + 범위로 증명되는 것을 없애고 루프마다 한 번으로 끌어내면 검사 없는 코드보다 0–3% 느리다. 그 코드는 C의 0.64–1.02배(기하 평균 + 0.90)다. 그러니 C를 넘지 못하게 하는 것은 −0이나 결함이나 예산이 아니라 실행 계층이다. +- **그래서 다음은 [023](../design/023-optimizing-tier.md)이다.** 모든 블록을 SSA로 올려 타입과 범위를 알고, 검사를 루프 밖으로 끌어내고, + 작업량을 루프마다 세고, 레지스터를 할당한다. 기준(일마다 C의 1.25배 안, 기하 평균 1.0 아래, 뜻의 검사 5% 안)은 구현 전에 커밋했다. +- **고친 것.** 정수 산술의 결과 레지스터가 피연산자와 같을 때 범위 검사가 포기하면 실행기가 덮인 피연산자로 다시 계산하던 버그를 + aup의 검사가 잡았다(`4537289`, 시험 `LOCALS_SOURCE`). 022 전부터 있던 것이다. + +## 결과 + +### 022의 3단계 (코어 BFS, `bfs-run`, 탐색 하나의 중앙값) + +| 커밋 | 바꾼 것 | 시간 | 명령 | 사이클 | +|---|---|---:|---:|---:| +| `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만 | + +명령을 1,160만 줄인 장부(`e8d213b`)는 사이클을 500만 줄였고, 명령 320만을 줄인 `4537289`는 사이클이 그대로였다. 사이클을 쥔 것은 +간선 열의 미스였다(프로파일에서 사이클의 21%가 간선 열을 읽은 바로 뒤). 노드의 간선(약 40바이트)이 64바이트 줄을 넘는 일이 많아, +첫 셀만 미리 읽던 것을 마지막 셀까지 넓히자 사이클이 3분의 2가 됐다. + +미리 읽기를 두고 끄며(`e9e0d22`, `2026-10-05-suite.jsonl`): + +| | Pure | `bfs.c` | `bfs.c` + 같은 미리 읽기 | +|---|---:|---:|---:| +| 미리 읽기 켬 | 7.58 ms | 9.89 ms | 7.29 ms | +| 미리 읽기 끔 (`PURE_AHEAD=0`) | 15.7 ms | 10.0 ms | | + +022의 코어 통과 조건(같은 프로세스의 `bfs.c`보다 작다)은 글자로는 선다. 그러나 C가 하지 않는 기법으로 선 것이라 통과로 치지 않는다. +022의 나머지 계열(HTTP, 지금의 앱, 기기 사이)은 재지 않고 기준을 023으로 옮겼다. + +### 묶음 (`5fffb63`, 11번의 중앙값) + +| 일 | Pure | C | Pure / C | 실행기만 / C | +|---|---:|---:|---:|---:| +| roots (실수, 나눗셈) | 22.9 ms | 6.86 ms | 3.3 | 19.3 | +| knapsack (정수 DP) | 1,880 ms | 6.27 ms | 300 | 298 | +| sort (키로 둔 리스트) | 128 ms | 27.0 ms | 4.8 | 4.7 | +| join (희소한 키로 찾기) | 672 ms | 30.8 ms | 22 | 24 | +| words (텍스트 키) | 455 ms | 38.3 ms | 12 | 12 | +| matmul (실수 그리드) | 2,284 ms | 7.52 ms | 304 | 303 | +| bfs (미리 읽기 없이) | 15.7 ms | 10.0 ms | 1.57 | 9.4 | + +모든 회차에서 Pure와 C의 답이 같다. 입력은 양쪽이 같은 MINSTD 수열로 이벤트 안에서 만든다. + +### 바닥과 뜻의 값 (`floor.c`, `2026-10-05-floor.jsonl`) + +| 일 | bare / C | hoisted / C | naive / C | +|---|---:|---:|---:| +| roots | 0.99 | 1.02 | 1.77 | +| knapsack | 0.95 | 0.97 | 10.8 | +| sort | 0.61 | 0.64 | 0.83 | +| join | 0.95 | 0.91 | 1.57 | +| words | 0.92 | 0.90 | 0.91 | +| matmul | 0.96 | 0.95 | 12.1 | +| bfs | 1.09 | 0.96 | 1.23 | +| 기하 평균 | 0.91 | 0.90 | 2.6 | + +- bare는 Pure의 표현만, hoisted는 컴파일러가 남길 검사(범위가 증명하지 못하는 것, 루프마다 한 번으로 끌어낸 것), naive는 수를 + binary64로 두고 뜻의 검사를 모두 제자리에 둔 것이다. +- **sort와 words가 C보다 빠른 것은 C의 표준 라이브러리 몫이다**: `qsort`는 비교마다 함수를 부르고, `snprintf`는 정수 하나에 무겁다. + 깡연산의 몫으로 치지 않는다. 그것을 빼면(sort를 1.0으로) 기하 평균은 0.96이다. +- join의 바닥은 처음 1.8이었다(색인의 칸에 키 8바이트, 위치는 따로). 칸에 키와 위치를 함께 두고 키를 4바이트로 좁혀 0.91이 됐다. + +## 판정 + +- 022: 코어 BFS는 미리 읽기 덕으로만 C를 넘었다. 깡연산으로는 C의 1.57배다. 미달로 적는다. +- 기준을 바꿨다: 묶음과 그 수치 기준을 023에 구현 전에 커밋했다(`ab4f8d3`, `b1bc98b`). + +## 다음 + +- 023의 1단계: 블록을 SSA로 올리고 타입과 범위를 내며, IR을 해석하는 시험용 실행기로 모든 검사의 프로그램을 실행기와 견준다. +- 기준의 긴장: 기하 평균 1.0은 sort와 words가 C의 라이브러리 몫으로 받쳐 준다. 일마다의 한계 1.25는 몇 가지에서 C에 질 수 있음을 + 허락한다. 사용자의 판단에 따라 일마다 1.0으로 조이거나 sort를 인라인한 C와 견주도록 바꿀 수 있다. |