140's 8, box layout, written in aup with no new opcode (aup's examples/layout.aup: a subset of CSS Flexbox 1 written down first, one line, row or column, padding, gap, six justify-content, four align-items, grow and shrink with 9.7's loop, cross sizes stretched, nothing sized by content): 2,000 random trees (29,388 nodes; 7,659 items frozen at their padding by the loop) are Taffy 0.15's within 0.01 (layout_taffy, built by cargo; the worst 8.3e-5) and layout.py's bit for bit on the three paths, the paths the same; the single-pass subset first tried refused 66% of trees, so the loop came in; Taffy given min sizes equal to the padding (given 0 it floors at 0 while resolving lengths, where 9.7 floors the content box), the reference adding from the left (sum compensates since Python 3.12); module_specs in make check: 100 trees (tests/specs/layout); bars: 116 lines against Python's 54, 4,754 ns a node, Taffy's 644 (7.4x), pure Python 5,396 (Pure 1.14x faster), 1,494 instructions a node (9.7's loop 44%); four frictions; aup's rows read by position no longer copy (99,067 ns a node before); the suite table's row 8; CHECKPOINT's direction row

4 files changed, 310 insertions, 0 deletions

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();
+    }
+}