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: sage-8.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:

Status badges

Description (last modified by vdelecroix)

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 vdelecroix

  • Description modified (diff)

comment:2 Changed 7 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to u/vdelecroix/18303
  • Description modified (diff)

comment:3 Changed 7 years ago by git

  • Commit set to d4ee0f91df82a54df6c6959a28e72273176e04f4

Branch pushed to git repo; I updated commit sha1. New commits:

a7cbb88Remove _cmp_c_impl and _richcmp_c_impl
9b48fecDoctest .pxd files also
1ad339bImplement _rich_to_bool as inline function instead of member function
17bd067Merge tag '6.7.beta2' into t/17890/ticket/17890
d4ee0f9Trac 18303: faster comparisons of elements in AA

comment:4 Changed 7 years ago by vdelecroix

  • Dependencies set to #17890
  • Description modified (diff)
  • Status changed from new to needs_review

comment:5 Changed 7 years ago by vdelecroix

  • Status changed from needs_review to needs_work

failing doctests

comment:6 Changed 7 years ago by vdelecroix

  • Dependencies changed from #17890 to #17890, #18337

comment:7 Changed 7 years ago by git

  • Commit changed from d4ee0f91df82a54df6c6959a28e72273176e04f4 to b3bfdfd61822dcc7b89746897881f997398cae18

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

203820bTrac 18305: py_rich_to_bool(_sgn) and operators
c6d3e23Trac 18305: use `_cmp_` for alternating sign matrices
f3e46e3Trac 18305: use _cmp_ for ideals of finite dimensional algebras
b0c39b0Trac 18305: _richcmp_ for indexed monoids and groups
220a140Trac 18305: _richcmp_ for Newton polygons
042b6feTrac 18305: modify Element._richcmp so that _richcmp_ can raise errors
7749fe8Trac 18305: _richcmp_ for `finite dimensional algebra elements
81be759Trac 18305: update comments in sage.structure.element
eac87c8Merge #18305 in #18337
b3bfdfdTrac 18303: comparison of algebraic numbers

comment:8 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:9 Changed 7 years ago by chapoton

  • Status changed from needs_review to needs_work

2 failing doctests, see patchbot report

comment:10 Changed 7 years ago by git

  • Commit changed from b3bfdfd61822dcc7b89746897881f997398cae18 to 747c1110f111c8cf676b507f5bd1290bd3027e0c

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

d826520Use LazyFormat for _cmp_ exception
ac9ca1cUpdate comment
89d1b0bTrac 18305: py_rich_to_bool(_sgn) and operators
1078589Trac 18305: use _cmp_ for ideals of finite dimensional algebras
7f6c59fTrac 18305: _richcmp_ for indexed monoids and groups
0fb7c8eTrac 18305: _richcmp_ for Newton polygons
51abce8Trac 18305: _richcmp_ for `finite dimensional algebra elements
0259eb7Trac 18305: update comments in sage.structure.element
52d7168Trac 18303: comparison of algebraic numbers
747c111Trac 18303: fix doctest in matrix and elliptic curves

comment:11 Changed 7 years ago by vdelecroix

  • Dependencies changed from #17890, #18337 to #18305
  • Status changed from needs_work to needs_review

comment:12 Changed 7 years ago by git

  • Commit changed from 747c1110f111c8cf676b507f5bd1290bd3027e0c to 22384295b949c3ed6c06184bc2cac967e9ee86f6

Branch pushed to git repo; I updated commit sha1. New commits:

2238429Trac 18303: typo in the documentation

comment:13 Changed 6 years ago by git

  • Commit changed from 22384295b949c3ed6c06184bc2cac967e9ee86f6 to 53375b042a18ed92b39e27bc108a9904fc94b9fc

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

522d61fTrac 18305: py_rich_to_bool(_sgn) and operators
6089576Trac 18305: use _cmp_ for ideals of finite dimensional algebras
2cc324cTrac 18305: _richcmp_ for indexed monoids and groups
88fd79eTrac 18305: _richcmp_ for Newton polygons
690b959Trac 18305: _richcmp_ for `finite dimensional algebra elements
d768d25Trac #18305: comments about Python comparisons
89c6705Trac 18303: comparison of algebraic numbers
af6e3efTrac 18303: fix doctest in matrix and elliptic curves
53375b0Trac 18303: typo in the documentation

comment:14 Changed 6 years ago by vdelecroix

rebased on the rebased #18305

comment:15 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

does not apply

comment:16 Changed 5 years ago by chapoton

  • 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:

8d2742bTrac 18303: comparison of algebraic numbers (new tentative)

comment:17 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.7 to sage-8.0
  • Status changed from needs_work to needs_review

comment:18 Changed 5 years ago by chapoton

  • Dependencies #18305 deleted

comment:19 Changed 5 years ago by git

  • Commit changed from 8d2742b06e48bdd01ffbdceab84dc531e5cfca85 to ca5b9f69a3328530e82a4305e921642a93f0acec

Branch pushed to git repo; I updated commit sha1. New commits:

ca5b9f6trac 18303 some details

comment:20 Changed 5 years ago by git

  • Commit changed from ca5b9f69a3328530e82a4305e921642a93f0acec to f552e6f2ce479c8ac6517f45ee4dbe655b3c72bf

Branch pushed to git repo; I updated commit sha1. New commits:

f552e6ftrac 18303 more details

comment:21 Changed 5 years ago by chapoton

Vincent, would you have time to make progress here ? Maybe this is close to be ready, but I am not so sure.

This is on the road to #22907, which is on the road to #22297, which is on the long road to python3.

comment:22 Changed 5 years ago by git

  • Commit changed from f552e6f2ce479c8ac6517f45ee4dbe655b3c72bf to 77911f649b2c40004d1912607cd6a351ea31382a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

49979fcTrac 18303: comparison of algebraic numbers (new tentative)
7481c2btrac 18303 some details
77911f6Trac 18303: a simplification, some fixes and more tests

comment:23 Changed 5 years ago by vdelecroix

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 git

  • Commit changed from 77911f649b2c40004d1912607cd6a351ea31382a to 515fb996026d21645e6fe0bc0aca5b58935899a3

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

515fb99Trac 18303: a simplification, some fixes and more tests

comment:25 Changed 5 years ago by chapoton

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 git

  • Commit changed from 515fb996026d21645e6fe0bc0aca5b58935899a3 to 86e541d7697cb0bdc2b4ecbe7c3fc4bec7a26816

Branch pushed to git repo; I updated commit sha1. New commits:

86e541dtrac 18303 fix failing doctests

comment:27 Changed 5 years ago by chapoton

I confirm that the timings are much better.

comment:28 Changed 5 years ago by git

  • Commit changed from 86e541d7697cb0bdc2b4ecbe7c3fc4bec7a26816 to f1a684897f6a2305e4b44c4ec190a7193c205f44

Branch pushed to git repo; I updated commit sha1. New commits:

f1a6848trac 18303 one typo

comment:29 follow-up: Changed 5 years ago by chapoton

I do not understand the doctest block starting with

+        The following are non-trivially zeros (though no exactification occur)::

How are these doctests related to this sentence ?

comment:30 follow-up: Changed 5 years ago by chapoton

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 ; follow-up: Changed 5 years ago by 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.

comment:32 in reply to: ↑ 29 Changed 5 years ago by vdelecroix

Replying to chapoton:

I do not understand the doctest block starting with

+        The following are non-trivially 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 vdelecroix

(I don't understand, I did not receive any notification by mail!)

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:34 in reply to: ↑ 31 Changed 5 years ago by vdelecroix

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 git

  • Commit changed from f1a684897f6a2305e4b44c4ec190a7193c205f44 to 99113f1d434a846d322100a919023c3437c551ad

Branch pushed to git repo; I updated commit sha1. New commits:

99113f1trac 18303: bool vs nonzero + doc

comment:36 follow-ups: Changed 5 years ago by chapoton

I would not have insisted on __nonzero__, but this indeed for python3-readiness.

For the doctests, sorry but I still do not understand. You say morally 'let us check that something is zero non-trivially" 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 vdelecroix

Replying to chapoton:

I would not have insisted on __nonzero__, but this indeed for python3-readiness.

For the doctests, sorry but I still do not understand. You say morally 'let us check that something is zero non-trivially" and then all doctests are of the kind

bool(something)
False

which 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 chapoton

  • 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 python3-readiness.

For the doctests, sorry but I still do not understand. You say morally 'let us check that something is zero non-trivially" and then all doctests are of the kind

bool(something)
False

which mean that something is NOT zero. What am I missing ?

comment:39 Changed 5 years ago by vdelecroix

Will do. Just waiting for quasar.

comment:40 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

quasar is happy! Thanks for the review.

comment:41 Changed 5 years ago by vbraun

  • Branch changed from public/18303 to 99113f1d434a846d322100a919023c3437c551ad
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.