perf: array-part constructor representation {tag, v0, v1} (#185) - #256
Merged
Conversation
) State the new representation contract red-first: a constructor value is a positional table — sum types {tag, v0, …} with the ctorId string in slot 1, product types {v0, …} with no tag — read back as e[1] for the tag and e[i + offset] for fields (offset 2 for sums, 1 for products). DataArgumentByIndex gains the AlgebraicType the lowering needs to pick the slot offset (compile-ready skeleton; consumers keep the old behavior until the flip). The Optimizer folds are pinned to require a matching algebraic type — a mismatched (ill-typed) read addresses a different runtime slot than the fold would return — and sinkProjectionIntoLet is pinned to sink constructor field reads the way it sinks record projections. The ObjectProp-on-known-ctor fold specs (#213) are deleted — their behaviors are fully twinned by the DataArgumentByIndex specs — and the through-let (#214), worker-reference (#180/#232) and Gen fixtures are migrated from the ObjectProp "valueN" convention to DataArgumentByIndex, which the matcher is about to emit.
) A constructor value lowers to a positional table — the ctorId string in slot 1 for sum types, fields in the slots after it; product types carry fields from slot 1 with no tag. ReflectCtor lowers to e[1] and a field read to e[i + offset], the offset picked by the algebraic type the node now carries. Positional rows pre-size the table's array part, where the old {["$ctor"] = …, value0 = …} layout hashed two string keys on every allocation and every read: ~1.4x faster on the allocate-and-match microbenchmark (PUC 5.1), and no hash part allocated. The pattern matcher now emits ctor-field reads as DataArgumentByIndex (a new TakeCtorField step) instead of ObjectProp "valueN" — record projections and constructor field reads are different operations under a positional layout, and the IR now says so. The ObjectProp-on-known- ctor fold branches (reduceKnownConstructor, propagateKnownCtorThroughLet, reduceKnownCtorRefRead) are dead with nothing emitting the shape and are removed along with the fieldIndex label-to-position helper; the DataArgumentByIndex folds instead require the read's algebraic type to match the constructor's, since the type decides the runtime slot offset. sinkProjectionIntoLet sinks field reads through a Let the way it sinks record projections, keeping the #180/#232 fold cascades intact. The representation is FFI-visible; the package-set audit found the entire published FFI surface constructor-abstract (changelog fragment records the break).
…ion (#185) 23 golden.lua and 20 golden.ir move: constructor tables lose their hash rows for positional ones ({"Data.Maybe∷Maybe.Just", x}; products {x, y} with no tag), tag reads become e[1], field reads e[2]…, and the IR shows the matcher's field reads as DataArgumentByIndex instead of ObjectProp "valueN". The output is net smaller. Every eval/golden.txt oracle is byte-identical — the flip is representation-only — and corefn.json inputs are untouched.
ctor_match gains three variants: the superseded hash-part layout as the baseline, the array-part layout with the string tag the compiler now emits, and the int-tag variant kept as the recorded anti-result (an interned tag string compares by pointer, so the integer buys nothing — re-measured: it is not faster). dict_compare's hand-modelled Ordering values follow the flip. Counter goldens are byte-identical — the representation changes tables, not function prototypes or traces.
Unisay
commented
Jul 12, 2026
Contributor
There was a problem hiding this comment.
Pull request overview
This PR changes the PureScript data-constructor runtime representation emitted by the Lua backend from hash-part tables (e.g. {["$ctor"]=..., value0=...}) to positional (array-part) tables (e.g. { "M∷T.C", v0, v1 } for sum types; { v0, v1 } for product types). This is a core codegen/IR contract change aimed at reducing allocation and access overhead in Lua 5.1, while keeping tag strings stable.
Changes:
- Lower
ReflectCtorandDataArgumentByIndexto constant index reads (e[1],e[i+2]for sums,e[i+1]for products) and emit constructors as positional tables. - Make constructor field reads representation-abstract in the matcher by emitting
DataArgumentByIndexvia a newTakeCtorFieldstep, and thread the constructor’sAlgebraicTypeintoDataArgumentByIndex. - Update optimizer folds/tests/generators and regenerate affected golden outputs and microbench baselines.
Reviewed changes
Copilot reviewed 53 out of 53 changed files in this pull request and generated no comments.
Show a summary per file
| File | Description |
|---|---|
| lib/Language/PureScript/Backend/Lua.hs | Switch constructor emission to positional rows; lower tag/field reads to numeric indices. |
| lib/Language/PureScript/Backend/IR/Types.hs | Extend DataArgumentByIndex with AlgebraicType; update helpers/traversals/equality. |
| lib/Language/PureScript/Backend/IR/Optimizer.hs | Remove ObjectProp-on-ctor folds; add/adjust ctor-field folding rules with alg-type checks and let-sinking. |
| lib/Language/PureScript/Backend/IR.hs | Matcher now emits ctor field reads as DataArgumentByIndex via TakeCtorField. |
| test/Language/PureScript/Backend/Lua/Spec.hs | Add assertions for positional ctor layout and index-based tag/field lowering. |
| test/Language/PureScript/Backend/IR/Optimizer/Spec.hs | Update/extend optimizer specs for new DataArgumentByIndex shape and mismatch-decline behavior. |
| test/Language/PureScript/Backend/IR/Gen.hs | Update fuzz generators to carry/read AlgebraicType and exercise mismatch paths. |
| changelog.d/20260712_170000_unisay_array_ctor_repr.md | Document the (FFI-visible) constructor representation change. |
| bench/micro/dict_compare.lua | Update benchmark to match new Ordering constructor representation and tag reads. |
| bench/micro/ctor_match.lua | Update ctor microbench: keep old hash baseline, add current array layout, preserve int-tag variant. |
| test/ps/output/Golden.TailRecM2Shadow.Test/golden.lua | Regenerated golden Lua for positional ctor representation and index-based reads. |
| test/ps/output/Golden.TailRecM2Shadow.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.StringCodePoints.Test/golden.lua | Regenerated golden Lua for positional ctor representation and index-based reads. |
| test/ps/output/Golden.StringCodePoints.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.RecDataDefs.Test/golden.lua | Regenerated golden Lua for positional ctor representation. |
| test/ps/output/Golden.Primops.Test/golden.lua | Regenerated golden Lua for index-based tag reads. |
| test/ps/output/Golden.PatternMatching.Test2/golden.lua | Regenerated golden Lua for positional ctors and index-based field/tag reads. |
| test/ps/output/Golden.PatternMatching.Test2/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.PatternMatching.Test1/golden.lua | Regenerated golden Lua for positional ctors and index-based field/tag reads. |
| test/ps/output/Golden.PatternMatching.Test1/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.MaybeChainModule.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.MaybeChainModule.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.MaybeChain.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.MaybeChain.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.LongWriterBind.Test/golden.lua | Regenerated golden Lua for positional product ctor representation and index-based reads. |
| test/ps/output/Golden.LongWriterBind.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.LongStateBind.Test/golden.lua | Regenerated golden Lua for positional product ctor representation and index-based reads. |
| test/ps/output/Golden.LongStateBind.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.LongStackBind.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.LongStackBind.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.LongMaybeBindModule.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.LongMaybeBindModule.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.LongMaybeBind.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.LongMaybeBind.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.LongExceptBind.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.LongExceptBind.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.LongEitherBind.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.LongEitherBind.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.LongBindFlipped.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.LongBindFlipped.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.LongApplyChain.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.LongApplyChain.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.GenericEqTwoTypes.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.GenericEqTwoTypes.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.DirectiveArity.Test/golden.lua | Regenerated golden Lua for positional product ctor representation and index-based reads. |
| test/ps/output/Golden.DirectiveArity.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.DerivedFunctor.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.DerivedFunctor.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.DataDeclarations.Test1/golden.lua | Regenerated golden Lua for positional ctors and product fields. |
| test/ps/output/Golden.CaseStatements.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.CaseStatements.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
| test/ps/output/Golden.BugListGenericEq.Test/golden.lua | Regenerated golden Lua for positional ctors and index-based reads. |
| test/ps/output/Golden.BugListGenericEq.Test/golden.ir | Regenerated golden IR to use DataArgumentByIndex … AlgebraicType …. |
The hash-vs-array comparison it recorded motivated the representation flip and is now acted on; the numbers and the int-tag anti-result live in the issue and the PR record. It gated nothing (bench/ci counts FNEW and traces of the linked macro artifacts only), and as a hand-model of the encoding it could only drift from the real output silently. dict_compare stays: dictionary dispatch against the native operator is still an open question.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Closes #185.
What
A data-constructor value now compiles to a positional Lua table: the
Module∷Type.Ctortag string in slot 1 (sum types only) and the fields in the slots after it. Product types carry their fields from slot 1 with no tag, as before. The previous layout was a hash-part table,{["$ctor"] = "Data.Maybe∷Maybe.Just", value0 = x}, which hashed two string keys on every allocation and on every tag or field read. Tag reads now lower toe[1], field reads toe[i + 2]for sums ande[i + 1]for products. The tag stays the same interned string: the issue's measurements showed the win comes from the positional layout, not the tag type, and re-measuring confirms it (the int-tag variant is slightly slower than the string tag, not faster). Onbench/micro/ctor_match.luathis machine shows a 0.124s median for hash vs 0.108s for array under PUC 5.1 (the issue's original measurement saw 1.4x on its hardware) and a 2x gap under LuaJIT. The generated output is also net smaller: the 43 regenerated goldens lose 700 lines and gain 493.How
The issue expected a pure lowering change, but that premise didn't survive contact with the matcher: constructor field reads were emitted as
ObjectProp scrutinee (PropName "valueN"), the same node genuine record access uses, so the lowering alone couldn't be re-pointed without breaking records. The matcher now emits the previously test-onlyDataArgumentByIndexnode via a newTakeCtorFieldstep, which also makes the IR honestly representation-abstract. The node gains the constructor'sAlgebraicType, because the lowering needs sum-vs-product to pick the slot offset and has no type environment to ask at that stage.In the optimizer, the
ObjectProp-on-known-constructor fold branches (reduceKnownConstructor,propagateKnownCtorThroughLet,reduceKnownCtorRefRead) died with nothing emitting that shape and are removed together with thefieldIndexlabel-to-position helper. TheDataArgumentByIndexfolds instead require the read's algebraic type to match the constructor's: the type decides the runtime slot offset, so folding a mismatched read (necessarily ill-typed, but the fuzz suites generate such shapes) would return a different value than the compiled slot access reads.sinkProjectionIntoLetsinks field reads through aLetthe way it sinks record projections, so the #180/#232 fold cascades stay intact.The constructor table keeps positional rows on purpose: only a positional constructor pre-sizes the table's array part in PUC 5.1 (
[i] = vkeyed rows go through the hash path this change exists to avoid), and rows are always plain parameter names, which are single-valued in Lua even when nil, so a row can never splice multiple values.FFI audit (checklist items 1 and 4)
The representation is FFI-visible, so before touching the compiler I grepped every surface for
$ctor/value0..Nreads, hand-built constructor tables, and generic table walkers over data values: the in-repo golden FFI files, the pinned.spagopackage-set sources, all fork clones (prelude Show/Eq/Ord FFI included), and the.purssources forunsafeCoerce-to-record views. No representation-dependent code exists anywhere. The entire published FFI surface is constructor-abstract (constructors arrive as function parameters, in the_codePointAt(just)(nothing)style), andshow/generic constructor names come from compile-timereflectSymbolliterals, so the tag string never escapes into program output. No fork fixes and no package-set bump are needed; the changelog fragment records the break for third-party FFI authors.Verification
The representation specs went in red-first (constructor table shapes, tag and field slot offsets, the algTy-mismatch decline, the field-read sink) and flipped green with the implementation. The full suite passes at 813 examples with the structural churn accepted: 23
golden.luaand 20golden.irmove, and everyeval/golden.txtoracle is byte-identical, which is the runtime-output proof that the flip changes the representation only and nothing depended on the old layout (checklist item 3).corefn.jsoninputs are untouched../bench/cicounter goldens (FNEW census and trace reports) are byte-identical too, so the change alters tables, not function prototypes or trace formation. The micro benchmarks are re-modelled so the array-part encoding is the measured current variant, with the hash layout kept as the baseline and the int-tag anti-result preserved.