Opened 3 years ago
Closed 3 years ago
#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: |
Description (last modified by )
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 3 years ago by
- 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
comment:2 follow-up: ↓ 3 Changed 3 years ago by
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: ↓ 4 Changed 3 years ago by
Thank you for the comment.
Replying to tscrim:
I am a little hesitant to use
@cached_method
forgen_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 3 years ago by
Replying to mmezzarobba:
Thank you for the comment.
Replying to tscrim:
I am a little hesitant to use
@cached_method
forgen_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 3 years ago by
- Commit changed from 24e633be6d93b0c2aefa12c7dc0d05bbc695cecc to 855d0ed8866dab2abfc850b7db03f828d2947db0
comment:6 Changed 3 years ago by
I'm fine with you suggestion; I just wanted to be sure I understood what you had in mind.
comment:7 Changed 3 years ago by
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 3 years ago by
- Commit changed from 855d0ed8866dab2abfc850b7db03f828d2947db0 to 24e633be6d93b0c2aefa12c7dc0d05bbc695cecc
comment:9 Changed 3 years ago by
Ooooops. Reverted.
comment:10 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
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 3 years ago by
- 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 3 years ago by
- Branch changed from u/mmezzarobba/29011-nfe to 24e633be6d93b0c2aefa12c7dc0d05bbc695cecc
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
#29011 cache number field generator embeddings
#29011 optimize NumberFieldElement.polynomial()