Skip to content

[Merged by Bors] - chore(RingTheory/AdicCompletion): manual instances#14534

Closed
chrisflav wants to merge 15 commits intomasterfrom
chrisflav-adic-speedup
Closed

[Merged by Bors] - chore(RingTheory/AdicCompletion): manual instances#14534
chrisflav wants to merge 15 commits intomasterfrom
chrisflav-adic-speedup

Conversation

@chrisflav
Copy link
Copy Markdown
Member

@chrisflav chrisflav commented Jul 8, 2024

Instead of inferring AddCommGroup, Module, etc. instances for AdicCompletion I M from being a submodule, we explicitly spell out the definitions to improve performance.

Also marks some definitions as noncomputable to save time spent on compilation.

See https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Adic.20completion.20is.20slow.


Open in Gitpod

@chrisflav chrisflav added awaiting-review awaiting-CI This PR does not pass CI yet. This label is automatically removed once it does. t-algebra Algebra (groups, rings, fields, etc) labels Jul 8, 2024
@github-actions
Copy link
Copy Markdown

github-actions bot commented Jul 8, 2024

PR summary 7330fdbaf7

Import changes for modified files

No significant changes to the import graph

Import changes for all files
Files Import difference

Declarations diff

+ incl
+ instance : Add (AdicCauchySequence I M)
+ instance : Add (AdicCompletion I M)
+ instance : AddCommGroup (AdicCauchySequence I M) := by
+ instance : IntCast (AdicCauchySequence I R)
+ instance : IntCast (AdicCompletion I R)
+ instance : Mul (AdicCauchySequence I R)
+ instance : Mul (AdicCompletion I R)
+ instance : NatCast (AdicCauchySequence I R)
+ instance : NatCast (AdicCompletion I R)
+ instance : Neg (AdicCauchySequence I M)
+ instance : Neg (AdicCompletion I M)
+ instance : One (AdicCauchySequence I R)
+ instance : One (AdicCompletion I R)
+ instance : Pow (AdicCauchySequence I R) ℕ
+ instance : Pow (AdicCompletion I R) ℕ
+ instance : SMul R (AdicCauchySequence I M)
+ instance : SMul R (AdicCompletion I M)
+ instance : SMul ℕ (AdicCauchySequence I M)
+ instance : SMul ℕ (AdicCompletion I M)
+ instance : SMul ℤ (AdicCauchySequence I M)
+ instance : SMul ℤ (AdicCompletion I M)
+ instance : Sub (AdicCauchySequence I M)
+ instance : Sub (AdicCompletion I M)
+ instance : Zero (AdicCauchySequence I M)
+ instance : Zero (AdicCompletion I M)
+ neg
+ nsmul
+ pow
+ sub
+ transitionMap_map_pow
+ zsmul
- instance : AddCommGroup (AdicCauchySequence I M)

You can run this locally as follows
## summary with just the declaration names:
./scripts/no_lost_declarations.sh short <optional_commit>

## more verbose report:
./scripts/no_lost_declarations.sh <optional_commit>

@chrisflav
Copy link
Copy Markdown
Member Author

!bench

@github-actions github-actions bot removed the awaiting-CI This PR does not pass CI yet. This label is automatically removed once it does. label Jul 8, 2024
@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit db687bf.
There were significant changes against commit 86414a8:

  Benchmark                                          Metric         Change
  ========================================================================
- ~Mathlib.RingTheory.AdicCompletion.Algebra         instructions    15.4%
- ~Mathlib.RingTheory.AdicCompletion.Basic           instructions    29.5%
+ ~Mathlib.RingTheory.AdicCompletion.Functoriality   instructions   -61.6%

@chrisflav
Copy link
Copy Markdown
Member Author

!bench

@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit ddef0a4.
There were significant changes against commit 86414a8:

  Benchmark                                    Metric         Change
  ==================================================================
- ~Mathlib.RingTheory.AdicCompletion.Algebra   instructions    15.4%
- ~Mathlib.RingTheory.AdicCompletion.Basic     instructions    29.5%

instance : One (AdicCompletion I R) where
one := ⟨1, by simp⟩

instance : CommRing (AdicCompletion I R) where
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

Function.Injective.commRing might help

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

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

I changed it, not entirely sure its better now though.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

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

I did another benchmark comparing the version with Function.Injective.commRing and the manual one: http://speed.lean-fro.org/mathlib4/compare/04e26275-26be-4d08-8dd1-ffeb4e23bd0e/to/e7b27246-a3e6-496a-b552-ff4b45c7236e?hash2=55cf90705c3509ab5da127b7ecd4db0e147af667
It seems the manual one is significantly faster, so I suggest we leave it at this.

@chrisflav
Copy link
Copy Markdown
Member Author

!bench

@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit 20fe104.
There were significant changes against commit 86414a8:

  Benchmark                                          Metric         Change
  ========================================================================
- ~Mathlib.RingTheory.AdicCompletion.Algebra         instructions    28.6%
- ~Mathlib.RingTheory.AdicCompletion.Basic           instructions    47.8%
+ ~Mathlib.RingTheory.AdicCompletion.Functoriality   instructions   -60.3%

@chrisflav
Copy link
Copy Markdown
Member Author

!bench

@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit 6b20ecb.
There were significant changes against commit 86414a8:

  Benchmark                                          Metric         Change
  ========================================================================
- ~Mathlib.RingTheory.AdicCompletion.Algebra         instructions    27.9%
- ~Mathlib.RingTheory.AdicCompletion.Basic           instructions    34.4%
+ ~Mathlib.RingTheory.AdicCompletion.Functoriality   instructions   -61.7%

@chrisflav
Copy link
Copy Markdown
Member Author

!bench

Comment on lines 339 to 343
unseal smul' in
unseal mul in
/-- A priori `AdicCompletion I R` has two `AdicCompletion I R`-module instances.
Both agree definitionally. -/
example : module I = @Algebra.toModule (AdicCompletion I R)
Copy link
Copy Markdown
Member Author

@chrisflav chrisflav Jul 9, 2024

Choose a reason for hiding this comment

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

I think the two unseals here are a problem: In the other PR in the AsTensorProduct file, I had to add the same unseals because Lean can no longer identify these two instances as equal:

unseal smul' in
unseal mul in
/-- If `M` is a finite `R`-module, then the canonical map
`AdicCompletion I R ⊗[R] M →ₗ AdicCompletion I M` is surjective. -/
lemma ofTensorProduct_surjective_of_fg [Module.Finite R M] :
Function.Surjective (ofTensorProduct I M) := by
Is there anything I can do about this? Or does it mean we can't make mul and smul' irreducible?

@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit 571a2f2.
There were significant changes against commit 86414a8:

  Benchmark                                          Metric         Change
  ========================================================================
- ~Mathlib.RingTheory.AdicCompletion.Algebra         instructions    30.9%
- ~Mathlib.RingTheory.AdicCompletion.Basic           instructions    36.4%
+ ~Mathlib.RingTheory.AdicCompletion.Functoriality   instructions   -61.7%

@mattrobball
Copy link
Copy Markdown
Contributor

It is out-dated but AdicCompletion.module didn't change its name right?

@chrisflav
Copy link
Copy Markdown
Member Author

It is out-dated but AdicCompletion.module didn't change its name right?

Ah yes, no it did not change its name, but then adding the dsimp does not seem to make a significant difference to count_heartbeats in.

@mattrobball
Copy link
Copy Markdown
Contributor

Oh well, it was minor I think anyway

@chrisflav
Copy link
Copy Markdown
Member Author

So should I go for a final benchmark?

@mattrobball
Copy link
Copy Markdown
Contributor

There is a good chance it won't make it in without using the Function.Injective constructors. We should test that fully first

@chrisflav
Copy link
Copy Markdown
Member Author

I had tried out the version with Function.Injective constructors above, but it was significantly slower. See this comparison: http://speed.lean-fro.org/mathlib4/compare/04e26275-26be-4d08-8dd1-ffeb4e23bd0e/to/e7b27246-a3e6-496a-b552-ff4b45c7236e?hash2=55cf90705c3509ab5da127b7ecd4db0e147af667

The first run is with Function.Injective constructors and the second one without.

@chrisflav
Copy link
Copy Markdown
Member Author

Anything else I should test?

@chrisflav
Copy link
Copy Markdown
Member Author

!bench

@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit 400c96f.
There were significant changes against commit 86414a8:

  Benchmark                                          Metric         Change
  ========================================================================
+ ~Mathlib.RingTheory.AdicCompletion.Algebra         instructions   -15.3%
+ ~Mathlib.RingTheory.AdicCompletion.Functoriality   instructions   -64.1%

@mattrobball
Copy link
Copy Markdown
Contributor

What's the effect on AsTensorProduct?

@chrisflav
Copy link
Copy Markdown
Member Author

chrisflav commented Jul 11, 2024

Benchmark is upcoming. My local one looks very good, i.e. comparable to the performance with explicit instances.

@chrisflav
Copy link
Copy Markdown
Member Author

Benchmark is there. This is the comparsion:

http://speed.lean-fro.org/mathlib4/compare/e7b27246-a3e6-496a-b552-ff4b45c7236e/to/74e2d180-1ac7-47c1-9b6e-c7589ce1cd90?hash1=abf5c5635c9bde7cefa76b2c18405067b604e089

First commit: manual instances
Second commit: Function.Injective constructors with fast_instance%.

I think this looks promising, so I'll revert the commits adding the fast_instance% stuff and we add them back in later when the #11521 lands. What do you think @mattrobball ?

@mattrobball
Copy link
Copy Markdown
Contributor

mattrobball commented Jul 11, 2024

Also please make a separate dependent PR with the fast_instance insertions also so we can quickly put them back when that PR lands

@chrisflav
Copy link
Copy Markdown
Member Author

Also please make a separate dependent PR with the fast_instance insertions also so we can quickly put them back when that PR lands

Since #11521 currently has merge conflicts, what should I do to create the dependent PR? Maybe from #11521 the actual fast_instance% code should be split of, otherwise it will collect merge conflicts all the time.

@mattrobball
Copy link
Copy Markdown
Contributor

I forgot it wasn't just the single file. I'll split it later today.

@chrisflav
Copy link
Copy Markdown
Member Author

Anything else I should do for this PR to be merged?

@mattrobball
Copy link
Copy Markdown
Contributor

I don't think so. Thanks for your patience.

bors merge

@github-actions github-actions bot added the ready-to-merge This PR has been sent to bors. label Jul 11, 2024
mathlib-bors bot pushed a commit that referenced this pull request Jul 11, 2024
Instead of inferring `AddCommGroup`, `Module`, etc. instances for `AdicCompletion I M` from being a submodule, we explicitly spell out the definitions to improve performance.

Also marks some definitions as `noncomputable` to save time spent on compilation.

See https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Adic.20completion.20is.20slow.
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jul 11, 2024

Pull request successfully merged into master.

Build succeeded:

@mathlib-bors mathlib-bors bot changed the title chore(RingTheory/AdicCompletion): manual instances [Merged by Bors] - chore(RingTheory/AdicCompletion): manual instances Jul 11, 2024
@mathlib-bors mathlib-bors bot closed this Jul 11, 2024
@mathlib-bors mathlib-bors bot deleted the chrisflav-adic-speedup branch July 11, 2024 16:15
@chrisflav
Copy link
Copy Markdown
Member Author

Thanks a lot for the guidance and for helping analyzing this!

@adomani adomani mentioned this pull request Aug 1, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

ready-to-merge This PR has been sent to bors. t-algebra Algebra (groups, rings, fields, etc)

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants