speed up number field element conversions

[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

[mmezzarobba]

New commits:

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

[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

[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?

[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?

[git]

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()

[mmezzarobba]

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

[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.

[git]

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()

[mmezzarobba]

Ooooops. Reverted.

[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

[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.

[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.

[tscrim]

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.