diff options
| author | eunhhu <[email protected]> | 2026-10-19 03:02:51 +0100 |
|---|---|---|
| committer | eunhhu <[email protected]> | 2026-10-19 03:02:51 +0100 |
| commit | 5842b26e8353a38192afb1ebe4c08809da48dbf4 (patch) | |
| tree | a4bf3d5e8ad8194b37d1beb1fa3639a6fd12c279 /docs/research | |
| parent | 85a35189c6588903ffc287837c9005ef3063e056 (diff) | |
| download | pure-5842b26e8353a38192afb1ebe4c08809da48dbf4.tar.gz pure-5842b26e8353a38192afb1ebe4c08809da48dbf4.zip | |
140's 9, HTTP/1.1 requests a packet at a time (RFC 9112), written in aup with no new opcode (aup's examples/http.aup: each packet an event, its bytes added to what the last left, every request they complete read, h11's grammar): 200 streams (132,623 bytes, 578 requests: methods, targets, HTTP/1.1 and a last 1.0, mixed-case names, spaces around values, Content-Length and chunked bodies with extensions and trailers, some ending in part of a request) fed whole, at random boundaries and a byte at a time (the 50 under 400 bytes), the requests read h11's on every cut and the bytes left those after them, the three paths' outputs the same bytes; 200 damaged streams fed whole as http_requests.py (the Python reference) reads them, 35 refused by both and 165 the same; module_specs in make check: 80 streams and their reading (tests/specs/http, no h11 at check time) whole on the three paths and cut 88 ways; bars: written, three workarounds (the bytes left in a list of one: bytes are no state; names and codings compared as text: bytes have no ==; field lines returned in a record: a fn returns no bare list), 159 lines against Python's 79, 278 ns a byte against the same algorithm in C 3.27 (85x), pure Python 67 (its bytes methods are C: Pure 4.1x slower), h11 284; 140's decision point after 027: bytes alone as a state (inflate, HTTP) and bytes' == (DNS, HTTP) now each met by two written specs, so the two-spec rule lets them into the core (their design not begun); a view calling a block fn met by one (DNS); aup's three its compiler's; CHECKPOINT's direction row
Diffstat (limited to 'docs/research')
| -rw-r--r-- | docs/research/140-spec-suite.md | 89 |
1 files changed, 87 insertions, 2 deletions
diff --git a/docs/research/140-spec-suite.md b/docs/research/140-spec-suite.md index cc9898c..28883a0 100644 --- a/docs/research/140-spec-suite.md +++ b/docs/research/140-spec-suite.md @@ -29,11 +29,13 @@ - **다음 결정.** 계산의 핵을 설계한다. 여섯 가지와 고정 한도, 상수 시간 암호가 핵이 받아야 할 최소의 후보다. - **027 뒤(2026-10-19).** 핵을 다섯 단계로 다시 세웠다. 탐침의 필요는 셋을 빼고 모두 컴파일된다: 보기에서 재귀 fn을 부르기, 레코드나 갈래 하나인 상태, 커서 자리의 글자(아래 "027 뒤의 탐침"). 묶음에서 쓴 것은 2(SHA-256), 4(JSON), 3(inflate), - 1(DNS)이다. + 1(DNS), 9(HTTP/1.1)이다. inflate는 새 명령 없이 써졌고 zlib의 스트림을 모두 맞게 푼다. 다만 우회가 셋(리스트를 받는 fn, 바이트 하나인 상태, 블록 안의 리스트)이고, 줄은 파이썬의 1.6배, 시간은 같은 알고리즘의 C의 108배다. DNS도 새 명령 없이 써졌고 dnspython의 메시지를 모두 맞게 읽고 다시 쓴다. 우회는 둘(바이트의 `==`, 보기에서의 블록 fn)이고, 보기에서 블록 fn을 부르지 못하는 틈에 써서 닿은 것은 DNS가 처음이다(배치는 탐침뿐). 줄은 파이썬의 1.6배, 시간은 C의 67배다. + HTTP/1.1(패킷마다)도 새 명령 없이 써졌고, 어디서 잘라도 h11과 같다. 이로써 바이트 하나인 상태와 바이트의 `==`는 써서 닿은 + 명세가 둘이 되었다(아래 "027 뒤의 결정점"). ## 묶음 @@ -53,7 +55,7 @@ | 6 | 관계 질의, 그래프 탐색 | 데이터 모델 | 리스트, 키, 접기, 이벤트의 리스트 | TPC-C, 은행 질의, 파이썬 모델 | 된다(기준선: [092](092-tpcc.md), 040의 은행 질의, aup `routes.aup`) | 된다. TPC-C가 SQLite와 오차 없이 같다(5단계) | | 7 | 텍스트 편집 | UI 개념 | text, 커서 | 편집기의 참조 모델 대조(aup `make check`) | 된다 | 된다 | | 8 | 상자 배치(flex 같은) | UI 개념 | 중첩, 재귀 | 기존 배치 구현(Yoga, Taffy)의 결과와 대조 | 못 쓴다(중첩, 재귀) | 중첩과 재귀는 핸들러에서 된다. 보기에서 재귀 fn을 부르지 못한다(탐침). 쓰지 않음 | -| 9 | HTTP/1.1 요청을 패킷마다(RFC 9112) | 스트림의 상태 기계 | 바이트, 이벤트를 넘는 상태 | 경계를 아무 데서나 자른 요청 모음 | 못 쓴다(바이트). 지금은 `serve/`의 C다 | 처음 필요한 것(바이트)이 컴파일된다. 쓰지 않음 | +| 9 | HTTP/1.1 요청을 패킷마다(RFC 9112) | 스트림의 상태 기계 | 바이트, 이벤트를 넘는 상태 | 경계를 아무 데서나 자른 요청 모음 | 못 쓴다(바이트). 지금은 `serve/`의 C다 | 썼다: 스트림 200개를 어디서 잘라도 h11과 같다. 우회 셋, 줄 수 못 미침, C의 85배(아래) | | 10 | 재시도, 물러서기, 시간 제한 | 시간 | 시각, 한 번의 타이머 | 시각을 준 시뮬레이션 | 우회(주기 틱 `every`와 `now`) | 다시 보지 않음 | | 11 | X25519, ChaCha20-Poly1305 | 상수 시간 암호 | 데이터에 따라 달라지지 않는 시간 | RFC 7748, RFC 8439의 벡터 | aup 밖(설계상, 아래) | 그대로(설계상 aup 밖) | @@ -594,6 +596,89 @@ - `2026-10-19-dns.jsonl`: 잰 수 - `tests/specs/dns/`: Pure의 검사가 읽는 메시지 200개 +## 묶음의 9: HTTP/1.1 요청을 패킷마다 (2026-10-19) + +027 뒤에 셋째로 쓴 명세다. 새 명령도 코어의 C도 없이 aup와 Pure만으로 썼다(aup의 `examples/http.aup`). +- **패킷마다의 이벤트.** 패킷 하나가 이벤트 하나다. 그 바이트를 앞 패킷들이 남긴 바이트 뒤에 잇고, 그것으로 끝나는 요청을 모두 + 읽는다. 요청 줄, 필드(이름은 소문자로), Content-Length나 chunked의 본문, chunked의 트레일러를 읽는다. 남은 바이트는 다음 패킷을 + 기다린다. +- **문법은 h11의 것이다.** 머리 값의 낱말에는 NUL, 공백류, CR, LF가 없다. chunk의 크기는 16진 1–20자리이고, `;` 뒤의 확장은 줄 + 끝까지다. Host는 하나이고, HTTP/1.1이면 꼭 있다. Transfer-Encoding은 `chunked` 하나만 받고, Content-Length와 함께면 거절한다. +- **우리가 더한 것.** 크기와 길이는 2^31까지만 받는다. h11에는 없는 한도다. + +**맞음.** +- `http_check.py`: 스트림 200개(132,623바이트, 요청 578개)를 쓴다. + - 요청은 여러 메서드와 대상이다. HTTP/1.1이고, 마지막 하나는 HTTP/1.0일 수 있다. 필드 이름은 대소문자가 섞이고 값의 양옆에 + 공백이 있다. 본문은 Content-Length나 chunked(확장, 트레일러)다. 일부 스트림은 요청의 앞부분에서 끝난다. + - 각 스트림을 통째로, 무작위 경계로, 짧으면(400바이트 아래 50개) 한 바이트씩 잘라 패킷마다 이벤트로 준다. + - 읽은 요청은 모든 자름에서 h11(바이트가 오는 대로 읽는 알려진 구현)과 같다. 남은 바이트는 마지막 요청 뒤의 바이트다. 세 길의 + 출력이 바이트까지 같다. + - 견줄 때 h11이 Transfer-Encoding의 값만 소문자로 바꿔 내놓는 것은 맞춰 준다. +- 손상된 스트림 200개(자른 것, 비트 하나를 뒤집은 것)를 통째로 주고, 같은 길로 읽는 파이썬 참조(`http_requests.py`)와 견준다. 35개는 + 둘 다 거절하고, 165개는 같은 요청과 같은 남은 바이트를 낸다. +- Pure의 `make check`(`module_specs`)에 들어갔다. h11에 기대지 않도록, 스트림 80개와 그 읽음을 `tests/specs/http`에 두었다. + - 스트림마다 통째로 세 길에서 준다. + - 무작위 경계와, 짧으면 한 바이트씩으로도 준다(자른 꼴 88개). 모두 같은 요청과 남은 바이트다. + +**막대.** + +| 막대 | 잰 것 | | +|---|---|---| +| 쓸 수 있다 | aup와 Pure만. 새 명령 없음 | 지남 | +| 우회가 없다 | 셋(아래): 항목 하나의 리스트에 둔 남은 바이트, text로 바꿔 견준 바이트, 레코드에 담아 돌려준 필드의 리스트 | **못 미침** | +| 줄 수 ≤ 파이썬 참조 | aup 159줄(닫는 괄호만인 줄 24) 대 파이썬 79줄 | **못 미침** | +| C 대비 시간 | 온전한 스트림 151개(98,838바이트, 요청 444개)를 패킷 하나씩. 바이트당 278 ns, 같은 알고리즘의 C(3.27 ns)의 **85배**. 순수 파이썬 67 ns(Pure가 **4.1배 느림**), h11 284 ns(Pure와 비슷하다). 기계어 계층도 같다(278 ns) | 기록(막대 없음) | +| 견고하다 | 위의 맞음, 세 길이 같음, 예산 안에서 끝남. 세 기계는 아직 돌리지 않았다 | 일부 | + +**우회 셋.** +1. **바이트 하나인 상태가 없다.** 패킷 사이의 남은 바이트는 바이트 하나가 제격인 상태다. 항목 하나의 리스트 `pending`에 두고, + 이벤트마다 꺼내 지우고 다시 둔다. inflate의 둘째 우회와 같다. +2. **바이트에 `==`가 없다.** 필드 이름(`host`, `content-length`, `transfer-encoding`), 판(`HTTP/1.`), 코딩(`chunked`)을 `text(…)`로 + 바꿔 견준다. 토큰은 ASCII라 text가 되므로 이번에는 짧게 됐다. ASCII가 아닌 값이면 그 변환이 `encoding`으로 실패한다. 그래도 그런 + 요청은 어차피 거절할 것이라 뜻은 같다. DNS의 첫째 우회와 같다. +3. **fn이 맨 리스트를 돌려주지 못한다.** 머리와 트레일러의 필드 줄을 읽는 fn이 리스트를 레코드 `Fields`에 담아 돌려준다. inflate의 + 첫째 우회(aup의 일)와 같다. + +**줄을 길게 한 것.** 159 대 79다. 닫는 괄호의 줄을 빼면 135다. +- 닫는 괄호의 줄이 24줄이다. +- 레코드 넷(`Field`, `Fields`, `Request`, `Left`)이 18줄이다. 파이썬은 튜플이다. +- 파이썬의 바이트 메서드(`find`, `partition`, `strip`, `split`, `lower`, 집합의 `<=`)가 한 줄씩인 곳을, aup는 바이트마다 도는 고리로 + 쓴다. CRLF 찾기의 fn이 8줄, 소문자의 fn이 5줄(둘 다 괄호의 줄을 포함한다), 콜론 찾기와 양옆 공백 깎기가 6줄, 요청 줄의 공백 + 찾기가 4줄, 토큰과 16진의 판정이 5줄이다. + +**시간이 가는 곳.** 바이트당 Pure 명령이 61.4개이고, 명령 하나에 약 4.5 ns가 든다. +- 파이썬이 4배 빠른 것은 위의 바이트 메서드가 C로 돌기 때문이다. aup는 같은 일을 바이트마다 명령으로 한다. 같은 일을 파이썬으로만 + 하는 h11(정규식과 바이트 메서드)은 Pure와 비슷하다. +- 기계어 계층은 빠르게 하지 못한다(278 대 277 ns). + +**원본.** `research/experiments/044-specs/` +- `http_requests.py`: 파이썬 참조. 그 아래의 main은 같은 스트림에서 그것과 h11의 시간을 잰다. +- `http_check.py`: 맞음과 줄 수. 경로를 주면 `http_time.c`가 읽을 스트림을 쓰고, 디렉터리를 하나 더 주면 `tests/specs/http`를 쓴다. +- `http_time.c`: 같은 스트림으로 같은 알고리즘의 C와 Pure의 시간. 두 쪽이 같은 수의 요청을 읽어야 잰다. +- `2026-10-19-http.jsonl`: 잰 수 +- `tests/specs/http/`: Pure의 검사가 읽는 스트림 80개와 그 읽음 + +## 027 뒤의 결정점 (2026-10-19) + +명세 셋(inflate, DNS, HTTP/1.1)을 새 명령 없이 썼다. 모두 알려진 구현(zlib, dnspython, h11)과 같고, 손상된 입력에서 같은 길로 +읽는 파이썬 참조와 같다. 셋 다 줄 수는 파이썬의 1.6–2.0배이고, 시간은 같은 알고리즘의 C의 67–108배다. 쓰며 드러난 틈과 그것에 +써서 닿은 명세는 다음과 같다. + +| 틈 | 주인 | 써서 닿은 명세 | 쌓임을 막는 규칙(둘 이상) | +|---|---|---|---| +| 바이트 하나인 상태 | Pure의 상태 종류 | inflate, HTTP | **넘는다** | +| 바이트의 `==` | Pure(TEXT_COMPARE가 text만 받는다) | DNS, HTTP | **넘는다** | +| 보기에서 블록 fn 부르기 | Pure(CALL은 핸들러와 함수에만) | DNS(배치는 탐침뿐) | 아직 하나 | +| fn이 맨 리스트를 받거나 돌려주기 | aup | inflate, HTTP | 핵이 아니다 | +| 블록 안의 let 리스트 | aup | inflate | 핵이 아니다 | +| 작은 블록 fn의 인라인 | aup | inflate(시간의 23%) | 핵이 아니다 | + +- 앞의 둘은 이제 핵에 들일 자격이 있다. 바이트 하나인 상태(저장, 교체, 보기, HTTP의 GET이 그것을 어떻게 다루는가)와 바이트의 비교 + (TEXT_COMPARE의 인자로 할지, 새 명령으로 할지)는 설계 문서에서 정한다. 아직 시작하지 않았다. +- aup의 셋은 컴파일러의 일이다. Pure의 함수 서명은 이미 리스트를 받는다. +- 시간은 명령당 3.8–6.0 ns가 든다. 바이트 일을 C에 가깝게 하려면 명령의 수(바이트 찾기 같은 일을 명령 하나로 할지)와 명령당 + 비용(기계어 계층이 맡지 못하는 명령들) 둘 다를 봐야 한다. 이것도 따로 정한다. + ## 착수 기준 (다음 일) - **바꿀 결정.** 계산의 핵을 설계한다(027). 위 표의 여덟 후보 가운데 무엇을 어떤 모양으로 받을지 정한다. |
