Skip to content

perf: array-part constructor representation {tag, v0, v1} (#185) - #256

Merged
Unisay merged 5 commits into
mainfrom
issue-185/array-ctor-representation
Jul 12, 2026
Merged

perf: array-part constructor representation {tag, v0, v1} (#185)#256
Unisay merged 5 commits into
mainfrom
issue-185/array-ctor-representation

Conversation

@Unisay

@Unisay Unisay commented Jul 12, 2026

Copy link
Copy Markdown
Collaborator

Closes #185.

What

A data-constructor value now compiles to a positional Lua table: the Module∷Type.Ctor tag 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 to e[1], field reads to e[i + 2] for sums and e[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). On bench/micro/ctor_match.lua this 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-only DataArgumentByIndex node via a new TakeCtorField step, which also makes the IR honestly representation-abstract. The node gains the constructor's AlgebraicType, 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 the fieldIndex label-to-position helper. The DataArgumentByIndex folds 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. sinkProjectionIntoLet sinks field reads through a Let the 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] = v keyed 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..N reads, hand-built constructor tables, and generic table walkers over data values: the in-repo golden FFI files, the pinned .spago package-set sources, all fork clones (prelude Show/Eq/Ord FFI included), and the .purs sources for unsafeCoerce-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), and show/generic constructor names come from compile-time reflectSymbol literals, 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.lua and 20 golden.ir move, and every eval/golden.txt oracle 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.json inputs are untouched. ./bench/ci counter 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.

Unisay added 4 commits July 12, 2026 17:48
)

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
Unisay requested a review from Copilot July 12, 2026 16:06
@Unisay Unisay self-assigned this Jul 12, 2026
@Unisay
Unisay marked this pull request as ready for review July 12, 2026 16:07
Comment thread bench/micro/ctor_match.lua Outdated

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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 ReflectCtor and DataArgumentByIndex to 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 DataArgumentByIndex via a new TakeCtorField step, and thread the constructor’s AlgebraicType into DataArgumentByIndex.
  • 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.
@Unisay
Unisay merged commit 344f944 into main Jul 12, 2026
2 checks passed
@Unisay
Unisay deleted the issue-185/array-ctor-representation branch July 12, 2026 16:26
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Array-part constructor representation: {tag, v0, v1} instead of hash-part {$ctor=…, value0=…}

2 participants