diff options
| -rw-r--r-- | CHECKPOINT.md | 2 | ||||
| -rw-r--r-- | docs/design/027-computation-core.md | 20 | ||||
| -rw-r--r-- | docs/research/140-spec-suite.md | 65 | ||||
| -rw-r--r-- | research/experiments/040-against-c/2026-10-18-counts-s27.jsonl | 4 | ||||
| -rw-r--r-- | research/experiments/040-against-c/2026-10-18-counts-s27b.jsonl | 4 | ||||
| -rw-r--r-- | research/experiments/041-batches/2026-10-18-counts.jsonl | 20 | ||||
| -rw-r--r-- | research/experiments/044-specs/2026-10-18-stage2c.jsonl | 6 | ||||
| -rw-r--r-- | research/experiments/044-specs/json_rec.py | 159 | ||||
| -rw-r--r-- | research/experiments/044-specs/json_rec_time.c | 119 | ||||
| -rw-r--r-- | tests/check.py | 18 |
10 files changed, 405 insertions, 12 deletions
diff --git a/CHECKPOINT.md b/CHECKPOINT.md index 3c05d86..dccb646 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개). 줄 수는 검사기만 파이썬 이하이고(80 대 90), SHA-256(42 대 28)과 트리(167 대 133)는 길다. 시간은 C의 40–159배이고 바이트를 다루는 일은 순수 파이썬과 비슷하거나 느리다(0.43–1.3배): 핵이 선 뒤 빠르게 할 과녁이다 | [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`로 거절한다. 반복 아래에 값을 둔 모듈이 검증을 지나 실행기를 죽이던 구멍도 찾아 막았다. 줄 수는 검사기만 파이썬 이하이고(80 대 90), SHA-256(42 대 28)과 트리(142 대 105)는 길다. 시간은 C의 40–159배이고 바이트를 다루는 일은 순수 파이썬과 비슷하거나 느리다(0.43–1.6배): 핵이 선 뒤 빠르게 할 과녁이다 | [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/design/027-computation-core.md b/docs/design/027-computation-core.md index 7b851f6..660fccf 100644 --- a/docs/design/027-computation-core.md +++ b/docs/design/027-computation-core.md @@ -65,8 +65,8 @@ - n은 0부터 63까지다. 밖이면 `limit`이다. - 어느 기계에서나 같은 뜻이고, C의 정의되지 않은 동작이 없다. - **끝남과 결정성.** - - 모든 걸음은 실행량을 쓰고, 부름의 깊이는 프레임의 바이트로 메모리 몫에 센다. 넘으면 `work`나 `memory`로 끝나고, 이벤트는 - 통째로 되돌아간다. + - 모든 걸음은 실행량을 쓰고, 부름의 깊이는 프레임의 바이트로 메모리 몫에 센다(2c: 프레임의 바이트는 구현과 떨어진 표다). 넘으면 + `work`나 `memory`로 끝나고, 이벤트는 통째로 되돌아간다. - 결정성의 단위는 모듈이다. 같은 모듈과 같은 이벤트열이면 실패의 자리까지 같다. - 소스는 컴파일러의 판에 묶인다. EVM의 바이트코드와 가스표가 그렇다. 이것이 026의 의심 6(예산의 단위)에 대한 답이다. @@ -146,7 +146,21 @@ - **JSON 트리.** JSONTestSuite에서 틀린 것이 없고, 무작위 문서 300개의 다이제스트가 파이썬과 같다. - **막대.** 줄 수는 못 미쳤다(167 대 133: 타입 선언). 시간은 C(cJSON)의 40배이고, 순수 파이썬보다도 1.3배 느리다. - **남은 것.** 메시지 필드의 아무 값(JSON 경계에서 바로 트리로)과 저장되는 리스트의 리스트는 3·4단계로 남긴다. -- **2c:** 재귀(부르기와 돌아가기, 함수마다의 검증), 글자로 읽기. +- **2c(만듦):** 재귀(부르기와 돌아가기, 함수마다의 검증), 값으로서의 레코드, 글자로 읽기. 결과는 140의 2c절이다. + - **꼴.** 함수는 CALL이 도는 블록이다. 매개변수를 스택에 두고 시작해 RETURN이 결과를 돌려준다. 부름마다 제 스택, 지역 칸, 그리고 + 함수의 코드가 이름을 대는 이벤트의 리스트, 레지스터, 이름으로 담은 값을 가진다. 부른 쪽의 것은 돌아올 때 그대로다. + - **끝남.** 부름의 깊이는 프레임마다의 바이트를 이벤트의 몫에 세어 묶는다(넘으면 `memory`). 그 바이트는 구현의 크기가 아니라 + 표다(`module.h`의 `PURE_CALL_*`, 가스표처럼). 그래서 같은 모듈은 어느 기계, 어느 빌드에서나 같은 깊이에서 실패한다. + - **값으로서의 레코드.** aup는 레코드와 갈래의 값을 필드들로 스택에 놓고, 이름 하나(필드마다 let)에 담고, 함수에 주고받는다. + 항목은 함수에 값으로 넘어간다. 함수는 제 리스트를 가지므로 항목의 자리는 뜻이 없다. + - **글자.** `for ch in t`가 text를 코드 포인트로 돈다(CHAR_AT). `char(n)`이 코드 포인트를 text로 짓는다(CHAR). + - **JSON 트리.** 재귀 하강 파서와 깊이 우선 걷기로 다시 썼다. JSONTestSuite와 무작위 문서 300개가 파이썬과 같다. 10만 겹은 + 프레임이 몫을 다 써서 거절되고, 3만 겹의 올바른 배열은 받는다(파이썬의 `json`은 그 깊이를 못 읽는다). + - **막대.** 줄 수는 못 미쳤다(142 대 105). 시간은 cJSON의 46배, 같은 설계의 순수 파이썬의 1.6배다. + - **막은 구멍.** 반복 아래에 값을 둔 모듈이 검증을 지나 실행기를 죽였다(반복의 블록이 그 실행의 스택 바닥에서 시작해 64칸을 넘었다). + 이제 LOOP와 EACH는 제 피연산자만 있는 스택에서 연다. aup가 만든 모듈에는 그런 꼴이 없었다. + - **남은 것.** 작은 블록 fn의 인라인(JSON 트리의 부름 대부분이 `skip` 같은 작은 fn이다), 보기에서의 부름, 레코드 값의 `if` + 합류, 저장 상태의 중첩(3단계). - 레코드의 필드와 리스트의 원소가 아무 값을 가진다. - 갈래와 `match`를 둔다. diff --git a/docs/research/140-spec-suite.md b/docs/research/140-spec-suite.md index f8dda2a..13d8849 100644 --- a/docs/research/140-spec-suite.md +++ b/docs/research/140-spec-suite.md @@ -299,6 +299,71 @@ - 은행 질의(s25 대 s26, 각 네 번)는 −0.66%에서 +0.05%다(막대 ±1%). - 원본: `041-batches/2026-10-13-counts.jsonl`(b24, b26), `040-against-c/2026-10-13-counts-s26.jsonl`, `-s26b.jsonl`. +## 027의 2c: 재귀와 글자 (2026-10-18) + +2c에서 더한 것: +- **Pure.** + - 함수: 함수 표와 서명, CALL·RETURN, 함수마다의 검증, 부름을 아는 실행기(`run_calls`) + - 부름마다 제 스택, 지역 칸, 이벤트의 리스트, 레지스터, 담은 값. 프레임의 바이트는 표로 센다(구현과 떨어져 결정적이다). + - 리스트를 담는 지역 칸(타입 4), CHAR_AT과 CHAR +- **aup.** + - 블록 본문의 fn, `-> 타입`, `return a, b`, 호출 문장, 여러 값의 `let a, b = f(x)` + - 값으로서의 레코드와 갈래: 짓기, 이름에 담기, 주고받기, `match` + - `for ch in t`, `char(n)` +- **찾아 막은 구멍.** 반복 아래에 값을 둔 모듈이 검증을 지나 실행기를 죽였다(아래 62개, 반복 안 64개에서 세그폴트). 반복의 블록은 그 + 실행의 스택 바닥에서 시작하는데 검증기는 그것을 보지 않았다. 이제 LOOP와 EACH는 제 피연산자만 있는 스택에서 연다. aup가 만든 + 모듈에는 그런 꼴이 없어 모듈은 그대로다. + +**JSON 트리.** `examples/json_tree.aup`를 재귀 하강으로 다시 썼다. +- `value(d, i) -> Json, number`가 값과 끝난 자리를 돌려준다. 배열과 객체는 부름마다 제 let의 리스트에 모은다. `string`이 이스케이프를 + 풀고 `char(u)`로 코드 포인트를 잇는다. 잘못된 텍스트는 이벤트의 실패(`require`, 끝 너머의 읽기)로 거절된다. +- `walk(x)`가 깊이 우선으로 돌며 다이제스트를 낸다. 항목(`y`, `m.value`)은 값으로 넘어간다. +- 2b의 스택(`list of Open`)과 상태 기계(mode 0–5)가 사라졌다. + +**맞음.** 같은 순서(깊이 우선)로 돈 파이썬의 `json.loads`와 견준다. +- JSONTestSuite에서 틀린 것이 없다. `y_` 95개를 모두 받아 다이제스트가 같고, `n_`은 하나도 받지 않는다. `i_`는 2b와 같은 6개를 + 받는다(아주 큰 정수와 언더플로 다섯, 500겹). 짝 없는 서로게이트는 `char`가 `encoding`으로 거절한다. +- 깊이. 10만 겹 `[`와 5만 겹 `[{"":`는 프레임이 이벤트의 몫(256 MB)을 다 써서 `memory`로 거절된다(0.2초). 3만 겹의 올바른 배열은 + 받는다. 파이썬의 `json`은 그 깊이를 읽지 못한다(RecursionError). +- 무작위 중첩 문서 300개가 모두 같다. 세 실행 길이 같다. Pure의 `make check`에는 JSONTestSuite와 무작위 문서 100개로 들어 있다. + +**막대.** + +| 막대 | 잰 것 | | +|---|---|---| +| 공식 케이스 | `y_` 모두 받음, `n_` 모두 거절 | 지남 | +| 줄 수 ≤ 파이썬 참조 | aup 142줄(닫는 괄호만인 줄 23) 대 같은 설계의 파이썬 105줄(`json_rec.py`) | **못 미침** | +| 시간 | 바이트당 600 ns. cJSON 13 ns(46배), 같은 설계의 순수 파이썬 368 ns(Pure가 1.6배 느림), 파이썬의 C `json` 모듈 54 ns | 기록 | + +**줄.** +- 2b 대비 aup는 25줄, 파이썬은 28줄 줄었다. 재귀가 두 쪽의 스택과 상태 기계를 함께 지웠다. +- 남은 차이 37줄은 타입 선언(갈래 8, 레코드 4, 상태 11, 입력 1: 24줄)과 닫는 괄호(23줄)다. 둘을 빼면 aup가 짧다(95 대 105). +- 상태 11줄은 한 줄에 여럿을 적는 선언이 있으면 1줄이 된다. 다음 단계의 후보다. + +**시간이 가는 곳.** +- 바이트당 Pure 명령은 248개다(2b의 525개. 세는 법이 블록 길이라 그대로 견줄 수는 없다). 시간은 2b(556 ns)보다 8% 느리다. +- gprof로 보면 71%가 실행기의 걸음 자체이고, 부름의 드나듦(프레임, 리스트와 담은 값 돌려주기)이 10% 남짓이다. +- 10만 바이트에 부름이 6만 6천 번이다. 대부분이 `skip`처럼 작은 블록 fn이다. 027은 "작은 fn은 인라인, 재귀하는 fn은 부른다"로 + 적었다. 블록 fn의 인라인은 아직 없다. + +원본: `research/experiments/044-specs/json_rec.py`(파이썬 참조), `json_rec_time.c`(cJSON과 견줌, 깊이 우선 다이제스트가 같아야 +잰다), `2026-10-18-stage2c.jsonl`(세 번, 위는 중앙값). + +**글자.** `for ch in t`와 `char(n)`을 aup의 검사가 무작위 text 60개(1–4바이트 글자, U+10FFFF까지)로 파이썬의 `ord`와 대조한다. 글자 +수, 코드 포인트의 합, 넓은 글자 수, `char`로 다시 지은 text가 같다. 탐침 `p5-chars`(`for c in line.t`)가 이제 컴파일된다. 탐침 +`p4-rec`은 보기에서 자신을 부르는 fn이라 거절된다(보기는 부르지 않는다). 핸들러에서는 된다. + +**기존 일의 명령 수(2c).** +- b27(a9adaf2)의 워크로드 모듈은 b26과 바이트까지 같다. aup의 모듈도 2b의 컴파일러와 49개가 같다(다른 것은 `json_tree.aup`). +- 묶음의 길은 2b 대비 ±0.001%다(BFS −0.21%, 같은 빌드에서도 오가는 수). +- 실행기만의 길은 matmul −0.001%, roots 0.000%, join +0.14%, knapsack +0.30%, BFS +0.30%다(`step`에 경우 넷). +- 은행 질의(s26 대 s27, 각 네 번)는 −0.30%에서 +0.11%다(막대 ±1%). +- 그 뒤의 Pure 변경(프레임 바이트의 표)은 부름의 길만 건드린다. +- 원본: `041-batches/2026-10-18-counts.jsonl`(b26, b27), `040-against-c/2026-10-18-counts-s27.jsonl`, `-s27b.jsonl`. + +**2단계의 막대 전체.** JSON 파서가 `y_`를 모두 받고 `n_`을 모두 거절한다(지남). `i_`는 정한 쪽을 적었다. 줄 수는 못 미쳤다(위). +시간은 적었다. TPC-C의 모듈과 은행 질의의 명령 수는 그대로다(지남). + ## 착수 기준 (다음 일) - **바꿀 결정.** 계산의 핵을 설계한다(027). 위 표의 여덟 후보 가운데 무엇을 어떤 모양으로 받을지 정한다. diff --git a/research/experiments/040-against-c/2026-10-18-counts-s27.jsonl b/research/experiments/040-against-c/2026-10-18-counts-s27.jsonl new file mode 100644 index 0000000..6189828 --- /dev/null +++ b/research/experiments/040-against-c/2026-10-18-counts-s27.jsonl @@ -0,0 +1,4 @@ +{"serve": "pure-serve", "per_branch": {"instructions": 27104679, "cycles": 11890487}, "in_credit": {"instructions": 3517992, "cycles": 1599796}, "large": {"instructions": 1421141, "cycles": 635549}, "ranks": {"instructions": 24461843, "cycles": 14883419}, "none": {"instructions": 617594, "cycles": 206190}, "field": {"instructions": 8999054, "cycles": 3366751}, "found": {"instructions": 14151357, "cycles": 10583883}} +{"serve": "pure-serve", "per_branch": {"instructions": 27000469, "cycles": 11861597}, "in_credit": {"instructions": 3494299, "cycles": 1586220}, "large": {"instructions": 1421606, "cycles": 612299}, "ranks": {"instructions": 24408016, "cycles": 14881533}, "none": {"instructions": 617123, "cycles": 194839}, "field": {"instructions": 9008753, "cycles": 3313430}, "found": {"instructions": 14162216, "cycles": 10579828}} +{"serve": "pure-serve", "per_branch": {"instructions": 27179606, "cycles": 11895677}, "in_credit": {"instructions": 3534978, "cycles": 1593510}, "large": {"instructions": 1421029, "cycles": 615442}, "ranks": {"instructions": 24504036, "cycles": 14990092}, "none": {"instructions": 617586, "cycles": 195867}, "field": {"instructions": 8999045, "cycles": 3337164}, "found": {"instructions": 14147990, "cycles": 10807080}} +{"serve": "pure-serve", "per_branch": {"instructions": 27087988, "cycles": 11880543}, "in_credit": {"instructions": 3514114, "cycles": 1652760}, "large": {"instructions": 1421534, "cycles": 679535}, "ranks": {"instructions": 24458239, "cycles": 15232390}, "none": {"instructions": 617115, "cycles": 194019}, "field": {"instructions": 9008642, "cycles": 3371309}, "found": {"instructions": 14160887, "cycles": 10559598}} diff --git a/research/experiments/040-against-c/2026-10-18-counts-s27b.jsonl b/research/experiments/040-against-c/2026-10-18-counts-s27b.jsonl new file mode 100644 index 0000000..d230430 --- /dev/null +++ b/research/experiments/040-against-c/2026-10-18-counts-s27b.jsonl @@ -0,0 +1,4 @@ +{"serve": "pure-serve", "per_branch": {"instructions": 26965513, "cycles": 12329820}, "in_credit": {"instructions": 3486678, "cycles": 2301853}, "large": {"instructions": 1421213, "cycles": 764526}, "ranks": {"instructions": 24384330, "cycles": 14965408}, "none": {"instructions": 617594, "cycles": 198786}, "field": {"instructions": 8999053, "cycles": 3340870}, "found": {"instructions": 14153477, "cycles": 10932153}} +{"serve": "pure-serve", "per_branch": {"instructions": 27165700, "cycles": 11943061}, "in_credit": {"instructions": 3531402, "cycles": 1625620}, "large": {"instructions": 1421494, "cycles": 606837}, "ranks": {"instructions": 24499209, "cycles": 14876346}, "none": {"instructions": 617115, "cycles": 193396}, "field": {"instructions": 9008642, "cycles": 3349618}, "found": {"instructions": 14160543, "cycles": 10702223}} +{"serve": "pure-serve", "per_branch": {"instructions": 27199887, "cycles": 12121684}, "in_credit": {"instructions": 3539333, "cycles": 1628967}, "large": {"instructions": 1421149, "cycles": 608625}, "ranks": {"instructions": 24513416, "cycles": 15034269}, "none": {"instructions": 617594, "cycles": 195387}, "field": {"instructions": 8999053, "cycles": 3333569}, "found": {"instructions": 14151773, "cycles": 10702538}} +{"serve": "pure-serve", "per_branch": {"instructions": 27106101, "cycles": 11890926}, "in_credit": {"instructions": 3518026, "cycles": 1605106}, "large": {"instructions": 1421542, "cycles": 619029}, "ranks": {"instructions": 24466175, "cycles": 14887083}, "none": {"instructions": 617115, "cycles": 192958}, "field": {"instructions": 9008642, "cycles": 3345733}, "found": {"instructions": 14162615, "cycles": 10752104}} diff --git a/research/experiments/041-batches/2026-10-18-counts.jsonl b/research/experiments/041-batches/2026-10-18-counts.jsonl new file mode 100644 index 0000000..d1f5c4d --- /dev/null +++ b/research/experiments/041-batches/2026-10-18-counts.jsonl @@ -0,0 +1,20 @@ +{"version":"b27","way":"batches","work":"matmul","instructions":713395360,"cycles":230040058} +{"version":"b27","way":"rounds","work":"matmul","instructions":21265006173,"cycles":7306797350} +{"version":"b27","way":"batches","work":"knapsack","instructions":348632565,"cycles":105675668} +{"version":"b27","way":"rounds","work":"knapsack","instructions":21881484247,"cycles":8126458330} +{"version":"b27","way":"batches","work":"roots","instructions":157304235,"cycles":109481210} +{"version":"b27","way":"rounds","work":"roots","instructions":2719816869,"cycles":1107162486} +{"version":"b27","way":"batches","work":"join","instructions":1783718427,"cycles":1025538655} +{"version":"b27","way":"rounds","work":"join","instructions":7669671940,"cycles":3506384789} +{"version":"b27","way":"batches","work":"bfs","instructions":3364523250,"cycles":1646034641} +{"version":"b27","way":"rounds","work":"bfs","instructions":4726341201,"cycles":2095450104} +{"version":"b26","way":"batches","work":"matmul","instructions":713390693,"cycles":229445239} +{"version":"b26","way":"rounds","work":"matmul","instructions":21265242319,"cycles":7078307485} +{"version":"b26","way":"batches","work":"knapsack","instructions":348629421,"cycles":105752256} +{"version":"b26","way":"rounds","work":"knapsack","instructions":21816293868,"cycles":7885750723} +{"version":"b26","way":"batches","work":"roots","instructions":157302159,"cycles":109456602} +{"version":"b26","way":"rounds","work":"roots","instructions":2719815079,"cycles":1040127483} +{"version":"b26","way":"batches","work":"join","instructions":1783717810,"cycles":1064908324} +{"version":"b26","way":"rounds","work":"join","instructions":7659168467,"cycles":3373811804} +{"version":"b26","way":"batches","work":"bfs","instructions":3371506688,"cycles":1643771467} +{"version":"b26","way":"rounds","work":"bfs","instructions":4712039680,"cycles":2075728320} diff --git a/research/experiments/044-specs/2026-10-18-stage2c.jsonl b/research/experiments/044-specs/2026-10-18-stage2c.jsonl new file mode 100644 index 0000000..99972d6 --- /dev/null +++ b/research/experiments/044-specs/2026-10-18-stage2c.jsonl @@ -0,0 +1,6 @@ +{"size":103781,"jit":"0","batch":"","c_ns_per_byte":13.050,"pure_ns_per_byte":599.753,"ratio":46.0,"instructions":25733137,"instructions_per_byte":248.0} +{"size":103781,"python_ns_per_byte":367.8,"python_json_module_ns_per_byte":54.0} +{"size":103781,"jit":"0","batch":"","c_ns_per_byte":13.814,"pure_ns_per_byte":600.877,"ratio":43.5,"instructions":25733137,"instructions_per_byte":248.0} +{"size":103781,"python_ns_per_byte":365.5,"python_json_module_ns_per_byte":53.8} +{"size":103781,"jit":"0","batch":"","c_ns_per_byte":13.141,"pure_ns_per_byte":598.454,"ratio":45.5,"instructions":25733137,"instructions_per_byte":248.0} +{"size":103781,"python_ns_per_byte":369.3,"python_json_module_ns_per_byte":54.8} diff --git a/research/experiments/044-specs/json_rec.py b/research/experiments/044-specs/json_rec.py new file mode 100644 index 0000000..c7951e5 --- /dev/null +++ b/research/experiments/044-specs/json_rec.py @@ -0,0 +1,159 @@ +# A JSON text read into a tree by recursive descent and walked depth first for a digest: the design of aup's +# examples/json_tree.aup in 027's stage 2c, in plain Python (the reference 140 counts its lines against; the tree is +# Python's own values, an object kept as pairs). A text that is no JSON raises (ValueError, or IndexError past its +# end), as the event fails. +import re + + +class Pairs(list): + pass + + +def space(b): + return b in (0x20, 0x09, 0x0a, 0x0d) + + +def digit(b): + return 0x30 <= b <= 0x39 + + +def hexdigit(b): + return digit(b) or 0x61 <= b <= 0x66 or 0x41 <= b <= 0x46 + + +def require(ok): + if not ok: + raise ValueError + + +def code(d, i): + return int(d[i:i + 4], 16) + + +def escape(d, i): + return d[i] == 0x5c and d[i + 1] == 0x75 and all(hexdigit(d[k]) for k in range(i + 2, i + 6)) + + +def skip(d, i): + while i < len(d) and space(d[i]): + i += 1 + return i + + +def string(d, i): + require(d[i] == 0x22) + s, j = bytearray(), i + 1 + while d[j] != 0x22: + start = j + while d[j] != 0x22 and d[j] != 0x5c and d[j] >= 0x20: + j += 1 + s += d[start:j] + require(d[j] >= 0x20) + if d[j] == 0x5c: + e = d[j + 1] + if e == 0x75: + require(escape(d, j)) + u = code(d, j + 2) + j += 6 + if 0xd800 <= u < 0xdc00 and j + 5 < len(d) and escape(d, j) and 0xdc00 <= code(d, j + 2) < 0xe000: + u = 0x10000 + ((u - 0xd800) << 10 | code(d, j + 2) - 0xdc00) + j += 6 + s += chr(u).encode() # a lone surrogate raises + else: + require(e in b'"\\/bfnrt') + s += {0x62: b'\b', 0x66: b'\f', 0x6e: b'\n', 0x72: b'\r', 0x74: b'\t'}.get(e, bytes([e])) + j += 2 + return s.decode(), j + 1 + + +def number(t): + require(re.fullmatch(r'-?(0|[1-9]\d*)(\.\d+)?([eE][+-]?\d+)?', t)) + x = float(t) + require(abs(x) != float('inf')) + return x + + +def value(d, i): + j = skip(d, i) + b = d[j] + if b in (0x5b, 0x7b): + items = [] if b == 0x5b else Pairs() + j = skip(d, j + 1) + if d[j] != b + 2: + while True: + if b == 0x5b: + v, k = value(d, j) + items.append(v) + else: + name, k = string(d, j) + k = skip(d, k) + require(d[k] == 0x3a) + v, k = value(d, k + 1) + items.append((name, v)) + j = skip(d, k) + if d[j] != 0x2c: + break + j = skip(d, j + 1) + require(d[j] == b + 2) + return items, j + 1 + if b == 0x22: + return string(d, j) + if b == 0x2d or digit(b): + start, j = j, j + 1 + while j < len(d) and (digit(d[j]) or d[j] in b'.eE+-'): + j += 1 + return number(d[start:j].decode()), j + for word, v in ((b'true', True), (b'false', False), (b'null', None)): + if d[j:j + len(word)] == word: + return v, j + len(word) + raise ValueError + + +def walk(x, d): + if x is None: d['nulls'] += 1 + elif x is True: d['trues'] += 1 + elif x is False: d['falses'] += 1 + elif isinstance(x, float): d['numbers'] += 1; d['sum'] += x + elif isinstance(x, str): d['strings'] += 1; d['text_bytes'] += len(x.encode()) + elif isinstance(x, Pairs): + d['objects'] += 1 + for k, v in x: + d['key_bytes'] += len(k.encode()) + walk(v, d) + else: + d['arrays'] += 1 + for y in x: + walk(y, d) + + +def check(data): + data.decode() # UTF-8, as text(check.data) is + root, end = value(data, 0) + require(skip(data, end) == len(data)) + d = dict(nulls=0, trues=0, falses=0, numbers=0, strings=0, arrays=0, objects=0, sum=0.0, text_bytes=0, key_bytes=0) + walk(root, d) + return d + + +if __name__ == '__main__': + import json, os, sys, time + sys.setrecursionlimit(100000) + suite = sys.argv[1] + for name in sorted(os.listdir(suite)): + try: + got = check(open(os.path.join(suite, name), 'rb').read()) + except (ValueError, IndexError, RecursionError): + got = None + assert not name.startswith('y_') or got is not None, name + assert not name.startswith('n_') or got is None, name + big = b'[' + b','.join(b'{"key%d": [1.5e3, true, null, "text \\u00e9 %d"]}' % (k, k) for k in range(2000)) + b']' + runs, loads = [], [] + for _ in range(7): + start = time.perf_counter() + check(big) + runs.append((time.perf_counter() - start) * 1e9 / len(big)) + start = time.perf_counter() + d = dict(nulls=0, trues=0, falses=0, numbers=0, strings=0, arrays=0, objects=0, sum=0.0, text_bytes=0, key_bytes=0) + walk(json.loads(big, object_pairs_hook=Pairs, parse_int=float), d) + loads.append((time.perf_counter() - start) * 1e9 / len(big)) + print('{"size":%d,"python_ns_per_byte":%.1f,"python_json_module_ns_per_byte":%.1f}' % (len(big), sorted(runs)[3], sorted(loads)[3])) diff --git a/research/experiments/044-specs/json_rec_time.c b/research/experiments/044-specs/json_rec_time.c new file mode 100644 index 0000000..03c02c4 --- /dev/null +++ b/research/experiments/044-specs/json_rec_time.c @@ -0,0 +1,119 @@ +/* Research 140, design 027 stage 2c: aup's examples/json_tree.aup (run by + * Pure: a JSON text read into a tree by recursive descent, then a digest of + * the tree, depth first) against C: + * cJSON (the system's libcjson.so.1, its few declarations written here) + * reading the same document into its tree, and the same digest. Both digests + * must be equal; then each is timed (the median of seven runs of rounds). + * + * cc -O2 -std=c17 -I../../../core json_rec_time.c ../../../build/libpure.a -l:libcjson.so.1 -lm -pthread -o json_rec_time + * ./json_rec_time json_tree.pmod ROUNDS + * + * The document is json_time.c's: 2,000 objects of a key and an array of a + * number, true, null and a string with an escape. One JSON line. */ +#define _POSIX_C_SOURCE 200809L +#include "module.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +typedef struct cJSON { + struct cJSON *next, *prev, *child; + int type; + char *valuestring; + int valueint; + double valuedouble; + char *string; +} cJSON; +cJSON *cJSON_Parse(const char *value); +void cJSON_Delete(cJSON *item); +enum { FALSE_ = 1, TRUE_ = 2, NULL_ = 4, NUMBER = 8, STRING = 16, ARRAY = 32, OBJECT = 64 }; + +/* nulls, trues, falses, numbers, strings, arrays, objects, sum, text bytes, key bytes: depth first, as json_tree.aup. */ +typedef struct { double count[7], sum, text_bytes, key_bytes; } Digest; +static void walk(const cJSON *x, Digest *d) { + switch (x->type & 0xFF) { + case NULL_: d->count[0]++; break; + case TRUE_: d->count[1]++; break; + case FALSE_: d->count[2]++; break; + case NUMBER: d->count[3]++, d->sum += x->valuedouble; break; + case STRING: d->count[4]++, d->text_bytes += (double)strlen(x->valuestring); break; + case ARRAY: d->count[5]++; for (const cJSON *y = x->child; y; y = y->next) walk(y, d); break; + default: d->count[6]++; for (const cJSON *y = x->child; y; y = y->next) d->key_bytes += (double)strlen(y->string), walk(y, d); + } +} +static Digest digest(const char *text, cJSON **queue) { + (void)queue; + Digest d = {{0}, 0, 0, 0}; + cJSON *root = cJSON_Parse(text); + walk(root, &d); + cJSON_Delete(root); + return d; +} + +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); +} + +int main(int argc, char **argv) { + if (argc != 3) { fprintf(stderr, "usage: %s MODULE ROUNDS\n", argv[0]); return 2; } + int rounds = atoi(argv[2]); + static char doc[1 << 18]; + static cJSON *queue[1 << 16]; + size_t n = 0; + doc[n++] = '['; + for (int k = 0; k < 2000; ++k) + n += (size_t)sprintf(doc + n, "%s{\"key%d\": [1.5e3, true, null, \"text \\u00e9 %d\"]}", k ? "," : "", k, k); + doc[n++] = ']'; + doc[n] = 0; + PureModule module; + 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 check = pure_module_input(&module, "check"); + if (pure_app_message(&app, (uint32_t)check, NULL, -1, (PureSpan){(const unsigned char *)doc, n}) != PURE_OK) { + fprintf(stderr, "event failed\n"); + return 1; + } + uint64_t work = app.work; + Digest c = digest(doc, queue); + /* The states after valid: nulls, trues, falses, numbers, strings, arrays, objects, sum, text_bytes, key_bytes. */ + const char *names[] = {"nulls", "trues", "falses", "numbers", "strings", "arrays", "objects", "sum", "text_bytes", "key_bytes"}; + double want[] = {c.count[0], c.count[1], c.count[2], c.count[3], c.count[4], c.count[5], c.count[6], c.sum, c.text_bytes, c.key_bytes}; + for (unsigned k = 0; k < 10; ++k) { + int state = -1; + for (uint32_t s = 0; s < module.states; ++s) if (!strcmp(module.state_names[s], names[k])) state = (int)s; + if (state < 0 || app.values[state].num != want[k]) { + fprintf(stderr, "%s: %g against %g\n", names[k], state < 0 ? -1 : app.values[state].num, want[k]); + return 1; + } + } + double c_runs[7], pure_runs[7]; + volatile double sink = 0; + for (int r = 0; r < 7; ++r) { + double start = now_ns(); + for (int i = 0; i < rounds; ++i) sink += digest(doc, queue).sum; + 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; + pure_runs[r] = (now_ns() - start) / rounds; + } + qsort(c_runs, 7, sizeof(double), by_value); + qsort(pure_runs, 7, sizeof(double), by_value); + const char *jit = getenv("PURE_JIT"), *batch = getenv("PURE_BATCH"); + printf("{\"size\":%zu,\"jit\":\"%s\",\"batch\":\"%s\",\"c_ns_per_byte\":%.3f,\"pure_ns_per_byte\":%.3f,\"ratio\":%.1f," + "\"instructions\":%llu,\"instructions_per_byte\":%.1f}\n", + n, jit ? jit : "", batch ? batch : "", c_runs[3] / (double)n, pure_runs[3] / (double)n, pure_runs[3] / c_runs[3], + (unsigned long long)work, (double)work / (double)n); + pure_app_stop(&app); + return 0; +} diff --git a/tests/check.py b/tests/check.py index 9386ced..ed2a5c9 100644 --- a/tests/check.py +++ b/tests/check.py @@ -1738,17 +1738,17 @@ def module_specs(aup, pure, work): assert accepted == (name[0] == 'y') or name[0] == 'i', (name, accepted) taken[name[0]] += accepted runs['json'] = {'cases': len(cases), 'taken': taken} - # A JSON text read into a tree of values (its examples/json_tree.aup, 027's 2b: a variant, lists in records, match), - # walked breadth first for a digest, against Python's reading walked so: JSONTestSuite's cases and random documents. + # A JSON text read into a tree of values by recursive descent (its examples/json_tree.aup, 027's 2b and 2c: a + # variant, lists in records, match, fns that call themselves), walked depth first for a digest, against Python's + # reading walked so: JSONTestSuite's cases and random documents. class Pairs(list): pass def digest(data): doc = json.loads(data.decode('utf-8'), object_pairs_hook=Pairs) d = dict(nulls=0, trues=0, falses=0, numbers=0, strings=0, arrays=0, objects=0, sum=0.0, text_bytes=0, key_bytes=0) - q, at = [doc], 0 - while at < len(q): - x = q[at] + + def walk(x): if x is None: d['nulls'] += 1 elif x is True: d['trues'] += 1 elif x is False: d['falses'] += 1 @@ -1756,9 +1756,11 @@ def module_specs(aup, pure, work): elif isinstance(x, str): d['strings'] += 1; d['text_bytes'] += len(x.encode('utf-8')) elif isinstance(x, Pairs): d['objects'] += 1 - for k, v in x: d['key_bytes'] += len(k.encode('utf-8')); q.append(v) - else: d['arrays'] += 1; q.extend(x) - at += 1 + for k, v in x: d['key_bytes'] += len(k.encode('utf-8')); walk(v) + else: + d['arrays'] += 1 + for y in x: walk(y) + walk(doc) return d def value(depth): |