Mitigate speed regressions in symmetric function related code due to #12313 #13991
Comments
|
comment:1
For information, the results of First time is reference, second one with #12313. Variations have not been compensated for, but the really big differences are probably due to a genuine issue. As you can see, the slowdown in |
|
comment:2
If I am not mistaken, symmetric function algebras are our key example of algebras with multiple realisations. Hence, here one has frequent coercions back and forth between different realisations of the same abstract algebra. However, if I am not mistaken, the different realisations of an algebra are stored by strong references as attributes of the algebra. |
This comment has been minimized.
This comment has been minimized.
|
comment:4
With #12313, I get I do find it strange that 472 homsets are created, but apparently this does not contribute much to the computation time - at least not directly. I am afraid the problem is not clear to me from these statistics. But perhaps a comparison with the pre-#12313 state gives a clue? |
|
comment:5
Note that the list of calls from my previous post is much longer. I just gave the calls that occur most frequently. And here is the same without #12313: That's a huge difference. |
|
comment:6
One very astonishing difference is that without #12313, Hom (or anything else from sage.categories.homset) is not called at all!!! Note that the list without #12313 is complete. I expected that it would be called once, and then cached. But why is no homset created, even though coercion maps should certainly be involved? |
|
comment:7
Replying to @simon-king-jena:
Probably the homsets are associated with the coercion maps. Note that Also note that |
|
comment:8
In fact, you might try running the code in the python debugger and set a breakpoint on |
|
comment:9
Replying to @nbruin:
Why so complicated? A print statement would do as well. That's of course the next thing I'll try, as soon as I'm done helping my son with his homework. |
|
comment:10
Cool! this sort of works: So it seems to me the first problem arises in this statement: With I guess it's the which is obviously a parent that needs to be created again and again! So my guess is that Better yet, the call should just be replaced by The lessons here are interesting for people intending to drive Sage's category and coercion system to its limits:
|
|
comment:11
Replying to @simon-king-jena:
Because it's not complicated as you can see! plus, you get to examine the call stack. And by setting the breakpoint only after initialization you avoid all the irrelevant data (I assume a lot of homspaces are created) |
|
comment:12
Replying to @nbruin:
OK, I thought that for setting a break point one needs to change the source code. |
|
comment:13
I don't think that Actually, Partitions(1) is not a unique parent - and I think this actually is the problem. Namely, we have In the old way of caching homsets, domain and codomain were tested for equality. But now, they are tested for identity. Hence, we now have which used to return True, because Hom was caching by equality. Hence, rather than having less caching, I actually suggest to have more caching in this case: This cache should either be a weak cache, or it should be semi-weak (e.g., cache the output of |
|
comment:14
OK, I indeed get when making Hence, it seems to me that more caching (but weak caching, with |
|
comment:15
A strange problem is the fact that |
|
comment:16
The following is very bad: I'll ask sage-devel about it. |
|
comment:17
The following (in which I use |
|
comment:18
Aha! It could actually be the overhead of calling |
|
Experimental patch |
|
comment:19
Attachment: trac13991-UniqueRepresentation_for_partitions.patch.gz I have attached an unfinished patch (if Can you test whether this patch would completely resolve the regression we are dealing with here? |
|
comment:20
Aha. Cythoning I guess making |
|
comment:21
Great! When implementing comparison of Still, I am not totally happy that it takes longer than 400 ns, but certainly 696 ns is a lot better than 2.33 µs. I will try to make cythoned unique representations work, but that will be on a different ticket. |
|
comment:22
Hi Simon! Replying to @simon-king-jena:
Thanks for investigating performance of UniqueRepresentation. Do not waste time on making CombinatorialClass and UniqueRepresentation play perfectly smoothly. CombinatorialClass is meant to dissapear anyway. Cheers, |
|
comment:23
Other than that, a definite +1 on having Partitions_n have UniqueRepresentation and on cythoning UniqueRepresentation. |
|
Dependencies: #13605 |
|
comment:45
Replying to @nbruin:
No, since this factory function is uncached. The cache lives in
OK. This makes sense.
OK, but who has typical use cases? Something else. I noticed that k_dual.py uses Partition, Partitions and Partitions_all_bounded quite a lot---without storing their results in most cases. Since their own cache is now weak, I wouldn't be surprised if here is the reason for the slow down. Since these partitions are repeatedly used in different methods, I think they should be cached more strongly. I see the following options:
What do you think? |
|
comment:46
I think it makes sense to change this ticket into a "task", and to create separate tickets for several independent aspects/ideas that make sense individually. See #14225 for one of these aspects. |
|
comment:47
Replying to @simon-king-jena:
I think that if it is indeed the case that Partitions get deleted and recreated often and if that is resulting in unacceptable slowdowns, then someone who understands the usage scenarios should look at Expecting that Thus, whenever code has If you're absolutely intent on making The most important value of this exercise I think is as a case-study into the pitfalls of getting good performance relating to complicated parent structures. I'd hope you'll eventually find some general guidelines people should follow if they want their code to perform reasonably well. |
|
comment:48
Hi guys! Replying to @nbruin:
Sorry for jumping a bit late in the discussion. Thanks for investigating this. I just wanted to say to not worry too Also, from the top of my head, the k in k-Schur is basically the same Cheers, |
|
comment:49
Replying to @nthiery:
I think the slow-down is dramatic enough, and we should do something against it.
What about the partitions? My guess is that they can't be too many either (namely, they used to be strongly cached, but the k_schur tests did not run out of memory). |
|
comment:50
Concerning "modularity": At #14225, I do both the |
|
comment:51
Replying to @simon-king-jena:
Sorry that I didn't wait for a reply. I updated #14225, so that it only deals with |
|
comment:52
In fact, sage.combinat.sf.k_dual uses I think it really makes sense to cache this, because the cache will be limited (and will live in the objects that really use the cached data). With this, I obtain: on the same machine as with the timings mentioned above. Hence, I think there is hope to solve the problem in a convenient way. Since this ticket is now a "task", I will post my patch on a new ticket. |
|
comment:53
Hey Simon, I have a patch which does the caching. Here's the message I was going to post (right) before the server crash: With some further digging, there is exactly one meaningful call to Here are my top function calls. Before changes: After: Doing some digging through all the data, the longest tests seems to be: Which basically comes from doing With changes: I can post my patch in the new ticket you create (I gather that it the appropriate thing to do for tasks). Sorry for the message bomb. Best, Travis |
|
comment:54
Replying to @tscrim:
OK. Let's see how we will merge the two patches. At least part of it should be orthogonal (you talk here about Weyl group caching, but my to-be-posted patch is about caching of partitions). |
|
comment:56
I have created #14228 for the caching. |
|
comment:57
Sorry for the typo in the ticket number. |
|
Reviewer: Simon King |
|
comment:58
With sage-5.8.beta0 plus I obtain and and second time Adding I obtain and and second time Adding I obtain and and second time Hence, it seems to me that #14228 did indeed fix the problem. |
|
comment:60
positive_review to what? |
|
comment:61
Replying to @jdemeyer:
To the fact that the issue (for which I originally thought we might need more independent tickets) is fixed by the dependencies of this "task" ticket. |
As was found in #12313, there is some code, especially
k_dual.pyintroduced in #13762, that seems to be extremely reliant for its performance on parents being immortal. Actually as it turned out it's not immortality, it was relying on non-unique parents comparing as equal, where parents should be unique and hence should be comparable by identity:Profiling gives some indication what is happening:
it seems certain parents are created again and again (indeed they are, but the problem here turns out to be that they are created newly rather than the existing parent being reused) and the coercion discoveries need to be redone every time.
Probably, the most straightforward solution is to equip the classes with appropriate caches so that they themselves are now ensuring the lifetime of parents they use rather than rely on sage to keep them around.
Depends on #13605
Depends on #14225
Depends on #14228
CC: @tscrim
Component: combinatorics
Reviewer: Simon King
Issue created by migration from https://trac.sagemath.org/ticket/13991
The text was updated successfully, but these errors were encountered: