Opened 4 years ago

Closed 21 months ago

#25743 closed enhancement (fixed)

Speed up iteration of ProjectiveSpace_finite_field

Reported by: Jeroen Demeyer Owned by:
Priority: major Milestone: sage-9.3
Component: performance Keywords:
Cc: Merged in:
Authors: Frédéric Chapoton, Travis Scrimshaw, John Cremona Reviewers: Travis Scrimshaw, Frédéric Chapoton, John Cremona
Report Upstream: N/A Work issues:
Branch: 329f89b (Commits, GitHub, GitLab) Commit: 329f89b72504e0daa6195f924c584a8d90cf008b
Dependencies: Stopgaps:

Status badges

Description

While implementing some algorithm involving projective spaces, I noticed that 90% of the time was simply spent enumerating the points of a projective space.

Change History (18)

comment:1 Changed 23 months ago by Frédéric Chapoton

Authors: Jeroen DemeyerFrédéric Chapoton
Branch: u/chapoton/25743
Commit: 04f29f3a7080590fe7532bd24f0c17a69e0cc22a
Status: newneeds_review

here is a proposal. not yet benchmarked

plus the file is cleaned up a little bit


New commits:

04f29f3refresh projective_space

comment:2 Changed 23 months ago by Frédéric Chapoton

Milestone: sage-8.3sage-9.3

comment:3 Changed 23 months ago by Frédéric Chapoton

apparently not faster at all

comment:4 Changed 23 months ago by Frédéric Chapoton

Status: needs_reviewneeds_work

comment:5 Changed 22 months ago by Travis Scrimshaw

Authors: Frédéric ChapotonFrédéric Chapoton, Travis Scrimshaw
Branch: u/chapoton/25743public/performance/iteration_ff_proj_space-25743
Commit: 04f29f3a7080590fe7532bd24f0c17a69e0cc22adef48f4a85ff15df748ff5fd625c735136d6822b
Reviewers: Travis Scrimshaw, Frédéric Chapoton
Status: needs_workneeds_review

This branch speeds up the iteration ~5x on this example:

sage: PS = ProjectiveSpace(3, GF(71))
sage: %time L = list(PS)
CPU times: user 2.32 s, sys: 27.3 ms, total: 2.35 s
Wall time: 2.35 s

vs before

CPU times: user 10.6 s, sys: 18.2 ms, total: 10.6 s
Wall time: 10.6 s

Basically I avoid the checks, as well as more directly call the corresponding constructor since none of the points will by infinity. Feel free to merge this with your other cleanup stuff.


New commits:

def48f4Speeding up iteration of projective space over finite fields.

comment:6 Changed 22 months ago by John Cremona

The element constructors for affine and projetive space are very slow. They go back to the very early days of Sage when this sort of thing was done in a very highbrow schemey way, at the expense of speed. For example

sage: F = GF(73)                                                                                                                                      
sage: %time L = list(cartesian_product_iterator([F for _ in range(3)]))                                                                               
CPU times: user 189 ms, sys: 24.1 ms, total: 213 ms
Wall time: 212 ms
sage: A = AffineSpace(F,3)                                                                                                                            
sage: %time L = [A(v) for v in cartesian_product_iterator([F for _ in range(3)])]                                                                     
CPU times: user 10.8 s, sys: 47.9 ms, total: 10.8 s
Wall time: 10.8 s
sage: len(L)                                                                                                                                          
389017

So calling the constructor 389000 times results in a 10s run time. Using A.point(v) is not much better, but with check=False we do gain:

sage: %time L = [A.point(v) for v in cartesian_product_iterator([F for _ in range(3)])]                                                               
CPU times: user 9.07 s, sys: 47.8 ms, total: 9.12 s
Wall time: 9.12 s
sage: %time L = [A.point(v, check=False) for v in cartesian_product_iterator([F for _ in range(3)])]                                                  
CPU times: user 3 s, sys: 64 ms, total: 3.07 s
Wall time: 3.07 s

So we could replace the current iterator for affine space over a finite field with this:

def aff_iter(A):
    F = A.base_ring()
    d = A.dimension()
    for v in cartesian_product_iterator([F for _ in range(d)]):
        yield A.point(v, check=False)

and now

sage: %time L=list(aff_iter(A))                                                                                                                       
CPU times: user 2.62 s, sys: 60.1 ms, total: 2.68 s
Wall time: 2.68 s

Similarly for projective space, here is a new iterator, using the affine one:

def proj_iter(P):
    F = P.base_ring()
    d = P.dimension()
    one = (F.one(),)
    zero = (F.zero(),)
    for k in range(d+1): # position of last 1 before the 0's
        for v in cartesian_product_iterator([F for _ in range(k)]):
            yield P.point(v + one + zero*(d-k), check=False)

after which

sage: P = ProjectiveSpace(GF(73), 3)                                                                                                                  
sage: %time oldL=list(P)                                                                                                                              
CPU times: user 11.6 s, sys: 63.8 ms, total: 11.6 s
Wall time: 11.6 s
sage: %time L=list(proj_iter(P))                                                                                                                      
CPU times: user 2.31 s, sys: 76.3 ms, total: 2.38 s
Wall time: 2.38 s
sage: Set(L)==Set(oldL)                                                                                                                               
True

I think my code is a lot easier to read than the old version, or the proposed adjustment to it -- shall we replace these two iterator methods with new version based on what I wrote?

comment:7 Changed 22 months ago by Travis Scrimshaw

Please go ahead and make those changes.

comment:8 in reply to:  7 Changed 22 months ago by John Cremona

Replying to tscrim:

Please go ahead and make those changes.

Will do. Since the new iterators will deliver the elements in a different order I'll be sure to check all doctests.

comment:9 Changed 22 months ago by John Cremona

Authors: Frédéric Chapoton, Travis ScrimshawFrédéric Chapoton, Travis Scrimshaw, John Cremona
Branch: public/performance/iteration_ff_proj_space-25743u/cremona/25743
Commit: def48f4a85ff15df748ff5fd625c735136d6822b37fc4e9f791fa3ace21c2c996bbabb8f9739ae39
Reviewers: Travis Scrimshaw, Frédéric ChapotonTravis Scrimshaw, Frédéric Chapoton, John Cremona

I made te changes I suggesed for both affine and projective space. A small number of doctest outputs had to be changed since the order of iteration is now different, though I adjusted the code from what I had posted here to make the changes fewer.

For the original time tests, on the machine I was using we have the old version (9.2)

sage: PS = ProjectiveSpace(3, GF(71))                                                                                                                 
sage: %time L = list(PS)                                                                                                                              
CPU times: user 9.98 s, sys: 51.3 ms, total: 10 s
Wall time: 10 s

and the new

sage: PS = ProjectiveSpace(3, GF(71))                                                                                                                 
sage: %time L = list(PS)                                                                                                                              
CPU times: user 3.09 s, sys: 56.1 ms, total: 3.14 s
Wall time: 3.14 s

which I know is not so good a speedup as before. If someone else wants to try to improve it further, they are welcome, but the time is all in the 363024 calls to the point constructor which is slow even with check-False. (For this reason, the class for points on elliptic curves is not a specialization of the scheme point class -- it is rather ridiculous that it takes so long to construct a point when you do not even check that equations are satisfied.)

By the way, one thing I tried which definitely did not work is to construct one point outside the loop and then only assign its coordinates in the loop before yielding it. The result is that all the points delivered are the same (pointers). Adding in a copy() calls the constructor again...

The commit I made in u/cremona/25743 builds on the previous branch here, so it has Frédéric's tidying up in the projective_space file, but I did not do similar in the affine_space file.


New commits:

39ecf74Merge remote-tracking branch 'trac/public/performance/iteration_ff_proj_space-25743' into 25743
37fc4e9#25743: more efficient iterators for affine and projective space over finite fields

comment:10 Changed 21 months ago by Travis Scrimshaw

Branch: u/cremona/25743public/performance/iteration_ff_affine_proj_space-25743
Commit: 37fc4e9f791fa3ace21c2c996bbabb8f9739ae391bd776656843a54edade2a70a9394034e10298f1

So ~19% of the time is spent in the

sage.schemes.generic.homset.SchemeHomset_generic.__call__

most likely because of the

from sage.structure.parent import Set_generic

local import. So just moving that to the top of the file makes it go from 3.5s to 3s (via %prun).

Next, I just avoided the intermediate step through the homset's _element_constructor_ and just built the point directly.

I also do some other changes to be more lazily about stuff. I strongly suspect the (co)domain attributes of SchemeMorphism can be standard morphisms with maybe an added _domain. So these are now both ~2x faster for me. Although it seems like it makes more sense to have _point be an attribute to the class, which will shave off even more time.


New commits:

1bd7766Further speedups to affine/projective point enumeration.

comment:11 Changed 21 months ago by John Cremona

Well done, I am happy to see the further improvement. I do also think that the default point constructor for such a scheme should use the mechanism used here -- users should be able to write their own loops constructing points via A(coords_list) without having to go through the homset/codomain construction, which is rather obscure.

(I think that just about the first ever Sage development I did in 2007 was adding proper support for urst-transforms on elliptic curves, when I noted that one way to recover the curve from a point P on it was to use P.codomain()!)

comment:12 in reply to:  11 Changed 21 months ago by Travis Scrimshaw

Replying to cremona:

Well done, I am happy to see the further improvement. I do also think that the default point constructor for such a scheme should use the mechanism used here -- users should be able to write their own loops constructing points via A(coords_list) without having to go through the homset/codomain construction, which is rather obscure.

I am not quite sure what you are suggesting here. Are you saying the current version is sufficient or is there something else to be done?

Also, green patchbot.

comment:13 Changed 21 months ago by John Cremona

Status: needs_reviewpositive_review

I did not mean to delay this ticket, just perhaps suggesting that another ticket making it easy to construct points on schemes more efficiently might be worth while. As you have been thinking about what would be needed, you might be the one to do that, but that is up to you of course.

comment:14 in reply to:  13 Changed 21 months ago by Travis Scrimshaw

Status: positive_reviewneeds_work

Replying to cremona:

I did not mean to delay this ticket, just perhaps suggesting that another ticket making it easy to construct points on schemes more efficiently might be worth while. As you have been thinking about what would be needed, you might be the one to do that, but that is up to you of course.

That is no problem. I just wasn't sure of your intentions. I agree that would be a good thing to have.

I did just notice that Frédéric's cleanup did not get merged in. I will do this on Monday (unless someone else does it first). So I am just temporarily reverting the positive review until I do that.

comment:15 Changed 21 months ago by Frédéric Chapoton

This was not necessary. You could set back to positive, in my opinion.

comment:16 Changed 21 months ago by git

Commit: 1bd776656843a54edade2a70a9394034e10298f1329f89b72504e0daa6195f924c584a8d90cf008b

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

04f29f3refresh projective_space
329f89bMerge branch 'u/chapoton/25743' of git://trac.sagemath.org/sage into public/performance/iteration_ff_affine_proj_space-25743

comment:17 Changed 21 months ago by Travis Scrimshaw

Status: needs_workpositive_review

I merged in Frédéric's branch. Since I had already reviewed it, I am allowing myself to set this back to positive review. (I also double-checked by re-running the tests locally.)

comment:18 Changed 21 months ago by Volker Braun

Branch: public/performance/iteration_ff_affine_proj_space-25743329f89b72504e0daa6195f924c584a8d90cf008b
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.