# 131 — 범용 장치로 값 줄이기: 같은 코드의 값 다시 쓰기, 고르기, 비트로 묻기

2026-10-08. [130](130-batch-executor-frontiers.md)이 BFS로 보인 간선당 명령 211개(기계어 38.5)를, 어떤 코드에도 듣는 장치로만
줄였다. 사용자의 방향은 범용이다. 스위트의 꼴만 골라 합친 연산의 표를 만들지 않는다. 코드는 `589e669`와 `735ba81`이다. 같은 방법으로 쟀다
(`041-batches/runs.sh`, 빌드 `b9` = `735ba81`, 11번의 중앙값; 탐색만의 명령은 `041-batches/search/`, `2026-10-08-search-counts.jsonl`).

## 쉬운 말로

- **BFS가 간선당 211개에서 112개가 됐다.** 41.0 ms에서 24.0 ms다(기계어 7.7, C 9.9). 기계어의 3.1배다(5.4배였다).
- **바꾼 것은 다섯 가지 범용 장치다.** 같은 코드로 다시 계산하는 값을 한 번만 계산하기, `if !c`를 분기 하나로, 레인이 적은 갈래를
  그 레인만 모아 돌기(고르기), 키가 비트로 있는 리스트에 비트로 묻기, `L.first + i`를 아핀 값으로. 어느 것도 BFS만을 위한 것이
  아니다. 다만 knapsack과 matmul은 약 10% 느려졌다(아래: 패스의 코드가 커진 값으로 보이며, 원인을 다 가르지는 못했다).
- **이 꼴의 바닥은 기계어의 약 2배로 보인다.** 간선마다 레인을 한 번씩 훑는 일(모으기, 묻기, 분기, 고르기, 덩어리 만들기)이 약 40개,
  노드마다 약 20개, 후보마다 약 250개(간선당 26개)다. 레인 훑기는 연산마다 메모리를 오가고, 기계어는 레지스터에서 한다. 더 줄이려면
  훑기를 합쳐야 하는데, 그것은 범용이 아니라 꼴의 표다.

## 묶음

| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C | 묶음의 명령 / 실행기만 |
|---|---:|---:|---:|---:|---:|
| roots | 9.57 ms | **8.97** | 130.5 | 6.86 | 1.69억 / 27.56억 |
| knapsack | 7.93 | 11.45 (b7 10.32) | 1,040.7 | 6.25 | 3.94억 / 216.88억 |
| matmul | 14.24 | 39.98 (36.51) | 914.9 | 7.58 | 9.68억 / 214.37억 |
| join | 84.6 | 116.9 (117.8) | 435.1 | 31.7 | 18.93억 / 76.70억 |
| sort | 35.2 | 56.4 (56.8) | 77.0 | 26.9 | 10.08억 / 15.03억 |
| BFS | 7.71 | **24.0** (41.0) | 92.7 | 9.90 | 33.74억 / 47.12억 |
| words | 215.5 | 217.6 (214.3) | 209.9 | 39.5 | 39.77억 / 39.34억 |

- 실행기만의 명령은 모두 그대로다. 기계어의 join이 78.8에서 84.6 ms로 오간 것은 같은 코드라 놓인 자리다.
- **knapsack과 matmul이 느려졌다.** 명령이 3–4%, 사이클이 7–8% 많다. 같은 코드의 값 다시 쓰기의 검사를 끄면 2%가 돌아오고(그래서
  그런 값이 없는 모듈은 검사를 건너뛰게 했다), 고르기를 꺼도 나머지는 그대로다. 패스 함수가 커져 인라인과 배치가 바뀐 값으로 보인다.
  남겨 둔다.

## 만든 것

- **같은 코드의 값 다시 쓰기**(`plan_reuse`, 로드 때). 묶음 블록 안에서 값 하나를 만드는 코드 조각(스택 높이로 자른 부분 나무)이
  앞선 조각과 같고(`same_code`), 둘이 같은 가장 안쪽 블록의 한 줄에 있고(사이에 `JMP`·루프·`break`·착지 없음; `JZ`는 레인을
  좁히기만 한다), 사이에서 조각이 읽는 지역 변수를 쓰거나 리스트를 바꾸지 않으면, 뒤의 조각은 앞의 값을 그대로 쓴다. 앞의 값은
  묶음이 쥔다(버퍼를 놓지 않는다). 모듈은 조각의 시작마다 `reuse_from`, `reuse_length`를 둔다. BFS의 `e.to`를 세 번 모으던 것이
  한 번이 됐다.
- **`if !c`는 분기 하나.** `NOT` 바로 뒤가 `JZ`면 `NOT`을 돌지 않고 뒤집어 가른다. 레인 세기도 같은 루프에서 한다.
- **고르기**(`select`, `deselect`). 가른 뒤 가는 레인이 4분의 1 이하이고 갈래가 곧은 코드(안에 분기·루프·`break` 없음, 끝의 `JMP`는
  else)면, 그 레인들만 모아(`sel[j]`) 갈래를 돈다. 갈래 안에서 바깥 값을 읽으면 `sel`로 모은다(펼친 걷기 안에서는 항목의 바깥
  레인을 거쳐 한 번에). 모으기는 바깥 레인의 몫에 더한다. 갈래가 쓴 지역 변수는 갈래가 끝날 때 바깥 레인으로 돌려놓는다(바깥의
  값은 그대로, 가른 레인만 새 값; 일부 레인에만 썼으면 그 마스크로). 미룬 쓰기와 칸에 더하기는 기록할 때 바깥 레인으로 펼친다.
  덧붙이기는 모은 레인의 칸을 `sel`과 함께 두어 끝의 처리가 그 레인만 돈다. 걸러내기의 몸체가 고르기면, 모은 회차의 기록도 후보만
  돈다. `PURE_SELECT=all`은 레인 수와 상관없이 모든 곧은 갈래를 고르게 해서(시험용), 무작위 시험이 이 길을 다 지나게 한다.
- **비트로 묻기.** 키를 비트로 두는 리스트(`pure_list_bits`)의 `has`는 레인 루프 하나다. 걸러내기의 결정도 그 비트와 우리 비트
  (모은 회차가 더하는 키를 표시, 끝에 지움)로 한다. 해시 집합이 없어졌다. 비트가 없는 키(정수가 아니거나 범위 밖)는 없는 키다
  (`pure_list_contains`와 같다). 처음에 이것을 "있는 키"로 잘못 두어 무작위 시험 하나가 작업량에서 어긋났고, 고쳤다.
- **`L.first + i`는 아핀.** 균일 값과 아핀 값을 더한 자리가 리스트 안이면 아핀 값이다(전에는 레인마다 계산해 수 레인이 됐다). 그
  뒤의 읽기가 보폭 읽기가 되고 범위 검사가 양 끝만 본다.
- **조각의 양 끝을 한 번에**(`pure_list_slice`). 걷기의 조각 경계 둘을 한 호출로 찾는다. 묶인 리스트의 정수 키면 버킷으로 바로 간다.
- **모은 회차의 기록.** 키와 칸을 수 레인으로 한 번 만들고 그대로 복사한다(레인마다 값의 꼴을 묻지 않는다).

## 무엇에 값을 내는가 (BFS, 간선당 명령)

| 단계 | 간선당 명령 | ms |
|---|---:|---:|
| 130 (`b7`) | 211 | 41.0 |
| 같은 코드의 값 다시 쓰기, `if !c` | 205 | 39.0 |
| 고르기 | 146 | 30.2 |
| 비트로 묻기, 아핀 `first + i`, 바깥 값 한 번에 | 121 | 24.8 |
| 모은 회차의 기록, 조각 양 끝 | **112** | **24.0** |
| 기계어 | 38.5 | 7.7 |

프런티어 합(간선의 `to`만 더하기)은 70 → 56개다(기계어 35). 사이클로는 BFS 81 → 57(기계어 19), 프런티어 26 → 20(15)이다.

남은 112개를 표본으로 나누면 대략 이렇다.
- 간선마다 레인을 훑는 일 약 45개: `to` 모으기 12, 비트로 묻기 11, 뒤집어 가르기와 고르기 7, 덩어리 만들기 7, 나머지 디스패치.
- 노드마다 약 20개(간선당): 조각 경계, 레인마다의 수와 작업량.
- 후보(간선의 10.5%)마다 약 250개(간선당 26개): 기록 50, 결정 90, 넣기 110(`pure_list_add_many`의 폭 검사와 칸 쓰기, 몫 셈).
- 묶음마다의 고정 값은 작다.

**바닥.** 간선마다의 훑기는 연산마다 레인 배열을 메모리로 오가며 요소당 4–12개가 든다. 기계어는 같은 일을 레지스터에서 요소당
1–2개로 한다. 훑기를 줄이지 않고는 간선당 약 45개 아래로 가지 못하고, 노드와 후보의 몫을 반으로 줄여도 70개쯤이다. 기계어의
1.8배다. 훑기를 합치는 것은 꼴의 표라서 범용의 길에서는 여기가 바닥이다. 후보의 넣기(110개)는 리스트 쪽 C라 더 줄일 수 있다.

## 뜻과 맞음

- 시드 1, 2, 3, 5, 23의 무작위 프로그램이 다섯 길에서 같았다. `PURE_SELECT=all`로 모든 곧은 갈래를 고르게 해도(시드 1, 2, 3, 5, 23)
  같았다. 처음 돌렸을 때 시드 23의 프로그램 하나가 작업량에서 어긋났다(위의 비트 없는 키). 고치고 다시 돌려 같았다.
- 고정 소스 여섯(`BATCH`, `NESTED`, `RECUR`, `APPEND`, `FRONT`, `GRAPH`)이 세 길에서 같았다(기본과 `PURE_SELECT=all`).
- 단위 시험 세 모드, ASan(실행기 모드), aup의 검사 두 모드, Pure의 `make check`가 통과했다. sanitized `pure-run`으로 시드 23의
  프로그램과 고정 소스를 기본과 `PURE_SELECT=all`로 돌려도 오류가 없었고 출력은 실행기만으로 돈 것과 같았다.
- 실행기만의 명령은 그대로다(`run`은 건드리지 않았다).

## 다음

- 후보의 넣기를 리스트 쪽에서 줄이기(폭 검사를 한 번에, 비트와 칸을 함께).
- 고르기를 중첩 루프의 회차에도(roots의 빠진 레인).
- `total = total + A + B` 꼴의 모으기 인식(129).
- knapsack과 matmul의 10%: 패스를 나누거나 묶음 구조체의 뜨거운 자리를 모아 되찾기.
- 기계어를 걷어낼지는 사용자의 몫이다. 범용의 길로는 BFS가 기계어의 약 2배에서 멈춘다. 다른 일은 roots가 기계어보다 빠르고,
  knapsack 1.4배, matmul 2.8배, join 1.4배, sort 1.6배다.