From 241016b0fc3139414089619f0ef8cb7237722c6c Mon Sep 17 00:00:00 2001 From: eunhhu Date: Sun, 18 Oct 2026 16:44:17 +0100 Subject: Research 140, 027's stage 2c measured: JSON read into a tree by recursive descent (aup's examples/json_tree.aup: value(d, i) -> Json, number giving the value and where it ends, each call's own let's lists, string's escapes joined by char(u), a depth-first walk passing items as values) against Python's reading walked so: JSONTestSuite's 95 y_ taken alike, no n_ taken, 2b's 6 i_ taken (a lone surrogate refused by char as encoding); 100,000 and 50,000 deep refused as memory (the frames fill the event's room, 0.2 s), 30,000 deep taken (past Python's json); 300 random documents alike; in make check (module_specs' digest now depth first, three paths); 142 lines against the same design's 105 in Python (json_rec.py; the bar missed: 24 lines of declarations, 23 of braces), 46 times cJSON's time and 1.6 times plain Python's (600 ns a byte, 248 Pure instructions; 71% in the steps, about 10% in calls, 66,000 calls a document, most of them small block fns like skip); characters against Python's ord in aup's check; probes: p5-chars compiles, p4-rec (a view calling itself) refused; instruction counts: the workloads' modules the same, batches within 0.001% of 2b (BFS -0.21%), the executor alone -0.001% to +0.30%, the bank's queries -0.30% to +0.11% (four runs each; bar 1%); json_rec_time.c (cJSON, a depth-first digest compared first); CHECKPOINT's direction row through 2c --- docs/design/027-computation-core.md | 20 ++++++++++-- docs/research/140-spec-suite.md | 65 +++++++++++++++++++++++++++++++++++++ 2 files changed, 82 insertions(+), 3 deletions(-) (limited to 'docs') 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). 위 표의 여덟 후보 가운데 무엇을 어떤 모양으로 받을지 정한다. -- cgit v1.2.3