Opened 9 years ago
Closed 9 years ago
#14516 closed enhancement (fixed)
Refactoring of crystals for speedup
Reported by: | tscrim | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.12 |
Component: | combinatorics | Keywords: | crystals speedup, days49 |
Cc: | sage-combinat, bsalisbury1, aschilling, nthiery | Merged in: | sage-5.12.beta1 |
Authors: | Travis Scrimshaw | Reviewers: | Anne Schilling |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #2023, #14402, #14413, #14143, #12940 | Stopgaps: |
Description (last modified by )
In order to speed up many of the crystals computations, I'm proposing the following:
- Cythonize
CrystalOfLetters
- Make
index_set()
a cached method. Subsequently this requires it to be returned as a tuple instead of a list - Make different letters classes, one for integers (classical types), one for tuples (exceptional/spin)
- Store by caching result of
_element_constructor_()
the elements ofCrystalOfLetters
.
See #14686 for a followup.
Apply:
Attachments (3)
Change History (29)
comment:1 Changed 9 years ago by
- Dependencies changed from #14402 #2023 to #14402 #14413 #14143 #2023
comment:2 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
I'm also getting significant speedups now in creating CrystalOfLetters
and doctests for tensor_product.py
and kirillov_reshetikhin.py
:
sage: %time C = CrystalOfLetters(['D',100]) CPU times: user 0.84 s, sys: 0.24 s, total: 1.08 s Wall time: 1.67 s sage -t tensor_product.py [349 tests, 13.05 s] sage -t kirillov_reshetikhin.py [653 tests, 30.51 s]
Before:
sage: %time C = CrystalOfLetters(['D',100]) CPU times: user 2.33 s, sys: 0.42 s, total: 2.76 s Wall time: 3.58 s sage -t tensor_product.py [349 tests, 14.60 s] sage -t kirillov_reshetikhin.py [653 tests, 47.96 s]
comment:3 Changed 9 years ago by
- Dependencies changed from #14402 #14413 #14143 #2023 to #2023 #14402 #14413 #14143 #14573
comment:4 Changed 9 years ago by
- Description modified (diff)
comment:5 Changed 9 years ago by
- Dependencies changed from #2023 #14402 #14413 #14143 #14573 to #2023 #14402 #14413 #14143
- Status changed from needs_review to needs_work
I'll upload the split patch shortly and check to see if it can commute pass #14143.
comment:6 Changed 9 years ago by
- Dependencies changed from #2023 #14402 #14413 #14143 to #2023 #14402 #14413
- Status changed from needs_work to needs_review
comment:7 follow-up: ↓ 8 Changed 9 years ago by
With patch:
sage: %time C = CrystalOfLetters(['D',100]) CPU times: user 1.54 s, sys: 0.03 s, total: 1.56 s Wall time: 1.72 s sage: B = InfinityCrystalOfTableaux(['B',3]) sage: S = B.subcrystal(max_depth=4) sage: %time G = B.digraph(subset=S) CPU times: user 28.20 s, sys: 0.03 s, total: 28.23 s Wall time: 28.62 s sage: C = CrystalOfTableaux(['D',4], shape=[2,1]) sage: %time G = C.digraph() CPU times: user 0.33 s, sys: 0.00 s, total: 0.34 s Wall time: 0.34 s
Before:
sage: %time C = CrystalOfLetters(['D',100]) CPU times: user 1.84 s, sys: 0.02 s, total: 1.86 s Wall time: 2.00 s sage: B = InfinityCrystalOfTableaux(['B',3]) sage: S = B.subcrystal(max_depth=4) sage: sage: %time G = B.digraph(subset=S) CPU times: user 28.96 s, sys: 0.03 s, total: 28.99 s Wall time: 29.94 s sage: C = CrystalOfTableaux(['D',4], shape=[2,1]) sage: %time G = C.digraph() CPU times: user 0.39 s, sys: 0.01 s, total: 0.40 s Wall time: 0.39 s
So currently I'm seeing small performance gains, the bigger ones are likely going to come from #14686.
comment:8 in reply to: ↑ 7 Changed 9 years ago by
Hi Travis,
The two tests (with and without patch) do not seem to be the same!
Anne
comment:9 Changed 9 years ago by
- Dependencies changed from #2023 #14402 #14413 to #2023 #14402 #14413 #14143
@Anne There was some omissions.
New version which fixes the pickling issues and should pass all doctests. #14143 does fix some of the doctests.
comment:10 Changed 9 years ago by
- Reviewers set to Anne Schilling
comment:11 follow-up: ↓ 12 Changed 9 years ago by
- Keywords days49 added
comment:12 in reply to: ↑ 11 Changed 9 years ago by
Hi Travis,
The patch looks good (I put a reviewed patch on the sage-combinat queue). I am not so happy about the huge doc tests for setstate. As we discussed, perhaps just put a loads/dumps test?
Best,
Anne
comment:13 Changed 9 years ago by
Done.
comment:14 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:15 Changed 9 years ago by
- Description modified (diff)
Forgot to qrefresh.
Apply: trac_14516-crystals_speedup-ts.2.patch
comment:16 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:17 Changed 9 years ago by
- Status changed from positive_review to needs_work
I get a warning when building the doc:
[combinat ] docstring of sage.combinat.crystals.letters.CrystalOfLetters:21: WARNING: duplicate citation KN94, other instance in /Applications/sage/devel/sage/doc/en/reference/combinat/sage/combinat/crystals/infinity_crystals.rst
comment:18 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to positive_review
Fixed. Thanks for catching that Jeff (I wish duplicate references would always show up every time you rebuild the doc instead of just the first time).
For patchbot:
Apply: trac_14516-crystals_speedup-ts.patch
comment:19 Changed 9 years ago by
- Dependencies changed from #2023 #14402 #14413 #14143 to #2023, #14402, #14413, #14143, #12940
- Status changed from positive_review to needs_work
There are doctest failures with #12940, please rebase:
sage -t devel/sage/sage/combinat/affine_permutation.py ********************************************************************** File "devel/sage/sage/combinat/affine_permutation.py", line 241, in sage.combinat.affine_permutation.AffinePermutation.index_set Failed example: A.index_set() Expected: [0, 1, 2, 3, 4, 5, 6, 7] Got: (0, 1, 2, 3, 4, 5, 6, 7) ********************************************************************** File "devel/sage/sage/combinat/affine_permutation.py", line 2077, in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.index_set Failed example: AffinePermutationGroup(['A',7,1]).index_set() Expected: [0, 1, 2, 3, 4, 5, 6, 7] Got: (0, 1, 2, 3, 4, 5, 6, 7) ********************************************************************** File "devel/sage/sage/combinat/affine_permutation.py", line 2088, in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.reflection_index_set Failed example: AffinePermutationGroup(['A',7,1]).index_set() Expected: [0, 1, 2, 3, 4, 5, 6, 7] Got: (0, 1, 2, 3, 4, 5, 6, 7) **********************************************************************
comment:20 Changed 9 years ago by
- Status changed from needs_work to needs_review
Fixed:
sage -t affine_permutation.py [335 tests, 28.87 s] ---------------------------------------------------------------------- All tests passed! ----------------------------------------------------------------------
For patchbot:
Apply: trac_14516-crystals_speedup-ts.patch
comment:21 follow-up: ↓ 22 Changed 9 years ago by
Anne, could you do a double-check to make sure everything is consistent and works for you? Thanks.
comment:22 in reply to: ↑ 21 Changed 9 years ago by
Replying to tscrim:
Anne, could you do a double-check to make sure everything is consistent and works for you? Thanks.
I still get the above mentioned errors:
sage -t affine_permutation.py ********************************************************************** File "affine_permutation.py", line 241, in sage.combinat.affine_permutation.AffinePermutation.index_set Failed example: A.index_set() Expected: [0, 1, 2, 3, 4, 5, 6, 7] Got: (0, 1, 2, 3, 4, 5, 6, 7) ********************************************************************** File "affine_permutation.py", line 2077, in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.index_set Failed example: AffinePermutationGroup(['A',7,1]).index_set() Expected: [0, 1, 2, 3, 4, 5, 6, 7] Got: (0, 1, 2, 3, 4, 5, 6, 7) ********************************************************************** File "affine_permutation.py", line 2088, in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.reflection_index_set Failed example: AffinePermutationGroup(['A',7,1]).index_set() Expected: [0, 1, 2, 3, 4, 5, 6, 7] Got: (0, 1, 2, 3, 4, 5, 6, 7) ********************************************************************** 3 items had failures: 1 of 3 in sage.combinat.affine_permutation.AffinePermutation.index_set 1 of 2 in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.index_set 1 of 2 in sage.combinat.affine_permutation.AffinePermutationGroupGeneric.reflection_index_set [335 tests, 3 failures, 6.17 s]
Did you post an updated patch? I cannot see any mention of affine_permutation in your patch.
Anne
Changed 9 years ago by
comment:23 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
Changed 9 years ago by
comment:24 follow-up: ↓ 25 Changed 9 years ago by
- Description modified (diff)
Here's the fixed patch.
For patchbot:
Apply: trac_14516-crystals_speedup-ts.patch
comment:25 in reply to: ↑ 24 Changed 9 years ago by
Ok, looks good now!
Anne
comment:26 Changed 9 years ago by
- Merged in set to sage-5.12.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
Here are some timings.
With the patch:
Before: