diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/design/018-lifetimes-and-computation.md | 3 | ||||
| -rw-r--r-- | docs/research/118-computing-in-one-event.md | 90 |
2 files changed, 92 insertions, 1 deletions
diff --git a/docs/design/018-lifetimes-and-computation.md b/docs/design/018-lifetimes-and-computation.md index 1aad50f..b27c13a 100644 --- a/docs/design/018-lifetimes-and-computation.md +++ b/docs/design/018-lifetimes-and-computation.md @@ -1,7 +1,8 @@ # 018 — 상태의 수명과 메모리 안의 계산 작성일: 2026-10-04. 상태: 설계와 착수 기준. 1단계(transient) 구현, 검사로 고정하고 쟀다 -([117](../research/117-transient-states.md)). +([117](../research/117-transient-states.md)). 2단계(핸들러의 계산) 구현, 검사로 고정하고 쟀다 +([118](../research/118-computing-in-one-event.md)). [외부 리뷰 005](../outside-feedback/feedback-005.md)의 (1) "순수 인메모리 연산 및 알고리즘의 단절"과, 상태의 영속성과 상태성을 aup 안에서 정할 수단이 필요하다는 요청에서 시작한다. diff --git a/docs/research/118-computing-in-one-event.md b/docs/research/118-computing-in-one-event.md new file mode 100644 index 0000000..daf7eba --- /dev/null +++ b/docs/research/118-computing-in-one-event.md @@ -0,0 +1,90 @@ +# 118 — 한 이벤트 안의 계산 + +2026-10-04. [018](../design/018-lifetimes-and-computation.md)의 2단계(핸들러의 계산)를 잰다. 기준은 구현하기 전에 018에 적어 +커밋했다(`4d93488`). + +- 바꿀 결정: 핸들러에 이벤트의 리스트, 세는 반복, `break`, 중첩을 두고 모든 앱에 기본 예산을 둘지. +- 통과 조건(RAM의 Pi 5): 지금의 앱(TPC-C, 은행 질의)이 전과 후 번갈아 여섯 쌍에서 3% 넘게 느려지지 않고 은행 질의의 명령 수가 + 1% 넘게 늘지 않는다. 노드 10만 개, 간선 100만 개의 BFS가 기본 예산 안에 든다(그 시간을 C, CPython과 견주어 밝힌다). + +## 쉬운 말로 + +- **통과했다.** aup로 BFS, DFS, 다익스트라, 뉴턴 반복, 배낭 문제를 쓸 수 있다. 큐와 방문 집합은 이벤트의 리스트(`let seen: list of + Seen by node`)이고, 반복은 세는 `for`와 `break`, 걷기 안의 걷기다. +- 노드 10만 개, 간선 100만 개의 그래프에서 BFS 한 번이 한 이벤트로 **396 ms**다. 같은 일을 CPython은 441 ms, C는 9 ms에 한다. + Pure의 바이트코드 실행기는 C의 44배이고 CPython보다 조금 빠르다. +- 지금의 앱에는 거의 값이 없다. TPC-C가 1.7% 느려졌고(기준 3% 안), 은행 질의의 명령 수는 1% 안에서 같다. +- 끝나지 않는 반복은 이제 끝난다. 예산 없이 띄운 호스트에서도 세기만 하는 반복은 1.4초 만에 `work`로, 저장되는 리스트를 채우는 + 반복은 1.5초 만에 `memory`로 실패하고 아무것도 바꾸지 않는다. 그동안 호스트의 메모리 정점은 263 MiB 늘었다(기준 300 MiB). +- 같은 계산이 Pi, WSL2(x86_64), M3 Mac에서 같은 결과를 낸다. 모듈 바이트도 같다. + +## 결과 + +원시 결과와 명령은 [033-computing](../../research/experiments/033-computing/)에 있다(`runs.sh`). + +### 지금의 앱 (전 `850f783`, 후 `7a6cdba`) + +026과 같게 TPC-C(RAM, W=1, 64터미널, 20초)와 은행 질의를 전과 후 번갈아 여섯 라운드 쟀다(`pairs.py`). + +| | 전 | 후 | 바뀜 | +|---|---:|---:|---:| +| TPC-C 중앙값(초당 트랜잭션) | 43,108 | 42,369 | −1.7% | +| TPC-C의 트랜잭션당 CPU(µs) | 44.3 | 44.8 | | +| per_branch(ms) | 5.25 | 5.27 | +0.4% | +| in_credit(ms) | 0.86 | 0.85 | −1.2% | +| large(ms) | 0.385 | 0.385 | 0 | +| ranks(ms) | 6.74 | 6.80 | +0.8% | + +TPC-C는 여섯 라운드 모두 후가 같거나 낮았다(0에서 −4.1%). 흔들림만은 아니다. 지금의 이벤트에 더해진 일은 넷이다: 실행량 예산이 +늘 있어 세는 일(전에는 예산이 없으면 세지 않았다), 이벤트마다 자람의 셈을 0으로 두는 일, 리스트와 text를 바꿀 때마다 크기 둘을 +읽어 더하는 일, 걷기마다 `break`를 보는 일. 은행 질의의 명령 수(025의 `count.py`, 두 번씩)는 0.6% 안에서 오르내린다(field +0.7%, +found +0.6%, per_branch −0.5%). + +### BFS 한 번 (노드 100,000, 간선 1,000,000) + +`bfs.py`: 무작위 그래프(시드 118)를 `graph.aup`에 행으로 넣고, 무작위 출발 다섯 곳에서 BFS를 다섯 번씩 한다. Pure는 요청 하나가 +이벤트 하나다(유지된 연결에서 클라이언트가 잰 요청 시간, 거의 모두가 이벤트다). C(`bfs.c`, 인접을 오프셋 배열로)와 CPython(리스트와 +deque)이 같은 탐색을 한다. 세 쪽의 거리와 닿은 노드 수(99,996)가 모두 같다. + +| 중앙값 | C | CPython | Pure | +|---|---:|---:|---:| +| BFS 한 번 | 8.96 ms | 441 ms | 396 ms | + +Pure의 BFS 한 번은 실행량으로 약 2,300만 명령이다(노드마다 반복 블록과 그 노드의 간선 조각). 기본 예산(2^28)의 10분의 1이 안 된다. + +### 끝나지 않는 반복 (`tests/check.py`의 `server_runaway`, 예산 없는 `pure-serve`) + +| 반복 | 끝 | 걸린 시간 | 메모리 정점이 는 양 | +|---|---|---:|---:| +| `for i in 0 .. 1e15 { count = count + 1 }` | `work` | 1.4 s | 0 MiB | +| `for i in 0 .. 1e15 { xs.append(R { n: i }) }` (저장되는 리스트) | `memory` | 1.5 s | 263 MiB | +| `let ys: list of R` 에 같은 반복 | `limit` (리스트의 항목 수 한도 2^24) | 3.2 s | 163 MiB | + +셋 모두 상태를 바꾸지 않았고, 호스트는 뒤의 요청에 답했다. 이벤트의 리스트는 저장 기록과 되돌리기 기록이 없어서 256 MiB의 몫보다 +리스트의 항목 수 한도가 먼저 왔다. + +### 검사 + +- `test-module`의 `loops`: LOOP(정수가 아닌 경계는 `limit`, 빈 범위, i64의 끝 근처), 여러 깊이의 `break`, 같은 리스트를 도는 걷기 + 안의 걷기, 키 있는 이벤트의 리스트(이벤트마다 비어서 시작한다), 기본 예산의 `work`(빈 블록의 반복도 센다), 기본 몫과 예산의 + `memory`, 검증기의 거절 8가지(반복 밖의 BREAK, 값이 남은 BREAK, 반복 안으로의 분기, 타입, 인자, 두 가지로 쓰인 칸, 바깥 걷기의 + 리스트에 넣기, 9겹)와 8겹은 받아들이는 것. +- aup `tests/check.py`의 `computing`: 무작위 그래프 20개에서 질의마다 BFS, DFS(스택, 방문 순서까지), 다익스트라가 Python 모델과 + 같다(600번). 뉴턴의 제곱근 200개가 같은 순서로 계산한 Python의 binary64와 비트까지, 단계 수까지 같다. 배낭 문제 100개가 동적 + 계획법 모델과 같다. 진단 14건(반복 밖의 `break`, 블록 안의 리스트 `let`, 세는 이름에 대입, 바깥 걷기의 리스트에 넣기와 지우기, + 같은 이름의 다른 리스트, 한 이벤트의 두 핸들러, 9겹, …). +- 기기 사이(`record.py`, 029의 기록 방식): 위 두 검사의 `pure-run` 46번이 Pi, WSL2, M3 Mac에서 출력, 오류, 종료 코드까지 모두 같고, + 그 모듈 넷의 바이트가 같다. + +## 판정 + +- **018의 2단계는 들어간다.** 무거운 계산을 앱 밖으로 내보내지 않고 aup 안에서 쓸 수 있다. 모든 반복은 시작할 때 횟수의 상한을 갖고, + 모든 이벤트는 실행량 예산과 메모리 몫 안에서 끝난다. +- 바이트코드 실행기의 속도는 CPython 수준이다. C의 수십 배라는 것은 005의 3장이 말한 대로이고, 그것을 줄이는 일(명령 디스패치, + 키로 찾기)은 따로 잰다. + +## 다음 + +- 018의 3단계: 보기의 본문. 읽기만 하는 계산(경로 찾기)을 스냅숏에서 돌려 소유자를 막지 않는다. +- 실행기의 BFS 한 걸음 값: 노드마다 키 있는 리스트를 반씩 나눠 찾는 일(`seen.has`, `seen[q.node]`, 간선 조각의 경계)이 대부분일 것이다. + 재지 않았다. |