-
-
Notifications
You must be signed in to change notification settings - Fork 481
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Make getattr faster on parents and elements #11342
Comments
Attachment: trac11342-faster_getattr.patch.gz Make attribute access faster on elements and parents |
comment:1
Here are my ideas to make attribute access faster. 1. Make raising an attribute error faster It is very common that one tries to get an attribute, but it does not exist - attribute error. Since it occurs so frequently, it is essential that the error be raised as quickly as possible. Raising the error is therefore the job of a Cython function 1.a) The second argument to that function always is a string: The attribute name. Thus, why not explicitly state it in the Cython code? 1.b) It internally operates with the type of the first argument. So, why not explicitly state it in the Cython code? 1.c) The error message is formed from the name of the class and the name of the attribute. There is one complication: If one has an extension type then its name shall be prepended by its module name. There is a Cython function 1.d) How shall one create the error message? In unpatched Sage, it is done by a formatted string that is formed by the class name (perhaps together with the name of the module of the class) and the attribute name. However, it turned out in some timings that I did that composing the error message by addition of strings is faster than the formatted string. 1.e) If one has an extension type then it turns out to be faster to get module name plus class name from the string representation of that type, rather than from addition of strings. Hence, the new
Timings for I compare the timings of unpatched and patched sage-4.7.alpha5, stating the patched version first. We have to distinguish extension types and others:
2. Raise attribute errors earlier An attribute of a parent can be obtained from the category only if its category is properly initialised. Otherwise an attribute error is raised. In order to test whether it is properly initialised, the method Hence, first suggestion: Directly test whether Up to now, an attribute of an element can be obtained from the category of its parent, even if the category of the parent is not properly initialised. I doubt that this is a good idea. In fact, there is only a single doctest error if one requests the parent's category to be initialised, and this error vanishes if #9944 is applied. Hence, second suggestion: If self is an element, then try to get an attribute from the category only if self._parent._category is not None. These changes have a nice effect on the performance. Again, I state the timings for the patched version first. Recall that by #10467, if the Hence, we have to consider the following cases:
Long doctests pass for me - #9944 is required for one test in Depends on #9944 |
Dependencies: #9944 |
Author: Simon King |
Make attribute access faster on elements and parents: Create the error message only when needed |
comment:2
Attachment: trac11342-AttributeErrorMessage.patch.gz Using an additional idea, I was able to improve the timings even further. I have already indicated that the process of raising the attribute error actually is a bottle neck. To be precise: Most time is spent for creating the nicely formatted error message. The point is: The typical fate of an Therefore I suggest that the error message will only be created if someone wants to see it. This is possible by introducing a new class Hence, rather than calling
Compare with the timings for Other than that, I added the specification that the attribute name is supposed to be a string:
instead of
Updated timings I am repeating the tests from my previous comments.
There is a clear improvement, even compared with the previous patch version.
There is a clear improvement, even compared with the previous patch version.
Note Usually, errors are raised with an error message that is given by a string. It seems that raising it with an instance of Therefore I'm informing sage-devel, and I did not override the old patch but created a new one. For the patchbot: Depends on #9944 Apply [attachent:trac11342-AttributeErrorMessage.patch] |
This comment has been minimized.
This comment has been minimized.
comment:3
Hi Simon, I didn't realize that it was part of your problem, that's why I only react now. It seems that your class Florent |
comment:5
I did the following test with lazy format strings:
That string is a good approximation to what we really want, but the differences to the original error messages could only be resolved by a case distinction:
However, even if we do not insist on reproducing the exact same error message, lazy format strings are simply too slow.
So, it is nearly eight times slower than using |
comment:6
As I already said: [It] is pure Python so that probably a little Cythonizing is needed if it fits you needs. Plus compared to your code I have have to pay the extra cost of calling the operator |
comment:7
Hi Simon Some more info: According to prun most of the time is spend during the copy in
For example
I'm pretty sure that cythonizing properly this copy should give a large |
comment:8
Replying to @hivert:
I don't think that there is any code or feature duplication. Certainly there is no code duplication. What you can do with Moreover, this ticket explicitly is about speed. A slow down by an extra call to |
comment:9
Replying to @hivert:
Backward compatibility is one thing. In addition I don't think that you can come up to speed, even with cython, if you need to copy strings etc. The point of Of course, you may try to tune the lazy format strings so that they are fast enough for the application here. But for the moment, I really don't see why one should not introduce a very slim new class (it only has |
comment:10
Please have a look at the code... I'm just copying the object itself if it is
If you tell me you won't use it, I'm less motivated to tune it finely ;-) |
This comment has been minimized.
This comment has been minimized.
comment:12
Ping! For the patchbot (since it doesn't read the ticket description): Apply trac11342-AttributeErrorMessage.patch |
comment:13
On June 27, the patchbot applied both patches, even though on June 26 I pointed out that only one patch has to be applied. Let's ty again... Apply trac11342-AttributeErrorMessage.patch |
comment:14
apply only trac11342-AttributeErrorMessage.patch |
comment:15
Stupid auto-wikification |
apply only this patch |
comment:16
Attachment: trac11342-attribute_error_message.patch.gz Replying to @robertwb:
Thank you for your effort and for renaming the patch! Now, the patchbot has still trouble, namely when applying #9944. That ticket was merged in sage-4.7.1.alpha2, but apparently it can not be applied to sage-4.7. Hélas. For the record: It should work on top of sage-4.7.1.rc2. |
Only apply this patch. Make attribute access faster on elements and parents: Create the error message only when needed |
comment:17
Attachment: trac11342-attribute_error_message.rebased.patch.gz I had to rebase the patch, since it only applied with fuzz 1 against sage-4.7.1.rc1. Still needs review. Apply trac11342-attribute_error_message.rebased.patch |
This comment has been minimized.
This comment has been minimized.
comment:46
Replying to @vbraun:
I guess, implicitly we are using it all: As we have seen, some pari objects are generated when sage starts. And you are right, it is evident that sage/rings/pari_ring.py has been written long time ago... Do you think we should attempt to bring it up to date here? Or do it on a different ticket and just use the work-around provided by attachment: trac_11342_fix_pari_initialization.patch? If we fix it here: Did you already start with it? Otherwise, I'd do it myself. |
comment:47
Volker, I am not getting the segfault you reported. With the current two patches, I obtain:
So, the question is whether we should fix it here, or open a new ticket and make it a dependency. |
Some fixes for the Pari pseudoring |
comment:48
Attachment: trac_11342_fix_pari_ring.patch.gz I have already produced a patch on the pari ring problem. Volker, does it make your segfault vanish? At least, I think that my patch improves the code quality of pari_ring.py. |
This comment has been minimized.
This comment has been minimized.
Attachment: trac_11342_crypto_fixes.patch.gz Initial patch |
comment:49
Your patch fixes the I've fixed the crash in The next crash, in |
comment:50
Replying to @vbraun:
Thank you!
OK, I'll have a look (but the problem is that I can't verify that it fixes a segfault, because I don't get a segfault.
Too bad. There is #11068, which introduces proper support for one- and twosided ideals in non-commutative rings. But that comes much later in my patch chain... Perhaps we can use a temporary workaround: Of course, any additional test will affect the performance. But perhaps it is still acceptable? I think that would be the easiest solution, so, let's do some tests with it. |
comment:51
The crypto fix looks nice. I didn't run the doc tests yet, but "what could possibly go wrong"? I think it should be used even if the segfaults could be used in a different way. That's to say, I will add |
comment:52
I have added a new patch. Since any element has a parent, I do actually not test whether That works, because Since the parent needs to be retrieved anyway, my new patch essentially preserves the performance. So, the additional test is essentially for free. I suppose that my patch would suffice to fix the problem. However, Volker's crypto patch improves the code quality and thus should be included as well. For me, the tests pass when adding Volker's and my patch. But, after all, I did not suffer from the segfault. So, please see if it's fixed! Apply trac11342-attribute_error_message.rebased.patch, trac_11342_fix_pari_initialization.patch, trac_11342_fix_pari_ring.patch, trac_11342_crypto_fixes.patch, trac11342_test_parent_on_getattr.patch |
This comment has been minimized.
This comment has been minimized.
comment:53
Thats not good enough because e.g. the ideals in the quaternion algebra return
and with this ticket it still segfaults. |
comment:54
Replying to @vbraun:
Too bad. Then I'll try the more radical solution and test whether P is None. |
comment:55
And, by the way, even my patch on ideals in non-commutative rings wouldn't solve the problems with Quaternion algebra, since #11068 is about ideals, not fractional ideals. |
Attachment: trac11342_test_parent_on_getattr.patch.gz Test whether self._parent is None, before requestin self._parent._category |
comment:56
I just updated my last patch. It should be absolutely airtight, since it is now explicitly tested whether the parent is None. The timings, which is the main point of this ticket, are still fine. They did almost not change compared with the old patches, but they are much better than with unpatched sage-4.7.2.alpha2:
I hope that the segfaults are finally gone!! Apply trac11342-attribute_error_message.rebased.patch, trac_11342_fix_pari_initialization.patch, trac_11342_fix_pari_ring.patch, trac_11342_crypto_fixes.patch, trac11342_test_parent_on_getattr.patch |
Changed reviewer from Jeroen Demeyer to Jeroen Demeyer, Volker Braun |
comment:58
We should probably merge this ticket first since it is more low-level. I'm happy with it, so positive review for everything except |
comment:59
If it is needed (one could argue that your patches are small enough to be reviewer patches), I give your patches a positive review as well. |
Changed reviewer from Jeroen Demeyer, Volker Braun to Jeroen Demeyer, Volker Braun, Simon King |
Changed author from Simon King to Simon King, Volker Braun |
Merged: sage-4.7.2.alpha3 |
If an attribute of a parent or element can not be found by inspecting the method resolution order,
__getattr__
is invoked. It tries to obtain the attribute from the parent class or the element class of the category of the parent. If it can not be found, the attribute error is raised using a Cython functionsage.structure.parent.raise_attribute_error
.I see several ways to make both
__getattr__
andsage.structure.parent.raise_attribute_error
a lot faster. Details will be given in the comments.Because of one doctest in
sage.categories.primer
, it is needed that the category of polynomial rings is properly initialised. Therefore:Depends on #9944
Apply
Depends on #9944
CC: @jdemeyer
Component: performance
Keywords: getattr parent element
Author: Simon King, Volker Braun
Reviewer: Jeroen Demeyer, Volker Braun, Simon King
Merged: sage-4.7.2.alpha3
Issue created by migration from https://trac.sagemath.org/ticket/11342
The text was updated successfully, but these errors were encountered: