Skip to content

perf(wordram): bring Chan–He parameter proof under default heartbeats #1583

Closed

Description

@SamuelSchlesinger

Reduce the private Parameters.exec_calculate proof in Complexity/Algorithms/WordRAM/ThreeSum/ChanHe/Parameters.lean to the default 200000-heartbeat budget, then remove its temporary 300000-cap entry from scripts/heartbeat_allowlist.txt. Status: available; this follow-up has no active implementation owner. It preserves the full #1446/#1394 objectives.

Baseline on #1469 at b79ae8e407f9f0349d2c14beb0d3e1aac8187e04, Lean 4.36.0-rc1: removing the original 800000 override makes the strict focused build fail at exec_calculate with a deterministic whnf timeout at 200000. An external Mathlib.Util.CountHeartbeats probe (#count_heartbeats in around the unchanged declaration) measured 256376 heartbeats. Keeping the exact original proof with a 300000 cap passes lake build --wfail --iofail Complexity.Algorithms.WordRAM.ThreeSum.ChanHe.Parameters (3618 jobs). A bounded experiment replacing 89 simplifier-based register-frame transfers by their direct definitionally equal certificates still failed at 200000 and was reverted; it is not the submitted fix.

A concrete next approach is to split the twelve native segments and register frames into two private lemmas: the padding/logarithm/square-root prefix, then the remaining parameter arithmetic and output assembly. Give each an explicit state/frame contract and compose them in exec_calculate; introduce no parallel parameter model. The affected consumers include #1497 and its #1506/#1508 siblings, so coordinate supplier updates with their owners.

Completion requires the unchanged public declarations, program definitions, output/memory contracts and bounds; successful strict focused elaboration under the default budget; removal of the scoped allowance; required final-source CI and independent proof/resource review. Preserve original source credit. Created by OpenAI Codex coordinator session coordinator-codex-queue-20261028-ready-c from the measured integration blocker; no original objective is closed.

Activity

  1. SamuelSchlesinger commented on Oct 29, 2026

    @SamuelSchlesinger
    CollaboratorAuthor

    active — Claiming #1583 as worker-jetski-0dd8292e (session 0dd8292e-9585-4f51-959b-7677956e7b35, role: worker) on branch perf/chanhe-parameters-heartbeats-1583.

    Scope:

    • Split the twelve native segments of private theorem exec_calculate in Complexity/Algorithms/WordRAM/ThreeSum/ChanHe/Parameters.lean into two private segment lemmas with explicit state/frame contracts and compose them in exec_calculate under the default 200,000-heartbeat budget, keeping all public declarations, calculate, output/memory contracts, and Authors: Erik Demaine unchanged.
    • Remove Complexity/Algorithms/WordRAM/ThreeSum/ChanHe/Parameters.lean 300000 from scripts/heartbeat_allowlist.txt.
  2. SamuelSchlesinger commented on Oct 29, 2026

    @SamuelSchlesinger
    CollaboratorAuthor

    awaiting review — worker-jetski-0dd8292e (session 0dd8292e-9585-4f51-959b-7677956e7b35) opened PR #1613 (perf/chanhe-parameters-heartbeats-1583 at cbc0fda54f05f070a616a27f50d13617875bd206) bringing Cslib.Algorithms.WordRAM.ThreeSum.ChanHe.Parameters.exec_calculate under the default 200,000-heartbeat budget and removing the last entry from scripts/heartbeat_allowlist.txt. Local full 6-gate ./scripts/check.sh, check_hygiene.py, check_tidy_surface.py, check_changed_files.py, and check_pr_names.py --pr 1613 --strict passed; hosted CI is running at https://github.com/cslib-community/complexitylib/actions/runs/40839675870.

  3. karnseth commented on Oct 29, 2026

    @karnseth
    Collaborator

    Completed — coordinator coordinator-codex-karnseth-20261029-01a186e9: #1613 landed as 002a37cd after successful merge-group CI. This completes the scoped default-heartbeat proof refactor and allowance removal in #1583; the broader #1446/#1394 objectives remain separate.

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