#31810 closed enhancement (fixed)

Speedup number field element __getitem__ and for Gaussians

Reported by: Travis Scrimshaw Owned by:
Priority: major Milestone: sage-9.4
Component: performance Keywords: number field element, Gaussian
Cc: Vincent Delecroix, Marc Mezzarobba Merged in:
Authors: Travis Scrimshaw Reviewers: Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: b52d759 (Commits, GitHub, GitLab) Commit: b52d759212a264f3c4805f76393ac327357302c2
Dependencies: #31808 Stopgaps:

Status badges

Description (last modified by Travis Scrimshaw)

Right now we needlessly construct a polynomial to call __getitem__ on a number field element. We can just directly call _coefficients() and return 0 if the index is outside that list.

We also do some other speedups for the Gaussian numbers.

Change History (23)

comment:1 Changed 19 months ago by Travis Scrimshaw

Branch: public/performance/speedups_nf_getitem-31810
Commit: fd038896796f00880f0b83de9f45e5798904a74f
Status: newneeds_review

There is no real dependency on #31808 other than it made things easier for conflicts.

I also did some slight bit of trivial cleanup.


New commits:

157c525Fix conversion of Gaussian number field elements to AA.
fd03889Speedups to NF element __getitem__ and Guassian real/imag.

comment:2 Changed 19 months ago by Vincent Delecroix

Guassians :)

comment:3 Changed 19 months ago by Travis Scrimshaw

Description: modified (diff)
Summary: Speedup number field element __getitem__ and for GuassiansSpeedup number field element __getitem__ and for Gaussians

They are like the Gaussian, but under the nonstandard embedding into correct spelling. :P

I type too quickly and don't proofread as much as I should. Bad habits. ^^;;

comment:4 Changed 19 months ago by Marc Mezzarobba

Reviewers: Marc Mezzarobba
Status: needs_reviewneeds_work

Using parts() to implement __getitem__() changes the output of

sage: K.<a> = NumberField(x^2-x+7)
sage: list(a)
[1/2, 3/2]

(cf. the documentation of parts()).

Last edited 19 months ago by Marc Mezzarobba (previous) (diff)

comment:5 Changed 19 months ago by Samuel Lelièvre

This would be a good opportunity to fix this typo (from #5930 merged in Sage 4.0.rc0):

         Return the real part of ``self``, which is either ``self`` (if
-        ``self`` lives it a totally real field) or a rational number.
+        ``self`` lives in a totally real field) or a rational number.

comment:6 Changed 19 months ago by Travis Scrimshaw

Good catch. I am going to create a subclass for that case since it is something based on the parent and can be decided during the parent initialization. I will also add a doctest for the list(a) and fix the typo (feel free to suggest other things to fix/cleanup too).

comment:7 Changed 19 months ago by git

Commit: fd038896796f00880f0b83de9f45e5798904a74f7b44ccc7670aa7d91071d5844f0909009b1687e3

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

7b44cccMove the is_sqrt_disc() check to the parent (mostly).

comment:8 Changed 19 months ago by git

Commit: 7b44ccc7670aa7d91071d5844f0909009b1687e3044ae53ba7aa59038a5ce2472b921ac54c5ce7f4

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

044ae53Move the is_sqrt_disc() check to the parent (mostly).

comment:9 Changed 19 months ago by Travis Scrimshaw

I have created the subclass that separates the two cases for the number fields. I couldn't think of a good solution in terms of the classes for the Order, so I just left that as a delegation. Likewise for the _coefficients() in the new class; I couldn't see a way to get around that call to get the generator. However, it does remove some checks for calling _coefficients().

I did some other cleanup too. The documentation of is_sqrt_disc() is poor because it does not depend on D. However, I don't know the theory here to be able to change it.

comment:10 Changed 19 months ago by Travis Scrimshaw

Status: needs_workneeds_review

comment:11 Changed 19 months ago by Marc Mezzarobba

I haven't read the code in detail (and I am not really familiar with the theory either), but can you explain why you decided to create a subclass for the case where is_sqrt_disc() is False rather than for the other case? (It seems to me that the code for the case is_sqrt_disc() == False works in the other case too, at least for some methods. Is that correct?)

comment:12 Changed 19 months ago by Travis Scrimshaw

Status: needs_reviewneeds_work

I was thinking of NumberFieldElement_gaussian keeping the same structure, but if I did swap it, I could just put it as a subclass of the new _sqrt class. That is a good idea to swap the two. I will do that, as well as fix the doctest failures.

comment:13 Changed 19 months ago by git

Commit: 044ae53ba7aa59038a5ce2472b921ac54c5ce7f42661da45b41293e2b6224c551414f34ab948f542

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

8e69de0Changing from _nonsqrt to _sqrt and fixing bugs.
2661da4Removed some unneed imports in complex_mpc.pyx.

comment:14 Changed 19 months ago by Travis Scrimshaw

Status: needs_workneeds_review

I have changed it. I also made some simplifications to the Matrix_cyclotomic_dense.set_unsafe() code (mirroring the get_unsafe() implementation) as part of the bug fixing. CyclotomicField(4) now takes advantage of the fact it is the same as QuadraticField(-1) by using the NumberFieldElement_gaussian class.

Timings:

sage: %timeit list(I)
1.46 µs ± 5.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
sage: %timeit I[0]
351 ns ± 2.13 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

versus before:

sage: %timeit list(I)
16 µs ± 58.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit I[0]
7.62 µs ± 91.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

comment:15 Changed 19 months ago by Marc Mezzarobba

Thanks Travis!

The code looks good to me, but I cannot easily run the complete testsuite locally at the moment, so let's wait for the patchbot to wake up.

comment:16 Changed 19 months ago by git

Commit: 2661da45b41293e2b6224c551414f34ab948f542565dcdf9cd45adfe2967afddde3be0100435fc43

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

565dcdfMoving __getitem__ to the sqrt class.

comment:17 Changed 19 months ago by Travis Scrimshaw

Patchbot did have a look at it, and found more errors. These came from the fact I forgot to move the __getitem__ to the _sqrt class. Although debugging this was annoying because of how it was appearing in the polynomial code. Anyways, this should squash all other doctest failures (and hopefully bugs!).

Some other timings:

sage: K.<a> = NumberField(x^5 + x^4 + x^2 - 5)
sage: p = a^5
sage: %timeit list(p)
6.91 µs ± 30.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit p[3]
1.41 µs ± 13.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

sage: K.<a> = QuadraticField(5)
sage: %timeit list(a)
1.45 µs ± 6.69 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
sage: %timeit a[1]
372 ns ± 7.12 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

versus before

sage: %timeit list(p)
41.3 µs ± 561 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
sage: %timeit p[3]
7.94 µs ± 143 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

sage: %timeit list(a)
16.9 µs ± 77.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
sage: %timeit a[1]
7.95 µs ± 57 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

comment:18 Changed 19 months ago by Travis Scrimshaw

Also

sage: K.<a> = NumberField(x^5 + x^4 + x^2 - 5)
sage: p = a^3
sage: %timeit p[4]
1.3 µs ± 4.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

versus before

7.73 µs ± 53 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

comment:19 Changed 19 months ago by git

Commit: 565dcdf9cd45adfe2967afddde3be0100435fc43b52d759212a264f3c4805f76393ac327357302c2

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

b52d759Fixing output type for singular.pyx.

comment:20 Changed 19 months ago by Travis Scrimshaw

Patchbot was green except for one trivial doctest output, which is now fixed:

sage -t --random-seed=0 src/sage/libs/singular/singular.pyx
    [78 tests, 0.09 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.1 seconds
    cpu time: 0.1 seconds
    cumulative wall time: 0.1 seconds

comment:21 Changed 19 months ago by Marc Mezzarobba

Status: needs_reviewpositive_review

There is still a detail that I am not sure I like:

--- a/src/sage/matrix/matrix_cyclo_dense.pyx
+++ b/src/sage/matrix/matrix_cyclo_dense.pyx
-        if type(value) is NumberFieldElement_quadratic:
+        if self._degree == 2:

will lead to crashes if someone force-creates NumberFieldElement_absolute elements of degree two. At the same time, I suppose a call to isinstance() would be slower, and we don't usually support messing with the choice of element classes too much.

So I think this is good to go. Thanks again Travis!

comment:22 Changed 19 months ago by Travis Scrimshaw

Thank you for the review.

It is called set_unsafe() for a reason ;). Yet, that is a good point I hadn't considered. My counterargument would be that we should optimize for assuming it is the correct type of element and if there is a specific need for this, then we can address it later.

comment:23 Changed 18 months ago by Volker Braun

Branch: public/performance/speedups_nf_getitem-31810b52d759212a264f3c4805f76393ac327357302c2
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.