diff options
| -rw-r--r-- | CHECKPOINT.md | 2 | ||||
| -rw-r--r-- | docs/research/140-spec-suite.md | 79 | ||||
| -rw-r--r-- | research/experiments/044-specs/2026-10-19-layout.jsonl | 8 | ||||
| -rw-r--r-- | research/experiments/044-specs/layout.py | 67 | ||||
| -rw-r--r-- | research/experiments/044-specs/layout_check.py | 141 | ||||
| -rw-r--r-- | research/experiments/044-specs/layout_taffy/.gitignore | 1 | ||||
| -rw-r--r-- | research/experiments/044-specs/layout_taffy/Cargo.lock | 132 | ||||
| -rw-r--r-- | research/experiments/044-specs/layout_taffy/Cargo.toml | 9 | ||||
| -rw-r--r-- | research/experiments/044-specs/layout_taffy/src/main.rs | 168 | ||||
| -rw-r--r-- | research/experiments/044-specs/layout_time.c | 99 | ||||
| -rw-r--r-- | tests/check.py | 25 | ||||
| -rw-r--r-- | tests/specs/layout/README.md | 7 | ||||
| -rw-r--r-- | tests/specs/layout/trees.bin | bin | 0 -> 218992 bytes |
13 files changed, 735 insertions, 3 deletions
diff --git a/CHECKPOINT.md b/CHECKPOINT.md index e7fa6fd..050931b 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의 다섯 단계를 마쳤다. 그 뒤 묶음의 3(inflate)을 새 명령 없이 썼다: zlib가 만든 스트림 640개와 손상된 240개가 파이썬 참조와 같지만, 우회가 셋(리스트를 받지 않는 fn, 바이트 하나인 상태, 블록 안의 리스트)이고 줄은 파이썬의 1.6배, 시간은 같은 알고리즘의 C의 108배다. 묶음의 1(DNS 메시지)도 새 명령 없이 썼다: dnspython이 만든 메시지 400개를 읽고 다시 써 dnspython이 같게 읽고, 손상된 300개가 파이썬 참조와 같다. 우회는 둘(바이트의 `==`, 보기에서 부르는 블록 fn)이고 둘 다 핵의 일이며, 줄은 파이썬의 1.6배, 시간은 C의 67배(파이썬보다 1.9배 느림)다. 묶음의 9(HTTP/1.1 요청을 패킷마다)도 새 명령 없이 썼다: 스트림 200개를 어디서 잘라도 h11과 같다. 이로써 바이트 하나인 상태와 바이트의 `==`는 써서 닿은 명세가 둘이 되어 핵에 들일 자격이 생겼다(140의 결정점). 그 둘을 핵에 들였다: 바이트의 비교(TEXT_COMPARE의 비트)와 바이트 하나인 상태(028, `values`의 표시로 손상과 옮김을 가른다). aup에는 맨 리스트의 인자와 결과, 블록 안의 let 리스트를 더했다(작은 블록 fn의 인라인은 만들어 쟀으나 효과가 없어 넣지 않았다). 세 명세의 우회를 걷어 내니 줄이 파이썬의 1.5–1.9배가 되었고, DNS는 명령이 21% 줄었다. 묶음의 5(UAX #14 줄 나누기)를 데이터를 입력으로 받아 썼다: LineBreakTest.txt 16,672줄 모두와 무작위 2,000줄이 세 길에서 맞고, 시간은 Vega의 C의 199배다. 상자 배치(8)는 참조(Taffy)와 부분집합을, 단발 타이머(10)는 핵의 원시인지를 먼저 정해야 한다 | [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배다. 묶음의 1(DNS 메시지)도 새 명령 없이 썼다: dnspython이 만든 메시지 400개를 읽고 다시 써 dnspython이 같게 읽고, 손상된 300개가 파이썬 참조와 같다. 우회는 둘(바이트의 `==`, 보기에서 부르는 블록 fn)이고 둘 다 핵의 일이며, 줄은 파이썬의 1.6배, 시간은 C의 67배(파이썬보다 1.9배 느림)다. 묶음의 9(HTTP/1.1 요청을 패킷마다)도 새 명령 없이 썼다: 스트림 200개를 어디서 잘라도 h11과 같다. 이로써 바이트 하나인 상태와 바이트의 `==`는 써서 닿은 명세가 둘이 되어 핵에 들일 자격이 생겼다(140의 결정점). 그 둘을 핵에 들였다: 바이트의 비교(TEXT_COMPARE의 비트)와 바이트 하나인 상태(028, `values`의 표시로 손상과 옮김을 가른다). aup에는 맨 리스트의 인자와 결과, 블록 안의 let 리스트를 더했다(작은 블록 fn의 인라인은 만들어 쟀으나 효과가 없어 넣지 않았다). 세 명세의 우회를 걷어 내니 줄이 파이썬의 1.5–1.9배가 되었고, DNS는 명령이 21% 줄었다. 묶음의 5(UAX #14 줄 나누기)를 데이터를 입력으로 받아 썼다: LineBreakTest.txt 16,672줄 모두와 무작위 2,000줄이 세 길에서 맞고, 시간은 Vega의 C의 199배다. 묶음의 10(RFC 6298 재전송 타이머)을 주기 틱으로 썼다: 사건 241,612개가 같은 규칙의 모델과 같고, 10 ms 틱이면 타임아웃 하나에 틱이 2,796개 든다. 단발 타이머는 명세 하나만 닿아 적어 두고 만들지 않았다. 묶음의 8(상자 배치)을 Flexbox의 부분집합(한 줄, 9.7의 고정 고리까지, 내용 크기 없이)으로 썼다: 무작위 트리 2,000개가 Taffy와 0.01 안, 파이썬 참조와 비트까지 같고, 시간은 Taffy의 7.4배다. 쓰는 동안 aup가 메시지의 행을 위치로 읽을 때마다 행 전체를 복사하던 것을 찾아 고쳤다(노드당 99,067 → 4,737 ns) | [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 1da8f4b..89d92e8 100644 --- a/docs/research/140-spec-suite.md +++ b/docs/research/140-spec-suite.md @@ -54,7 +54,7 @@ | 5 | UTF-8과 줄 나누기(UAX #14) | 텍스트 | 바이트, 코드 포인트, 속성 표 | Unicode의 `LineBreakTest.txt` | 못 쓴다(글자) | 썼다: LineBreakTest.txt 16,672줄 모두와 무작위 2,000줄이 맞다. 줄 1.8배, C의 199배(아래) | | 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을 부르지 못한다(탐침). 쓰지 않음 | +| 8 | 상자 배치(flex 같은) | UI 개념 | 중첩, 재귀 | 기존 배치 구현(Yoga, Taffy)의 결과와 대조 | 못 쓴다(중첩, 재귀) | 썼다(Flexbox의 부분집합): 무작위 트리 2,000개가 Taffy와 0.01 안, 파이썬 참조와 비트까지 같다. 줄 2.1배, Taffy의 7.4배(아래) | | 9 | HTTP/1.1 요청을 패킷마다(RFC 9112) | 스트림의 상태 기계 | 바이트, 이벤트를 넘는 상태 | 경계를 아무 데서나 자른 요청 모음 | 못 쓴다(바이트). 지금은 `serve/`의 C다 | 썼다: 스트림 200개를 어디서 잘라도 h11과 같다. 우회 하나(리스트 값의 대입), 줄 1.9배, C의 83배(아래) | | 10 | 재시도, 물러서기, 시간 제한 | 시간 | 시각, 한 번의 타이머 | 시각을 준 시뮬레이션 | 우회(주기 틱 `every`와 `now`) | 썼다(RFC 6298): 사건 241,612개가 같은 규칙의 모델과 같다. 우회 하나(주기 틱: 10 ms면 타임아웃 하나에 틱 2,796개), 줄 1.9배(아래) | | 11 | X25519, ChaCha20-Poly1305 | 상수 시간 암호 | 데이터에 따라 달라지지 않는 시간 | RFC 7748, RFC 8439의 벡터 | aup 밖(설계상, 아래) | 그대로(설계상 aup 밖) | @@ -842,6 +842,83 @@ 번째 후보: HTTP의 유휴 연결 시간 제한, DNS 질의의 재시도. 둘 다 아직 묶음의 명세가 다루지 않는다. - 원본: `rto.py`(모델), `rto_check.py`(맞음, 틱의 값, 줄 수), `2026-10-19-rto.jsonl`. +## 묶음의 8: 상자 배치 (CSS Flexbox 1의 부분집합, 2026-10-19) + +**부분집합(쓰기 전에 정했다).** 막대를 셈하려면 알고리즘의 어디까지를 쓰는지 먼저 정해야 한다. +- 컨테이너: 한 줄(wrap 없음), 방향 row·column(역방향 없음), padding 네 변, 항목 사이의 gap, justify-content 여섯(start, end, + center, space-between, space-around, space-evenly), align-items 넷(start, end, center, stretch). +- 항목: flex-grow와 flex-shrink는 0–3의 정수, flex-basis는 정한 길이, 주축 크기는 auto, 교차 크기는 정한 길이이거나 auto(auto는 + 늘이는 줄에서만). +- 최소 크기는 0이다(그래서 바닥은 항목의 padding이다). 최대 크기, margin, border, 절대 위치, 종횡비, align-self, order는 없다. + box-sizing은 border-box(Taffy의 기본)다. +- 내용으로 정하는 크기(intrinsic sizing)는 없다. 모든 크기가 위에서 아래로 정해진다. 뿌리는 정한 너비와 높이를 가진다. +- 9.7(유연한 길이 결정)은 고정 고리까지 쓴다. 인자가 정수라 "풀린 항목의 인자 합이 1 미만"(4b)은 일어나지 않는다. 그 가지는 이 + 부분집합 밖이다. +- 알려진 구현은 Taffy 0.15(cargo로 받은 Rust, `layout_taffy`)다. 반올림을 끄고, 이진32인 Taffy와 이진64인 파이썬 참조의 차는 + 0.01 안이어야 한다. aup 앱은 파이썬 참조와 비트까지 같아야 한다. +- **고정 고리가 들어온 까닭.** 처음에는 9.7을 한 번에 끝나는 경우만 쓰고, 고리가 필요한 트리(줄이다 padding 밑으로 내려가는 + 항목)를 버렸다. 무작위 트리 6,538개를 뽑아 2,000개를 얻는 동안 4,346개(66%)가 그래서 버려졌다. 그 부분집합은 "늘이기만"을 재는 + 셈이다. 그래서 고리를 썼다. 고리는 돌 때마다 항목을 하나 이상 고정하므로 항목 수만큼 돌면 끝난다. + +**쓴 것.** aup의 `examples/layout.aup`이다. 새 명령도 코어의 C도 없다. +- 트리는 메시지 하나로 온다. 노드의 행(부모의 위치, 방향, 크기, 인자, basis, padding 넷, gap, justify, align)이 앞차례(preorder)로 + 든다. 부모가 아이보다 먼저 오므로, 앱은 행을 차례로 돌며 노드마다 아이들의 상자를 정한다. 크기가 모두 위에서 오므로 재귀가 필요 + 없다. 파이썬 참조(`layout.py`)도 같은 행을 같은 차례로 돈다. +- 상자(x, y, w, h, 부모의 상자에 대해)는 같은 차례의 저장 리스트다. + +**맞음.** +- `layout_check.py`: 무작위 트리 2,000개(노드 29,388개). Taffy의 상자가 모두 파이썬 참조의 0.01 안이다(가장 큰 차 8.3e-5). aup + 앱의 상자는 세 실행 길에서 모두 파이썬 참조와 비트까지 같고, 세 길이 같다. 버린 트리는 없다. +- 9.7의 고리가 padding에서 고정한 항목이 7,659개다(트리 1,399개, 70%). 고리는 시험에서 늘 돈다. +- Taffy와 맞추며 찾은 것 둘. + 1. min-size를 0으로 주면 Taffy는 9.7의 d단계에서 항목을 0에서만 자른다. padding은 항목이 끝에 갖는 크기의 바닥일 뿐이다. 표준은 + 내용 상자를 0에서 자르라고 한다(border-box에서는 padding이 바닥이다). 그래서 Taffy에 min-size로 padding의 합을 준다. 그 값이 + 표준의 규칙이 내는 값이다. Taffy의 버릇을 앱에 베끼지 않았다. + 2. 파이썬은 3.12부터 `sum()`으로 부동소수를 보정해 더한다(Neumaier). 앱은 왼쪽부터 더하므로 참조도 왼쪽부터 더한다(`reduce`). + 처음에는 트리 200개 가운데 15개가 1e-14쯤 어긋났다. +- Pure의 `make check`(`module_specs`)에 들어갔다. 트리 100개(노드 1,518개)를 상자와 함께 `tests/specs/layout`에 두었다. + space-around의 첫 간격을 3으로 나누는 앱은 그 검사에서 떨어진다. + +**막대.** + +| 막대 | 잰 것 | | +|---|---|---| +| 쓸 수 있다 | aup와 Pure만. 새 명령 없음 | 지남 | +| 우회가 없다 | 마찰 넷(아래). 우회라 할 꼴은 없다 | 지남(마찰은 적는다) | +| 줄 수 ≤ 파이썬 참조 | aup 116줄(닫는 괄호만인 줄 17) 대 파이썬 54줄 | **못 미침**(2.1배) | +| C 대비 시간 | 노드당 4,754 ns(묶음), 4,917(라운드), 4,751(모두 컴파일). Taffy(Rust, 트리를 짓고 배치)는 644 ns로, Pure가 **7.4배**다. 순수 파이썬 5,396 ns(Pure가 **1.14배 빠름**) | 기록(막대 없음) | +| 견고하다 | 위의 맞음, 세 길이 같음. 세 기계는 아직 | 일부 | + +**aup에서 고친 것: 메시지의 행을 위치로 읽기.** `tree.nodes[k]`가 행 전체를 리스트 값으로 복사하고(`LIST_VALUE`) 그 복사본에서 +읽었다. 그래서 읽을 때마다 행의 수만큼 들었다. 처음 잰 시간은 노드당 99,067 ns였다. 명령은 노드당 1,539개뿐이라 명령 하나에 +64 ns였다. 행을 그 자리에서 읽게 고치자(aup의 커밋 e5a6209) 4,737 ns가 되었고, 답은 같다. aup, Pure, Vega의 다른 모듈은 하나도 +바뀌지 않는다. aup의 `make check`에 `rows_at`을 넣었다. + +**마찰 넷.** +1. 저장 리스트 항목의 필드 여럿에 한 번에 대입하지 못한다(`boxes[k].x, boxes[k].y = …`). 네 줄로 썼다. +2. 저장 리스트를 비우는 말이 없다. `while boxes.count > 0 { boxes.remove(boxes.last) }`로 썼다. +3. 축을 고르는 길이 없다. 파이썬은 상자의 칸을 번호(`m`, `c`)로 고른다. 레코드의 필드는 번호로 고를 수 없어서 `if d.column { … } + else { … }`가 열두 번 든다. +4. 리스트의 let은 한 줄에 하나다(다섯 줄). 줄 나누기의 마찰 3과 같다. + +**줄을 길게 한 것.** 116 대 54다. 닫는 괄호의 줄을 빼면 99다. +- 레코드 둘(`Node`, `Box`)이 22줄이다. 파이썬은 튜플의 칸을 번호로 읽는다. +- 9.7의 고리가 aup에서 24줄, 파이썬에서 10줄이다. 파이썬은 리스트 내포로 풀린 항목, 인자, 위반을 한 줄씩 짓는다. +- justify의 첫 간격과 사이 간격이 파이썬에서 dict 한 줄씩, aup에서 `if … else if …` 한 줄씩이다(같다). + +**시간이 가는 곳.** 노드당 Pure 명령이 1,494개이고, 명령 하나에 약 3.2 ns가 든다. 앱을 단계마다 끊어 셈했다. +- 아이 찾기(앞차례에서 부모가 그 노드인 행, 노드 수의 제곱의 반)와 상자 만들기가 159개다. +- 항목의 리스트 다섯을 짓는 데 329개다. +- 9.7의 고리가 658개(44%)다. 한 바퀴에 항목마다 세 번 돈다(쓴 크기와 인자, 나눔과 위반, 고정). +- 남은 공간과 위치가 328개다. +- 원본: `layout.py`(파이썬 참조), `layout_check.py`(맞음, 고정한 항목, 줄 수, 경로를 주면 트리를 쓴다), `layout_taffy`(Taffy + 0.15의 오라클과 `--time`, cargo), `layout_time.c`(Pure의 시간, 트리마다의 상자가 참조와 비트까지 같아야 잰다), + `2026-10-19-layout.jsonl`. + +**부분집합이 재지 않는 것.** 내용으로 정하는 크기(min-content 기여, 자동 최소 크기), wrap과 여러 줄, margin과 auto margin, +min과 max가 남는다. Flexbox의 어려운 반은 크기가 아래에서 위로 올라오는 쪽인데, 이 부분집합은 크기가 위에서 오는 반만 잰다. +그 반은 aup로 새 명령 없이 쓰이고, Taffy와 같다. + ## 착수 기준 (다음 일) - **바꿀 결정.** 계산의 핵을 설계한다(027). 위 표의 여덟 후보 가운데 무엇을 어떤 모양으로 받을지 정한다. diff --git a/research/experiments/044-specs/2026-10-19-layout.jsonl b/research/experiments/044-specs/2026-10-19-layout.jsonl new file mode 100644 index 0000000..383bd8b --- /dev/null +++ b/research/experiments/044-specs/2026-10-19-layout.jsonl @@ -0,0 +1,8 @@ +{"what": "check", "tool": "layout_check.py 2000", "trees": 2000, "nodes": 29388, "refused": {}, "floored": {"items": 7659, "trees": 1399}, "taffy_right": 2000, "taffy_worst": 8.33333334639974e-05, "right": {"batches": 2000, "rounds": 2000, "all": 2000}, "paths_same": true, "aup_lines": 116, "aup_brace_lines": 17, "python_lines": 54} +{"what": "time", "tool": "layout_time.c (ROUNDS 1)", "trees": 2000, "nodes": 29388, "right": 2000, "jit": "0", "batch": "", "pure_ns_per_node": 4754.0, "instructions": 43902659, "instructions_per_node": 1493.9} +{"what": "time", "tool": "layout_time.c (ROUNDS 1)", "trees": 2000, "nodes": 29388, "right": 2000, "jit": "0", "batch": "0", "pure_ns_per_node": 4916.5, "instructions": 43902659, "instructions_per_node": 1493.9} +{"what": "time", "tool": "layout_time.c (ROUNDS 1)", "trees": 2000, "nodes": 29388, "right": 2000, "jit": "all", "batch": "", "pure_ns_per_node": 4751.1, "instructions": 43902659, "instructions_per_node": 1493.9} +{"what": "time", "tool": "layout_taffy --time 3 (each tree built and laid out)", "trees": 2000, "nodes": 29388, "taffy_ns_per_node": 644.1} +{"what": "time", "tool": "layout.py (median of seven passes)", "trees": 2000, "nodes": 29388, "python_ns_per_node": 5396.1} +{"what": "time before", "note": "aup before e5a6209: input.rows[k] read a copy of the rows (LIST_VALUE)", "tool": "layout_time.c (ROUNDS 1)", "trees": 2000, "nodes": 29388, "paths": {"batches": 99066.7, "all": 98324.0}, "instructions_per_node": 1539.2} +{"what": "instructions by stage", "note": "the app cut after each stage, cumulative, a node (batches)", "kids_found_and_boxes_made": 159.2, "items_lists": 488.3, "before_9_7_loop": 508.6, "after_9_7_loop": 1166.3, "whole": 1493.9} diff --git a/research/experiments/044-specs/layout.py b/research/experiments/044-specs/layout.py new file mode 100644 index 0000000..1cea31a --- /dev/null +++ b/research/experiments/044-specs/layout.py @@ -0,0 +1,67 @@ +# Box layout, a subset of CSS Flexbox 1, in plain Python: the reference 140 counts aup's lines against. Containers lay +# their items out in one line (no wrap) along a row or a column: padding, a gap between items, justify-content (start, +# end, center, space-between, space-around, space-evenly) and align-items (start, end, center, stretch). An item's main +# size is its flex basis grown or shrunk (9.7), its cross size its own or, auto, stretched to the line. Every size is +# known from above: nothing is sized by its content, and min sizes are 0 (an item's padding at least). Flex factors +# are whole numbers: 9.7's sum below one (4b) does not arise. +from functools import reduce +from operator import add + +START, END, CENTER, BETWEEN, AROUND, EVENLY = range(6) # justify-content; align-items: START, END, CENTER, STRETCH +STRETCH = 3 + + +class Refused(Exception): + pass + + +def total(xs): # added from the left, as the app adds (sum compensates since Python 3.12) + return reduce(add, xs, 0) + + +def layout(nodes): + """nodes in preorder, each (parent, column, w, h, grow, shrink, basis, left, right, top, bottom, gap, justify, + align), w and h -1 when auto; each node's box [x, y, w, h], relative to its parent's.""" + boxes = [[0.0, 0.0, 0.0, 0.0] for _ in nodes] + boxes[0][2:] = nodes[0][2], nodes[0][3] + for i, (_, column, _, _, _, _, _, left, right, top, bottom, gap, justify, align) in enumerate(nodes): + kids = [j for j in range(i + 1, len(nodes)) if nodes[j][0] == i] + if not kids: + continue + m, c = (3, 2) if column else (2, 3) # the main and the cross sizes' places + inner = boxes[i][m] - (top + bottom if column else left + right) + line = max(boxes[i][c] - (left + right if column else top + bottom), 0) + pads = [(nodes[k][9] + nodes[k][10], nodes[k][7] + nodes[k][8]) if column else + (nodes[k][7] + nodes[k][8], nodes[k][9] + nodes[k][10]) for k in kids] + bases = [max(nodes[k][6], p) for k, (p, _) in zip(kids, pads)] + gaps = gap * (len(kids) - 1) + free = inner - (total(bases) + gaps) + n, growing = len(kids), free > 0 + sizes, frozen = bases[:], [free == 0 or nodes[k][4] == nodes[k][5] == 0 for k in kids] + while not all(frozen): # 9.7: each pass freezes one item at least + free = inner - (total(sizes[x] if frozen[x] else bases[x] for x in range(n)) + gaps) + loose = [x for x in range(n) if not frozen[x]] + factors = [nodes[kids[x]][4] if growing else (bases[x] - pads[x][0]) * nodes[kids[x]][5] for x in loose] + if free != 0 and total(factors) > 0: # grown by the grow factors, or shrunk by the shrink factors scaled + for x, f in zip(loose, factors): + sizes[x] = bases[x] + free * (f / total(factors)) + violations = [max(sizes[x], pads[x][0]) - sizes[x] for x in loose] # min violations: below the padding + for x, v in zip(loose, violations): + sizes[x], frozen[x] = max(sizes[x], pads[x][0]), v > 0 or total(violations) == 0 + free = inner - (total(sizes) + gaps) # 9.5: what is left, by justify-content + if (len(kids) == 1 or free <= 0) and justify in (BETWEEN, AROUND, EVENLY): + justify = START if free <= 0 or justify == BETWEEN else CENTER + first = {START: 0, END: free, CENTER: free / 2, BETWEEN: 0, AROUND: free / n / 2, EVENLY: free / (n + 1)}[justify] + between = {BETWEEN: free / max(n - 1, 1), AROUND: free / n, EVENLY: free / (n + 1)}.get(justify, 0) + gap + at = top if column else left + for x, (k, size, (_, p)) in enumerate(zip(kids, sizes, pads)): + at = at + (first if x == 0 else between) + own = nodes[k][c] + if own < 0 and align != STRETCH: + raise Refused('an auto cross size not stretched: sized by its content') + across = max(line if own < 0 else own, p) + offset = {START: 0, END: line - across, CENTER: (line - across) / 2}.get(align, 0) + boxes[k][m - 2], boxes[k][c - 2] = at, (left if column else top) + offset + boxes[k][m], boxes[k][c] = size, across + at = at + size + return boxes diff --git a/research/experiments/044-specs/layout_check.py b/research/experiments/044-specs/layout_check.py new file mode 100644 index 0000000..7b0c300 --- /dev/null +++ b/research/experiments/044-specs/layout_check.py @@ -0,0 +1,141 @@ +#!/usr/bin/env python3 +"""Research 140: box layout (a subset of CSS Flexbox 1) written in aup (aup's examples/layout.aup). + +Draws random trees of flex containers inside the subset layout.py states (one line, row or column, padding, gap, +justify-content, align-items, grow, shrink and a definite basis, cross sizes definite or stretched, min sizes 0), and +lays each out three ways: Taffy (0.15, the known implementation: layout_taffy, built by cargo), layout.py (the Python +reference) and the app on Pure's three paths (batches, rounds, all compiled), a tree a message of its nodes in preorder. +Taffy works in binary32: its boxes must be the reference's within TOLERANCE; the app's must be the reference's exactly, +the paths the same. A tree the reference refuses (a size from content) is drawn again, and counted; the items 9.7's +loop froze at their padding are counted too. Then counts lines (code lines: neither blank nor a comment; brace lines: a closing brace alone) of layout.aup +and of layout.py. One JSON line; given a directory, it writes the trees there for layout_time.c. + + python3 layout_check.py [TREES] [DIRECTORY] (TREES: 2,000 by default)""" +import json, os, random, struct, subprocess, sys, tempfile + +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')) +taffy = os.environ.get('TAFFY', os.path.join(here, 'layout_taffy', 'target', 'release', 'layout_taffy')) +sys.path.insert(0, here) +import layout # noqa: E402 + +TOLERANCE = 0.01 # Taffy's binary32 against binary64, at sizes up to a thousand +JUSTIFY = ['start', 'end', 'center', 'space-between', 'space-around', 'space-evenly'] +ALIGN = ['start', 'end', 'center', 'stretch'] + + +def lines(path): + code = braces = 0 + for line in open(path): + text = line.strip() + if not text or text.startswith('#'): continue + code += 1 + braces += text == '}' + return code, braces + + +def draw(chooser, depth=0, parent=None): + """A node and its subtree: a container's own properties, and an item's in its parent (main size auto, the basis + definite; the cross size definite, or auto when the parent stretches).""" + node = {'dir': chooser.choice(['row', 'column']), 'pad': [chooser.choice([0, 0, 0, 1, 2, 4, 8]) for _ in range(4)], + 'gap': chooser.choice([0, 0, 2, 5, 10]), 'justify': chooser.choice(JUSTIFY), 'align': chooser.choice(ALIGN), + 'grow': 0, 'shrink': 0, 'basis': None, 'w': None, 'h': None} + if parent is None: + node['w'], node['h'] = chooser.randrange(100, 1000), chooser.randrange(100, 800) + else: + node['grow'], node['shrink'] = chooser.choice([0, 0, 1, 1, 2, 3]), chooser.choice([0, 1, 1, 1, 2, 3]) + node['basis'] = chooser.choice([0, 5, 10, 20, 40, 60, 100, 150, 250]) + cross = 'w' if parent['dir'] == 'column' else 'h' + if parent['align'] != 'stretch' or chooser.random() < 0.4: + node[cross] = chooser.choice([0, 10, 20, 30, 50, 80, 120, 200]) + count = chooser.choice([1, 2, 3, 4, 5]) if parent is None else chooser.choice([0, 0, 0, 1, 2, 3, 4]) if depth < 3 else 0 + node['kids'] = [draw(chooser, depth + 1, node) for _ in range(count)] + return node + + +def rows(tree, parent=-1, out=None): + """The nodes in preorder, as layout.py and the app take them.""" + out = [] if out is None else out + me = len(out) + out.append((parent, int(tree['dir'] == 'column'), -1 if tree['w'] is None else tree['w'], -1 if tree['h'] is None else tree['h'], + tree['grow'], tree['shrink'], tree['basis'] or 0, *tree['pad'], tree['gap'], JUSTIFY.index(tree['justify']), + ALIGN.index(tree['align']))) + for kid in tree['kids']: + rows(kid, me, out) + return out + + +def trees(count, seed=140): + chooser, out, refused = random.Random(seed), [], {} + while len(out) < count: + tree = draw(chooser) + try: + out.append((tree, rows(tree), layout.layout(rows(tree)))) + except layout.Refused as why: + refused[str(why)] = refused.get(str(why), 0) + 1 + return out, refused + + +def floored(nodes, boxes): + """The items 9.7's loop froze at their padding: shrunk from a basis above it to it.""" + count = 0 + for k, node in enumerate(nodes[1:], 1): + column = nodes[node[0]][1] + pad = node[9] + node[10] if column else node[7] + node[8] + count += max(node[6], pad) > pad and boxes[k][3 if column else 2] == pad + return count + + +def run(module, given, env, work): + commands = os.path.join(work, 'layout.commands') + with open(commands, 'w') as f: + for _, nodes, _ in given: + f.write(f"message tree {b''.join(struct.pack('<14d', *n) for n in nodes).hex()}\n") + got = [] + with open(commands) as stdin: + process = subprocess.Popen([os.path.join(pure, 'build', 'pure-run'), module], stdin=stdin, stdout=subprocess.PIPE, + text=True, env=dict(os.environ, **env)) + for line in process.stdout: + state = json.loads(line) + got.append([[b['x'], b['y'], b['w'], b['h']] for b in state['states']['boxes']] if state['fault'] == 'none' else None) + process.wait() + return got + + +if __name__ == '__main__': + count = int(sys.argv[1]) if len(sys.argv) > 1 else 2000 + given, refused = trees(count) + oracle = subprocess.run([taffy], input=''.join(json.dumps(t) + '\n' for t, _, _ in given), capture_output=True, text=True, + check=True).stdout.splitlines() + worst, taffy_right = 0.0, 0 + for (_, _, want), line in zip(given, oracle): + boxes = json.loads(line) + far = max(abs(a - b) for g, w in zip(boxes, want) for a, b in zip(g, w)) if len(boxes) == len(want) else float('inf') + worst = max(worst, far) + taffy_right += far <= TOLERANCE + frozen = [floored(nodes, want) for _, nodes, want in given] + report = {'trees': len(given), 'nodes': sum(len(n) for _, n, _ in given), 'refused': refused, + 'floored': {'items': sum(frozen), 'trees': sum(f > 0 for f in frozen)}, 'taffy_right': taffy_right, + 'taffy_worst': worst, 'right': {}, 'paths_same': True} + if len(sys.argv) > 2: + os.makedirs(sys.argv[2], exist_ok=True) + with open(os.path.join(sys.argv[2], 'trees.bin'), 'wb') as f: # each: u32 nodes, their rows, then their boxes + for _, nodes, want in given: + f.write(struct.pack('<I', len(nodes)) + b''.join(struct.pack('<14d', *n) for n in nodes) + + b''.join(struct.pack('<4d', *b) for b in want)) + source = os.path.join(aup, 'examples', 'layout.aup') + if os.path.exists(source): + with tempfile.TemporaryDirectory() as work: + module = os.path.join(work, 'layout.pmod') + subprocess.run([os.path.join(aup, 'build', 'aup'), 'build', source, '-o', module], check=True) + outputs = {} + for name, env in (('batches', {'PURE_JIT': '0'}), ('rounds', {'PURE_JIT': '0', 'PURE_BATCH': '0'}), ('all', {'PURE_JIT': 'all'})): + outputs[name] = run(module, given, env, work) + report['right'][name] = sum(g == w for g, (_, _, w) in zip(outputs[name], given)) + report['paths_same'] = outputs['batches'] == outputs['rounds'] == outputs['all'] + report['aup_lines'], report['aup_brace_lines'] = lines(source) + report['python_lines'] = lines(os.path.join(here, 'layout.py'))[0] + ok = taffy_right == len(given) and report['paths_same'] and all(n == len(given) for n in report['right'].values()) + print(json.dumps(report)) + sys.exit(0 if ok else 1) diff --git a/research/experiments/044-specs/layout_taffy/.gitignore b/research/experiments/044-specs/layout_taffy/.gitignore new file mode 100644 index 0000000..ea8c4bf --- /dev/null +++ b/research/experiments/044-specs/layout_taffy/.gitignore @@ -0,0 +1 @@ +/target diff --git a/research/experiments/044-specs/layout_taffy/Cargo.lock b/research/experiments/044-specs/layout_taffy/Cargo.lock new file mode 100644 index 0000000..6fd842b --- /dev/null +++ b/research/experiments/044-specs/layout_taffy/Cargo.lock @@ -0,0 +1,132 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "itoa" +version = "1.0.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8f42a60cbdf9a97f5d2305f08a87dc4e09308d1276d28c869c684d7777685682" + +[[package]] +name = "layout_taffy" +version = "0.1.0" +dependencies = [ + "serde_json", + "taffy", +] + +[[package]] +name = "memchr" +version = "2.8.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cf8baf1c55e62ffcace7a9f06f4bd9cd3f0c4beb022d3b367256b91b87513d98" + +[[package]] +name = "proc-macro2" +version = "1.0.107" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "985e7ec9bb745e6ce6535b544d84d6cd6f7ad8bd711c398938ae983b91a766d9" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "quote" +version = "1.0.47" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1fbf4db142a473a8d80c26bbf18454ed458bf8d26c8219c331daecfdbd079001" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "serde" +version = "1.0.229" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4148590afebada386688f18773da617792bf2ef03ffc1e4cbd2b1d45b023e0ba" +dependencies = [ + "serde_core", + "serde_derive", +] + +[[package]] +name = "serde_core" +version = "1.0.229" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "67dca2c9c51e58a4791a4b1ed58308b39c64224d349a935ab5039aa360942a48" +dependencies = [ + "serde_derive", +] + +[[package]] +name = "serde_derive" +version = "1.0.229" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e7a5d71263a5a7d47b41f6b3f06ba276f10cc18b0931f1799f710578e2309348" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "serde_json" +version = "1.0.154" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e7e9cc8b1b85264074fbcc02a88680c4096b1e47df8f739dceb03bf482f04bd6" +dependencies = [ + "itoa", + "memchr", + "serde", + "serde_core", + "zmij", +] + +[[package]] +name = "slotmap" +version = "1.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bdd58c3c93c3d278ca835519292445cb4b0d4dc59ccfdf7ceadaab3f8aeb4038" +dependencies = [ + "version_check", +] + +[[package]] +name = "syn" +version = "3.0.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d78c8dee4c7bf0e14673097256fed6142ce9d3b85a408189d07482442145823b" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "taffy" +version = "0.15.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3c8480887e8803986d96a7173729565520d4bbb721ad6b7ad6941a22897207aa" +dependencies = [ + "serde", + "slotmap", +] + +[[package]] +name = "unicode-ident" +version = "1.0.27" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a2c754d6c33795a1c324727428e5a7dedb5b06195f9890bdbcba760d3e246563" + +[[package]] +name = "version_check" +version = "0.9.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0b928f33d975fc6ad9f86c8f283853ad26bdd5b10b7f1542aa2fa15e2289105a" + +[[package]] +name = "zmij" +version = "1.0.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "29666d0abbfad1e3dc4dcf6144730dd3a3ab225bbbdac83319345b1b44ccfc1b" diff --git a/research/experiments/044-specs/layout_taffy/Cargo.toml b/research/experiments/044-specs/layout_taffy/Cargo.toml new file mode 100644 index 0000000..ef3c005 --- /dev/null +++ b/research/experiments/044-specs/layout_taffy/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "layout_taffy" +version = "0.1.0" +edition = "2021" +publish = false + +[dependencies] +taffy = { version = "=0.15.0", default-features = false, features = ["std", "taffy_tree", "flexbox"] } +serde_json = "1" diff --git a/research/experiments/044-specs/layout_taffy/src/main.rs b/research/experiments/044-specs/layout_taffy/src/main.rs new file mode 100644 index 0000000..5d66df3 --- /dev/null +++ b/research/experiments/044-specs/layout_taffy/src/main.rs @@ -0,0 +1,168 @@ +//! Research 140: the known implementation box layout (spec 8) is checked against. Each line of stdin is a tree of +//! flex containers, a JSON object a node: `dir` ("row", "column"), `w`, `h` (a length, or null: auto), `grow`, `shrink`, +//! `basis` (a length, or null: auto), `pad` ([left, right, top, bottom]), `gap`, `justify` ("start", "end", "center", +//! "space-between", "space-around", "space-evenly"), `align` ("start", "end", "center", "stretch") and `kids`. Taffy lays +//! it out (flexbox, no wrap, no rounding) in the root's size; each line of stdout is the nodes' boxes in preorder, +//! [x, y, w, h], each relative to its parent's. Min sizes are 0, which 9.7 floors at an item's padding (its content box +//! at zero); Taffy, given 0, floors at 0 while it resolves lengths (its padding only bounds the size it ends with), so +//! it is given the padding. +//! +//! `layout_taffy --time ROUNDS TREES` times Taffy instead, on the trees layout_check.py writes (each a u32 count, its +//! nodes' rows of 14 binary64s in preorder, as the app takes them, and their boxes): each tree built and laid out, its +//! boxes the file's within 0.01 first, then the median of seven runs of ROUNDS passes. One JSON line. +use serde_json::Value; +use std::io::{self, BufRead, Write}; +use std::time::Instant; +use taffy::prelude::*; + +fn length(v: &Value) -> Dimension { + v.as_f64().map_or(Dimension::auto(), |x| Dimension::length(x as f32)) +} + +fn node(tree: &mut TaffyTree<()>, v: &Value) -> NodeId { + let kids: Vec<NodeId> = v["kids"].as_array().map_or(vec![], |k| k.iter().map(|c| node(tree, c)).collect()); + let pad: Vec<f32> = v["pad"].as_array().map_or(vec![0.0; 4], |p| p.iter().map(|x| x.as_f64().unwrap() as f32).collect()); + let gap = v["gap"].as_f64().unwrap_or(0.0) as f32; + let style = Style { + display: Display::Flex, + flex_direction: if v["dir"] == "column" { FlexDirection::Column } else { FlexDirection::Row }, + flex_wrap: FlexWrap::NoWrap, + size: Size { width: length(&v["w"]), height: length(&v["h"]) }, + min_size: Size { + width: LengthPercentageAuto::length(pad[0] + pad[1]), + height: LengthPercentageAuto::length(pad[2] + pad[3]), + }, + flex_grow: v["grow"].as_f64().unwrap_or(0.0) as f32, + flex_shrink: v["shrink"].as_f64().unwrap_or(0.0) as f32, + flex_basis: length(&v["basis"]), + padding: Rect { + left: LengthPercentage::length(pad[0]), + right: LengthPercentage::length(pad[1]), + top: LengthPercentage::length(pad[2]), + bottom: LengthPercentage::length(pad[3]), + }, + gap: Size { width: LengthPercentage::length(gap), height: LengthPercentage::length(gap) }, + justify_content: match v["justify"].as_str().unwrap_or("start") { + "end" => JustifyContent::END, + "center" => JustifyContent::CENTER, + "space-between" => JustifyContent::SPACE_BETWEEN, + "space-around" => JustifyContent::SPACE_AROUND, + "space-evenly" => JustifyContent::SPACE_EVENLY, + _ => JustifyContent::START, + }, + align_items: match v["align"].as_str().unwrap_or("stretch") { + "start" => AlignItems::START, + "end" => AlignItems::END, + "center" => AlignItems::CENTER, + _ => AlignItems::STRETCH, + }, + ..Default::default() + }; + tree.new_with_children(style, &kids).unwrap() +} + +fn boxes(tree: &TaffyTree<()>, n: NodeId, out: &mut Vec<[f32; 4]>) { + let l = tree.layout(n).unwrap(); + out.push([l.location.x, l.location.y, l.size.width, l.size.height]); + for c in tree.children(n).unwrap() { + boxes(tree, c, out); + } +} + +/// A row's node: parent, column, w, h (-1: auto), grow, shrink, basis, left, right, top, bottom, gap, justify, align. +fn style_of(r: &[f64]) -> Style { + let length = |x: f64| if x < 0.0 { Dimension::auto() } else { Dimension::length(x as f32) }; + let (l, rt, t, b) = (r[7] as f32, r[8] as f32, r[9] as f32, r[10] as f32); + Style { + display: Display::Flex, + flex_direction: if r[1] != 0.0 { FlexDirection::Column } else { FlexDirection::Row }, + size: Size { width: length(r[2]), height: length(r[3]) }, + min_size: Size { width: LengthPercentageAuto::length(l + rt), height: LengthPercentageAuto::length(t + b) }, + flex_grow: r[4] as f32, + flex_shrink: r[5] as f32, + flex_basis: if r[0] < 0.0 { Dimension::auto() } else { length(r[6]) }, + padding: Rect { + left: LengthPercentage::length(l), + right: LengthPercentage::length(rt), + top: LengthPercentage::length(t), + bottom: LengthPercentage::length(b), + }, + gap: Size { width: LengthPercentage::length(r[11] as f32), height: LengthPercentage::length(r[11] as f32) }, + justify_content: [JustifyContent::START, JustifyContent::END, JustifyContent::CENTER, JustifyContent::SPACE_BETWEEN, + JustifyContent::SPACE_AROUND, JustifyContent::SPACE_EVENLY][r[12] as usize], + align_items: [AlignItems::START, AlignItems::END, AlignItems::CENTER, AlignItems::STRETCH][r[13] as usize], + ..Default::default() + } +} + +/// A tree of rows built and laid out in its root's size: its nodes, in the rows' order. +fn lay(size: Size<f32>, styles: &[(i64, Style)]) -> (TaffyTree<()>, Vec<NodeId>) { + let mut tree: TaffyTree<()> = TaffyTree::new(); + tree.disable_rounding(); + let ids: Vec<NodeId> = styles.iter().map(|(_, s)| tree.new_leaf(s.clone()).unwrap()).collect(); + for (k, (parent, _)) in styles.iter().enumerate().skip(1) { + tree.add_child(ids[*parent as usize], ids[k]).unwrap(); + } + let space = Size { width: AvailableSpace::Definite(size.width), height: AvailableSpace::Definite(size.height) }; + tree.compute_layout(ids[0], space).unwrap(); + (tree, ids) +} + +fn time(rounds: usize, path: &str) { + let data = std::fs::read(path).unwrap(); + let number = |at: usize| f64::from_le_bytes(data[at..at + 8].try_into().unwrap()); + let (mut trees, mut wants, mut at, mut nodes) = (vec![], vec![], 0, 0); + while at < data.len() { + let n = u32::from_le_bytes(data[at..at + 4].try_into().unwrap()) as usize; + let rows: Vec<Vec<f64>> = (0..n).map(|k| (0..14).map(|f| number(at + 4 + 112 * k + 8 * f)).collect()).collect(); + let boxes: Vec<f64> = (0..4 * n).map(|f| number(at + 4 + 112 * n + 8 * f)).collect(); + let size = Size { width: rows[0][2] as f32, height: rows[0][3] as f32 }; + trees.push((size, rows.iter().map(|r| (r[0] as i64, style_of(r))).collect::<Vec<_>>())); + wants.push(boxes); + at += 4 + 112 * n + 32 * n; + nodes += n; + } + for ((size, styles), want) in trees.iter().zip(&wants) { + let (tree, ids) = lay(*size, styles); + for (k, id) in ids.iter().enumerate() { + let l = tree.layout(*id).unwrap(); + let got = [l.location.x, l.location.y, l.size.width, l.size.height]; + assert!((0..4).all(|f| (got[f] as f64 - want[4 * k + f]).abs() <= 0.01), "a box not the reference's"); + } + } + let mut runs = vec![]; + for _ in 0..7 { + let start = Instant::now(); + for _ in 0..rounds { + for (size, styles) in &trees { + std::hint::black_box(lay(*size, styles)); + } + } + runs.push(start.elapsed().as_nanos() as f64 / rounds as f64); + } + runs.sort_by(|a, b| a.partial_cmp(b).unwrap()); + println!("{{\"trees\":{},\"nodes\":{},\"taffy_ns_per_node\":{:.1}}}", trees.len(), nodes, runs[3] / nodes as f64); +} + +fn main() { + let args: Vec<String> = std::env::args().collect(); + if args.len() == 4 && args[1] == "--time" { + return time(args[2].parse().unwrap(), &args[3]); + } + let stdout = io::stdout(); + let mut out = io::BufWriter::new(stdout.lock()); + for line in io::stdin().lock().lines() { + let v: Value = serde_json::from_str(&line.unwrap()).unwrap(); + let mut tree: TaffyTree<()> = TaffyTree::new(); + tree.disable_rounding(); + let root = node(&mut tree, &v); + let space = Size { + width: AvailableSpace::Definite(v["w"].as_f64().unwrap() as f32), + height: AvailableSpace::Definite(v["h"].as_f64().unwrap() as f32), + }; + tree.compute_layout(root, space).unwrap(); + let mut b = vec![]; + boxes(&tree, root, &mut b); + writeln!(out, "{}", serde_json::to_string(&b).unwrap()).unwrap(); + } +} diff --git a/research/experiments/044-specs/layout_time.c b/research/experiments/044-specs/layout_time.c new file mode 100644 index 0000000..3f2ce52 --- /dev/null +++ b/research/experiments/044-specs/layout_time.c @@ -0,0 +1,99 @@ +/* Research 140: box layout (a subset of CSS Flexbox 1) in aup (aup's examples/layout.aup, run by Pure), timed on the + * trees layout_check.py writes (each a u32 count, its nodes' rows of 14 binary64s in preorder, then their boxes, four + * binary64s each, as layout.py works them out). Each tree is a message; its boxes must be the file's, bit for bit; then + * the median of seven runs of ROUNDS passes. Taffy's time is layout_taffy --time's. + * + * cc -O2 -std=c17 -I../../../core layout_time.c ../../../build/libpure.a -lm -pthread -o layout_time + * ./layout_time layout.pmod TREES ROUNDS + * + * One JSON line: the trees and nodes, the nanoseconds per node, and the instructions Pure counted for one pass. */ +#define _POSIX_C_SOURCE 200809L +#include "module.h" +#include "module-list.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +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; +} + +typedef struct { uint32_t count; const unsigned char *rows; const unsigned char *boxes; } Tree; + +int main(int argc, char **argv) { + if (argc != 4) { fprintf(stderr, "usage: %s MODULE TREES ROUNDS\n", argv[0]); return 2; } + size_t size; + unsigned char *bytes = whole(argv[2], &size); + int rounds = atoi(argv[3]); + if (!bytes) { fprintf(stderr, "cannot read the trees\n"); return 1; } + static Tree trees[1 << 16]; + size_t count = 0, nodes = 0; + for (size_t at = 0; at + 4 <= size && count < sizeof(trees) / sizeof(*trees); ++count) { + Tree *t = &trees[count]; + memcpy(&t->count, bytes + at, 4); + t->rows = bytes + at + 4; + t->boxes = t->rows + 112 * (size_t)t->count; + at += 4 + 144 * (size_t)t->count; + nodes += t->count; + } + + 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, "tree"), boxes = pure_module_state(&module, "boxes"); + size_t right = 0; + uint64_t work = 0; + for (size_t k = 0; k < count; ++k) { + const Tree *t = &trees[k]; + bool same = pure_app_message(&app, (uint32_t)input, (PureSpan){t->rows, 112 * (size_t)t->count}) == PURE_OK && + pure_list_count(app.lists[boxes]) == t->count; + work += app.work; + for (uint32_t i = 0; same && i < t->count; ++i) + for (unsigned f = 0; same && f < 4; ++f) { + double want; + memcpy(&want, t->boxes + 32 * (size_t)i + 8 * f, 8); + same = pure_list_get(app.lists[boxes], i, f).num == want; + } + right += same; + } + if (right != count) { fprintf(stderr, "trees %zu: Pure right %zu\n", count, right); return 1; } + double runs[7]; + for (int r = 0; r < 7; ++r) { + double start = now_ns(); + for (int i = 0; i < rounds; ++i) + for (size_t k = 0; k < count; ++k) + if (pure_app_message(&app, (uint32_t)input, (PureSpan){trees[k].rows, 112 * (size_t)trees[k].count}) != PURE_OK) + return 1; + runs[r] = (now_ns() - start) / rounds; + } + qsort(runs, 7, sizeof(double), by_value); + const char *jit = getenv("PURE_JIT"), *batch = getenv("PURE_BATCH"); + printf("{\"trees\":%zu,\"nodes\":%zu,\"right\":%zu,\"jit\":\"%s\",\"batch\":\"%s\",\"pure_ns_per_node\":%.1f," + "\"instructions\":%llu,\"instructions_per_node\":%.1f}\n", + count, nodes, right, jit ? jit : "", batch ? batch : "", runs[3] / (double)nodes, (unsigned long long)work, + (double)work / (double)nodes); + pure_app_stop(&app); + return 0; +} diff --git a/tests/check.py b/tests/check.py index 5574b80..dd64e03 100644 --- a/tests/check.py +++ b/tests/check.py @@ -1738,7 +1738,9 @@ def module_specs(aup, pure, work): at a time, cut anywhere, to the same requests; line breaking (UAX #14) by its examples/linebreak.aup on LineBreakTest.txt's lines (tests/specs/linebreak); RFC 6298's retransmission timer by its examples/rto.aup on a scenario's - events (tests/specs/rto), the model's state after each.""" + events (tests/specs/rto), the model's state after each; box layout (a + subset of CSS Flexbox 1) by its examples/layout.aup on trees + (tests/specs/layout), each box bit for bit.""" import hashlib import os import random @@ -1988,6 +1990,27 @@ def module_specs(aup, pure, work): len(s['retransmits'])] == want, ('rto', period, want) events += len(out) runs['rto'] = {'scenarios': 2, 'events': events} + # Box layout (a subset of CSS Flexbox 1, its examples/layout.aup): trees as layout.py lays them out (tests/specs/layout, + # Taffy's within 0.01), a tree a message of its nodes in preorder, its boxes bit for bit on the three paths. + program = work / 'layout.pmod' + compile_module(aup, EXAMPLES / 'layout.aup', program) + given, trees = (pure / 'tests/specs/layout/trees.bin').read_bytes(), [] + while given: + n = struct.unpack_from('<I', given)[0] + trees.append((given[4:4 + 112 * n], [list(struct.unpack_from('<4d', given, 4 + 112 * n + 32 * k)) for k in range(n)])) + given = given[4 + 144 * n:] + given = ''.join(f'message tree {rows.hex()}\n' for rows, _ in trees) + shown = {name: subprocess.run([str(pure / 'build/pure-run'), str(program)], input=given, capture_output=True, text=True, + timeout=120, 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 shown[name] == shown['batches'], ('layout', name) + out = shown['batches'].splitlines() + assert len(out) == len(trees), ('layout', len(out)) + for (_, want), line in zip(trees, out): + state = json.loads(line) + assert state['fault'] == 'none' and [[b['x'], b['y'], b['w'], b['h']] for b in state['states']['boxes']] == want, want + runs['layout'] = {'trees': len(trees), 'nodes': sum(len(w) for _, w in trees)} return runs diff --git a/tests/specs/layout/README.md b/tests/specs/layout/README.md new file mode 100644 index 0000000..3341c4e --- /dev/null +++ b/tests/specs/layout/README.md @@ -0,0 +1,7 @@ +# Box layout (a subset of CSS Flexbox 1): 100 trees + +`trees.bin` holds the first 100 trees `research/experiments/044-specs/layout_check.py` draws, each a u32 count of its +nodes, their rows in preorder (14 binary64s: parent, column, w, h, grow, shrink, basis, left, right, top, bottom, gap, +justify, align), then their boxes (x, y, w, h, each relative to its parent's), as `layout.py` works them out; Taffy +0.15's are the same within 0.01. `tests/check.py`'s `module_specs` gives each tree to aup's `examples/layout.aup` as a +message, on Pure's three paths: its boxes must be these, bit for bit. diff --git a/tests/specs/layout/trees.bin b/tests/specs/layout/trees.bin Binary files differnew file mode 100644 index 0000000..387caff --- /dev/null +++ b/tests/specs/layout/trees.bin |