Integer and Rational comparisons

[videlec]

MPIR 3.0.0 is shipped with the function mpq_cmp_z(mpq_t, mpz_t). We can use it to make integer/rational comparisons much faster.

Comparing integers is very fast, comparing rationals is very fast but comparing integer with rational is about 5x slower:

sage: a = 1; b = 18
sage: timeit("a < b", number=500000, repeat=100)
500000 loops, best of 100: 64.3 ns per loop
sage: a = QQ(1); b = QQ(18)
sage: timeit("a < b", number=500000, repeat=100)
500000 loops, best of 100: 84 ns per loop
sage: a = 1; b = QQ(18)
sage: timeit("a < b", number=500000, repeat=100)
500000 loops, best of 100: 405 ns per loop

With the branch applied, it gets better

sage: a = 1; b = 18
sage: timeit("a < b", number=500000, repeat=100)
500000 loops, best of 100: 64 ns per loop
sage: a = QQ(1); b = QQ(18)
sage: timeit("a < b", number=500000, repeat=100)
500000 loops, best of 100: 65.6 ns per loop
sage: a = 1; b = QQ(18)
sage: timeit("a < b", number=500000, repeat=100)
500000 loops, best of 100: 87.1 ns per loop

CC: @jdemeyer

Component: performance

Author: Vincent Delecroix

Branch/Commit: e72c82d

Reviewer: Marc Mezzarobba, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/18304

[videlec]

Author: Vincent Delecroix

[videlec]

Branch: u/vdelecroix/18304

[sagetrac-git]

Commit: dbb7831

[sagetrac-git]

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

a7cbb88	Remove _cmp_c_impl and _richcmp_c_impl
9b48fec	Doctest .pxd files also
1ad339b	Implement _rich_to_bool as inline function instead of member function
17bd067	Merge tag '6.7.beta2' into t/17890/ticket/17890
dbb7831	Trac 18304: faster comparisons Integer <-> Rational

[sagetrac-git]

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

313a400	Optimize rich_to_bool_sgn
629f6a5	Improve comparisons for permutation groups
0d1e049	Improve _richcmp and documentation
39273f1	Fix doctest formatting
04570b3	Fix bad doctest in etaproducts
3976f2c	Add pointers for special uses of __richcmp__
7e8315f	Merge branch 'u/jdemeyer/ticket/17890' into sage-6.7.beta3
554c435	Trac 18304: faster comparisons for Rational

[sagetrac-git]

Changed commit from dbb7831 to 554c435

[mezzarobba]

comment:6

It's not really a big deal, but I'm not much of a fan of these global mpz_tmp/mpq_tmp: this is one more thing that will break if it ever becomes possible to have multi-threaded sage code... Did you check if there is a measurable performance benefit?

Also, couldn't __richcmp__ just call itself instead of having duplicate code to handle the case where right is of the type defined by the class?

By the way, if you make further changes, perhaps you could take the occasion to make _cmp_ use rich_to_bool_sign too.

[videlec]

comment:7

Hello,

Replying to @mezzarobba:

It's not really a big deal, but I'm not much of a fan of these global mpz_tmp/mpq_tmp: this is one more thing that will break if it ever becomes possible to have multi-threaded sage code...

Me neither (and there is actually one in sage.rings.integer that is not from me). The ideal would be for gmp/mpir to provide a mpq_cmp_mpz. Do you think that it is reasonable to ask them?

Did you check if there is a measurable performance benefit?

It is minor but timings are in the ticket description. In a more concrete situation

sage: l = [ZZ.random_element() for _ in range(100)]
sage: l.extend(QQ.random_element() for _ in range(100))
sage: shuffle(l)
sage: %time l.sort()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 1.21 ms

compared to

sage: %time l.sort()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 247 µs

Also, couldn't __richcmp__ just call itself instead of having duplicate code to handle the case where right is of the type defined by the class?

I do not know why it was done this way for integers. I just naively used the implementation of Integer.__richcmp__ as a template.

By the way, if you make further changes, perhaps you could take the occasion to make _cmp_ use rich_to_bool_sign too.

Yes.

[videlec]

comment:8

Replying to @videlec:

By the way, if you make further changes, perhaps you could take the occasion to make _cmp_ use rich_to_bool_sign too.

Yes.

Actually, no. Because it is not a rich comparison but just comparison.

[mezzarobba]

comment:9

Replying to @videlec:

Me neither (and there is actually one in sage.rings.integer that is not from me).

Yes, I saw that.

The ideal would be for gmp/mpir to provide a mpq_cmp_mpz. Do you think that it is reasonable to ask them?

I have no idea.

Did you check if there is a measurable performance benefit?

It is minor but timings are in the ticket description.

No, I mean specifically for using a global temporary variable instead of creating a new one each time.

[mezzarobba]

comment:10

Replying to @videlec:

Replying to @videlec:

By the way, if you make further changes, perhaps you could take the occasion to make _cmp_ use rich_to_bool_sign too.

Yes.

Actually, no. Because it is not a rich comparison but just comparison.

Right, sorry.

[videlec]

comment:11

With

sage: l = [ZZ.random_element() for _ in range(100)]
sage: l.extend(QQ.random_element() for _ in range(100))

declaring global mpz_tmp and mpq_tmp I got

timeit("shuffle(l); l.sort()", number=5000, repeat=10)
5000 loops, best of 10: 131 µs per loop

and with local ones

sage: timeit("shuffle(l); l.sort()", number=5000, repeat=10)
5000 loops, best of 10: 177 µs per loop

Note that this bad scenario only occurs for comparisons of:

• Python long with Sage Integer
• Sage Rationals with Sage Integer, Python int, Python long

There is a slightly another annoying thing with the global mpz_tmp/mpq_tmp: mpir/gmp do not free the memory of a mpz/mpq if it is not asked explicitely. So if you compare a very big rational with a very big integer you will occupy some memory for the rest of the Sage session (similarly for a big Python long with a big Sage Integer).

I will try harder to see if there is a way to tweak mpir to avoid the creation of anything when we want to compare mpz to mpq. I think that having slow comparison Python long / Sage integer is not an issue. In other words, we should get rid of these global variables.

Vincent

[sagetrac-git]

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

cf21996	Trac 18304: mpir patch for mpq_cmp_mpz
e03a26e	Trac 18304: faster comparisons for Integer/Rational

[sagetrac-git]

Changed commit from 554c435 to e03a26e

[mezzarobba]

comment:15

Hi Vincent,

Do you still want to patch mpir after the answers you got on mpir-devel and gmp-devel? If you do: would the code from this ticket still work if sage is built with gmp?

[sagetrac-git]

Changed commit from 81b637b to e2b7230

[sagetrac-git]

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

575d855

Trac 18304: faster comparisons for Integer/Rational

[sagetrac-git]

Changed commit from e2b7230 to 575d855

[videlec]

Changed dependencies from #22493 to none

[tscrim]

comment:28

Overall, I think this is ready to go into Sage. However, close to the realm of bikeshedding, I would change:

-if not isinstance(left, Rational):
-   raise RuntimeError('this should not happen')
+assert isinstance(left, Rational)

[sagetrac-git]

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

8c60c6a

Trac 18304: faster comparisons for Integer/Rational

[sagetrac-git]

Changed commit from 575d855 to 8c60c6a

[sagetrac-git]

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

6294a5f

Trac 18304: faster comparisons for Integer/Rational

[sagetrac-git]

Changed commit from 8c60c6a to 6294a5f

[videlec]

comment:31

rebased on 8.0.beta10 (and incorported your comment:28)

[tscrim]

comment:32

Thanks. However, I just had a strong sense of dread come over me when I thought about why the old code was checking left/right. In code like __eq__, Python will sometimes swap the arguments, see:

https://eev.ee/blog/2012/03/24/python-faq-equality/

I do not know if this is done for __richcmp__ with extension classes, but I probably won't be able to look into this until tomorrow.

[fchapoton]

comment:33

does not build, due to a changed import (richcmp stuff is now in sage.structure.richcmp)

[sagetrac-git]

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

e72c82d

Trac 18304: faster comparisons for Integer/Rational

[sagetrac-git]

Changed commit from 6294a5f to e72c82d

[videlec]

comment:35

Indeed. I rebased on 8.0.beta11.

[tscrim]

Reviewer: Marc Mezzarobba, Travis Scrimshaw

[tscrim]

comment:36

Hmm...I could've sworn Python sometimes flips inputs for something like __eq__, but maybe I am thinking of some other operation. Anyways, looks good and ready to be merged.

[vbraun]

Changed branch from u/vdelecroix/18304 to e72c82d