vx-lang / vx-lang/Vx

Content-addressed generic identity: remove the interning barrier rather than make it cheap

Open
#307 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement parallel-frontend
Dominant language
Rust
Stars
14
Forks
2
Avg merge
12h 42m
Merged PRs (30d)
61

Description

Implemented on parallel-frontend-eval as --intern-mode=content (a1b01f08). Filed so the design
and its result have a record independent of the branch, which is never merged.

The problem

mint_deferred_generic sets the deferred bit unconditionally, so reconciliation is O(occurrences),
not O(distinct instantiations). Two things make that worse than it sounds:

  • LocalWorkerState is constructed per function, not per thread — verified: 32 local arenas for
    32 functions on 8 threads. So each function starts with an empty arena and the same instantiation
    in two functions of one module cannot be recognised as a repeat even in principle. There is no
    thread-local amortisation anywhere. (paper.tex §"The zero-lock session" describes one
    LocalWorkerState per worker, which is not what the code does.)
  • GlobalSession::generics_arena is never consulted at mint time. It is produced by reconciliation
    and handed to _epoch_2_session, which is read only by a debug verifier. So an instantiation can
    never be recognised as already-canonical, even though looking it up would be a read of immutable
    data requiring no lock.

The design

Word 2 becomes an FNV-1a digest of the argument GIDs, computed locally:

scale<f32> = [h(math), h(scale), ESC|D[f32], IS_GENERIC_INST|GENERIC_DIGEST]

Two workers reaching the same instantiation agree at mint time. No arena entry, no deferred bit,
nothing to reconcile, nothing to patch.

Keyed on arguments alone, mirroring intern_generic, so Pair<i32> and Box<i32> share a digest
and stay distinct GIDs via words 0–1 — the sharing the arena gave, without the arena.

The digest gets its own word-3 bit (40, previously free) rather than reusing an existing state.
"IS_GENERIC_INST set, LOCAL_DEFERRED clear" already means post-patch global index; overloading it
would recreate hiraditya/Vx.1#193 exactly.

Measured — this is not a speedup

64 modules × 16 fns, 16,384 occurrences over 6 distinct keys (the cell where deferred is
structurally worst), release, 7 reps, on a 10-core M4.

threads sp(deferred) sp(locked) sp(content) ms def/lock/cont
1 1.00 1.00 1.00 74.5 / 73.8 / 73.4
4 2.26 2.34 2.28 33.0 / 31.5 / 32.2
8 2.72 2.78 2.73 27.4 / 26.6 / 26.9

Phases at 8 threads:

deferred  type_check 15.7  dedup_barrier 0.7  simd_patch 0.1 | 24.6 ms
locked    type_check 15.1  dedup_barrier 0.0  simd_patch 0.0 | 22.3 ms
content   type_check 14.7  dedup_barrier 0.0  simd_patch 0.0 | 22.0 ms

The barrier is gone — 0.7 ms → 0.0, the mechanism working as specified. It was worth ~1–2% of wall
clock, which is what was predicted before implementing (dedup_barrier was ~1% of single-thread
time). content ties locked and edges deferred.

It should not be reported as a performance result.

What it is instead

Identity that needs no coordination. Determinism becomes structural rather than earned by a
canonical-order walk at a barrier, so it holds across any scheduling, partitioning, worker count, or
process boundary. A compilation-local arena index cannot do that, which is why the current scheme
cannot extend to separate, incremental, or distributed compilation.

It also composes recursively, so #305 dissolves: a nested argument is just another GID under the
same rule, where nominal_gid returned None and filter_map silently dropped it.

Precedent already in the tree: tensor_gid content-addresses Tensor<f32,[2,4]> by hashing element
and shape, with no arena and no deferral. Structural types are already content-addressed here;
generic instantiations were the anomaly.

Exactness

The paper's objection is that structural equality must be exact, not probabilistic. With a side
table keyed by digest, a collision is detectable — on insert, a present key with a different
argument vector is a genuine collision and can be raised as an error rather than miscompiled. That
is exactness by detection, at 63 bits over 256-bit inputs. Nothing currently recovers argument
vectors from the arena (monomorphization goes through monomorphized_functions on the AST side), so
the table can be added when something needs it.

If this is adopted on main

Open questions, none blocking the measurement:

  • What identity an uninstantiated Foo<T> should get. Today it mints args [] and collides with
    every other unresolvable case; a de Bruijn-style parameter identity would content-address it too.
  • The SlowMeta arena (types that are both generic and borrowed) carries genuine per-instance
    lifetime data and keeps its indices, deferral and reconciliation. Deferred interning survives as a
    mechanism — it just stops being the mechanism for generic identity.
  • Whether LocalWorkerState should become per-thread regardless. Content addressing removes the
    reason it mattered for generics, but the per-function allocation churn remains.

Caveat on all numbers above

Measured on an Apple M4: 4 performance cores + 6 efficiency cores. Mode ratios are sound (same
machine, same cores, all three modes), but absolute scaling curves conflate design scalability with
core heterogeneity and are not publishable from this machine. See hiraditya/Vx.1#295.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the parallel-frontend-eval implementation, especially mint_deferred_generic, LocalWorkerState, GlobalSession::generics_arena, and tensor_gid. Compare the branch behavior with paper.tex and the existing reconciliation path; done requires resolving the listed identity questions and determining whether the content-addressed design belongs on main without misusing the existing generic state bit.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
28/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.