Skip to content

perf: improve heuristic at isDefEq#3837

Merged
leodemoura merged 2 commits intomasterfrom
3807_slowdown
Apr 22, 2024
Merged

perf: improve heuristic at isDefEq#3837
leodemoura merged 2 commits intomasterfrom
3807_slowdown

Conversation

@kim-em
Copy link
Copy Markdown
Collaborator

@kim-em kim-em commented Apr 6, 2024

Adds a test case containing a minimization of a Mathlib slowdown from #3807, and a patch to isDefEq to fix the slowdown.

Prior to #3807, the declaration exists_algHom_adjoin_of_splits''' at the end of the file would take around 16,000 heartbeats. After #3807 it took around 210,000 heartbeats.

@kim-em
Copy link
Copy Markdown
Collaborator Author

kim-em commented Apr 6, 2024

Curiously, deleting setOf in both

def range (f : ι → α) : Set α := setOf fun x => ∃ y, f y = x

and

def image (f : α → β) (s : Set α) : Set β := setOf fun b => ∃ a ∈ s, f a = b

reduces the heartbeat count to around 80,000.

@kim-em
Copy link
Copy Markdown
Collaborator Author

kim-em commented Apr 6, 2024

These are the outputs of

set_option trace.Meta.isDefEq true in
exact (congrFun (congrArg (fun g : L' →ₐ[F] K => (g : L' → K)) hφ) _).trans (congrArg f <| AlgEquiv.symm_apply_apply _ _)

(i.e. the step that is timing out) both before and after #3807. Be warned that after.txt is about 7gb uncompressed....
before.txt.gz
after.txt.gz

@github-actions github-actions bot added the toolchain-available A toolchain is available for this PR, at leanprover/lean4-pr-releases:pr-release-NNNN label Apr 6, 2024
@ghost
Copy link
Copy Markdown

ghost commented Apr 6, 2024

Mathlib CI status (docs):

  • ❗ Mathlib CI can not be attempted yet, as the nightly-testing-2024-04-05 tag does not exist there yet. We will retry when you push more commits. If you rebase your branch onto nightly-with-mathlib, Mathlib CI should run now. (2024-04-06 07:48:20)
  • ❗ Std CI can not be attempted yet, as the nightly-testing-2024-04-21 tag does not exist there yet. We will retry when you push more commits. If you rebase your branch onto nightly-with-mathlib, Std CI should run now. (2024-04-21 21:29:45)

@leodemoura leodemoura changed the title chore: add test case exhibiting slowdown post #3807 perf: improve heuristic at tryHeuristic at ExprDefEq.lean Apr 21, 2024
@leodemoura leodemoura changed the title perf: improve heuristic at tryHeuristic at ExprDefEq.lean perf: improve heuristic at isDefEq Apr 21, 2024
@leodemoura leodemoura enabled auto-merge April 21, 2024 21:15
@github-actions github-actions bot temporarily deployed to lean-lang.org/lean4/doc April 21, 2024 21:21 Inactive
@leodemoura leodemoura added this pull request to the merge queue Apr 21, 2024
@github-merge-queue github-merge-queue bot removed this pull request from the merge queue due to failed status checks Apr 21, 2024
@leodemoura leodemoura added this pull request to the merge queue Apr 21, 2024
@github-merge-queue github-merge-queue bot removed this pull request from the merge queue due to failed status checks Apr 21, 2024
@leodemoura leodemoura added this pull request to the merge queue Apr 21, 2024
Merged via the queue into master with commit ac0f699 Apr 22, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

toolchain-available A toolchain is available for this PR, at leanprover/lean4-pr-releases:pr-release-NNNN

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants