On May 5, 2008, at 12:07 PM, John Cremona wrote: > > 2008/5/5 Robert Bradshaw <[EMAIL PROTECTED]>: >> >> On May 5, 2008, at 8:32 AM, John Cremona wrote: >> >>> I took a quick look at Ondrej's detailed changelog, and was >>> interested >>> to see that major speedups had been made by technical-looking >>> changes >>> to __eq__ and __ne__ functions. >>> >>> When I was testing the generic groups code for Sage a month or two >>> ago, using the profiler, I was concerned to see what a large >>> proportion of (say) the generic discrete log function was being >>> spent >>> in testing objects for equality. For example, I effected a >>> significant speedup in a loop which was looking for a match (of an >>> object in a dict() of similar objects) by changing tests of the form >>> if current == target: >>> to >>> if target == current: >>> which is explained, I think, as follows. The first one calls >>> current.__eq__(target) which is a different function every time >>> (since >>> current is changing through the loop while target is not), while the >>> latter calls the same function target.__eq__() with different values >>> of current. >>> >>> A related thing I also noticed at the time was this, in a test where >>> both current and target were points on the same elliptic curve: >>> testing equality went through seemingly endless tests to make sure >>> that the curves were the same, that their base rings were the same, >>> and so on, where in the context this was guaranteed to be true. But >>> as this was a generic function I could not see how to avoid this >>> (perhaps some kind of hash would work: since the generic functions >>> use dict()s the underlying objects must be hashable anyway. >>> >>> This has turned into rather a ramble but might be of some >>> interest to >>> someone out there! >>> >>> John >> >> Elliptic curve points have probably some of the most inefficient >> comparison code in all of Sage... Typically what happens on >> writing a >> == b is the following: >> >> 1) if a.parent() is b.parent(), call the specialized comparison code >> on a._cmp_(b) which forgoes all checks and assumes a and be have the >> same parent (which implies in particular that a and b are the >> same type) >> 2) try and find a cannonical coersion of a and b into the same >> parent >> (the same as if one did a + b) and do the comparison there >> 3) that failing, if a or b is the integer 0, or 1, then try and cast >> that into the parent of the other (this is so P == 0 makes sense for >> P in an elliptic curve, even if there is no canonical coercion ZZ -> >> elliptic curve). It is often faster to use "not P" to determine if P >> is not 0, or "not not P" to determine if P is 0. >> >> Elliptic curve points are particularly messy because their parents >> are homsets (as the points are morphisms) not the curves themselves >> which makes sense mathematically but makes the implementation much >> harder to follow, and, as mentioned above, they are implemented >> to be >> as generic as possible (with it seems little attention given (so >> far) >> to speed). >> >> A specific note on your loop comments, looking for a match by >> doing a >> loop is probably not going to be near as efficient as using a >> dictionary. > > I do use dicts in the giant step stage; but in the baby step stage > when one is creating the dict to be used later, I use == comparison to > catch the unlikely event that we win during the baby step stage. So > doing the loop is the whole point here, as it is creating the dict > which is then used for real later. The baby step stage (creating the > dict) usually takes much linger than the giant step stage (looking > things up in it).
I guess I should have actually looked at your code before commenting on it :-). Hopefully the rest of the comments were at least illuminating (even if elliptic curve point comparison is still dreadfully slow). - Robert --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
