Skip to content

Investigate unboxed quotient carriers for noncanonical field arithmetic #393

Open

Description

@mitschabaude-bot

Why a quotient would be an ideal carrier

A field element is a residue class, not a particular integer encoding. For Goldilocks, two UInt64 words can represent the same field element: 0 and p, for example. Arithmetic only needs to preserve the residue; forcing every intermediate result into [0, p) is extra work.

Georgios’s Goldilocks PR #392 makes this cost concrete. Its widening multiplication compiles to one native mul, but the public multiplication still performs a final canonical subtraction. Plonky3 allows noncanonical words and skips that step. Georgios attributes roughly 0.7 ns of the remaining multiplication gap to canonicalization.

A quotient of UInt64 by equality modulo p would express exactly the abstraction we want:

  • Ordinary field equality: 0 and p are equal as quotient elements. The field laws hold in Lean’s propositional equality, so existing generic code and proofs using [Field F] can work unchanged.
  • Cheap representatives: multiplication can return any word with the correct residue, without paying for a unique encoding after every operation. The representation invariant is simply that the result fits in a machine word.
  • Optimization through generic code: the benefit could apply to chains assembled by polynomial algorithms and other callers of the Field API. Today, we get it inside specially written inversion/exponentiation loops that explicitly carry noncanonical words; returning through the canonical public carrier reintroduces normalization.
  • Canonicalization at the boundaries that need it: serialization or conversion to a canonical integer can normalize once. Equality tests can compare residues. A unique byte encoding does not require every arithmetic intermediate to have a unique word encoding.

A plain word wrapper with a custom BEq cannot provide the first property: Boolean equality does not change Lean’s propositional equality. A canonical subtype provides a lawful Field and an efficient unboxed carrier, but requires normalization after each public operation. A quotient is the natural way to combine the mathematical API of the subtype with the arithmetic freedom of noncanonical words.

Crucially, quotienting need not perform any normalization at runtime. Constructing a quotient can retain the supplied representative; a well-defined operation can work directly on representatives, with its proof establishing that the result is independent of the choice. Those proofs are erased. Ideally, quotient construction and elimination would therefore preserve the same raw-word runtime representation as the underlying arithmetic.

What currently prevents this

Georgios reports in #392 that he built and proved a quotient carrier, but it allocated a boxed value per multiplication and was slower. The current implementation instead uses noncanonical words inside inversion/exponentiation chains and canonicalizes at the boundary.

This makes unboxed quotients an interesting performance opportunity: the missing piece appears to be preserving an efficient runtime representation, rather than finding a suitable mathematical abstraction.

Compiler insight to investigate

Why can the canonical subtype be cheap while the quotient boxes its representative?

Inspection of Lean 4.34.0 suggests a distinction between erasing a wrapper and preserving an unboxed runtime type:

  • A subtype has one computationally relevant field after proof erasure. Lean’s trivial-structure optimization can replace it with that field’s runtime type, so a subtype of UInt64 can use a raw machine word in specialized code.
  • Quot is a kernel primitive, not an ordinary single-constructor structure handled by that optimization.
  • The compiler does eliminate Quot.mk itself. Thus the suspected cost is not an extra quotient container, but boxing the underlying UInt64 at quotient-typed boundaries.

Relevant compiler sources:

This is a proposed explanation for the reported allocation, not yet a demonstrated compiler fix. Inlining, specialization, and the exact quotient API may affect where boxing survives.

Possible follow-up

  • Recover the quotient experiment from perf(fields): faster Goldilocks, inlined 32-bit Montgomery add #392, or build a minimal comparison of UInt64, a subtype of UInt64, and a quotient of UInt64 with equivalent arithmetic.
  • Inspect generated code to locate boxing/unboxing and allocations, including across function boundaries and in specialized loops.
  • Check whether existing Lean compilation mechanisms can preserve the unboxed representation without custom C externs.
  • If the limitation is in the compiler, reduce it to an upstream Lean issue: can a quotient inherit its representative’s runtime representation while preserving the existing semantics and polymorphic calling conventions?
  • If successful, remeasure a proved noncanonical Goldilocks Field against the current canonical implementation and Plonky3 using matched workloads.

The opportunity is to retain a normal verified Field API while avoiding per-operation canonicalization. Removing quotient boxing would make that worth testing; it does not by itself guarantee a speedup.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions