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:  sage9.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: 
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
Authors:  Jeroen Demeyer → Frédéric Chapoton 

Branch:  → u/chapoton/25743 
Commit:  → 04f29f3a7080590fe7532bd24f0c17a69e0cc22a 
Status:  new → needs_review 
comment:2 Changed 23 months ago by
Milestone:  sage8.3 → sage9.3 

comment:4 Changed 23 months ago by
Status:  needs_review → needs_work 

comment:5 Changed 22 months ago by
Authors:  Frédéric Chapoton → Frédéric Chapoton, Travis Scrimshaw 

Branch:  u/chapoton/25743 → public/performance/iteration_ff_proj_space25743 
Commit:  04f29f3a7080590fe7532bd24f0c17a69e0cc22a → def48f4a85ff15df748ff5fd625c735136d6822b 
Reviewers:  → Travis Scrimshaw, Frédéric Chapoton 
Status:  needs_work → needs_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:
def48f4  Speeding up iteration of projective space over finite fields.

comment:6 Changed 22 months ago by
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*(dk), 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:8 Changed 22 months ago by
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
Authors:  Frédéric Chapoton, Travis Scrimshaw → Frédéric Chapoton, Travis Scrimshaw, John Cremona 

Branch:  public/performance/iteration_ff_proj_space25743 → u/cremona/25743 
Commit:  def48f4a85ff15df748ff5fd625c735136d6822b → 37fc4e9f791fa3ace21c2c996bbabb8f9739ae39 
Reviewers:  Travis Scrimshaw, Frédéric Chapoton → Travis 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 checkFalse. (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:
39ecf74  Merge remotetracking branch 'trac/public/performance/iteration_ff_proj_space25743' into 25743

37fc4e9  #25743: more efficient iterators for affine and projective space over finite fields

comment:10 Changed 21 months ago by
Branch:  u/cremona/25743 → public/performance/iteration_ff_affine_proj_space25743 

Commit:  37fc4e9f791fa3ace21c2c996bbabb8f9739ae39 → 1bd776656843a54edade2a70a9394034e10298f1 
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:
1bd7766  Further speedups to affine/projective point enumeration.

comment:11 followup: 12 Changed 21 months ago by
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 ursttransforms 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 Changed 21 months ago by
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 followup: 14 Changed 21 months ago by
Status:  needs_review → positive_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 Changed 21 months ago by
Status:  positive_review → needs_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
This was not necessary. You could set back to positive, in my opinion.
comment:16 Changed 21 months ago by
Commit:  1bd776656843a54edade2a70a9394034e10298f1 → 329f89b72504e0daa6195f924c584a8d90cf008b 

comment:17 Changed 21 months ago by
Status:  needs_work → positive_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 doublechecked by rerunning the tests locally.)
comment:18 Changed 21 months ago by
Branch:  public/performance/iteration_ff_affine_proj_space25743 → 329f89b72504e0daa6195f924c584a8d90cf008b 

Resolution:  → fixed 
Status:  positive_review → closed 
here is a proposal. not yet benchmarked
plus the file is cleaned up a little bit
New commits:
refresh projective_space