Opened 7 years ago
Closed 5 years ago
#18303 closed enhancement (fixed)
faster comparisons in AA and QQbar
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  number fields  Keywords:  
Cc:  gagern, jdemeyer  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  99113f1 (Commits, GitHub, GitLab)  Commit:  99113f1d434a846d322100a919023c3437c551ad 
Dependencies:  Stopgaps: 
Description (last modified by )
The comparisons of elements of AA
can be much faster! We got
old timing
sage: a = AA(125/13) sage: b = AA(3/5) sage: timeit("a < b", repeat=10, number=50000) 50000 loops, best of 10: 15.9 µs per loop sage: a = AA(2).sqrt() sage: timeit("a < b", repeat=10, number=50000) 50000 loops, best of 10: 17.9 µs per loop
new timing
sage: a = AA(125/13) sage: b = AA(3/5) sage: timeit("a < b", repeat=10, number=50000) 50000 loops, best of 10: 680 ns per loop sage: a = AA(2).sqrt() sage: timeit("a < b", repeat=10, number=50000) 50000 loops, best of 10: 686 ns per loop
Also, instead of implementing __cmp__
we implement _cmp_
(that avoids one function call).
see also: #18304 (comparisons involving integers and rationals)
Change History (41)
comment:1 Changed 7 years ago by
 Description modified (diff)
comment:2 Changed 7 years ago by
 Branch set to u/vdelecroix/18303
 Description modified (diff)
comment:3 Changed 7 years ago by
 Commit set to d4ee0f91df82a54df6c6959a28e72273176e04f4
comment:4 Changed 7 years ago by
 Dependencies set to #17890
 Description modified (diff)
 Status changed from new to needs_review
comment:6 Changed 7 years ago by
 Dependencies changed from #17890 to #17890, #18337
comment:7 Changed 7 years ago by
 Commit changed from d4ee0f91df82a54df6c6959a28e72273176e04f4 to b3bfdfd61822dcc7b89746897881f997398cae18
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
203820b  Trac 18305: py_rich_to_bool(_sgn) and operators

c6d3e23  Trac 18305: use `_cmp_` for alternating sign matrices

f3e46e3  Trac 18305: use _cmp_ for ideals of finite dimensional algebras

b0c39b0  Trac 18305: _richcmp_ for indexed monoids and groups

220a140  Trac 18305: _richcmp_ for Newton polygons

042b6fe  Trac 18305: modify Element._richcmp so that _richcmp_ can raise errors

7749fe8  Trac 18305: _richcmp_ for `finite dimensional algebra elements

81be759  Trac 18305: update comments in sage.structure.element

eac87c8  Merge #18305 in #18337

b3bfdfd  Trac 18303: comparison of algebraic numbers

comment:8 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:9 Changed 7 years ago by
 Status changed from needs_review to needs_work
2 failing doctests, see patchbot report
comment:10 Changed 7 years ago by
 Commit changed from b3bfdfd61822dcc7b89746897881f997398cae18 to 747c1110f111c8cf676b507f5bd1290bd3027e0c
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
d826520  Use LazyFormat for _cmp_ exception

ac9ca1c  Update comment

89d1b0b  Trac 18305: py_rich_to_bool(_sgn) and operators

1078589  Trac 18305: use _cmp_ for ideals of finite dimensional algebras

7f6c59f  Trac 18305: _richcmp_ for indexed monoids and groups

0fb7c8e  Trac 18305: _richcmp_ for Newton polygons

51abce8  Trac 18305: _richcmp_ for `finite dimensional algebra elements

0259eb7  Trac 18305: update comments in sage.structure.element

52d7168  Trac 18303: comparison of algebraic numbers

747c111  Trac 18303: fix doctest in matrix and elliptic curves

comment:11 Changed 7 years ago by
 Dependencies changed from #17890, #18337 to #18305
 Status changed from needs_work to needs_review
comment:12 Changed 7 years ago by
 Commit changed from 747c1110f111c8cf676b507f5bd1290bd3027e0c to 22384295b949c3ed6c06184bc2cac967e9ee86f6
Branch pushed to git repo; I updated commit sha1. New commits:
2238429  Trac 18303: typo in the documentation

comment:13 Changed 7 years ago by
 Commit changed from 22384295b949c3ed6c06184bc2cac967e9ee86f6 to 53375b042a18ed92b39e27bc108a9904fc94b9fc
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
522d61f  Trac 18305: py_rich_to_bool(_sgn) and operators

6089576  Trac 18305: use _cmp_ for ideals of finite dimensional algebras

2cc324c  Trac 18305: _richcmp_ for indexed monoids and groups

88fd79e  Trac 18305: _richcmp_ for Newton polygons

690b959  Trac 18305: _richcmp_ for `finite dimensional algebra elements

d768d25  Trac #18305: comments about Python comparisons

89c6705  Trac 18303: comparison of algebraic numbers

af6e3ef  Trac 18303: fix doctest in matrix and elliptic curves

53375b0  Trac 18303: typo in the documentation

comment:14 Changed 7 years ago by
rebased on the rebased #18305
comment:16 Changed 5 years ago by
 Branch changed from u/vdelecroix/18303 to public/18303
 Commit changed from 53375b042a18ed92b39e27bc108a9904fc94b9fc to 8d2742b06e48bdd01ffbdceab84dc531e5cfca85
here is a new tentative based on the existing branch
The idea is to use only rich comparison, and avoid calls to cmp or _cmp_
New commits:
8d2742b  Trac 18303: comparison of algebraic numbers (new tentative)

comment:17 Changed 5 years ago by
 Milestone changed from sage6.7 to sage8.0
 Status changed from needs_work to needs_review
comment:18 Changed 5 years ago by
 Dependencies #18305 deleted
comment:19 Changed 5 years ago by
 Commit changed from 8d2742b06e48bdd01ffbdceab84dc531e5cfca85 to ca5b9f69a3328530e82a4305e921642a93f0acec
Branch pushed to git repo; I updated commit sha1. New commits:
ca5b9f6  trac 18303 some details

comment:20 Changed 5 years ago by
 Commit changed from ca5b9f69a3328530e82a4305e921642a93f0acec to f552e6f2ce479c8ac6517f45ee4dbe655b3c72bf
Branch pushed to git repo; I updated commit sha1. New commits:
f552e6f  trac 18303 more details

comment:21 Changed 5 years ago by
comment:22 Changed 5 years ago by
 Commit changed from f552e6f2ce479c8ac6517f45ee4dbe655b3c72bf to 77911f649b2c40004d1912607cd6a351ea31382a
comment:23 Changed 5 years ago by
Thanks Frédéric for taking care. I squashed your two commits and rebased on 8.0.beta4. The code needed some fix and actually it was possible to get rid of one of the implementation of __nonzero__
.
Needs review again!
comment:24 Changed 5 years ago by
 Commit changed from 77911f649b2c40004d1912607cd6a351ea31382a to 515fb996026d21645e6fe0bc0aca5b58935899a3
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
515fb99  Trac 18303: a simplification, some fixes and more tests

comment:25 Changed 5 years ago by
Merci, Vincent.
 There are now a few trivial failing doctests. Should I take care of them ?
 Did you check that speed is improved ?
comment:26 Changed 5 years ago by
 Commit changed from 515fb996026d21645e6fe0bc0aca5b58935899a3 to 86e541d7697cb0bdc2b4ecbe7c3fc4bec7a26816
Branch pushed to git repo; I updated commit sha1. New commits:
86e541d  trac 18303 fix failing doctests

comment:27 Changed 5 years ago by
I confirm that the timings are much better.
comment:28 Changed 5 years ago by
 Commit changed from 86e541d7697cb0bdc2b4ecbe7c3fc4bec7a26816 to f1a684897f6a2305e4b44c4ec190a7193c205f44
Branch pushed to git repo; I updated commit sha1. New commits:
f1a6848  trac 18303 one typo

comment:29 followup: ↓ 32 Changed 5 years ago by
I do not understand the doctest block starting with
+ The following are nontrivially zeros (though no exactification occur)::
How are these doctests related to this sentence ?
comment:30 followup: ↓ 31 Changed 5 years ago by
I think one should rather keep __bool__
for the name, and {{{nonzero}} only as an alias, as I did.
comment:31 in reply to: ↑ 30 ; followup: ↓ 34 Changed 5 years ago by
Replying to chapoton:
I think one should rather keep
__bool__
for the name, and {{{nonzero}} only as an alias, as I did.
What is the point!? __nonzero__
is standard Python and is used everywhere in Sage.
comment:32 in reply to: ↑ 29 Changed 5 years ago by
Replying to chapoton:
I do not understand the doctest block starting with
+ The following are nontrivially zeros (though no exactification occur)::How are these doctests related to this sentence ?
Because the doctests test whether some quantity is zero. Let me try to rephrase it.
comment:33 Changed 5 years ago by
(I don't understand, I did not receive any notification by mail!)
comment:34 in reply to: ↑ 31 Changed 5 years ago by
Replying to vdelecroix:
Replying to chapoton:
I think one should rather keep
__bool__
for the name, and {{{nonzero}} only as an alias, as I did.What is the point!?
__nonzero__
is standard Python and is used everywhere in Sage.
I see, __nonzero__
does not exists anymore in Python3. But then, will you take care again of removing all aliases __nonzero__ = __bool__
? As this 2to3 move is pretty simple I do not see the point of doing it now.
comment:35 Changed 5 years ago by
 Commit changed from f1a684897f6a2305e4b44c4ec190a7193c205f44 to 99113f1d434a846d322100a919023c3437c551ad
Branch pushed to git repo; I updated commit sha1. New commits:
99113f1  trac 18303: bool vs nonzero + doc

comment:36 followups: ↓ 37 ↓ 38 Changed 5 years ago by
I would not have insisted on __nonzero__
, but this indeed for python3readiness.
For the doctests, sorry but I still do not understand. You say morally 'let us check that something is zero nontrivially" and then all doctests are of the kind
bool(something) False
which mean that something is NOT zero. What am I missing ?
comment:37 in reply to: ↑ 36 Changed 5 years ago by
Replying to chapoton:
I would not have insisted on
__nonzero__
, but this indeed for python3readiness.For the doctests, sorry but I still do not understand. You say morally 'let us check that something is zero nontrivially" and then all doctests are of the kind
bool(something) Falsewhich mean that something is NOT zero. What am I missing ?
bool(0)
>False
bool(1)
>True
comment:38 in reply to: ↑ 36 Changed 5 years ago by
 Reviewers set to Frédéric Chapoton
oh, damn. Must be tired.
Then I think this is ready to go. You can set to positive if you agree.
Replying to chapoton:
I would not have insisted on
__nonzero__
, but this indeed for python3readiness.For the doctests, sorry but I still do not understand. You say morally 'let us check that something is zero nontrivially" and then all doctests are of the kind
bool(something) Falsewhich mean that something is NOT zero. What am I missing ?
comment:39 Changed 5 years ago by
Will do. Just waiting for quasar.
comment:40 Changed 5 years ago by
 Status changed from needs_review to positive_review
quasar is happy! Thanks for the review.
comment:41 Changed 5 years ago by
 Branch changed from public/18303 to 99113f1d434a846d322100a919023c3437c551ad
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Remove _cmp_c_impl and _richcmp_c_impl
Doctest .pxd files also
Implement _rich_to_bool as inline function instead of member function
Merge tag '6.7.beta2' into t/17890/ticket/17890
Trac 18303: faster comparisons of elements in AA