Skip to content

isDefEq cache for terms not containing metavariables.#2644

Merged
leodemoura merged 7 commits intomasterfrom
defEqCache
Oct 14, 2023
Merged

isDefEq cache for terms not containing metavariables.#2644
leodemoura merged 7 commits intomasterfrom
defEqCache

Conversation

@leodemoura
Copy link
Copy Markdown
Member

No description provided.

@leodemoura
Copy link
Copy Markdown
Member Author

!bench

@leodemoura
Copy link
Copy Markdown
Member Author

!bench

@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit a0ba45c.
There were significant changes against commit 9f50f44:

  Benchmark          Metric          Change
  ===================================================
+ lake build clean   branch-misses    -2.5% (-36.0 σ)

@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit 8ba8496.
There were significant changes against commit 9f50f44:

  Benchmark          Metric             Change
  ======================================================
+ lake build clean   branch-misses       -2.5% (-23.8 σ)
+ stdlib             tactic execution    -7.5% (-23.1 σ)

@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 Oct 10, 2023
ghost pushed a commit to leanprover-community/mathlib4 that referenced this pull request Oct 10, 2023
@ghost ghost added the breaks-mathlib This is not necessarily a blocker for merging: but there needs to be a plan label Oct 10, 2023
@ghost
Copy link
Copy Markdown

ghost commented Oct 10, 2023

kim-em added a commit to kim-em/std4 that referenced this pull request Oct 10, 2023
kim-em added a commit to leanprover-community/mathlib4 that referenced this pull request Oct 10, 2023
kim-em added a commit to leanprover-community/mathlib4 that referenced this pull request Oct 10, 2023
kim-em added a commit to leanprover-community/mathlib4 that referenced this pull request Oct 10, 2023
@kim-em
Copy link
Copy Markdown
Collaborator

kim-em commented Oct 10, 2023

Unfortunately the Mathlib test:

-- Check that we avoid deep recursion in evaluating large powers.
example : 10^40000000 = 10^40000000 := by norm_num

is now taking forever!

This test was introduced in leanprover-community/mathlib4#5740.

@Kha
Copy link
Copy Markdown
Member

Kha commented Oct 10, 2023

@semorrison Hmm, this at least seems fine on my machine?

$ git describe
port-complete-1153-gf1a26d74c
$ lake +leanprover/lean4-pr-releases:pr-release-2644 env lean -Dtrace.profiler=true <(echo "import Mathlib\nexample : 10^40000000 = 10^40000000 := by norm_num")
[Elab.command] [1.786160s] example : 10 ^ 40000000 = 10 ^ 40000000 := by norm_num
  [Elab.step] [1.177314s] norm_num
    [Elab.step] [1.177298s] norm_num
      [Elab.step] [1.177283s] norm_num
  [Kernel] [0.595197s] typechecking declaration

@kim-em
Copy link
Copy Markdown
Collaborator

kim-em commented Oct 10, 2023

Oh, dear! This test has been failing for a while on Apple Silicon (which we don't test in CI). It's not relevant to this PR.

@Kha
Copy link
Copy Markdown
Member

Kha commented Oct 10, 2023

!bench

@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit 5afb7a5.
There were significant changes against commit 9f50f44:

  Benchmark          Metric             Change
  ======================================================
+ lake build clean   branch-misses       -2.4% (-23.8 σ)
+ stdlib             tactic execution    -8.4% (-49.9 σ)

ghost pushed a commit to leanprover-community/mathlib4 that referenced this pull request Oct 10, 2023
@kim-em
Copy link
Copy Markdown
Collaborator

kim-em commented Oct 10, 2023

After @Kha's change there are still many regressions in Mathlib: leanprover-community/mathlib4#7606

@leodemoura
Copy link
Copy Markdown
Member Author

!bench

@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit a84dad5.
There were significant changes against commit 9f50f44:

  Benchmark          Metric             Change
  ======================================================
- lake build clean   branch-misses        1.7%  (15.9 σ)
- lake env           branch-misses        2.8%  (10.2 σ)
+ stdlib             tactic execution    -6.8% (-75.1 σ)

ghost pushed a commit to leanprover-community/mathlib4 that referenced this pull request Oct 11, 2023
Copy link
Copy Markdown
Contributor

@timotree3 timotree3 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

A couple cleanups to comments

Co-authored-by: Timo <timorcb@gmail.com>
@eric-wieser
Copy link
Copy Markdown
Contributor

That looks like a defeq abuse problem to me; (Icc a b).map Embedding.some is of type Finset (Option α), but you're pretending its of type Finset (WithTop α). Does introducing a custom Embedding.withTopSome function with the right type make the problem go away?

@mattrobball
Copy link
Copy Markdown
Contributor

mattrobball commented Oct 12, 2023

abbrev WithTop := Option has the same effect. Looking at the trace, it is exactly at Option =?= WithTop where the current toolchain for mathlib succeeds, the abbrev version succeeds, and the def version fails. Everything else from trace.Meta.isDefEq looks the same.

[Meta.isDefEq] ❌ FunLike.coe { toFun := ?f } =?= FunLike.coe { toFun := some } ▼
  [] ✅ ?α =?= α ▶
  [] found messy fun a ↦ (fun x ↦ ?β) a =?= fun a ↦ WithTop α
  [] ✅ { toFun := ?f } =?= { toFun := some } ▶
  [] ✅ α ↪ Option α =?= α ↪ WithTop α ▶
  [] ✅ Function.instFunLikeEmbedding =?= Function.instFunLikeEmbedding ▶
  [] ❌ fun a ↦ (fun x ↦ Option α) a =?= fun a ↦ WithTop α ▼
    [] ✅ α =?= α
    [] ❌ (fun x ↦ Option α) a =?= WithTop α ▼
      [] ❌ Option α =?= WithTop α ▼
        [] ❌ Option =?= WithTop
        [onFailure] ❌ Option α =?= WithTop α
        [onFailure] ❌ Option α =?= WithTop α
  [onFailure] ❌ FunLike.coe { toFun := ?f } =?= FunLike.coe { toFun := some }
  [onFailure] ❌ FunLike.coe { toFun := ?f } =?= FunLike.coe { toFun := some }

vs

[Meta.isDefEq] ✅ FunLike.coe { toFun := ?f } =?= FunLike.coe { toFun := some } ▼
  [] ✅ ?α =?= α ▶
  [] found messy fun a ↦ (fun x ↦ ?β) a =?= fun a ↦ WithTop α
  [] ✅ { toFun := ?f } =?= { toFun := some } ▶
  [] ✅ α ↪ Option α =?= α ↪ WithTop α ▶
  [] ✅ Function.instFunLikeEmbedding =?= Function.instFunLikeEmbedding ▶
  [] ✅ fun a ↦ (fun x ↦ Option α) a =?= fun a ↦ WithTop α ▼
    [] ✅ α =?= α
    [] ✅ (fun x ↦ Option α) a =?= WithTop α ▼
      [] ✅ Option α =?= WithTop α

@ghost ghost added builds-mathlib CI has verified that Mathlib builds against this PR and removed breaks-mathlib This is not necessarily a blocker for merging: but there needs to be a plan labels Oct 13, 2023
PatrickMassot added a commit to leanprover-community/mathlib4 that referenced this pull request Oct 13, 2023
Excluding new rfl and nolint.
@kim-em kim-em added the awaiting-review Waiting for someone to review the PR label Oct 13, 2023
Copy link
Copy Markdown
Collaborator

@kim-em kim-em left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this is good to go, from the point of view of Mathlib.

@Kha Kha added the changelog label Oct 13, 2023
@ghost ghost added breaks-mathlib This is not necessarily a blocker for merging: but there needs to be a plan builds-mathlib CI has verified that Mathlib builds against this PR and removed builds-mathlib CI has verified that Mathlib builds against this PR breaks-mathlib This is not necessarily a blocker for merging: but there needs to be a plan labels Oct 13, 2023
@leodemoura
Copy link
Copy Markdown
Member Author

I think this is good to go, from the point of view of Mathlib.

Thanks everybody that invested time on this PR. Awesome teamwork!
Planning to merge at the end of the day.

@leodemoura leodemoura merged commit b8af36f into master Oct 14, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

awaiting-review Waiting for someone to review the PR builds-mathlib CI has verified that Mathlib builds against this PR 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.

7 participants