diff options
| -rw-r--r-- | CHECKPOINT.md | 2 | ||||
| -rw-r--r-- | docs/research/140-spec-suite.md | 63 | ||||
| -rw-r--r-- | research/experiments/044-specs/2026-10-19-inflate.jsonl | 5 | ||||
| -rw-r--r-- | research/experiments/044-specs/inflate.py | 109 | ||||
| -rw-r--r-- | research/experiments/044-specs/inflate_check.py | 105 | ||||
| -rw-r--r-- | research/experiments/044-specs/inflate_time.c | 231 | ||||
| -rw-r--r-- | research/experiments/044-specs/json_rec_time.c | 4 | ||||
| -rw-r--r-- | research/experiments/044-specs/json_time.c | 4 | ||||
| -rw-r--r-- | research/experiments/044-specs/json_tree_time.c | 4 | ||||
| -rw-r--r-- | research/experiments/044-specs/time.c | 4 | ||||
| -rw-r--r-- | tests/check.py | 37 |
11 files changed, 556 insertions, 12 deletions
diff --git a/CHECKPOINT.md b/CHECKPOINT.md index 4bdbe2c..450acc7 100644 --- a/CHECKPOINT.md +++ b/CHECKPOINT.md @@ -26,7 +26,7 @@ | 표 크기의 상태 | 목록이 영속 B+트리다(변경·키 탐색·저장본 위치 O(log n), 스냅숏 O(1), 1,600만 항목, 런타임 상태 1 GiB). pgbench의 TPC-B 같은 이체(세 표의 행과 이력, 한 트랜잭션)가 10만 계좌에서 RAM 24.5k/s(전: 3만 계좌 3.2k/s), SD 카드 내구 1,339/s(SQLite WAL FULL 84–153/s) | [090](docs/research/090-tables.md) | | 일반 트랜잭션 | TPC-C의 다섯 트랜잭션을 aup 앱 하나로 쓴다(여러 표 읽기·쓰기, 조각 훑기, 중복 없는 셈, 실패하면 통째 되돌림). 같은 입력에서 SQLite와 아홉 표의 모든 행이 같다(창고 하나와 넷). RAM 초당 40,976건(W=4 35,838; 조율한 SQLite 10,164, 트랜잭션당 CPU 43–50 µs, HTTP·JSON 포함), SD 카드 내구 4,980건(W=4 4,590). SQLite도 카드에 맞게 조율하고 묶어 커밋하면 739건(W=4 426)이다. 남은 차이는 거래당 쓰는 바이트다(SQLite는 페이지째 써서 8–18배) | [092](docs/research/092-tpcc.md), [106](docs/research/106-tpcc-conditions-first.md), [107](docs/research/107-snapshot-nodes-reused.md) | | 질의 | 질의는 앱의 상태 위에 보기를 더한 모듈이다(`aup query`, `PUT·GET /queries/이름`). 검증한 뒤 스냅숏에서 돌고, 열 안의 fold가 그 행을 읽는다(상관 부질의). 잎이 항목을 필드별로 들고, fold와 필터는 잎 하나씩 돌며(결함이 날 잎만 항목별로), 열 안의 그룹·순위 fold는 목록을 한 번 지나 모든 행에 답한다. 10만 계좌에서 지점별 합계 4.9 ms(SQLite 45, 인덱스를 주면 14.3), 조인 0.48 ms(1.47), 자기 조인 순위 6.8 ms(2,840, 인덱스를 주면 7.6). Pure에는 인덱스 선언이 없다 | [091](docs/research/091-queries.md) | -| 방향(1.0 전) | 앱 계약을 1.0에서 얼릴 후보로 적었다: 이벤트는 전함수이고 원자적이며 결정적이다, 시간은 입력이다, 보기는 커밋된 상태의 순수 함수다, 보이는 역사는 커밋의 앞부분이다, 전달은 순서대로 한 번이다. 계산의 언어(명령 90개, 상태 종류 7개)는 패턴의 모음이라 다시 세운다. 분야마다 고른 명세 열한 개의 묶음에서 오늘의 aup는 바이트, 비트 연산, 중첩, 재귀, 갈래, 글자 읽기에 막힌다(탐침 열 개). 1.0 전에는 호환을 챙기지 않고, JSON과 HTTP는 경계에 남는다. 계산의 핵을 다섯 단계로 다시 세운다(027). 1단계(비트 연산, 자리의 바이트, 수의 리스트, 한 번에 주기)로 aup로 쓴 SHA-256이 공식 벡터를 세 실행 길에서 모두 지난다. 2a(형식 지정, 바이트 잇기와 자르기, 바이트와 text의 let, `while`, 단락 평가의 `&&`·`||`)로 쓴 JSON 검사기가 JSONTestSuite에서 하나도 틀리지 않는다. 2b(레코드 안의 레코드, 갈래와 `match`, 레코드 안의 리스트, 수 읽기)로 JSON을 트리로 읽어 다이제스트가 파이썬과 같다(JSONTestSuite, 무작위 문서 300개). 2c(스스로 부르는 함수: 부름마다 제 스택·지역 칸·리스트·레지스터·담은 값, 깊이는 표로 센 프레임 바이트가 몫에서 묶음; 값으로서의 레코드; 글자 읽기)로 JSON 트리를 재귀 하강으로 다시 써 JSONTestSuite와 무작위 문서 300개가 파이썬과 같고, 10만 겹은 `memory`로 거절한다. 반복 아래에 값을 둔 모듈이 검증을 지나 실행기를 죽이던 구멍도 찾아 막았다. 3단계(중첩한 저장 상태: 저장과 transient의 리스트가 리스트를 담은 레코드를 받고, 그 칸은 값을 항목들의 저장 형태로 바이트처럼 담아 이미지·로그·되돌리기·회복이 그대로다)로 열 → 카드 → 태그의 보드가 메모리 앱과 여덟 번 재시작하는 저장 앱에서 매 걸음 같고(스냅숏 2,400개), 커밋의 여섯 단계 어디서 죽여도 전부 아니면 없음이며, 교체는 이름으로 깊이까지 옮긴다. 중첩 리스트를 바꾸는 비용은 그 값의 크기에 비례한다(이미 있는 항목 하나에 170 ns). 줄 수는 검사기만 파이썬 이하이고(80 대 90), SHA-256(42 대 28)과 트리(142 대 105)는 길다. 시간은 C의 40–159배이고 바이트를 다루는 일은 순수 파이썬과 비슷하거나 느리다(0.43–1.6배): 핵이 선 뒤 빠르게 할 과녁이다. 4단계(패턴 모으기)로 메시지의 행이 중첩을 받고, 키별 문서가 키 있는 리스트에 녹고, 커서와 인덱스가 앵커 하나가 되고, 키·text·타이머·프레임·가리킴이 묶인 메시지가 되고, 보기가 아무 값(리스트 보기: 상태 그대로, 걸러짐, 지도, 본문이 지은 리스트; 바이트)이 되고, 고정 한도가 형식과 리스트 엔진의 너비만 남았다: 명령 106 → 95, 상태 종류 7 → 6, 입력 종류 6 → 3, 그동안 다섯 일의 명령 수와 은행 질의는 걸음마다 1% 안, TPC-C는 3단계 끝과 같다(+0.37%). 5단계(수의 모델: number는 binary64로 리터럴과 셈의 기본, i64는 정확한 정수·비트·돈, `/`와 내림한 몫 `//`, i64의 합은 정확하게, 돈은 i64의 센트로 `.2d`에 보이고, 교체는 정확할 때만 옮긴다)로 TPC-C의 돈과 비율이 Pure와 SQLite 모두에서 정수가 되어, 2만 트랜잭션 뒤 모든 행이 오차 없이 같다: 명령 95 → 96, 다섯 일의 명령 수와 은행 질의는 4단계 끝과 1% 안, TPC-C는 런타임이 같고(−0.03%) i64의 돈으로 앱이 2.6% 빠르다. 027의 다섯 단계를 마쳤다 | [026](docs/design/026-app-contract.md), [027](docs/design/027-computation-core.md), [140](docs/research/140-spec-suite.md) | +| 방향(1.0 전) | 앱 계약을 1.0에서 얼릴 후보로 적었다: 이벤트는 전함수이고 원자적이며 결정적이다, 시간은 입력이다, 보기는 커밋된 상태의 순수 함수다, 보이는 역사는 커밋의 앞부분이다, 전달은 순서대로 한 번이다. 계산의 언어(명령 90개, 상태 종류 7개)는 패턴의 모음이라 다시 세운다. 분야마다 고른 명세 열한 개의 묶음에서 오늘의 aup는 바이트, 비트 연산, 중첩, 재귀, 갈래, 글자 읽기에 막힌다(탐침 열 개). 1.0 전에는 호환을 챙기지 않고, JSON과 HTTP는 경계에 남는다. 계산의 핵을 다섯 단계로 다시 세운다(027). 1단계(비트 연산, 자리의 바이트, 수의 리스트, 한 번에 주기)로 aup로 쓴 SHA-256이 공식 벡터를 세 실행 길에서 모두 지난다. 2a(형식 지정, 바이트 잇기와 자르기, 바이트와 text의 let, `while`, 단락 평가의 `&&`·`||`)로 쓴 JSON 검사기가 JSONTestSuite에서 하나도 틀리지 않는다. 2b(레코드 안의 레코드, 갈래와 `match`, 레코드 안의 리스트, 수 읽기)로 JSON을 트리로 읽어 다이제스트가 파이썬과 같다(JSONTestSuite, 무작위 문서 300개). 2c(스스로 부르는 함수: 부름마다 제 스택·지역 칸·리스트·레지스터·담은 값, 깊이는 표로 센 프레임 바이트가 몫에서 묶음; 값으로서의 레코드; 글자 읽기)로 JSON 트리를 재귀 하강으로 다시 써 JSONTestSuite와 무작위 문서 300개가 파이썬과 같고, 10만 겹은 `memory`로 거절한다. 반복 아래에 값을 둔 모듈이 검증을 지나 실행기를 죽이던 구멍도 찾아 막았다. 3단계(중첩한 저장 상태: 저장과 transient의 리스트가 리스트를 담은 레코드를 받고, 그 칸은 값을 항목들의 저장 형태로 바이트처럼 담아 이미지·로그·되돌리기·회복이 그대로다)로 열 → 카드 → 태그의 보드가 메모리 앱과 여덟 번 재시작하는 저장 앱에서 매 걸음 같고(스냅숏 2,400개), 커밋의 여섯 단계 어디서 죽여도 전부 아니면 없음이며, 교체는 이름으로 깊이까지 옮긴다. 중첩 리스트를 바꾸는 비용은 그 값의 크기에 비례한다(이미 있는 항목 하나에 170 ns). 줄 수는 검사기만 파이썬 이하이고(80 대 90), SHA-256(42 대 28)과 트리(142 대 105)는 길다. 시간은 C의 40–159배이고 바이트를 다루는 일은 순수 파이썬과 비슷하거나 느리다(0.43–1.6배): 핵이 선 뒤 빠르게 할 과녁이다. 4단계(패턴 모으기)로 메시지의 행이 중첩을 받고, 키별 문서가 키 있는 리스트에 녹고, 커서와 인덱스가 앵커 하나가 되고, 키·text·타이머·프레임·가리킴이 묶인 메시지가 되고, 보기가 아무 값(리스트 보기: 상태 그대로, 걸러짐, 지도, 본문이 지은 리스트; 바이트)이 되고, 고정 한도가 형식과 리스트 엔진의 너비만 남았다: 명령 106 → 95, 상태 종류 7 → 6, 입력 종류 6 → 3, 그동안 다섯 일의 명령 수와 은행 질의는 걸음마다 1% 안, TPC-C는 3단계 끝과 같다(+0.37%). 5단계(수의 모델: number는 binary64로 리터럴과 셈의 기본, i64는 정확한 정수·비트·돈, `/`와 내림한 몫 `//`, i64의 합은 정확하게, 돈은 i64의 센트로 `.2d`에 보이고, 교체는 정확할 때만 옮긴다)로 TPC-C의 돈과 비율이 Pure와 SQLite 모두에서 정수가 되어, 2만 트랜잭션 뒤 모든 행이 오차 없이 같다: 명령 95 → 96, 다섯 일의 명령 수와 은행 질의는 4단계 끝과 1% 안, TPC-C는 런타임이 같고(−0.03%) i64의 돈으로 앱이 2.6% 빠르다. 027의 다섯 단계를 마쳤다. 그 뒤 묶음의 3(inflate)을 새 명령 없이 썼다: zlib가 만든 스트림 640개와 손상된 240개가 파이썬 참조와 같지만, 우회가 셋(리스트를 받지 않는 fn, 바이트 하나인 상태, 블록 안의 리스트)이고 줄은 파이썬의 1.6배, 시간은 같은 알고리즘의 C의 108배다 | [026](docs/design/026-app-contract.md), [027](docs/design/027-computation-core.md), [140](docs/research/140-spec-suite.md) | 키로 나눈 소유자와 저장을 넘길 스레드는 하지 않기로 했다. 이 장치는 동기화를 한 줄로 세워, 나누면 쓰기가 23% 줄고 넘겨도 기기의 일은 줄지 않는다([084](docs/research/084-parallel-syncs.md)). 다만 동기화가 공짜인 RAM에서 TPC-C는 소유자 하나가 diff --git a/docs/research/140-spec-suite.md b/docs/research/140-spec-suite.md index e0e1b13..d6f6a26 100644 --- a/docs/research/140-spec-suite.md +++ b/docs/research/140-spec-suite.md @@ -28,7 +28,9 @@ - **직접 확인할 것.** `research/experiments/044-specs/run.sh`가 탐침을 컴파일하고 진단을 낸다. - **다음 결정.** 계산의 핵을 설계한다. 여섯 가지와 고정 한도, 상수 시간 암호가 핵이 받아야 할 최소의 후보다. - **027 뒤(2026-10-19).** 핵을 다섯 단계로 다시 세웠다. 탐침의 필요는 셋을 빼고 모두 컴파일된다: 보기에서 재귀 fn을 - 부르기, 레코드나 갈래 하나인 상태, 커서 자리의 글자(아래 "027 뒤의 탐침"). 묶음에서 쓴 것은 2(SHA-256)와 4(JSON)다. + 부르기, 레코드나 갈래 하나인 상태, 커서 자리의 글자(아래 "027 뒤의 탐침"). 묶음에서 쓴 것은 2(SHA-256), 4(JSON), 3(inflate)이다. + inflate는 새 명령 없이 써졌고 zlib의 스트림을 모두 맞게 푼다. 다만 우회가 셋(리스트를 받는 fn, 바이트 하나인 상태, 블록 안의 + 리스트)이고, 줄은 파이썬의 1.6배, 시간은 같은 알고리즘의 C의 108배다. ## 묶음 @@ -42,7 +44,7 @@ |---|---|---|---|---|---|---| | 1 | DNS 메시지(RFC 1035) | 와이어 프로토콜 | 바이트 읽고 쓰기, 빅엔디언, 비트 필드, 이름 압축(바이트 안의 참조) | 알려진 구현이 만든 질의·응답 바이트와 대조 | 못 쓴다(바이트, 비트) | 처음 필요한 것(바이트, 비트)이 컴파일된다. 쓰지 않음 | | 2 | SHA-256(FIPS 180-4) | 해시 | 32비트 낱말, 회전, xor | NIST CAVP의 SHA 벡터 | 우회로만 될 것으로 보인다(써 보지 않음) | 썼다: NIST 벡터를 세 실행 길에서 지난다(1단계) | -| 3 | inflate(RFC 1951) | 압축 | 비트 읽기, 허프만 표, 뒤 참조 | zlib로 압축한 말뭉치를 풀어 원본과 비교 | 못 쓴다(바이트, 비트) | 처음 필요한 것(바이트, 비트)이 컴파일된다. 쓰지 않음 | +| 3 | inflate(RFC 1951) | 압축 | 비트 읽기, 허프만 표, 뒤 참조 | zlib로 압축한 말뭉치를 풀어 원본과 비교 | 못 쓴다(바이트, 비트) | 썼다: zlib 스트림 640개, 손상 240개가 파이썬 참조와 같다. 우회 셋, 줄 수 못 미침, C의 108배(아래) | | 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단계) | @@ -458,6 +460,63 @@ - 커서 자리의 글자를 읽지 못한다. - 셋 다 핵의 변경이다. 묶음의 명세를 더 쓰며 둘 이상이 필요로 하는지 본 뒤에 정한다(쌓임을 막는 규칙). +## 묶음의 3: inflate (2026-10-19) + +027 뒤에 처음 쓴 명세다. 새 명령도 코어의 C도 없이 aup와 Pure만으로 썼다(aup의 `examples/inflate.aup`). 원시 deflate +스트림(RFC 1951)을 그 바이트로 푼다. 부호는 표준 부호의 길이별 수에서 한 비트씩 읽는다(zlib의 `puff.c`와 같은 길). 그래서 걸음마다 +명세의 것이다. deflate가 아닌 스트림은 그 이벤트를 실패시킨다. + +**맞음.** +- `inflate_check.py`: zlib가 만든 스트림 640개(6,488,480바이트)가 세 실행 길(묶음, 실행기만, 기계어)에서 모두 원본과 같고, 세 + 길의 출력이 바이트까지 같다. + - 내용은 0–70,000바이트의 무작위 바이트, 낱말, 짧은 반복, 32,768바이트 뒤의 반복이다. + - 수준 0·1·6·9와 zlib의 다섯 전략(기본, filtered, 허프만만, RLE, 고정)이라 저장·고정·동적 블록을 모두 지난다. +- 손상된 스트림 240개(자른 것과 비트 하나를 뒤집은 것)를 같은 길로 읽는 파이썬 참조(`inflate.py`)와 견준다. 165개는 둘 다 + 거절하고, 75개는 같은 바이트를 낸다. +- Pure의 `make check`(`module_specs`)에 들어갔다. 스트림 144개(1.2 MB)를 세 길에서 풀고, 반으로 자른 21개는 이벤트가 실패해 앞 + 스트림의 바이트를 남긴다. + +**막대.** + +| 막대 | 잰 것 | | +|---|---|---| +| 쓸 수 있다 | aup와 Pure만. 새 명령 없음 | 지남 | +| 우회가 없다 | 셋(아래): 레코드에 담아 넘긴 리스트, 항목 하나의 리스트에 둔 바이트, fn으로 옮긴 블록의 표 | **못 미침** | +| 줄 수 ≤ 파이썬 참조 | aup 132줄(닫는 괄호만인 줄 18) 대 파이썬 81줄 | **못 미침** | +| C 대비 시간 | 낱말 65,536바이트(22,991바이트로 압축)에서 출력 바이트당 1,152 ns. 같은 알고리즘의 C(10.7 ns)의 **108배**, zlib(표로 읽는다, 3.5 ns)의 329배. 순수 파이썬은 1,214 ns(Pure가 1.05배 빠름) | 기록(막대 없음) | +| 견고하다 | 위의 맞음, 세 길이 같음, 예산 안에서 끝남. 세 기계는 아직 돌리지 않았다 | 일부 | + +**우회 셋(언어의 틈).** +1. fn이 리스트를 인자로 받지 않는다(`'counts' is a list`). 갈래나 레코드의 값은 리스트를 담은 채 넘어간다(json_tree의 `walk`). + 그래서 부호의 두 표를 레코드 `Code`에, 길이들을 레코드 `Lengths`에 담아 넘긴다. `Lengths`는 우회만을 위한 레코드다. +2. 바이트나 레코드 하나를 상태로 두지 못한다(027 뒤의 탐침의 둘째 틈). 출력을 항목 하나의 리스트 `inflated`에 두고, 이벤트마다 + 지우고 덧붙인다. 묶음의 명세가 이 틈에 처음 닿았다. +3. let의 리스트는 핸들러의 맨 바깥 블록에만 두고, 비우지 못한다(`[]`를 대입하지 못한다). 블록마다 새로 짓는 길이의 표를 fn + `codes`로 옮겼다(fn은 부를 때마다 제 리스트를 가진다). 줄은 거의 늘지 않았지만, 구조가 명세가 아니라 언어를 따른다. + +**줄을 길게 한 것.** 132 대 81이다. 닫는 괄호의 줄을 빼면 114다. +- 닫는 괄호의 줄이 18줄이다(파이썬은 들여쓰기). +- 우회의 레코드 셋(`Code`, `Lengths`, `Inflated`)과 항목 하나를 비우는 줄이 11줄이다. +- 비트 자리를 옮기는 줄(`at = next`, `i = i + 2` 같은 것)이 11줄이다. 파이썬은 `Bits` 객체(8줄)가 자리를 들고 간다. aup의 fn은 + 값만 돌려주므로 부른 쪽이 자리를 따로 더한다. +- 리스트의 선언이 5줄이다(파이썬은 쓰는 자리에서 짓는다). + +**시간이 가는 곳.** 출력 바이트당 Pure 명령이 191개이고, 명령 하나에 약 6.0 ns가 든다. +- 처음 쓴 꼴은 decode가 비트마다 블록 fn `take(d, at, 1)`를 불렀다. 그때는 246개, 1,553 ns였다. 비트 하나를 식 하나의 fn `bit`로 + 쓰니 인라인되어 명령이 23%, 시간이 26% 줄었다. 블록 fn의 부름 하나가 그만큼 무겁다. 작은 블록 fn의 인라인은 2c의 남은 것이다 + (컴파일러의 일). +- 기계어 계층(`PURE_JIT=all`)은 빠르게 하지 못한다(1,151 대 1,152 ns). 바이트 읽기, fn 부름, 리스트 덧붙이기를 실행기에 맡겨서다. + SHA-256과 같은 까닭이다. +- 같은 날 SHA-256은 바이트당 1,479 ns(C의 163배)다. 1단계의 1,591 ns보다 조금 빠르다. + +**원본.** `research/experiments/044-specs/` +- `inflate.py`: 파이썬 참조 +- `inflate_check.py`: 맞음과 줄 수 +- `inflate_time.c`: 같은 바이트로 같은 알고리즘의 C, zlib, Pure의 시간. 셋의 출력이 원본과 같아야 잰다. +- `2026-10-19-inflate.jsonl`: 잰 수 +- 그 사이 Pure의 API가 바뀌어(4b, 메시지의 키가 빠졌다) 컴파일되지 않던 시간 도구 넷(`time.c`, `json_time.c`, `json_tree_time.c`, + `json_rec_time.c`)의 메시지 부름을 고쳤다. + ## 착수 기준 (다음 일) - **바꿀 결정.** 계산의 핵을 설계한다(027). 위 표의 여덟 후보 가운데 무엇을 어떤 모양으로 받을지 정한다. diff --git a/research/experiments/044-specs/2026-10-19-inflate.jsonl b/research/experiments/044-specs/2026-10-19-inflate.jsonl new file mode 100644 index 0000000..9c85c06 --- /dev/null +++ b/research/experiments/044-specs/2026-10-19-inflate.jsonl @@ -0,0 +1,5 @@ +{"streams": 640, "bytes": 6488480, "right": {"batches": 640, "rounds": 640, "all": 640}, "paths_same": true, "damaged": 240, "damaged_refused": 165, "damaged_agreed": 240, "aup_lines": 132, "aup_brace_lines": 18, "python_lines": 81} +{"size":65536,"stream":22991,"jit":"0","batch":"","c_ns_per_byte":10.657,"zlib_ns_per_byte":3.500,"pure_ns_per_byte":1152.379,"to_c":108.1,"to_zlib":329.3,"instructions":12527836,"instructions_per_byte":191.2} +{"size":65536,"stream":22991,"jit":"0","batch":"0","c_ns_per_byte":10.651,"zlib_ns_per_byte":3.491,"pure_ns_per_byte":1153.844,"to_c":108.3,"to_zlib":330.6,"instructions":12527836,"instructions_per_byte":191.2} +{"size":65536,"stream":22991,"jit":"all","batch":"","c_ns_per_byte":10.646,"zlib_ns_per_byte":3.503,"pure_ns_per_byte":1151.154,"to_c":108.1,"to_zlib":328.7,"instructions":12527836,"instructions_per_byte":191.2} +{"size":65536,"packed":22991,"python_ns_per_byte":1213.5} diff --git a/research/experiments/044-specs/inflate.py b/research/experiments/044-specs/inflate.py new file mode 100644 index 0000000..ac84b20 --- /dev/null +++ b/research/experiments/044-specs/inflate.py @@ -0,0 +1,109 @@ +# inflate (RFC 1951) in plain Python: the reference 140 counts aup's lines against. Codes are read a bit at a time +# from canonical counts (as zlib's puff.c does), so each step is the specification's. +LENGTH_BASE = [3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258] +LENGTH_EXTRA = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0] +DISTANCE_BASE = [1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, + 4097, 6145, 8193, 12289, 16385, 24577] +DISTANCE_EXTRA = [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13] +ORDER = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15] + + +class Bits: + def __init__(self, data): + self.data, self.at = data, 0 + + def take(self, n): + v = 0 + for k in range(n): + v |= (self.data[self.at >> 3] >> (self.at & 7) & 1) << k + self.at += 1 + return v + + +def code(lengths): + """A canonical code: how many codes of each length, and the symbols in code order.""" + counts = [lengths.count(n) for n in range(16)] + return counts, [s for n in range(1, 16) for s in range(len(lengths)) if lengths[s] == n] + + +def decode(bits, counts, symbols): + value = first = index = 0 + for n in range(1, 16): + value |= bits.take(1) + if value - first < counts[n]: + return symbols[index + value - first] + index += counts[n] + first = (first + counts[n]) << 1 + value <<= 1 + raise ValueError('no such code') + + +def inflate(data): + bits, out, last = Bits(data), bytearray(), 0 + while not last: + last, kind = bits.take(1), bits.take(2) + if kind == 0: # stored: from the next byte, its length and the length's complement + at = (bits.at + 7) >> 3 + size = data[at] | data[at + 1] << 8 + if size != (data[at + 2] | data[at + 3] << 8) ^ 0xffff or at + 4 + size > len(data): + raise ValueError('stored length') + out += data[at + 4:at + 4 + size] + bits.at = (at + 4 + size) * 8 + continue + if kind == 1: + lengths, distances = code([8] * 144 + [9] * 112 + [7] * 24 + [8] * 8), code([5] * 30) + elif kind == 2: + literals, count, lengths = bits.take(5) + 257, bits.take(5) + 1, [0] * 19 + for n in range(bits.take(4) + 4): + lengths[ORDER[n]] = bits.take(3) + lengths = code(lengths) + both = [] + while len(both) < literals + count: + symbol = decode(bits, *lengths) + if symbol < 16: + both.append(symbol) + elif symbol == 16: + if not both: + raise ValueError('a repeat with nothing before it') + both += [both[-1]] * (3 + bits.take(2)) + else: + both += [0] * (3 + bits.take(3) if symbol == 17 else 11 + bits.take(7)) + if len(both) > literals + count: + raise ValueError('too many lengths') + lengths, distances = code(both[:literals]), code(both[literals:]) + else: + raise ValueError('block type 3') + while (symbol := decode(bits, *lengths)) != 256: + if symbol < 256: + out.append(symbol) + continue + symbol -= 257 + if symbol >= 29: + raise ValueError('length symbol') + length = LENGTH_BASE[symbol] + bits.take(LENGTH_EXTRA[symbol]) + symbol = decode(bits, *distances) + if symbol >= 30: + raise ValueError('distance symbol') + distance = DISTANCE_BASE[symbol] + bits.take(DISTANCE_EXTRA[symbol]) + if distance > len(out): + raise ValueError('too far back') + for _ in range(length): + out.append(out[-distance]) + return bytes(out) + + +if __name__ == '__main__': + import random, sys, time, zlib + size = int(sys.argv[1]) if len(sys.argv) > 1 else 65536 + chooser = random.Random(140) + words = [bytes(chooser.choices(b'abcdefghijklmnopqrstuvwxyz', k=chooser.randrange(2, 9))) for _ in range(400)] + text = b' '.join(chooser.choice(words) for _ in range(size))[:size] + packer = zlib.compressobj(9, zlib.DEFLATED, -15) + packed = packer.compress(text) + packer.flush() + assert inflate(packed) == text + runs = [] + for _ in range(7): + start = time.perf_counter() + inflate(packed) + runs.append((time.perf_counter() - start) * 1e9 / size) + print('{"size":%d,"packed":%d,"python_ns_per_byte":%.1f}' % (size, len(packed), sorted(runs)[3])) diff --git a/research/experiments/044-specs/inflate_check.py b/research/experiments/044-specs/inflate_check.py new file mode 100644 index 0000000..c3f37b4 --- /dev/null +++ b/research/experiments/044-specs/inflate_check.py @@ -0,0 +1,105 @@ +#!/usr/bin/env python3 +"""Research 140: inflate (RFC 1951) written in aup (aup's examples/inflate.aup). + +Builds it with aup (AUP, default the sibling checkout) and inflates raw deflate streams zlib made (stored, fixed and +dynamic blocks: levels 0, 1, 6 and 9 with each of zlib's five strategies, on random bytes, words, short runs and far +repeats, 0 to 70,000 bytes) on Pure's three paths (batches, rounds, all compiled), each output against the original; +then damaged streams (cut short, a bit flipped) against inflate.py, which reads them the same way: the same bytes when +it takes one, a failed event when it refuses it. Then counts lines (code lines: neither blank nor a comment; brace +lines: a closing brace alone) of inflate.aup and of inflate.py's algorithm (above its main). One JSON line.""" +import json, os, random, subprocess, sys, tempfile, zlib + +here = os.path.dirname(os.path.abspath(__file__)) +pure = os.path.normpath(os.path.join(here, '../../..')) +aup = os.environ.get('AUP', os.path.join(pure, '..', 'aup')) +sys.path.insert(0, here) +import inflate # noqa: E402 + + +def lines(path, stop=None): + code = braces = 0 + for line in open(path): + if stop and line.startswith(stop): break + text = line.strip() + if not text or text.startswith('#'): continue + code += 1 + braces += text == '}' + return code, braces + + +def corpus(chooser): + words = [bytes(chooser.choices(b'abcdefghijklmnopqrstuvwxyz', k=chooser.randrange(2, 9))) for _ in range(400)] + streams = [] + for size in (0, 1, 2, 3, 100, 1000, 10000, 70000): + far = bytes(chooser.randrange(256) for _ in range(min(size, 33000))) + kinds = {'random': bytes(chooser.randrange(256) for _ in range(size)), + 'words': b' '.join(chooser.choice(words) for _ in range(size))[:size], + 'runs': (bytes(chooser.choices(b'ab', k=7)) * size)[:size], + 'far': (far + far[:32768] * 3)[:size]} # repeats 32,768 bytes back at most + for data in kinds.values(): + for level in (0, 1, 6, 9): + for strategy in (zlib.Z_DEFAULT_STRATEGY, zlib.Z_FILTERED, zlib.Z_HUFFMAN_ONLY, zlib.Z_RLE, zlib.Z_FIXED): + packer = zlib.compressobj(level, zlib.DEFLATED, -15, 9, strategy) + streams.append((data, packer.compress(data) + packer.flush())) + return streams + + +def damaged(chooser, streams): + """Streams cut short or with a bit flipped, each with what inflate.py makes of it (None: refused).""" + out = [] + small = [packed for data, packed in streams if 0 < len(packed) < 3000] + for packed in chooser.sample(small, 120): + cut = packed[:chooser.randrange(len(packed))] + flipped = bytearray(packed) + flipped[chooser.randrange(len(packed))] ^= 1 << chooser.randrange(8) + for stream in (cut, bytes(flipped)): + try: + out.append((stream, inflate.inflate(stream))) + except (ValueError, IndexError): + out.append((stream, None)) + return out + + +def run(module, packed_streams, env, work): + given = [] + for n, packed in enumerate(packed_streams): + path = os.path.join(work, f'{n}.deflate') + with open(path, 'wb') as f: + f.write(packed) + given.append(f'message inflate @{path}\n') + out = subprocess.run([os.path.join(pure, 'build', 'pure-run'), module], input=''.join(given), capture_output=True, + text=True, env=dict(os.environ, **env), timeout=1800).stdout.splitlines() + 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) + return out, got + + +chooser = random.Random(140) +streams = corpus(chooser) +broken = damaged(chooser, streams) +paths = {} +with tempfile.TemporaryDirectory() as work: + module = os.path.join(work, 'inflate.pmod') + subprocess.run([os.path.join(aup, 'build', 'aup'), 'build', os.path.join(aup, 'examples', 'inflate.aup'), '-o', module], + check=True) + outputs = {} + for name, env in (('batches', {'PURE_JIT': '0'}), ('rounds', {'PURE_JIT': '0', 'PURE_BATCH': '0'}), + ('all', {'PURE_JIT': 'all'})): + raw, got = run(module, [packed for _, packed in streams], env, work) + paths[name] = sum(g == data for (data, _), g in zip(streams, got)) if len(got) == len(streams) else 0 + outputs[name] = raw + same_paths = outputs['rounds'] == outputs['batches'] and outputs['all'] == outputs['batches'] + # A damaged stream after a good one: a refused one fails its event and leaves the good one's bytes. + raw, got = run(module, [stream for stream, _ in broken], {}, work) + agreed = sum(g == want or (want is None and g is None) for (_, want), g in zip(broken, got)) if len(got) == len(broken) else 0 + refused = sum(want is None for _, want in broken) +aup_code, aup_braces = lines(os.path.join(aup, 'examples', 'inflate.aup')) +python_code, _ = lines(os.path.join(here, 'inflate.py'), stop='if __name__') +ok = all(n == len(streams) for n in paths.values()) and same_paths and agreed == len(broken) +print(json.dumps({'streams': len(streams), 'bytes': sum(len(d) for d, _ in streams), 'right': paths, 'paths_same': same_paths, + 'damaged': len(broken), 'damaged_refused': refused, 'damaged_agreed': agreed, 'aup_lines': aup_code, + 'aup_brace_lines': aup_braces, 'python_lines': python_code})) +sys.exit(0 if ok else 1) diff --git a/research/experiments/044-specs/inflate_time.c b/research/experiments/044-specs/inflate_time.c new file mode 100644 index 0000000..34cc2d5 --- /dev/null +++ b/research/experiments/044-specs/inflate_time.c @@ -0,0 +1,231 @@ +/* Research 140: inflate (RFC 1951) in aup (aup's examples/inflate.aup, run by Pure) against the same algorithm in C + * (codes read a bit at a time from canonical counts, as zlib's puff.c) and against zlib's inflate (tables), on the + * same raw deflate stream. Each output must be the original's bytes; then each is timed (the median of seven runs of + * rounds inflations). + * + * cc -O2 -std=c17 -I../../../core inflate_time.c ../../../build/libpure.a -lz -lm -pthread -o inflate_time + * ./inflate_time inflate.pmod STREAM ORIGINAL ROUNDS (PURE_JIT and PURE_BATCH choose Pure's path) + * + * One JSON line: the sizes, the nanoseconds per output byte of each, Pure's ratios to both and the instructions Pure + * counted for one stream. */ +#define _POSIX_C_SOURCE 200809L +#include "module.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <zlib.h> + +/* ---- inflate in C, bit by bit (puff's algorithm, no tables) */ +typedef struct { + const unsigned char *in; + size_t size, at; /* at in bits */ + unsigned char *out; + size_t used, room; +} Stream; +typedef struct { short counts[16], symbols[288]; } Code; + +static int take(Stream *s, int n) { + int v = 0; + for (int k = 0; k < n; ++k, ++s->at) { + if (s->at >> 3 >= s->size) return -1; + v |= (s->in[s->at >> 3] >> (s->at & 7) & 1) << k; + } + return v; +} + +static void code(Code *c, const short *lengths, int n) { + memset(c->counts, 0, sizeof(c->counts)); + for (int s = 0; s < n; ++s) c->counts[lengths[s]]++; + short offsets[16] = {0}; + for (int l = 1; l < 15; ++l) offsets[l + 1] = (short)(offsets[l] + c->counts[l]); + for (int s = 0; s < n; ++s) + if (lengths[s]) c->symbols[offsets[lengths[s]]++] = (short)s; +} + +static int decode(Stream *s, const Code *c) { + int value = 0, first = 0, index = 0; + for (int n = 1; n < 16; ++n) { + int b = take(s, 1); + if (b < 0) return -1; + value |= b; + if (value - first < c->counts[n]) return c->symbols[index + value - first]; + index += c->counts[n]; + first = (first + c->counts[n]) << 1; + value <<= 1; + } + return -1; +} + +static const short length_base[29] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, + 99, 115, 131, 163, 195, 227, 258}; +static const short length_extra[29] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0}; +static const short distance_base[30] = {1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, + 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577}; +static const short distance_extra[30] = {0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, + 12, 12, 13, 13}; + +static int put(Stream *s, unsigned char b) { + if (s->used == s->room) return -1; + s->out[s->used++] = b; + return 0; +} + +/* The bytes of a raw deflate stream; -1 if it is none (or the room is short). */ +static long puff(const unsigned char *in, size_t size, unsigned char *out, size_t room) { + Stream s = {in, size, 0, out, 0, room}; + static const short order[19] = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; + int last; + do { + last = take(&s, 1); + int kind = take(&s, 2); + if (last < 0 || kind < 0 || kind == 3) return -1; + if (kind == 0) { + size_t b = (s.at + 7) >> 3; + if (b + 4 > size) return -1; + size_t n = in[b] | in[b + 1] << 8; + if (n != ((in[b + 2] | in[b + 3] << 8) ^ 0xffffu) || b + 4 + n > size || s.used + n > room) return -1; + memcpy(out + s.used, in + b + 4, n); + s.used += n; + s.at = (b + 4 + n) * 8; + continue; + } + Code lc, dc; + short lengths[320]; + if (kind == 1) { + for (int i = 0; i < 288; ++i) lengths[i] = i < 144 ? 8 : i < 256 ? 9 : i < 280 ? 7 : 8; + code(&lc, lengths, 288); + for (int i = 0; i < 30; ++i) lengths[i] = 5; + code(&dc, lengths, 30); + } else { + int literals = take(&s, 5) + 257, count = take(&s, 5) + 1, n = take(&s, 4) + 4; + short small[19] = {0}; + for (int k = 0; k < n; ++k) small[order[k]] = (short)take(&s, 3); + Code c; + code(&c, small, 19); + int got = 0; + while (got < literals + count) { + int symbol = decode(&s, &c); + if (symbol < 0) return -1; + if (symbol < 16) { lengths[got++] = (short)symbol; continue; } + short repeat = 0; + int times; + if (symbol == 16) { + if (!got) return -1; + repeat = lengths[got - 1], times = 3 + take(&s, 2); + } else times = symbol == 17 ? 3 + take(&s, 3) : 11 + take(&s, 7); + if (got + times > literals + count) return -1; + while (times--) lengths[got++] = repeat; + } + code(&lc, lengths, literals); + code(&dc, lengths + literals, count); + } + for (;;) { + int symbol = decode(&s, &lc); + if (symbol < 0) return -1; + if (symbol == 256) break; + if (symbol < 256) { if (put(&s, (unsigned char)symbol)) return -1; continue; } + symbol -= 257; + if (symbol >= 29) return -1; + int length = length_base[symbol] + take(&s, length_extra[symbol]); + symbol = decode(&s, &dc); + if (symbol < 0 || symbol >= 30) return -1; + size_t distance = (size_t)(distance_base[symbol] + take(&s, distance_extra[symbol])); + if (distance > s.used) return -1; + while (length--) if (put(&s, s.out[s.used - distance])) return -1; + } + } while (!last); + return (long)s.used; +} + +static long zlib_inflate(const unsigned char *in, size_t size, unsigned char *out, size_t room) { + z_stream z = {0}; + if (inflateInit2(&z, -15) != Z_OK) return -1; + z.next_in = (unsigned char *)in, z.avail_in = (uInt)size, z.next_out = out, z.avail_out = (uInt)room; + int r = inflate(&z, Z_FINISH); + long used = (long)z.total_out; + inflateEnd(&z); + return r == Z_STREAM_END ? used : -1; +} + +static double now_ns(void) { + struct timespec t; + clock_gettime(CLOCK_MONOTONIC, &t); + return (double)t.tv_sec * 1e9 + (double)t.tv_nsec; +} + +static int by_value(const void *a, const void *b) { + double x = *(const double *)a, y = *(const double *)b; + return (x > y) - (x < y); +} + +static unsigned char *whole(const char *path, size_t *size) { + FILE *f = fopen(path, "rb"); + if (!f) return NULL; + fseek(f, 0, SEEK_END); + *size = (size_t)ftell(f); + rewind(f); + unsigned char *bytes = malloc(*size ? *size : 1); + if (fread(bytes, 1, *size, f) != *size) { free(bytes); bytes = NULL; } + fclose(f); + return bytes; +} + +int main(int argc, char **argv) { + if (argc != 5) { fprintf(stderr, "usage: %s MODULE STREAM ORIGINAL ROUNDS\n", argv[0]); return 2; } + size_t size, original_size; + unsigned char *stream = whole(argv[2], &size), *original = whole(argv[3], &original_size); + int rounds = atoi(argv[4]); + if (!stream || !original) { fprintf(stderr, "cannot read the stream or the original\n"); return 1; } + unsigned char *out = malloc(original_size + 1); + if (puff(stream, size, out, original_size) != (long)original_size || memcmp(out, original, original_size)) { + fprintf(stderr, "C's bytes differ\n"); + return 1; + } + if (zlib_inflate(stream, size, out, original_size + 1) != (long)original_size || memcmp(out, original, original_size)) { + fprintf(stderr, "zlib's bytes differ\n"); + return 1; + } + + PureModule module = {0}; + char error[160]; + if (pure_module_read(argv[1], &module, error, sizeof(error)) != PURE_OK) { fprintf(stderr, "%s\n", error); return 1; } + PureApp app; + if (pure_app_start(&app, &module, (PureData){0}) != PURE_OK) return 1; + int input = pure_module_input(&module, "inflate"), state = pure_module_state(&module, "inflated"); + uint64_t before = app.work; + if (pure_app_message(&app, (uint32_t)input, (PureSpan){stream, size}) != PURE_OK) { + fprintf(stderr, "event failed\n"); + 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; } + + double c_runs[7], zlib_runs[7], pure_runs[7]; + volatile unsigned char sink = 0; + for (int r = 0; r < 7; ++r) { + double start = now_ns(); + for (int i = 0; i < rounds; ++i) { puff(stream, size, out, original_size); sink ^= out[i % (original_size + 1)]; } + c_runs[r] = (now_ns() - start) / rounds; + start = now_ns(); + for (int i = 0; i < rounds; ++i) { zlib_inflate(stream, size, out, original_size + 1); sink ^= out[i % (original_size + 1)]; } + zlib_runs[r] = (now_ns() - start) / rounds; + start = now_ns(); + for (int i = 0; i < rounds; ++i) + if (pure_app_message(&app, (uint32_t)input, (PureSpan){stream, size}) != PURE_OK) return 1; + pure_runs[r] = (now_ns() - start) / rounds; + } + qsort(c_runs, 7, sizeof(double), by_value); + qsort(zlib_runs, 7, sizeof(double), by_value); + qsort(pure_runs, 7, sizeof(double), by_value); + double n = (double)original_size; + const char *jit = getenv("PURE_JIT"), *batch = getenv("PURE_BATCH"); + printf("{\"size\":%zu,\"stream\":%zu,\"jit\":\"%s\",\"batch\":\"%s\",\"c_ns_per_byte\":%.3f,\"zlib_ns_per_byte\":%.3f," + "\"pure_ns_per_byte\":%.3f,\"to_c\":%.1f,\"to_zlib\":%.1f,\"instructions\":%llu,\"instructions_per_byte\":%.1f}\n", + original_size, size, jit ? jit : "", batch ? batch : "", c_runs[3] / n, zlib_runs[3] / n, pure_runs[3] / n, + pure_runs[3] / c_runs[3], pure_runs[3] / zlib_runs[3], (unsigned long long)work, (double)work / n); + pure_app_stop(&app); + return 0; +} diff --git a/research/experiments/044-specs/json_rec_time.c b/research/experiments/044-specs/json_rec_time.c index 0d5b225..6c599f5 100644 --- a/research/experiments/044-specs/json_rec_time.c +++ b/research/experiments/044-specs/json_rec_time.c @@ -79,7 +79,7 @@ int main(int argc, char **argv) { PureApp app; if (pure_app_start(&app, &module, (PureData){0}) != PURE_OK) return 1; int check = pure_module_input(&module, "check"); - if (pure_app_message(&app, (uint32_t)check, NULL, -1, (PureSpan){(const unsigned char *)doc, n}) != PURE_OK) { + if (pure_app_message(&app, (uint32_t)check, (PureSpan){(const unsigned char *)doc, n}) != PURE_OK) { fprintf(stderr, "event failed\n"); return 1; } @@ -104,7 +104,7 @@ int main(int argc, char **argv) { c_runs[r] = (now_ns() - start) / rounds; start = now_ns(); for (int i = 0; i < rounds; ++i) - if (pure_app_message(&app, (uint32_t)check, NULL, -1, (PureSpan){(const unsigned char *)doc, n}) != PURE_OK) return 1; + if (pure_app_message(&app, (uint32_t)check, (PureSpan){(const unsigned char *)doc, n}) != PURE_OK) return 1; pure_runs[r] = (now_ns() - start) / rounds; } qsort(c_runs, 7, sizeof(double), by_value); diff --git a/research/experiments/044-specs/json_time.c b/research/experiments/044-specs/json_time.c index b4b2eae..1e747c1 100644 --- a/research/experiments/044-specs/json_time.c +++ b/research/experiments/044-specs/json_time.c @@ -106,7 +106,7 @@ int main(int argc, char **argv) { PureApp app; if (pure_app_start(&app, &module, (PureData){0}) != PURE_OK) return 1; int check = pure_module_input(&module, "check"); - if (pure_app_message(&app, (uint32_t)check, NULL, -1, (PureSpan){doc, n}) != PURE_OK) { fprintf(stderr, "event failed\n"); return 1; } + if (pure_app_message(&app, (uint32_t)check, (PureSpan){doc, n}) != PURE_OK) { fprintf(stderr, "event failed\n"); return 1; } uint64_t work = app.work; if (app.values[0].num != 1 || !valid(doc, n, open)) { fprintf(stderr, "not both valid\n"); return 1; } double c_runs[7], pure_runs[7]; @@ -117,7 +117,7 @@ int main(int argc, char **argv) { c_runs[r] = (now_ns() - start) / rounds; start = now_ns(); for (int i = 0; i < rounds; ++i) - if (pure_app_message(&app, (uint32_t)check, NULL, -1, (PureSpan){doc, n}) != PURE_OK) return 1; + if (pure_app_message(&app, (uint32_t)check, (PureSpan){doc, n}) != PURE_OK) return 1; pure_runs[r] = (now_ns() - start) / rounds; } qsort(c_runs, 7, sizeof(double), by_value); diff --git a/research/experiments/044-specs/json_tree_time.c b/research/experiments/044-specs/json_tree_time.c index 0ec4bec..636eed4 100644 --- a/research/experiments/044-specs/json_tree_time.c +++ b/research/experiments/044-specs/json_tree_time.c @@ -79,7 +79,7 @@ int main(int argc, char **argv) { PureApp app; if (pure_app_start(&app, &module, (PureData){0}) != PURE_OK) return 1; int check = pure_module_input(&module, "check"); - if (pure_app_message(&app, (uint32_t)check, NULL, -1, (PureSpan){(const unsigned char *)doc, n}) != PURE_OK) { + if (pure_app_message(&app, (uint32_t)check, (PureSpan){(const unsigned char *)doc, n}) != PURE_OK) { fprintf(stderr, "event failed\n"); return 1; } @@ -104,7 +104,7 @@ int main(int argc, char **argv) { c_runs[r] = (now_ns() - start) / rounds; start = now_ns(); for (int i = 0; i < rounds; ++i) - if (pure_app_message(&app, (uint32_t)check, NULL, -1, (PureSpan){(const unsigned char *)doc, n}) != PURE_OK) return 1; + if (pure_app_message(&app, (uint32_t)check, (PureSpan){(const unsigned char *)doc, n}) != PURE_OK) return 1; pure_runs[r] = (now_ns() - start) / rounds; } qsort(c_runs, 7, sizeof(double), by_value); diff --git a/research/experiments/044-specs/time.c b/research/experiments/044-specs/time.c index f296ece..a196aba 100644 --- a/research/experiments/044-specs/time.c +++ b/research/experiments/044-specs/time.c @@ -91,7 +91,7 @@ int main(int argc, char **argv) { int hash = pure_module_input(&module, "hash"); char want[65]; sha256(data, size, want); - if (pure_app_message(&app, (uint32_t)hash, NULL, -1, (PureSpan){data, size}) != PURE_OK) { fprintf(stderr, "event failed\n"); return 1; } + if (pure_app_message(&app, (uint32_t)hash, (PureSpan){data, size}) != PURE_OK) { fprintf(stderr, "event failed\n"); return 1; } uint64_t work = app.work; Hex got = {{0}, 0}; pure_draft_read(app.texts[0], 0, pure_draft_size(app.texts[0]), gather, &got); @@ -105,7 +105,7 @@ int main(int argc, char **argv) { c_runs[r] = (now_ns() - start) / rounds; start = now_ns(); for (int i = 0; i < rounds; ++i) - if (pure_app_message(&app, (uint32_t)hash, NULL, -1, (PureSpan){data, size}) != PURE_OK) return 1; + if (pure_app_message(&app, (uint32_t)hash, (PureSpan){data, size}) != PURE_OK) return 1; pure_runs[r] = (now_ns() - start) / rounds; } qsort(c_runs, 7, sizeof(double), by_value); diff --git a/tests/check.py b/tests/check.py index 3f2fee1..4f2fb98 100644 --- a/tests/check.py +++ b/tests/check.py @@ -1729,7 +1729,9 @@ def module_specs(aup, pure, work): messages of every length up to two blocks; whether bytes are JSON (its examples/json.aup) on JSONTestSuite's parsing cases (tests/specs/json): every y_ case taken, every n_ case refused (a refusal: valid false, or - the event failing as encoding on bytes that are not UTF-8).""" + the event failing as encoding on bytes that are not UTF-8); JSON read into + a tree (its examples/json_tree.aup); raw deflate streams zlib made inflated + by its examples/inflate.aup to the original's bytes, cut ones refused.""" import hashlib import os import random @@ -1829,6 +1831,39 @@ def module_specs(aup, pure, work): assert {k: state['states'][k] for k in keys} == digest(cases[name]), name trees[name[0]] += accepted runs['json_tree'] = {'cases': len(cases), 'taken': trees} + # inflate (RFC 1951, its examples/inflate.aup): raw deflate streams zlib made (stored, fixed and dynamic blocks, its + # strategies, words, runs and repeats 32,768 bytes back), each inflated to the original's bytes; a stream cut short + # fails its event and leaves the last stream's bytes. + import zlib + program = work / 'inflate.pmod' + compile_module(aup, EXAMPLES / 'inflate.aup', program) + words = [bytes(chooser.choices(b'abcdefghijklmnopqrstuvwxyz', k=chooser.randrange(2, 9))) for _ in range(200)] + streams = [] + for size in (0, 1, 100, 1000, 10000, 40000): + far = bytes(chooser.randrange(256) for _ in range(min(size, 33000))) + for data in (bytes(chooser.randrange(256) for _ in range(size)), b' '.join(chooser.choice(words) for _ in range(size))[:size], + (b'abaabbb' * size)[:size], (far + far[:32768])[:size]): + for level, strategy in ((0, zlib.Z_DEFAULT_STRATEGY), (6, zlib.Z_DEFAULT_STRATEGY), (9, zlib.Z_FILTERED), + (6, zlib.Z_HUFFMAN_ONLY), (6, zlib.Z_RLE), (9, zlib.Z_FIXED)): + packer = zlib.compressobj(level, zlib.DEFLATED, -15, 9, strategy) + streams.append((data, packer.compress(data) + packer.flush())) + cut = [(data, packed[:len(packed) // 2]) for data, packed in streams[::7] if len(packed) > 1] + given = '' + for n, (_, packed) in enumerate(streams + cut): + (work / f'{n}.deflate').write_bytes(packed) + given += f'message inflate @{work / f"{n}.deflate"}\n' + outputs = {name: subprocess.run([str(pure / 'build/pure-run'), str(program)], input=given, capture_output=True, text=True, + timeout=600, env=dict(os.environ, **env)).stdout + for name, env in (('batches', {'PURE_JIT': '0'}), ('rounds', {'PURE_JIT': '0', 'PURE_BATCH': '0'}), ('all', {'PURE_JIT': 'all'}))} + for name in ('rounds', 'all'): + assert outputs[name] == outputs['batches'], ('inflate', name) + 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)) + for state in shown[len(streams):]: + assert state['fault'] != 'none' and state['states']['inflated'][-1]['data'] == streams[-1][0].hex(), ('inflate cut', state['fault']) + runs['inflate'] = {'streams': len(streams), 'bytes': sum(len(d) for d, _ in streams), 'cut': len(cut)} return runs |