#29011 closed enhancement (fixed)

speed up number field element conversions

Reported by: mmezzarobba Owned by:
Priority: minor Milestone: sage-9.1
Component: basic arithmetic Keywords:
Cc: vdelecroix Merged in:
Authors: Marc Mezzarobba Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 24e633b (Commits, GitHub, GitLab) Commit: 24e633be6d93b0c2aefa12c7dc0d05bbc695cecc
Dependencies: Stopgaps:

Status badges

Description (last modified by mmezzarobba)

These simple changes (especially the first one) lead to surprisingly large speed-ups in real computations (larger speedups, in fact, that I'm able to observe in micro-benchmarks!). For instance, using ore_algebra:

9.1.beta0:

sage: from ore_algebra.examples import cbt
....: dop = cbt.dop[10]
....: s = dop.leading_coefficient().roots(QQbar, multiplicities=False)[0]
....: %time mat = dop.numerical_transition_matrix([0,s], 1e-30)
CPU times: user 2.45 s, sys: 79 µs, total: 2.45 s
Wall time: 2.45 s

with these patches:

sage: from ore_algebra.examples import cbt
....: dop = cbt.dop[10]
....: s = dop.leading_coefficient().roots(QQbar, multiplicities=False)[0]
....: %time mat = dop.numerical_transition_matrix([0,s], 1e-30)
CPU times: user 1.65 s, sys: 8.26 ms, total: 1.66 s
Wall time: 1.66 s

Change History (14)

comment:1 Changed 20 months ago by mmezzarobba

  • Authors set to Marc Mezzarobba
  • Branch set to u/mmezzarobba/29011-nfe
  • Cc vdelecroix added
  • Commit set to 24e633be6d93b0c2aefa12c7dc0d05bbc695cecc
  • Description modified (diff)
  • Priority changed from major to minor
  • Status changed from new to needs_review
  • Summary changed from speed up number field elements to speed up number field element conversions

New commits:

7be3684#29011 cache number field generator embeddings
24e633b#29011 optimize NumberFieldElement.polynomial()

comment:2 follow-up: Changed 20 months ago by tscrim

I am a little hesitant to use @cached_method for gen_embedding because the embedding could, in principle, originally not be defined and then added. In this case, I think it would be best to implement a custom cache:

if self._gen_emb is not None:
    return self._gen_emb
embedding = self.coerce_embedding()
if embedding is None:
    return None
else:
    self._gen_emb = embedding(self.gen())
    return self._gen_emb

comment:3 in reply to: ↑ 2 ; follow-up: Changed 20 months ago by mmezzarobba

Thank you for the comment.

Replying to tscrim:

I am a little hesitant to use @cached_method for gen_embedding because the embedding could, in principle, originally not be defined and then added.

Do you mean by misusing register_embedding() (which is not supposed to be be called after the parent has been “used”), or is there another mechanism I'm unaware of?

comment:4 in reply to: ↑ 3 Changed 20 months ago by tscrim

Replying to mmezzarobba:

Thank you for the comment.

Replying to tscrim:

I am a little hesitant to use @cached_method for gen_embedding because the embedding could, in principle, originally not be defined and then added.

Do you mean by misusing register_embedding() (which is not supposed to be be called after the parent has been “used”), or is there another mechanism I'm unaware of?

Well, I am not sure it is a misuse because suppose you create the field, then try gen_embedding but no embedding is found (which does not use the coercion framework), and then use register_embedding (say, because you forgot to set it) and try gen_embedding again. Granted, this is a very exceptional case, but it could happen. Perhaps it is sufficient to put in a .. WARNING:: about this instructing the user to clear the cache for this method if this does happen?

comment:5 Changed 20 months ago by git

  • Commit changed from 24e633be6d93b0c2aefa12c7dc0d05bbc695cecc to 855d0ed8866dab2abfc850b7db03f828d2947db0

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

dfccd87#29011 cache number field generator embeddings
855d0ed#29011 optimize NumberFieldElement.polynomial()

comment:6 Changed 20 months ago by mmezzarobba

I'm fine with you suggestion; I just wanted to be sure I understood what you had in mind.

comment:7 Changed 20 months ago by tscrim

Now you have it double cached. ;) The more I think about it, the more I am convinced that your original way with a @cached_method was best since my situation is a very special (and somewhat pathological) corner case that we can warn users about and it is the most simple in terms of code. Anyways, feel free to use whichever solution you want, both are good IMO.

comment:8 Changed 20 months ago by git

  • Commit changed from 855d0ed8866dab2abfc850b7db03f828d2947db0 to 24e633be6d93b0c2aefa12c7dc0d05bbc695cecc

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

7be3684#29011 cache number field generator embeddings
24e633b#29011 optimize NumberFieldElement.polynomial()

comment:9 Changed 20 months ago by mmezzarobba

Ooooops. Reverted.

comment:10 Changed 20 months ago by mmezzarobba

I don't have time to investigate what happens right now, but it looks like @cached_method may be doing some magic that makes what you suggested even without a custom cache:

sage: K = NumberField(x^2+7, 'a')
sage: K.gen_embedding()
sage: K.register_embedding(K.embeddings(CC)[0])
sage: K.gen_embedding()
-2.64575131106459*I

comment:11 Changed 20 months ago by tscrim

That is very surprising to me as the @cached_method shouldn't behave any differently when returning None. It is also not like it is returning a variable that has a reference that can be changed either. Well, if this is not an issue then it doesn't need to be documented I guess... Still it would be nice to know why this happens.

comment:12 Changed 20 months ago by tscrim

So I can confirm this in an isolated context:

sage: class Foo(object):
....:     def __init__(self):
....:         self.x = None
....:     @cached_method
....:     def bar(self):
....:         if self.x is None:
....:             return None
....:         return 5
....:     
sage: f = Foo()
sage: f.bar()
sage: f.x = -2
sage: f.bar()
5
sage: class Foo(object):
....:     def __init__(self):
....:         self.x = None
....:     @cached_method
....:     def bar(self):
....:         if self.x is None:
....:             return -1
....:         return 5
....:     
sage: f = Foo()
sage: f.bar()
-1
sage: f.x = 0
sage: f.bar()
-1

However, the same does not hold for @cached_function

sage: x = None
sage: @cached_function
....: def foo():
....:     if x is None:
....:         return None
....:     return 5
....: 
sage: foo()
sage: x = 2
sage: foo()

However, I would say this is a bug with @cached_method because sometimes having a result of None is important and a result of a long computation. This is now #29037. So I would be inclined to leave a warning of the effect This method is cached, so be sure to define the embedding before using it.

comment:13 Changed 20 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Okay from #29037, this is actually documented behavior, but only applies to methods that do not take any arguments. I think it is a likely necessary side-effect of the implementation, so the current state is good as the behavior of @cached_method is documented and it works well with the implementation here.

comment:14 Changed 20 months ago by vbraun

  • Branch changed from u/mmezzarobba/29011-nfe to 24e633be6d93b0c2aefa12c7dc0d05bbc695cecc
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.