609556f | plum | pyrossh

git clone https://git.pyrossh.dev/plum

A statically typed, imperative programming language inspired by rust, python

609556f — Peter John 2026-11-01T22:44:34+05:30

perf: Array[struct] stored as struct-of-arrays (one native array per leaf), no per-element boxing

Files changed (5) hide show

README.md +1 -1
plum-examples/struct_arrays.plum +110 -0
plum-std/Array.plum +8 -1
plum-wasm-codegen/src/lib.rs +166 -0
plum-wasm-codegen/tests/codegen_tests.rs +84 -0

README.md CHANGED Viewed

@@ -418,7 +418,7 @@ u2 := u
 u2.age = 4         # u.age is now 4: a record is a heap object, shared on assignment
 ```
-A `struct` has no generics; its fields are only `Int`, `Float`, `Bool` or other structs, and a struct can't contain itself. Values are copied on assignment and when passed, and are boxed inside `T?` and other generic slots. <!-- arrays-of-structs note --> A `record` may have any field types and may be generic (`record Pair[K, V](key: K, val: V)`). Methods and `match` work as for any enum. See [`plum-examples/values.plum`](plum-examples/values.plum).
+A `struct` has no generics; its fields are only `Int`, `Float`, `Bool` or other structs, and a struct can't contain itself. Values are copied on assignment and when passed, and are boxed inside `T?` and other generic slots. Arrays of structs (`Array[Vec2]`, and so `List[Vec2]` and `Grid[Tile]`) are stored field by field, one native array per field, with no per-element allocation. A `record` may have any field types and may be generic (`record Pair[K, V](key: K, val: V)`). Methods and `match` work as for any enum. See [`plum-examples/values.plum`](plum-examples/values.plum).
 ### Enums

plum-examples/struct_arrays.plum ADDED Viewed

@@ -0,0 +1,110 @@
+# Arrays of structs are stored field by field (struct-of-arrays): `Array[Vec2]`
+# is one object holding an `f64` array for `x` and one for `y`, so `get`/`set`
+# allocate nothing per element. `List`, `Grid` and friends get this for free.
+module struct_arrays
+import std/Str
+import std/Int
+import std/Float
+import std/Array
+import std/List
+import std/Grid
+struct Vec2(x: Float, y: Float)
+struct Rect(pos: Vec2, size: Vec2) =
+  fun area(self) -> Float =
+    self.size.x * self.size.y
+struct Tile(id: Int, solid: Bool, weight: Float)
+record World(points: List[Vec2], name: Str)
+test "List[Vec2] push/get/set round-trips across growth"
+  l := List[Vec2]()
+  for i := range 100
+    l.push(Vec2(x: Float(i), y: Float(i) * 2.0))
+  assert l.length() == 100
+  v := l.get(37)!
+  assert v.x == 37.0
+  assert v.y == 74.0
+  l.set(37, Vec2(x: v.x + 1.0, y: v.y))
+  assert l.get(37)!.x == 38.0
+  assert l.get(37)!.y == 74.0
+  assert l.get(36)!.x == 36.0
+  assert l.get(99)!.y == 198.0
+test "nested struct (Rect of Vec2s) in an Array"
+  a := Array[Rect]()
+  a = a.push(Rect(pos: Vec2(x: 1.0, y: 2.0), size: Vec2(x: 3.0, y: 4.0)))
+  a = a.push(Rect(pos: Vec2(x: 5.0, y: 6.0), size: Vec2(x: 7.0, y: 8.0)))
+  assert a.length() == 2
+  r := a.get(1)
+  assert r.pos.x == 5.0
+  assert r.pos.y == 6.0
+  assert r.size.x == 7.0
+  assert r.size.y == 8.0
+  a.set(0, Rect(pos: r.size, size: r.pos))
+  assert a.get(0).pos.y == 8.0
+  assert a.get(0).size.x == 5.0
+  assert a.get(0).area() == 30.0
+test "struct with Int, Bool and Float leaves"
+  a := Array[Tile]()
+  a = a.push(Tile(id: 7, solid: true, weight: 1.5))
+  a = a.push(Tile(id: 9, solid: false, weight: 2.5))
+  assert a.get(0).id == 7
+  assert a.get(0).solid
+  assert a.get(0).weight == 1.5
+  assert a.get(1).id == 9
+  assert !a.get(1).solid
+  assert a.get(1).weight == 2.5
+  b := a.resize(4)
+  assert b.length() == 4
+  assert b.get(1).id == 9
+  assert b.get(3).id == 0
+  assert !b.get(3).solid
+test "copy semantics: a value read from the array is a copy until set"
+  l := List[Vec2]()
+  l.push(Vec2(x: 1.0, y: 1.0))
+  v := l.get(0)!
+  v = Vec2(x: 99.0, y: 99.0)
+  assert l.get(0)!.x == 1.0
+  w := l.get(0)!
+  l.set(0, Vec2(x: 5.0, y: 5.0))
+  assert w.x == 1.0
+  assert l.get(0)!.x == 5.0
+  assert v.x == 99.0
+test "for x := range over Array[Vec2]"
+  a := Array[Vec2]().push(Vec2(x: 1.0, y: 10.0)).push(Vec2(x: 2.0, y: 20.0)).push(Vec2(x: 3.0, y: 30.0))
+  sx := 0.0
+  sy := 0.0
+  for v := range a
+    sx = sx + v.x
+    sy = sy + v.y
+  assert sx == 6.0
+  assert sy == 60.0
+test "Array.filled with a struct"
+  a := Array.filled(5, Vec2(x: 2.0, y: 3.0))
+  assert a.length() == 5
+  assert a.get(4).y == 3.0
+test "Grid[Tile] get/set"
+  g := Grid.filled(3, 2, Tile(id: 1, solid: false, weight: 0.5))
+  g.set(2, 1, Tile(id: 42, solid: true, weight: 9.0))
+  assert g.get(2, 1).id == 42
+  assert g.get(2, 1).solid
+  assert g.get(0, 0).id == 1
+  assert g.get(1, 1).weight == 0.5
+test "a List[Vec2] inside a record field"
+  w := World(points: List[Vec2](), name: "w")
+  w.points.push(Vec2(x: 1.0, y: 2.0))
+  w.points.push(Vec2(x: 3.0, y: 4.0))
+  assert w.points.length() == 2
+  w.points.set(1, Vec2(x: 30.0, y: 40.0))
+  assert w.points.get(1)!.x == 30.0
+  assert w.points.get(0)!.y == 2.0

plum-std/Array.plum CHANGED Viewed

@@ -11,7 +11,14 @@ import std/Str
 # `array<mut ref null T>` (all reference types of the same wasm type share one
 # array type). `get`/`set`/`push`/`resize`/`length`/`filled` on the value
 # arrays are plain `array.get`/`array.set`/`array.copy` on the raw elements —
+# nothing is boxed or allocated per element. `Array[S]` for a `struct` S is
+# stored struct-of-arrays: ONE GC struct holding one native array per leaf of
+# S (`Array[Vec2]` is `{xs: array<mut f64>, ys: array<mut f64>}`, a nested
+# `Rect(pos: Vec2, size: Vec2)` has four f64 arrays, Bool leaves are i32
+# arrays). `get` reads each leaf array and leaves the flattened value on the
+# stack, `set` writes each leaf, `push`/`resize` allocate the leaf arrays
+# together: no per-element allocation. (Records and other reference types
-# nothing is boxed or allocated per element. `init`/`get`/`set`/`length`/
+# stay arrays of references.) `init`/`get`/`set`/`length`/
 # `push`/`resize` are compiler intrinsics (see `compileIntrinsicFnBody`) —
 # there's no way to express raw array allocation/indexing in Plum source itself.
 # `List[T]` is built on this.

plum-wasm-codegen/src/lib.rs CHANGED Viewed

@@ -773,6 +773,12 @@ fn nullableErr(ty: &PlumType) -> Option<&PlumType> {
     plum_checker::nullableErrPayload(ty).filter(|p| !isValueTy(p))
 }
+/// `Array[S]` for a `struct` S (with at least one leaf) is stored field by
+/// field: one GC struct holding one native array per leaf.
+fn isSoaElem(ty: &PlumType) -> bool {
+    matches!(ty, PlumType::TNamed(_)) && valueFieldsOf(ty).is_some() && leafCount(ty) > 0
+}
 fn isValueTy(ty: &PlumType) -> bool {
     valueFieldsOf(ty).is_some()
 }
@@ -935,6 +941,9 @@ pub struct GcTypeRegistry {
     /// harmlessly never read as such) until/unless the program actually
     /// instantiates `Array` at least once.
     pub array_type_idx: u32,
+    /// Leaf wasm value type -> native `array<mut leaf>` type index; used by the
+    /// struct-of-arrays layout of `Array[S]` for a `struct` S.
+    pub leaf_array_idx: HashMap<ValType, u32>,
     /// Helper `(arr: array<i8>) -> Str` building `Str{arr}`; `None` when the program has no `Str`.
     pub mk_str_fn: Option<u32>,
     /// `!T` (keyed by `T`) -> its heap box struct `{leaves of T..., code: i32}`.
@@ -1063,6 +1072,7 @@ fn buildGcTypeRegistry(
         EnumSuper(PlumType),
         Variant(PlumType, String),
         ArrayRef(ValType),
+        ArraySoa(Vec<ValType>),
         ErrBox(PlumType),
     }
     let mut slots: Vec<Slot> = vec![Slot::Str];
@@ -1079,6 +1089,7 @@ fn buildGcTypeRegistry(
         closure_type_idx: 0,
         variadic_array_type_idx: HashMap::new(),
         array_type_idx: 0,
+        leaf_array_idx: HashMap::new(),
         mk_str_fn: None,
         err_box: HashMap::new(),
     };
@@ -1152,6 +1163,23 @@ fn buildGcTypeRegistry(
     let mut by_vt: HashMap<ValType, u32> = HashMap::new();
     for a in &arrays {
         let PlumType::TApp(_, args) = a else { continue };
+        if isSoaElem(&args[0]) {
+            // Struct-of-arrays: one native array per leaf, held by one struct.
+            let leaves = flatValtypes(&args[0], &reg);
+            for vt in &leaves {
+                let idx = *by_vt.entry(*vt).or_insert_with(|| {
+                    let idx = slots.len() as u32;
+                    slots.push(Slot::ArrayRef(*vt));
+                    idx
+                });
+                reg.leaf_array_idx.insert(*vt, idx);
+            }
+            let idx = slots.len() as u32;
+            slots.push(Slot::ArraySoa(leaves));
+            reg.app_super.insert(a.clone(), idx);
+            reg.app_class.insert(a.clone(), idx);
+            continue;
+        }
         let vt = plumTypeToGcValtype(&args[0], &reg);
         let idx = *by_vt.entry(vt).or_insert_with(|| {
             let idx = slots.len() as u32;
@@ -1258,6 +1286,23 @@ fn buildGcTypeRegistry(
                     },
                 }
             }
+            Slot::ArraySoa(leaves) => SubType {
+                is_final: true,
+                supertype_idx: None,
+                composite_type: CompositeType {
+                    inner: CompositeInnerType::Struct(StructType {
+                        fields: leaves
+                            .iter()
+                            .map(|vt| FieldType {
+                                element_type: StorageType::Val(gcRef(reg.leaf_array_idx[vt])),
+                                mutable: false,
+                            })
+                            .collect::<Vec<_>>()
+                            .into(),
+                    }),
+                    shared: false,
+                },
+            },
             Slot::ArrayRef(vt) => SubType {
                 is_final: true,
                 supertype_idx: None,
@@ -2790,6 +2835,9 @@ fn compileArrayIntrinsicFnBody(f: &ast::Fn, subst: &Subst) -> Option<Vec<u8>> {
     let array_elem = elem.clone();
     let array_ty = PlumType::TApp("Array".to_string(), vec![elem]);
     let array_type_idx = withGcTypes(|r| r.superIdx(&array_ty))?;
+    if isSoaElem(&array_elem) {
+        return compileSoaArrayIntrinsic(f.name.as_str(), &array_elem, array_type_idx);
+    }
     match f.name.as_str() {
         // init() -> Array[T] — always starts empty; see `push` for how a
         // specific length is actually built up.
@@ -2933,6 +2981,124 @@ fn compileArrayIntrinsicFnBody(f: &ast::Fn, subst: &Subst) -> Option<Vec<u8>> {
     }
 }
+/// `Array[S]` (S a `struct`) intrinsics for the struct-of-arrays layout: the array
+/// is one GC struct whose field `k` is the native array of leaf `k`. `get`/`set`
+/// read/write each leaf array directly (no allocation, no box).
+fn compileSoaArrayIntrinsic(name: &str, elem: &PlumType, soa_idx: u32) -> Option<Vec<u8>> {
+    let leaves = withGcTypes(|r| flatValtypes(elem, r));
+    let leaf_arrs: Vec<u32> = withGcTypes(|r| leaves.iter().map(|vt| r.leaf_array_idx[vt]).collect());
+    let n = leaves.len() as u32;
+    let mut body = Vec::new();
+    // Locals: declared groups, one entry per local (all single).
+    let declare = |body: &mut Vec<u8>, tys: &[ValType]| {
+        body.extend(encodeLeb128U32(tys.len() as u32));
+        for t in tys {
+            body.extend(encodeLeb128U32(1));
+            t.encode(body);
+        }
+    };
+    // Reads leaf array `k` of the soa struct held in local `src`.
+    let leaf_arr = |body: &mut Vec<u8>, src: u32, k: u32| {
+        Instruction::LocalGet(src).encode(body);
+        Instruction::StructGet { struct_type_index: soa_idx, field_index: k }.encode(body);
+    };
+    match name {
+        "init" => {
+            body.push(0);
+            for a in &leaf_arrs {
+                Instruction::I32Const(0).encode(&mut body);
+                Instruction::ArrayNewDefault(*a).encode(&mut body);
+            }
+            Instruction::StructNew(soa_idx).encode(&mut body);
+        }
+        "length" => {
+            body.push(0);
+            leaf_arr(&mut body, 0, 0);
+            Instruction::ArrayLen.encode(&mut body);
+            Instruction::I64ExtendI32U.encode(&mut body);
+        }
+        "get" => {
+            body.push(0);
+            for k in 0..n {
+                leaf_arr(&mut body, 0, k);
+                Instruction::LocalGet(1).encode(&mut body);
+                Instruction::I32WrapI64.encode(&mut body);
+                Instruction::ArrayGet(leaf_arrs[k as usize]).encode(&mut body);
+            }
+        }
+        "set" => {
+            body.push(0);
+            for k in 0..n {
+                leaf_arr(&mut body, 0, k);
+                Instruction::LocalGet(1).encode(&mut body);
+                Instruction::I32WrapI64.encode(&mut body);
+                Instruction::LocalGet(2 + k).encode(&mut body);
+                Instruction::ArraySet(leaf_arrs[k as usize]).encode(&mut body);
+            }
+        }
+        "push" | "resize" => {
+            let push = name == "push";
+            // params: self=0, then v leaves (push) or n (resize, one i64 at 1).
+            let nparams = if push { 1 + n } else { 2 };
+            let old_len = nparams;
+            let new_len = nparams + 1;
+            let copy_len = nparams + 2;
+            let first_arr = nparams + 3;
+            let mut tys = vec![ValType::I32, ValType::I32, ValType::I32];
+            tys.extend(leaf_arrs.iter().map(|a| gcRef(*a)));
+            declare(&mut body, &tys);
+            leaf_arr(&mut body, 0, 0);
+            Instruction::ArrayLen.encode(&mut body);
+            Instruction::LocalSet(old_len).encode(&mut body);
+            if push {
+                Instruction::LocalGet(old_len).encode(&mut body);
+                Instruction::I32Const(1).encode(&mut body);
+                Instruction::I32Add.encode(&mut body);
+            } else {
+                Instruction::LocalGet(1).encode(&mut body);
+                Instruction::I32WrapI64.encode(&mut body);
+            }
+            Instruction::LocalSet(new_len).encode(&mut body);
+            if push {
+                Instruction::LocalGet(old_len).encode(&mut body);
+            } else {
+                Instruction::LocalGet(old_len).encode(&mut body);
+                Instruction::LocalGet(new_len).encode(&mut body);
+                Instruction::LocalGet(old_len).encode(&mut body);
+                Instruction::LocalGet(new_len).encode(&mut body);
+                Instruction::I32LtU.encode(&mut body);
+                Instruction::Select.encode(&mut body);
+            }
+            Instruction::LocalSet(copy_len).encode(&mut body);
+            for k in 0..n {
+                let a = leaf_arrs[k as usize];
+                Instruction::LocalGet(new_len).encode(&mut body);
+                Instruction::ArrayNewDefault(a).encode(&mut body);
+                Instruction::LocalSet(first_arr + k).encode(&mut body);
+                Instruction::LocalGet(first_arr + k).encode(&mut body);
+                Instruction::I32Const(0).encode(&mut body);
+                leaf_arr(&mut body, 0, k);
+                Instruction::I32Const(0).encode(&mut body);
+                Instruction::LocalGet(copy_len).encode(&mut body);
+                Instruction::ArrayCopy { array_type_index_dst: a, array_type_index_src: a }.encode(&mut body);
+                if push {
+                    Instruction::LocalGet(first_arr + k).encode(&mut body);
+                    Instruction::LocalGet(old_len).encode(&mut body);
+                    Instruction::LocalGet(1 + k).encode(&mut body);
+                    Instruction::ArraySet(a).encode(&mut body);
+                }
+            }
+            for k in 0..n {
+                Instruction::LocalGet(first_arr + k).encode(&mut body);
+            }
+            Instruction::StructNew(soa_idx).encode(&mut body);
+        }
+        _ => return None,
+    }
+    Instruction::End.encode(&mut body);
+    Some(body)
+}
 /// The `PlumType` of a declared parameter, including `fn(...)`-typed params as `TFun`;
 /// a single-letter generic name is a `TParam`.
 /// The enum type (`TNamed`/`TApp`) a variant-constructing expression produces.

plum-wasm-codegen/tests/codegen_tests.rs CHANGED Viewed

@@ -3267,3 +3267,87 @@ fn bufferToStrLengthExactAfterDoubling() {
     let src = "import std/Str\nimport std/Buffer\nimport std/Int\nimport std/Float\n\nfun main() -> Int =\n  b := Buffer()\n  i := 0\n  while i < 37\n    b.write(\"abc\")\n    i = i + 1\n  b.toStr().length() * 1000 + b.length()\n";
     assert_eq!(runWithCrash("bufexact", src).0.unwrap(), 111111);
 }
+// ---- struct-of-arrays layout for Array[struct] ----
+#[test]
+fn array_of_struct_is_struct_of_f64_arrays_and_never_boxes() {
+    let src = "\
+import std/Str
+import std/Int
+import std/Float
+import std/Array
+struct Vec2(x: Float, y: Float)
+fun main() -> Float =
+  a := Array[Vec2]().push(Vec2(x: 1.0, y: 2.0)).push(Vec2(x: 3.0, y: 4.0))
+  v := a.get(1)
+  a.set(0, Vec2(x: v.x + 1.0, y: v.y))
+  b := a.resize(5)
+  a.get(0).x + b.get(1).y
+";
+    let dir = std::env::temp_dir().join(format!("plum_soa_{}", std::process::id()));
+    std::fs::create_dir_all(&dir).unwrap();
+    let path = dir.join("main.plum");
+    std::fs::write(&path, src).unwrap();
+    let source = plum_core::loadAndMerge(&path, &repoRoot()).expect("load");
+    plum_checker::checkSource(&source).expect("check");
+    let bytes = compileSource(&source).expect("compile failed");
+    let _ = std::fs::remove_dir_all(&dir);
+    wasmparser::validate(&bytes).expect("valid wasm");
+    use wasmparser::{CompositeInnerType, HeapType, Operator, StorageType, ValType};
+    let mut types: Vec<CompositeInnerType> = Vec::new();
+    let mut struct_news: Vec<u32> = Vec::new();
+    for payload in wasmparser::Parser::new(0).parse_all(&bytes) {
+        match payload.unwrap() {
+            wasmparser::Payload::TypeSection(s) => {
+                for g in s {
+                    for t in g.unwrap().types() {
+                        types.push(t.composite_type.inner.clone());
+                    }
+                }
+            }
+            wasmparser::Payload::CodeSectionEntry(body) => {
+                let mut r = body.get_operators_reader().unwrap();
+                while !r.eof() {
+                    if let Operator::StructNew { struct_type_index } = r.read().unwrap() {
+                        struct_news.push(struct_type_index);
+                    }
+                }
+            }
+            _ => {}
+        }
+    }
+    let f64_array = |i: u32| match &types[i as usize] {
+        CompositeInnerType::Array(a) => a.0.mutable && matches!(a.0.element_type, StorageType::Val(ValType::F64)),
+        _ => false,
+    };
+    let soa: Vec<usize> = (0..types.len())
+        .filter(|&i| match &types[i] {
+            CompositeInnerType::Struct(s) => {
+                s.fields.len() == 2
+                    && s.fields.iter().all(|f| match f.element_type {
+                        StorageType::Val(ValType::Ref(r)) => match r.heap_type() {
+                            HeapType::Concrete(u) => f64_array(u.as_module_index().unwrap()),
+                            _ => false,
+                        },
+                        _ => false,
+                    })
+            }
+            _ => false,
+        })
+        .collect();
+    assert_eq!(soa.len(), 1, "expected exactly one {{f64[], f64[]}} struct");
+    // The per-element box of Vec2 is `{f64, f64}`: nothing may allocate it.
+    for idx in &struct_news {
+        if let CompositeInnerType::Struct(s) = &types[*idx as usize] {
+            let is_box = s.fields.len() == 2
+                && s.fields.iter().all(|f| matches!(f.element_type, StorageType::Val(ValType::F64)));
+            assert!(!is_box, "struct.new of a boxed Vec2");
+        }
+    }
+    assert!(struct_news.contains(&(soa[0] as u32)));
+    assert_eq!(runMerged::<f64>("soa", src), 8.0);
+}