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. - Robert > > 2008/5/5 Ondrej Certik <[EMAIL PROTECTED]>: >> >> On Mon, May 5, 2008 at 3:46 PM, mabshoff >> <[EMAIL PROTECTED]> wrote: >>> >>> On May 5, 3:41 pm, "Ondrej Certik" <[EMAIL PROTECTED]> wrote: >>> <SNIP> >>> >>> Hi, >>> >>>> That would indeed be useful. Maybe even links to the respective >>>> commits? :) >>>> >>>> At least I like to browse how each major feature was >>>> implemented, for >>>> learning purposes. In SymPy, we do this: >>>> >>>> http://code.google.com/p/sympy/wiki/Changes >>>> >>>> Linux kernel does it too: >>>> >>>> http://kernelnewbies.org/LinuxChanges >>>> >>>> Ondrej >>> >>> You have a wiki account, don't you? [Ah, that was too easy :)]. >> >> Yeah, at least in SymPy, usually the release manager does this. :) >> >> >>> >>> Seriously: It would be nice, but we have the ticket numbers on the >>> full release notes, so if people are interested they can find the >>> tickets. I think that anyone truly interested will do so, but adding >>> some link to some key tickets would help to point the way. >> >> Right. I am browsing the tickets from time to time, too see if there >> were any comments during the review and to see the patch. However, >> some patches are (or used to be) mercurial bundles, and I don't want >> to download it and try to apply it. >> >> But anyway, that's just a wishlist. >> >> Ondrej >> >> >> >>> >> > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
