diff options
Diffstat (limited to 'research/experiments/044-specs')
| -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 |
8 files changed, 625 insertions, 0 deletions
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; +} |