1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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]`, 간선 조각의 경계)이 대부분일 것이다.
재지 않았다.
|
