Opened 5 years ago

Closed 4 years ago

#15780 closed enhancement (fixed)

Increase Performance in Projective Morphism

Reported by: drose Owned by: drose
Priority: minor Milestone: sage-6.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) 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 5 years ago by drose

  • Branch set to 15780

comment:2 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 5 years ago by drose

  • Branch changed from 15780 to u/drose/15780
  • Cc bhutz added
  • Component changed from performance to algebraic geometry
  • Owner changed from (none) to drose
  • Priority changed from major to minor

comment:4 Changed 5 years ago by git

  • Commit set to 5bafb1b5a5001794afd3c75a2d21797772813d47

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

5bafb1b# Tue Oct 22 20:59:00 2013 -0400

comment:5 Changed 5 years ago by bhutz

  • Reviewers set to Ben Hutz
  • Status changed from new to 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 5 years ago by bhutz

  • Status changed from needs_review to needs_work

comment:7 Changed 5 years ago by git

  • Commit changed from 5bafb1b5a5001794afd3c75a2d21797772813d47 to 52ec0b39daba695f9c11a3727304f0b4b9e0deff

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

52ec0b3trac 15780. Change to projective morphism _call_ function.

comment:8 Changed 5 years ago by bhutz

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 5 years ago by git

  • Commit changed from 52ec0b39daba695f9c11a3727304f0b4b9e0deff to 5ca376bcfb8e5c4e5c82a7bc36a04cc592994ea9

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

5ca376btrac 15780. Added documentation.

comment:10 Changed 5 years ago by git

  • Commit changed from 5ca376bcfb8e5c4e5c82a7bc36a04cc592994ea9 to 888a2abf3c6bdc514168da81171a19d3dad73d08

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

888a2abtrac 15780. Added documentation to projective morphism.

comment:11 Changed 5 years ago by git

  • Commit changed from 888a2abf3c6bdc514168da81171a19d3dad73d08 to 87572ab743acf23a63e213f1272192328fde7d49

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

87572abtrac 15780. Added documentation.

comment:12 Changed 4 years ago by bhutz

  • Dependencies set to 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 4 years ago by nbruin

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 straight-line 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).

Last edited 4 years ago by nbruin (previous) (diff)

comment:14 Changed 4 years ago by drose

  • Branch changed from u/drose/15780 to u/drose/ticket/15780
  • Created changed from 02/03/14 14:59:50 to 02/03/14 14:59:50
  • Modified changed from 04/03/14 16:43:13 to 04/03/14 16:43:13

comment:15 Changed 4 years ago by git

  • Commit changed from 87572ab743acf23a63e213f1272192328fde7d49 to 2993f7593de1e7cc2ea51068b959c14fc7866adf

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

2993f75Removed more camelCase variables.

comment:16 Changed 4 years ago by drose

  • Dependencies 16051 deleted

comment:17 Changed 4 years ago by git

  • Commit changed from 2993f7593de1e7cc2ea51068b959c14fc7866adf to 1aaeab2e9eac98286db0f2ab34190e500f4db792

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

27663feTrac 16051: comparing fast_callable constants by value and type
9eb0789Trac #16051: changed type to parent for constant comparison
1aaeab2Merge branch 'u/bhutz/ticket/16051' of git://trac.sagemath.org/sage into ticket/15780

comment:18 Changed 4 years ago by drose

  • Dependencies set to #16051
  • Modified changed from 04/07/14 13:04:36 to 04/07/14 13:04:36

comment:19 Changed 4 years ago by git

  • Commit changed from 1aaeab2e9eac98286db0f2ab34190e500f4db792 to 83f8b79aa0c508375c8b99acccbb4925722ddef7

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

83f8b79Fixed doctests.

comment:20 follow-up: Changed 4 years ago by drose

I used timeit on a random degree 3 map on P3 and it took 717 microseconds per loop. This is very fast and doesn't really warrant lazy initialization.

comment:21 Changed 4 years ago by bhutz

  • Branch changed from u/drose/ticket/15780 to u/bhutz/ticket/15780
  • Commit changed from 83f8b79aa0c508375c8b99acccbb4925722ddef7 to 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:

1ef4bf6trac 15780. Change to projective morphism _call_ function.
b707ba2trac 15780. Added documentation.
aaade14trac 15780. Added documentation to projective morphism.
309f4edtrac 15780. Added documentation.
e351fccTrac 16051: comparing fast_callable constants by value and type
79cbdf3Trac #16051: changed type to parent for constant comparison
c9cf64eRemoved camelCase variables.
4ffd64cRemoved more camelCase variables.
f7c887eFixed doctests.
6be7361rebase to 6.2.beta7 and remove whitespace

comment:22 in reply to: ↑ 20 Changed 4 years ago by nbruin

Replying to drose:

I used timeit on a random degree 3 map on P3 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 follow-up: Changed 4 years ago by bhutz

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 in reply to: ↑ 23 Changed 4 years ago by nbruin

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 4 years ago by drose

  • Branch changed from u/bhutz/ticket/15780 to u/drose/ticket/15780
  • Modified changed from 04/10/14 14:24:13 to 04/10/14 14:24:13

comment:26 Changed 4 years ago by drose

  • Dependencies changed from #16051 to #16051, #16168

comment:27 Changed 4 years ago by drose

  • Commit changed from 6be7361b9186ede2ff230139c7972c9f38fc8f94 to 2a4342e2ec2d4d5d3524ab9a7a0aa6510bd66447
  • Status changed from needs_work to needs_review

New commits:

d4c86a3Fixed error message in __call__.
a82afa0Added lazy_attribute to fastpolys.
6c0149cMerge branch 'develop' into ticket/15780
8215514Fixed parallelizaion using p_iter_fork.
9d93ea5Minor changes to fix initial bugs in fix.
3fd6fbdMerge branch 'u/drose/ticket/16168' of git://trac.sagemath.org/sage into ticket/15780
bf3c19fChanged code to comply with style.
d0489ecMerge branch 'u/drose/ticket/16168' of git://trac.sagemath.org/sage into ticket/15780
2a4342eFixed lazy attribute and merged 16168.

comment:28 Changed 4 years ago by bhutz

  • Status changed from needs_review to 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 4 years ago by nbruin

  • 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 64-bit integers, which would give you a much better bound than 2^27.

comment:30 Changed 4 years ago by git

  • Commit changed from 2a4342e2ec2d4d5d3524ab9a7a0aa6510bd66447 to 7484355186426d352ae82582722987b7b934e864

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

7484355Fixed issues reported on trac server comment 28 and 29.

comment:31 Changed 4 years ago by git

  • Commit changed from 7484355186426d352ae82582722987b7b934e864 to 9be3bba9c7a154309feb9d6e3951f12ed6622a62

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

9be3bbaChanged doctest for fast_eval.

comment:32 Changed 4 years ago by bhutz

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 64-bit 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 4 years ago by bhutz

  • Status changed from needs_work to positive_review

comment:34 Changed 4 years ago by git

  • Commit changed from 9be3bba9c7a154309feb9d6e3951f12ed6622a62 to 857d08c1d774c80701a4034fb0d296985a857195
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

c858d54Switched parallelization to p_iter_fork.
0a1cf6dAdded documentation on new keyword ncpus.
be46079moved import to header
857d08cMerge branch 'u/bhutz/ticket/16168' of git://trac.sagemath.org/sage into ticket/15780

comment:35 Changed 4 years ago by git

  • Commit changed from 857d08c1d774c80701a4034fb0d296985a857195 to 81fba1bf7dcba1262da95ed4af0b9bf5566adf43

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

81fba1bFixed import statements.

comment:36 Changed 4 years ago by bhutz

The 16168 changes had not been merged in. Now they are.

comment:37 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:38 Changed 4 years ago by bhutz

  • Status changed from needs_review to positive_review

This passes all tests and the changes look fine.

comment:39 Changed 4 years ago by bhutz

  • Status changed from positive_review to needs_work

need to clean-up the history

comment:40 Changed 4 years ago by bhutz

  • Status changed from needs_work to 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 4 years ago by vbraun

  • Branch changed from u/drose/ticket/15780 to 81fba1bf7dcba1262da95ed4af0b9bf5566adf43
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.