Opened 9 years ago
Closed 6 years ago
#13304 closed defect (fixed)
Very inefficient scalar multiplication on FreeModule_ambient with somewhat large rank
Reported by: | daniels | Owned by: | daniels |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | linear algebra | Keywords: | |
Cc: | jdemeyer | Merged in: | |
Authors: | Daniel Smertnig, Marc Mezzarobba | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | 8f09d51 (Commits, GitHub, GitLab) | Commit: | 8f09d5198e060add5dea75ed240739f6485ba8ce |
Dependencies: | Stopgaps: |
Description
As reported in a thread in sage-support trivial scalar multiplication in FreeModule_ambient
can be extremely slow or lead to out of memory errors:
n = 10000 v = vector([0]*n) # ok so far v2 = v/1 # kaboom
The problem is that, during coercion, _an_element_impl()
and in turn gen(0)
of FreeModule_ambient
gets called. The default implementation of gen
calls basis()
, computing the entire standard basis, and then returns the first basis vector.
Attachments (1)
Change History (29)
Changed 9 years ago by
comment:1 Changed 9 years ago by
comment:2 Changed 9 years ago by
- Status changed from new to needs_review
comment:3 Changed 9 years ago by
The change looks fine to me and passes all tests. Maybe you should
- fill in your real name as Author of this ticket
- add your name to the author section of the file
- mark the doctest with the ticket number as an in-line comment
- explain the speed efficiency gained after applying the patch.
comment:4 follow-up: ↓ 9 Changed 9 years ago by
It's possible that calling base_ring().one_element()
is a bit faster than converting the integer 1 into the ring every time. The method one_element
normally gets cached.
What's more, previously, asking for one basis element triggered basis computation and caching. After that, getting basis elements should be fast. With your patch this caching doesn't get triggered by asking for one basis vector any more. Code that previously benefited m might see a decrease in speed (which can be solved by first explicitly asking for the whole basis to trigger caching).
It might still be a good idea to not cache, but you might document the possible pitfall.
comment:5 Changed 9 years ago by
The question is, in which situations do we actually ask for the basis of the ambient space? I found out that there is a similar problem when constructing subspaces, see sage-devel. Unfortunately, this is not solved with this patch.
Surprisingly, there is a difference between the fields GF(4, 'a')
and QQ
.
comment:6 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:7 Changed 7 years ago by
- Status changed from needs_review to needs_work
(from the previous comments, it looks like the patch in its current state is not waiting for a review)
comment:8 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:9 in reply to: ↑ 4 Changed 7 years ago by
See also #10262.
Replying to nbruin:
What's more, previously, asking for one basis element triggered basis computation and caching. After that, getting basis elements should be fast.
If I understand correctly, the basis we are talking about is essentially the identity matrix. In fact, I am not convinced caching it (strongly at least) is such a good idea even in general—either recomputing it or computing whatever information one really needs instead sounds better in all cases I can think of. But in any case I think it is insane to call a function that may keep in cache a basis of, say, ℤ^{10000}, unless one absolutely needs the whole basis!
comment:10 Changed 7 years ago by
- Branch set to u/mmezzarobba/13304-free_module_ambient+coerce
- Commit set to 8fd7f887c5485001dbb8f6b2919db06ae8e686e2
comment:11 Changed 7 years ago by
- Status changed from needs_work to needs_review
I opened a separate ticket (#15953) for the more general issue of whether and when to cache the basis.
comment:12 Changed 7 years ago by
- Priority changed from minor to major
comment:13 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:14 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:15 Changed 7 years ago by
- Branch changed from u/mmezzarobba/13304-free_module_ambient+coerce to public/ticket/13304
- Commit changed from 8fd7f887c5485001dbb8f6b2919db06ae8e686e2 to 8f09d5198e060add5dea75ed240739f6485ba8ce
comment:16 Changed 6 years ago by
Frédéric, did you review the commits prior to yours?
comment:17 follow-up: ↓ 18 Changed 6 years ago by
- Reviewers set to Vincent Delecroix
- Status changed from needs_review to needs_work
Hello,
You got it right for integer vectors but the generic constructor of FreeModuleElement_generic_dense
does call the basis in a very stupid way
coefficient_ring = parent.basis()[0][0].parent()
In particular the following also takes life time for the very same reason
sage: V = ZZ['x']^50000 sage: V([0]*50000)
comment:18 in reply to: ↑ 17 ; follow-up: ↓ 19 Changed 6 years ago by
Replying to vdelecroix:
You got it right for integer vectors but the generic constructor of
FreeModuleElement_generic_dense
does call the basis in a very stupid waycoefficient_ring = parent.basis()[0][0].parent()In particular the following also takes life time for the very same reason
sage: V = ZZ['x']^50000 sage: V([0]*50000)
Does it make the solution in this ticket inadequate? Or is it just a similar problem that can be handled separately?
comment:19 in reply to: ↑ 18 ; follow-up: ↓ 20 Changed 6 years ago by
Replying to mmezzarobba:
Replying to vdelecroix:
You got it right for integer vectors but the generic constructor of
FreeModuleElement_generic_dense
does call the basis in a very stupid waycoefficient_ring = parent.basis()[0][0].parent()In particular the following also takes life time for the very same reason
sage: V = ZZ['x']^50000 sage: V([0]*50000)Does it make the solution in this ticket inadequate? Or is it just a similar problem that can be handled separately?
Second option. It is just a one line change (that I can even do myself). Do you prefer this one line change to be on another ticket?
comment:20 in reply to: ↑ 19 Changed 6 years ago by
Replying to vdelecroix:
Second option. It is just a one line change (that I can even do myself). Do you prefer this one line change to be on another ticket?
No, please feel free to do it here if you like. (I can't do it myself at the moment.)
comment:21 follow-up: ↓ 22 Changed 6 years ago by
- Cc jdemeyer added
comment:22 in reply to: ↑ 21 Changed 6 years ago by
Replying to vdelecroix:
Wow! Because of #11751 that introduces a very weird behavior the call to
.basis()
is somewhat unavoidable. Jeroen already pointed that out in #11751 and proposed to revert the changes. I am in favor of also reverting the changes. Might be better within another ticket?
The problem mentioned in comment:17 and the follow-ups needs #17585. In the meantime I am running the test for this branch on sage-6.6.beta0 and will set a positive review accordinlgy.
Vincent
comment:23 Changed 6 years ago by
- Status changed from needs_work to positive_review
comment:24 Changed 6 years ago by
I think that #17585 provides a better and more fundamental fix to the problem: the line
coefficient_ring = parent.basis()[0][0].parent()
is just removed completely.
comment:25 follow-up: ↓ 26 Changed 6 years ago by
- Status changed from positive_review to needs_work
- Work issues set to add doctest
comment:26 in reply to: ↑ 25 Changed 6 years ago by
Replying to jdemeyer:
Actually, #17585 fixes
sage: V = ZZ['x']^50000 sage: V([0]*50000)but not
sage: vector([0]*50000)/1Since this ticket looks quite independent of #17585, it makes sense to have both.
I do suggest to add the two doctests above, since they clearly test different issues.
The first one should go in #17585, no?
comment:27 Changed 6 years ago by
- Status changed from needs_work to positive_review
- Work issues add doctest deleted
Sorry, there was a misunderstanding. I thought that this ticket fixed both issues.
comment:28 Changed 6 years ago by
- Branch changed from public/ticket/13304 to 8f09d5198e060add5dea75ed240739f6485ba8ce
- Resolution set to fixed
- Status changed from positive_review to closed
The patch overrides
gen
inFreeModule_ambient
to avoid generating the entire standard basis.