2008/5/5 Robert Bradshaw <[EMAIL PROTECTED]>: > > > 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).
Certainly! One thing lost when moving from an elliptic-curve-specific of this bsgs algorithm was the ability to cheat in such comparisons: within that "internal" function I knew that the points were on the same curve and so sould compare them more simply. But I did check that after applying some profiling and tweaking that the elliptic curve code (for finding the order of a point, for example) was no slower using the generic functions than it had been when elliptic curves had their own discrete log functions. John > > - 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 -~----------~----~----~----~------~----~------~--~---
