Skip to content

Research: bounded superoptimization of pure OwnIR transfer helpers (enumeration / e-graphs / SMT) #459

Open

Description

@PhysShell

Classification

Hypothesis

For one demonstrably expensive, pure helper, a narrowly defined expression grammar plus semantic deduplication can reveal an equivalent cheaper implementation that manual refactoring or the compiler misses. This is not a proposal to rewrite the ownership analysis or its diagnostic semantics.

The blog enumerates expressions, deduplicates by vectors of results on ~20 tests and manually identifies subexpression reuse. Test-vector equality is a search heuristic, not proof. A four-operation expression also need not mean a faster machine-code implementation.

Kill-first protocol

  1. Establish need: profile existing workload and identify at most 1–2 actual hot pure functions (e.g., a state-transition/bitset helper only if one really exists). Pin code SHA, inputs, benchmark harness and semantics. KILL immediately if there is no meaningful hot spot or a standard compiler optimization already solves it.
  2. Fix semantics: specify allowed inputs, integer widths, overflow/shift behavior, undefined/invalid states, order/side effects, and target runtime. Exclude allocations, exceptions, aliases, lifetime/Dispose effects, interprocedural and WPF behavior from synthesis.
  3. Small search: restricted operators/constants; enumerate trees or use e-graph rewriting; retain shared-subexpression DAGs in cost accounting; deduplicate by test-output vectors; generate edge cases and counterexamples.
  4. Independent validation: exhaustive evaluation on a tractable bounded domain or SMT proof under explicit assumptions, plus compiler/build tests and differential/metamorphic regression. If equivalence is unproved, label UNVERIFIED and do not propose production replacement. Alive2 only if the candidate has genuinely equivalent LLVM IR semantics; no automatic claim of .NET/Rust proof.
  5. Measure: compare current implementation, optimized compiler baseline and generated candidate on representative workloads. Record correctness verdict, counterexamples, instruction count where meaningful, latency, throughput, allocation, memory, portability and maintainability cost.

Deliverables / decision gate

  • Reproducible self-contained spike with frozen inputs, exact versions/SHAs, candidate grammar and results.
  • Candidate + counterexample/proof receipt + before/after benchmark, or a documented negative result.
  • GO only for a verified rewrite with reproducible useful improvement and acceptable complexity; CHANGE for a reusable verifier/test generator only; KILL for no hot spot, insufficient proof, or negligible benefit.
  • No production integration, broad synthesis framework, or auto-fix roll-out as part of this issue.

A separate, architecture-level code-pattern recommender is documented in Pattern-Aware Refactoring; that is not Own.NET's remit.

Activity

  1. PhysShell commented on Nov 15, 2026

    @PhysShell
    OwnerAuthor

    Additional prior art: OpenEvolve (Asankhaya Sharma)

    Source: algorithmicsuperintelligence/openevolve, an LLM-guided evolutionary program-search framework with external evaluators and population-based search.

    Please treat this as an optional search baseline inside #459, not a new optimization project. The existing issue's pure, explicitly specified OwnIR helper / independent semantic-equivalence gate stays authoritative.

    Suggested comparison only after #459 identifies a real measured hotspot and a trusted oracle:

    1. A: current implementation + compiler optimization; B: bounded enumerative/e-graph/SMT search already specified in Research: bounded superoptimization of pure OwnIR transfer helpers (enumeration / e-graphs / SMT) #459; C: a narrow OpenEvolve-style LLM mutation loop.
    2. Equalize evaluation/time/token budgets and held-out independent tests; record seeds, generated variants, invalid-candidate rate and full cost. Best-of-N with no evolutionary feedback is a useful control.
    3. Candidate 'passes test suite' is only empirical evidence, never proof of equivalent transfer/ownership semantics. Counterexample/independent equivalence check and mutation negatives remain mandatory.
    4. Hard stop on unstable outputs, unproved rewrites, no gain beyond B, or maintainability/cost regression. No integration or production changes from this comment.

    Useful high-level donor: proposal/search/evaluator separation and archived candidate provenance, not automatic code replacement.

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

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions