diff options
| -rw-r--r-- | docs/research/140-spec-suite.md | 29 | ||||
| -rw-r--r-- | research/experiments/044-specs/2026-10-19-dns-after.jsonl | 4 | ||||
| -rw-r--r-- | research/experiments/044-specs/2026-10-19-http-after.jsonl | 4 | ||||
| -rw-r--r-- | research/experiments/044-specs/2026-10-19-inflate-after.jsonl | 4 | ||||
| -rw-r--r-- | research/experiments/044-specs/http_check.py | 2 | ||||
| -rw-r--r-- | research/experiments/044-specs/http_time.c | 2 | ||||
| -rw-r--r-- | research/experiments/044-specs/inflate_check.py | 3 | ||||
| -rw-r--r-- | research/experiments/044-specs/inflate_time.c | 18 | ||||
| -rw-r--r-- | tests/check.py | 6 |
9 files changed, 59 insertions, 13 deletions
diff --git a/docs/research/140-spec-suite.md b/docs/research/140-spec-suite.md index 187e0cf..1963c70 100644 --- a/docs/research/140-spec-suite.md +++ b/docs/research/140-spec-suite.md @@ -47,15 +47,15 @@ | # | 명세 | 분야 | 처음 필요한 것 | Pure 안의 검증 | 10-13 | 027 뒤(10-19) | |---|---|---|---|---|---|---| -| 1 | DNS 메시지(RFC 1035) | 와이어 프로토콜 | 바이트 읽고 쓰기, 빅엔디언, 비트 필드, 이름 압축(바이트 안의 참조) | 알려진 구현이 만든 질의·응답 바이트와 대조 | 못 쓴다(바이트, 비트) | 썼다: dnspython의 메시지 400개를 읽고 다시 써 같다. 우회 둘, 줄 수 못 미침, C의 67배(아래) | +| 1 | DNS 메시지(RFC 1035) | 와이어 프로토콜 | 바이트 읽고 쓰기, 빅엔디언, 비트 필드, 이름 압축(바이트 안의 참조) | 알려진 구현이 만든 질의·응답 바이트와 대조 | 못 쓴다(바이트, 비트) | 썼다: dnspython의 메시지 400개를 읽고 다시 써 같다. 우회 하나(보기의 블록 fn), 줄 1.5배, C의 61배(아래) | | 2 | SHA-256(FIPS 180-4) | 해시 | 32비트 낱말, 회전, xor | NIST CAVP의 SHA 벡터 | 우회로만 될 것으로 보인다(써 보지 않음) | 썼다: NIST 벡터를 세 실행 길에서 지난다(1단계) | -| 3 | inflate(RFC 1951) | 압축 | 비트 읽기, 허프만 표, 뒤 참조 | zlib로 압축한 말뭉치를 풀어 원본과 비교 | 못 쓴다(바이트, 비트) | 썼다: zlib 스트림 640개, 손상 240개가 파이썬 참조와 같다. 우회 셋, 줄 수 못 미침, C의 108배(아래) | +| 3 | inflate(RFC 1951) | 압축 | 비트 읽기, 허프만 표, 뒤 참조 | zlib로 압축한 말뭉치를 풀어 원본과 비교 | 못 쓴다(바이트, 비트) | 썼다: zlib 스트림 640개, 손상 240개가 파이썬 참조와 같다. 우회 없음, 줄 1.5배, C의 102배(아래) | | 4 | JSON(RFC 8259) → 트리와 질의 | 깊이를 모르는 데이터 | 글자 읽기, 중첩, 재귀, 갈래 | JSONTestSuite | 못 쓴다(글자, 중첩, 재귀, 갈래) | 썼다: JSONTestSuite와 무작위 문서가 파이썬과 같다(2a–2c) | | 5 | UTF-8과 줄 나누기(UAX #14) | 텍스트 | 바이트, 코드 포인트, 속성 표 | Unicode의 `LineBreakTest.txt` | 못 쓴다(글자) | 글자 읽기가 컴파일된다(2c). 쓰지 않음 | | 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다 | 썼다: 스트림 200개를 어디서 잘라도 h11과 같다. 우회 셋, 줄 수 못 미침, C의 85배(아래) | +| 9 | HTTP/1.1 요청을 패킷마다(RFC 9112) | 스트림의 상태 기계 | 바이트, 이벤트를 넘는 상태 | 경계를 아무 데서나 자른 요청 모음 | 못 쓴다(바이트). 지금은 `serve/`의 C다 | 썼다: 스트림 200개를 어디서 잘라도 h11과 같다. 우회 하나(리스트 값의 대입), 줄 1.9배, C의 83배(아래) | | 10 | 재시도, 물러서기, 시간 제한 | 시간 | 시각, 한 번의 타이머 | 시각을 준 시뮬레이션 | 우회(주기 틱 `every`와 `now`) | 다시 보지 않음 | | 11 | X25519, ChaCha20-Poly1305 | 상수 시간 암호 | 데이터에 따라 달라지지 않는 시간 | RFC 7748, RFC 8439의 벡터 | aup 밖(설계상, 아래) | 그대로(설계상 aup 밖) | @@ -695,6 +695,29 @@ - 시간은 명령당 3.8–6.0 ns가 든다. 바이트 일을 C에 가깝게 하려면 명령의 수(바이트 찾기 같은 일을 명령 하나로 할지)와 명령당 비용(기계어 계층이 맡지 못하는 명령들) 둘 다를 봐야 한다. 이것도 따로 정한다. +## 우회를 걷어 내고 다시 잼 (2026-10-19) + +결정점 뒤에 만든 넷(바이트의 `==`, 바이트 하나인 상태, fn의 맨 리스트, 블록 안의 let 리스트)으로 세 명세의 우회를 걷어 냈다. 앱은 +파이썬 참조의 꼴에 더 가까워졌다. inflate의 블록마다의 표는 핸들러 안에서 짓고, HTTP의 남은 바이트는 바이트 상태다. 세 명세의 검사가 +세 실행 길에서 그대로 지난다(zlib 스트림 640개와 손상 240개, dnspython의 메시지 400개와 손상 300개, h11의 스트림 200개를 모든 +자름으로, 손상 200개). + +| 명세 | 줄(닫는 괄호) 전 → 뒤 | 파이썬 | 바이트당 ns 전 → 뒤 | 같은 알고리즘의 C 대비 | 바이트당 명령 | 남은 우회 | +|---|---|---|---|---|---|---| +| inflate | 132(18) → 121(15) | 81 | 1,152 → 1,139 | 108배 → 102배 | 191.2 → 191.2 | 없음 | +| DNS | 115(21) → 106(18) | 72 | 244 → 221 | 67배 → 61배 | 63.6 → 49.9 | 보기가 블록 fn을 부르지 못한다(압축을 보기 안에 풀어 쓴다) | +| HTTP/1.1 | 159(24) → 148(21) | 79 | 278 → 270 | 85배 → 83배 | 61.4 → 61.5 | let의 리스트에 리스트 값을 대입하지 못해 트레일러를 하나씩 붙인다(2줄) | + +- **줄.** 파이썬의 1.6–2.0배에서 1.5–1.9배로 줄었다. 남은 차이의 대부분은 닫는 괄호의 줄과 레코드의 선언, 그리고 바이트마다 도는 + 고리(파이썬의 `find`, `strip`, `partition`이 C로 도는 곳)다. +- **시간.** DNS의 압축이 바이트를 한 바이트씩 견주던 것을 `==` 한 번으로 하니 명령이 21% 줄었다. inflate와 HTTP는 명령 수가 거의 + 같다: 우회의 값은 줄에 있었지 시간에 있지 않았다. +- **빈 잇기.** HTTP의 남은 바이트를 바이트 상태로 두자, 비어 있을 때도 `pending + packet.data`가 패킷을 통째로 복사해 같은 명령 수에 + 5.6% 느려졌다(273 → 288 ns). Pure의 CONCAT이 한쪽이 비면 다른 쪽을 복사 없이 그대로 두게 했다(뜻은 같다: 값은 바뀌지 않는다). + 그 뒤 옛 앱과 새 앱이 같은 시간이다(270.0 대 270.6 ns, 같은 자리에서 번갈아). 041의 다섯 일은 실행기만의 knapsack −0.42%, join + −0.16%, 묶음 BFS −0.12%, 나머지 ±0.03% 안이다(b48 대 b47). +- 원본: `2026-10-19-inflate-after.jsonl`, `-dns-after.jsonl`, `-http-after.jsonl`(검사 한 줄과 세 길의 시간). + ## 착수 기준 (다음 일) - **바꿀 결정.** 계산의 핵을 설계한다(027). 위 표의 여덟 후보 가운데 무엇을 어떤 모양으로 받을지 정한다. diff --git a/research/experiments/044-specs/2026-10-19-dns-after.jsonl b/research/experiments/044-specs/2026-10-19-dns-after.jsonl new file mode 100644 index 0000000..529ebbc --- /dev/null +++ b/research/experiments/044-specs/2026-10-19-dns-after.jsonl @@ -0,0 +1,4 @@ +{"messages": 400, "bytes": 148582, "records": 3466, "right": {"batches": 400, "rounds": 400, "all": 400}, "paths_same": true, "damaged": 300, "damaged_refused": 185, "damaged_agreed": 300, "aup_lines": 106, "aup_brace_lines": 18, "python_lines": 72} +{"messages":400,"bytes":148582,"jit":"0","batch":"","c_ns_per_byte":3.657,"resolver_read_ns_per_byte":4.406,"pure_ns_per_byte":221.336,"to_c":60.5,"to_resolver_read":50.2,"instructions":7409761,"instructions_per_byte":49.9} +{"messages":400,"bytes":148582,"jit":"0","batch":"0","c_ns_per_byte":3.656,"resolver_read_ns_per_byte":4.402,"pure_ns_per_byte":221.159,"to_c":60.5,"to_resolver_read":50.2,"instructions":7409761,"instructions_per_byte":49.9} +{"messages":400,"bytes":148582,"jit":"all","batch":"","c_ns_per_byte":3.658,"resolver_read_ns_per_byte":4.401,"pure_ns_per_byte":203.141,"to_c":55.5,"to_resolver_read":46.2,"instructions":7409761,"instructions_per_byte":49.9} diff --git a/research/experiments/044-specs/2026-10-19-http-after.jsonl b/research/experiments/044-specs/2026-10-19-http-after.jsonl new file mode 100644 index 0000000..d3c57ef --- /dev/null +++ b/research/experiments/044-specs/2026-10-19-http-after.jsonl @@ -0,0 +1,4 @@ +{"streams": 200, "bytes": 132623, "requests": 578, "right": {"whole": 200, "random": 200, "bytes": 50}, "paths": {"batches": 200, "rounds": 200, "all": 200}, "paths_same": true, "damaged": 200, "damaged_refused": 35, "damaged_agreed": 200, "aup_lines": 148, "aup_brace_lines": 21, "python_lines": 79} +{"streams":151,"bytes":98838,"requests":444,"jit":"0","batch":"","c_ns_per_byte":3.249,"pure_ns_per_byte":270.433,"to_c":83.2,"instructions":6074414,"instructions_per_byte":61.5} +{"streams":151,"bytes":98838,"requests":444,"jit":"0","batch":"0","c_ns_per_byte":3.250,"pure_ns_per_byte":270.680,"to_c":83.3,"instructions":6074414,"instructions_per_byte":61.5} +{"streams":151,"bytes":98838,"requests":444,"jit":"all","batch":"","c_ns_per_byte":3.245,"pure_ns_per_byte":270.454,"to_c":83.3,"instructions":6074414,"instructions_per_byte":61.5} diff --git a/research/experiments/044-specs/2026-10-19-inflate-after.jsonl b/research/experiments/044-specs/2026-10-19-inflate-after.jsonl new file mode 100644 index 0000000..179d2de --- /dev/null +++ b/research/experiments/044-specs/2026-10-19-inflate-after.jsonl @@ -0,0 +1,4 @@ +{"streams": 640, "bytes": 6488480, "right": {"batches": 640, "rounds": 640, "all": 640}, "paths_same": true, "damaged": 240, "damaged_refused": 165, "damaged_agreed": 240, "aup_lines": 121, "aup_brace_lines": 15, "python_lines": 81} +{"size":65536,"stream":22991,"jit":"0","batch":"","c_ns_per_byte":11.140,"zlib_ns_per_byte":3.499,"pure_ns_per_byte":1138.637,"to_c":102.2,"to_zlib":325.4,"instructions":12528479,"instructions_per_byte":191.2} +{"size":65536,"stream":22991,"jit":"0","batch":"0","c_ns_per_byte":11.121,"zlib_ns_per_byte":3.505,"pure_ns_per_byte":1139.351,"to_c":102.5,"to_zlib":325.1,"instructions":12528479,"instructions_per_byte":191.2} +{"size":65536,"stream":22991,"jit":"all","batch":"","c_ns_per_byte":10.649,"zlib_ns_per_byte":3.499,"pure_ns_per_byte":1136.972,"to_c":106.8,"to_zlib":324.9,"instructions":12528479,"instructions_per_byte":191.2} diff --git a/research/experiments/044-specs/http_check.py b/research/experiments/044-specs/http_check.py index e3982c3..305f783 100644 --- a/research/experiments/044-specs/http_check.py +++ b/research/experiments/044-specs/http_check.py @@ -137,7 +137,7 @@ def run(module, packets, env, work): pairs = lambda fs: [(bytes.fromhex(f['name']), bytes.fromhex(f['value'])) for f in fs] requests = [(bytes.fromhex(r['method']), bytes.fromhex(r['target']), r['minor'], pairs(r['fields']), bytes.fromhex(r['body']), pairs(r['trailers'])) for r in s['requests']] - left = bytes.fromhex(s['pending'][0]['data']) if s['pending'] else b'' + left = bytes.fromhex(s['pending']) # a bytes state (028) return out, (requests, left), any(json.loads(line)['fault'] != 'none' for line in out) diff --git a/research/experiments/044-specs/http_time.c b/research/experiments/044-specs/http_time.c index 51bd595..dc85fc1 100644 --- a/research/experiments/044-specs/http_time.c +++ b/research/experiments/044-specs/http_time.c @@ -217,7 +217,7 @@ int main(int argc, char **argv) { } work += app.work; } - if ((long)pure_list_count(app.lists[requests]) != c_requests || pure_list_count(app.lists[left])) { + if ((long)pure_list_count(app.lists[requests]) != c_requests || pure_draft_size(app.texts[left])) { fprintf(stderr, "Pure read %zu requests, C %ld\n", pure_list_count(app.lists[requests]), c_requests); return 1; } diff --git a/research/experiments/044-specs/inflate_check.py b/research/experiments/044-specs/inflate_check.py index c3f37b4..d71e59e 100644 --- a/research/experiments/044-specs/inflate_check.py +++ b/research/experiments/044-specs/inflate_check.py @@ -72,8 +72,7 @@ def run(module, packed_streams, env, work): got = [] for line in out: state = json.loads(line) - items = state['states']['inflated'] - got.append(bytes.fromhex(items[-1]['data']) if state['fault'] == 'none' and items else None) + got.append(bytes.fromhex(state['states']['inflated']) if state['fault'] == 'none' else None) # a bytes state (028) return out, got diff --git a/research/experiments/044-specs/inflate_time.c b/research/experiments/044-specs/inflate_time.c index 34cc2d5..8463a22 100644 --- a/research/experiments/044-specs/inflate_time.c +++ b/research/experiments/044-specs/inflate_time.c @@ -159,6 +159,15 @@ static int by_value(const void *a, const void *b) { return (x > y) - (x < y); } +/* Each span of a draft read in order against the original's bytes from where the last ended. */ +static size_t compared; +static bool compare_original(void *context, PureSpan span) { + const unsigned char *original = context; + if (memcmp(original + compared, span.data, span.size)) return false; + compared += span.size; + return true; +} + static unsigned char *whole(const char *path, size_t *size) { FILE *f = fopen(path, "rb"); if (!f) return NULL; @@ -199,9 +208,12 @@ int main(int argc, char **argv) { return 1; } uint64_t work = app.work - before; - const PureList *list = app.lists[state]; - PureCell cell = pure_list_count(list) == 1 ? pure_list_get(list, 0, 0) : (PureCell){0}; - if (cell.size != original_size || memcmp(cell.text, original, original_size)) { fprintf(stderr, "Pure's bytes differ\n"); return 1; } + /* The bytes state (028): its draft's bytes. */ + if (pure_draft_size(app.texts[state]) != original_size || + pure_draft_read(app.texts[state], 0, original_size, compare_original, original) != PURE_OK) { + fprintf(stderr, "Pure's bytes differ\n"); + return 1; + } double c_runs[7], zlib_runs[7], pure_runs[7]; volatile unsigned char sink = 0; diff --git a/tests/check.py b/tests/check.py index b3b4750..046e61a 100644 --- a/tests/check.py +++ b/tests/check.py @@ -1864,9 +1864,9 @@ def module_specs(aup, pure, work): shown = [json.loads(line) for line in outputs['batches'].splitlines()] assert len(shown) == len(streams) + len(cut), ('inflate', len(shown)) for (data, _), state in zip(streams, shown): - assert state['fault'] == 'none' and state['states']['inflated'][-1]['data'] == data.hex(), ('inflate', len(data)) + assert state['fault'] == 'none' and state['states']['inflated'] == data.hex(), ('inflate', len(data)) for state in shown[len(streams):]: - assert state['fault'] != 'none' and state['states']['inflated'][-1]['data'] == streams[-1][0].hex(), ('inflate cut', state['fault']) + assert state['fault'] != 'none' and state['states']['inflated'] == streams[-1][0].hex(), ('inflate cut', state['fault']) runs['inflate'] = {'streams': len(streams), 'bytes': sum(len(d) for d, _ in streams), 'cut': len(cut)} # DNS messages (RFC 1035, its examples/dns.aup): messages dnspython made (tests/specs/dns), each read without fault on # the three paths, what its view wire writes back read to the same records and written again to the same bytes; a @@ -1920,7 +1920,7 @@ def module_specs(aup, pure, work): s = json.loads(out[-1])['states'] pairs = lambda fs: [[f['name'], f['value']] for f in fs] return out[-1], {'requests': [[r['method'], r['target'], r['minor'], pairs(r['fields']), r['body'], pairs(r['trailers'])] - for r in s['requests']], 'left': s['pending'][0]['data'] if s['pending'] else ''} + for r in s['requests']], 'left': s['pending']} cuts = 0 for stream, want in zip(made, reading): |