Opened 9 years ago
Closed 9 years ago
#15780 closed enhancement (fixed)
Increase Performance in Projective Morphism
Reported by:  drose  Owned by:  drose 

Priority:  minor  Milestone:  sage6.3 
Component:  algebraic geometry  Keywords:  Projective, Morphism 
Cc:  bhutz  Merged in:  
Authors:  Dillon Rose  Reviewers:  Ben Hutz 
Report Upstream:  N/A  Work issues:  
Branch:  81fba1b (Commits, GitHub, GitLab)  Commit:  81fba1bf7dcba1262da95ed4af0b9bf5566adf43 
Dependencies:  #16051, #16168  Stopgaps: 
Description
Increase Performance in Projective Morphism by replacing all evaluation of polynomials with fast_callable from sage.ext.fast_callable
Change History (41)
comment:1 Changed 9 years ago by
Branch:  → 15780 

comment:2 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:3 Changed 9 years ago by
Branch:  15780 → u/drose/15780 

Cc:  bhutz added 
Component:  performance → algebraic geometry 
Owner:  set to drose 
Priority:  major → minor 
comment:4 Changed 9 years ago by
Commit:  → 5bafb1b5a5001794afd3c75a2d21797772813d47 

comment:5 Changed 9 years ago by
Reviewers:  → Ben Hutz 

Status:  new → needs_review 
I haven't looked closely at functionality yet, but there are a few things that need to be fixed first.
1) There are several doctests that fail with this:
sage t long sage/schemes/elliptic_curves/lseries_ell.py # 1 doctest failed sage t long sage/schemes/plane_conics/con_field.py # 3 doctests failed sage t long sage/schemes/generic/morphism.py # 3 doctests failed
It looks like most of these are because the __call__
in generic\morphism first coerces the input point into the domain and the __call__
in projective\morphism does not. Although the elliptic curve failure seems to be a precision issue.
2) The new functions must have appropriate documentation. See the developers guide for the appropriate format.
SCORE projective_morphism.py: 91.9% (34 of 37)
Missing documentation:
 line 182: def call(self, x, check=True)
 line 187: def _fast_eval(self, x, check=True)
 line 2625: def _fast_eval(self, x, check=True)
3) There are a number of Tab characters in projective_morphism.py
sage t long sage/schemes/projective/projective_morphism.py # Tab character found
comment:6 Changed 9 years ago by
Status:  needs_review → needs_work 

comment:7 Changed 9 years ago by
Commit:  5bafb1b5a5001794afd3c75a2d21797772813d47 → 52ec0b39daba695f9c11a3727304f0b4b9e0deff 

Branch pushed to git repo; I updated commit sha1. New commits:
52ec0b3  trac 15780. Change to projective morphism _call_ function.

comment:8 Changed 9 years ago by
Testing functionality. Everywhere where the evaluation works it gives the right answer. However, there are several places where you can no longer do the evaluation which give a variety of errors. These all previously worked.
T.<z>=PowerSeriesRing(ZZ) P.<x,y>=ProjectiveSpace(T,1) H=End(P) f=H([x^2+x*y,y^2]) Q=P(z,1) f(Q)
T.<z>=LaurentSeriesRing(ZZ) P.<x,y>=ProjectiveSpace(T,1) H=End(P) f=H([x^2+x*y,y^2]) Q=P(z,1) f(Q)
T.<z>=PolynomialRing(Qp(7)) I=T.ideal(z^3) P.<x,y>=ProjectiveSpace(T.quotient_ring(I),1) H=End(P) f=H([x^2+x*y,y^2]) Q=P(z^2,1) f(Q)
T.<z>=PolynomialRing(CC) I=T.ideal(z^3) P.<x,y>=ProjectiveSpace(T.quotient_ring(I),1) H=End(P) f=H([x^2+x*y,y^2]) Q=P(z^2,1) f(Q)
T.<z>=LaurentSeriesRing(CC) R.<t>=PolynomialRing(T) P.<x,y>=ProjectiveSpace(R,1) H=End(P) f=H([x^2+x*y,y^2]) F=f.dehomogenize(1) Q=P(t^2,z) f(Q)
comment:9 Changed 9 years ago by
Commit:  52ec0b39daba695f9c11a3727304f0b4b9e0deff → 5ca376bcfb8e5c4e5c82a7bc36a04cc592994ea9 

Branch pushed to git repo; I updated commit sha1. New commits:
5ca376b  trac 15780. Added documentation.

comment:10 Changed 9 years ago by
Commit:  5ca376bcfb8e5c4e5c82a7bc36a04cc592994ea9 → 888a2abf3c6bdc514168da81171a19d3dad73d08 

Branch pushed to git repo; I updated commit sha1. New commits:
888a2ab  trac 15780. Added documentation to projective morphism.

comment:11 Changed 9 years ago by
Commit:  888a2abf3c6bdc514168da81171a19d3dad73d08 → 87572ab743acf23a63e213f1272192328fde7d49 

Branch pushed to git repo; I updated commit sha1. New commits:
87572ab  trac 15780. Added documentation.

comment:12 Changed 9 years ago by
Dependencies:  → 16051 

Ticket #16051 fixes the functionality issues. So what remains to be done is the list of issues back in comment 5.
comment:13 Changed 9 years ago by
initialization of the fast_polys should probably be done lazily, unless you can show it is always quick. There are many reasons to create morphisms/rational maps that do not involve evaluating them at points. For instance, you might want to take direct or inverse images of subvarieties. For doing that one does not evaluate the defining polynomials, but one does computations with the polynomials. It would be a shame to waste time on computing fast_polys in those cases.
You'd also have to experiment to see if doing this really is an improvement: what you're basically doing is representing the polynomials by predetermined straightline programs, and using those programs regardless of the ring over which the evaluation point is defined. Different rings may benefit from different evaluation strategies. So there's something to be said for deferring the choice of evaluation algorithm until the ring in which this needs to happen is known. Of course, in many common cases the ring for the point is the same as the base ring of the polynomials. Then fast_eval probably does pretty well (also because no intermediate coercions are required).
comment:14 Changed 9 years ago by
Branch:  u/drose/15780 → u/drose/ticket/15780 

Created:  Feb 3, 2014, 2:59:50 PM → Feb 3, 2014, 2:59:50 PM 
Modified:  Apr 3, 2014, 4:43:13 PM → Apr 3, 2014, 4:43:13 PM 
comment:15 Changed 9 years ago by
Commit:  87572ab743acf23a63e213f1272192328fde7d49 → 2993f7593de1e7cc2ea51068b959c14fc7866adf 

Branch pushed to git repo; I updated commit sha1. New commits:
2993f75  Removed more camelCase variables.

comment:16 Changed 9 years ago by
Dependencies:  16051 

comment:17 Changed 9 years ago by
Commit:  2993f7593de1e7cc2ea51068b959c14fc7866adf → 1aaeab2e9eac98286db0f2ab34190e500f4db792 

comment:18 Changed 9 years ago by
Dependencies:  → #16051 

Modified:  Apr 7, 2014, 1:04:36 PM → Apr 7, 2014, 1:04:36 PM 
comment:19 Changed 9 years ago by
Commit:  1aaeab2e9eac98286db0f2ab34190e500f4db792 → 83f8b79aa0c508375c8b99acccbb4925722ddef7 

Branch pushed to git repo; I updated commit sha1. New commits:
83f8b79  Fixed doctests.

comment:20 followup: 22 Changed 9 years ago by
I used timeit on a random degree 3 map on P^{3 and it took 717 microseconds per loop. This is very fast and doesn't really warrant lazy initialization. }
comment:21 Changed 9 years ago by
Branch:  u/drose/ticket/15780 → u/bhutz/ticket/15780 

Commit:  83f8b79aa0c508375c8b99acccbb4925722ddef7 → 6be7361b9186ede2ff230139c7972c9f38fc8f94 
Had some trouble with the rebase, so had to force the push on the branch. I think everything is still correct.
Although there are a couple doctest failures that are still present
generic/morphism.py projective/projective_morphism.py (from the parallel code #15920)
Last 10 new commits:
1ef4bf6  trac 15780. Change to projective morphism _call_ function.

b707ba2  trac 15780. Added documentation.

aaade14  trac 15780. Added documentation to projective morphism.

309f4ed  trac 15780. Added documentation.

e351fcc  Trac 16051: comparing fast_callable constants by value and type

79cbdf3  Trac #16051: changed type to parent for constant comparison

c9cf64e  Removed camelCase variables.

4ffd64c  Removed more camelCase variables.

f7c887e  Fixed doctests.

6be7361  rebase to 6.2.beta7 and remove whitespace

comment:22 Changed 9 years ago by
Replying to drose:
I used timeit on a random degree 3 map on P^{3} and it took 717 microseconds per loop. This is very fast and doesn't really warrant lazy initialization.
Whether 717 ms is a lot depends on what you compare it to. I'm finding (on 6.0):
sage: P5=ProjectiveSpace(Rationals(),5) sage: R=P2.coordinate_ring() sage: mon=[R({tuple(a):1}) for a in WeightedIntegerVectors(4,[1,1,1,1,1,1])] sage: L=[sum(random_sublist(mon,0.1)) for j in [0..5]] sage: %timeit P2.hom(L,P2) 10000 loops, best of 3: 63.3 us per loop sage: %timeit [fast_callable(l) for l in L] 100 loops, best of 3: 1.94 ms per loop
as you see, creating the fast callables is *much* slower than creating the map. If you increase the polynomials in L (by increasing the degree of the monomials, for instance), the difference gets worse. I'd say that's enough time penalty to hold off on it unless you actually need the fast_callables.
comment:23 followup: 24 Changed 9 years ago by
Yes, it is definitely slower than creating the map, but < 1ms didn't seem to be worth bothering over. Note that you wrote 717ms not the actual 717us.
We could put a try/except in call and init them in the except. Any idea how much overhead a try block adds? As far as I can tell in a couple tests it doesn't actually add an execution time. If that's the case, then there is no reason not to do it lazily.
comment:24 Changed 9 years ago by
Replying to bhutz:
We could put a try/except in call and init them in the except. Any idea how much overhead a try block adds? As far as I can tell in a couple tests it doesn't actually add an execution time. If that's the case, then there is no reason not to do it lazily.
Python is designed to let "try" be very fast. If an exception occurs there is a bit larger penalty but in this case it wouldn't be measurable compared to the fast callable
.
The recommended way to store the fast_callable would be by accessing them through a cached_method
or a lazy_attribute
. See their docstrings for examples. Just don't go sticking cached_method
decorators on methods arbitrarily. That's how we get memory leaks :).
comment:25 Changed 9 years ago by
Branch:  u/bhutz/ticket/15780 → u/drose/ticket/15780 

Modified:  Apr 10, 2014, 2:24:13 PM → Apr 10, 2014, 2:24:13 PM 
comment:26 Changed 9 years ago by
Dependencies:  #16051 → #16051, #16168 

comment:27 Changed 9 years ago by
Commit:  6be7361b9186ede2ff230139c7972c9f38fc8f94 → 2a4342e2ec2d4d5d3524ab9a7a0aa6510bd66447 

Status:  needs_work → needs_review 
New commits:
d4c86a3  Fixed error message in __call__.

a82afa0  Added lazy_attribute to fastpolys.

6c0149c  Merge branch 'develop' into ticket/15780

8215514  Fixed parallelizaion using p_iter_fork.

9d93ea5  Minor changes to fix initial bugs in fix.

3fd6fbd  Merge branch 'u/drose/ticket/16168' of git://trac.sagemath.org/sage into ticket/15780

bf3c19f  Changed code to comply with style.

d0489ec  Merge branch 'u/drose/ticket/16168' of git://trac.sagemath.org/sage into ticket/15780

2a4342e  Fixed lazy attribute and merged 16168.

comment:28 Changed 9 years ago by
Status:  needs_review → needs_work 

Functionality all tests out fine. A couple minor issues that need to be addressed
1) _fast_eval does not use the parameter 'check'. Simply remove (from both _fast_eval functions)
2) @lazy_attribute function needs the documentation string + an example
2b) in the @lazy_attribute. Put the 'prime' and 'degree' inside the 'if' block so they are only computed if they are needed.
3) There is an extra blank line in _fast_eval for finite fields that can be removed
4) I'd like to see a few more doctests in _fast_eval. Maybe
a) Powerseries ring
b) quotient ring
You can pull them from comment 8 above.
comment:29 Changed 9 years ago by
 justify constant
2**27
as bound on "no overflow in float" (you should use doubles).  for the sake of defensive programming, would you use
max(abs(c.lift()) for c in coefficients)
instead? max(GF(17)).lift()
happens to work at present, but it doesn't really make mathematical sense.
Also, if you really want to scrape the bottom on this, you should use balanced representatives, also on the coordinates when you fill them in. That would give you a larger range where you can use float.
What you'd really need is a cdef ulong
domain. Then you could just evaluate with 64bit integers, which would give you a much better bound than 2^27
.
comment:30 Changed 9 years ago by
Commit:  2a4342e2ec2d4d5d3524ab9a7a0aa6510bd66447 → 7484355186426d352ae82582722987b7b934e864 

Branch pushed to git repo; I updated commit sha1. New commits:
7484355  Fixed issues reported on trac server comment 28 and 29.

comment:31 Changed 9 years ago by
Commit:  7484355186426d352ae82582722987b7b934e864 → 9be3bba9c7a154309feb9d6e3951f12ed6622a62 

Branch pushed to git repo; I updated commit sha1. New commits:
9be3bba  Changed doctest for fast_eval.

comment:32 Changed 9 years ago by
The previous issues all now test out and my concerns were all addressed. In response to Nils, the 27 is now replaced with the system float precision which is 53 on my 64bit machine. I'm not overly concerned about aggressively optimizing the float usage for speed increase since if the prime is large enough to overrun the height bound for 'reasonable' maps, then the algorithms would never finish anyway (which is what the speed increase is supposed to help). Maps that overrun the bound due to large degree/moderate prime are theoretically fine in the algorithm, but won't get this speed increase and will do the fast_eval over ZZ (or whatever the base ring is).
If you have any other comments on these changes let me know before I mark this as positive.
comment:33 Changed 9 years ago by
Status:  needs_work → positive_review 

comment:34 Changed 9 years ago by
Commit:  9be3bba9c7a154309feb9d6e3951f12ed6622a62 → 857d08c1d774c80701a4034fb0d296985a857195 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
c858d54  Switched parallelization to p_iter_fork.

0a1cf6d  Added documentation on new keyword ncpus.

be46079  moved import to header

857d08c  Merge branch 'u/bhutz/ticket/16168' of git://trac.sagemath.org/sage into ticket/15780

comment:35 Changed 9 years ago by
Commit:  857d08c1d774c80701a4034fb0d296985a857195 → 81fba1bf7dcba1262da95ed4af0b9bf5566adf43 

Branch pushed to git repo; I updated commit sha1. New commits:
81fba1b  Fixed import statements.

comment:37 Changed 9 years ago by
Milestone:  sage6.2 → sage6.3 

comment:38 Changed 9 years ago by
Status:  needs_review → positive_review 

This passes all tests and the changes look fine.
comment:40 Changed 9 years ago by
Status:  needs_work → positive_review 

never mind. I think this is ok. I was concerned about commit 6c0149c
, but it's where it is updated to 6.2.beta8
comment:41 Changed 9 years ago by
Branch:  u/drose/ticket/15780 → 81fba1bf7dcba1262da95ed4af0b9bf5566adf43 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
# Tue Oct 22 20:59:00 2013 0400