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:

Status badges

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)

trac_13304_gen_speedup.patch (1.8 KB) - added by daniels 9 years ago.

Download all attachments as: .zip

Change History (29)

Changed 9 years ago by daniels

comment:1 Changed 9 years ago by daniels

The patch overrides gen in FreeModule_ambient to avoid generating the entire standard basis.

comment:2 Changed 9 years ago by daniels

  • Status changed from new to needs_review

comment:3 Changed 9 years ago by tfeulner

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.
Last edited 9 years ago by tfeulner (previous) (diff)

comment:4 follow-up: Changed 9 years ago by nbruin

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

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

comment:5 Changed 9 years ago by tfeulner

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 jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:7 Changed 7 years ago by ncohen

  • 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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:9 in reply to: ↑ 4 Changed 7 years ago by mmezzarobba

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 mmezzarobba

  • Authors set to Daniel Smertnig, Marc Mezzarobba
  • Branch set to u/mmezzarobba/13304-free_module_ambient+coerce
  • Commit set to 8fd7f887c5485001dbb8f6b2919db06ae8e686e2

New commits:

3c87ef3Trac 13304: FreeModule_Ambient.gen speedup
8fd7f88Implement reviewer suggestions, + cosmetic changes

comment:11 Changed 7 years ago by mmezzarobba

  • 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 mmezzarobba

  • Priority changed from minor to major

comment:13 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:15 Changed 7 years ago by chapoton

  • Branch changed from u/mmezzarobba/13304-free_module_ambient+coerce to public/ticket/13304
  • Commit changed from 8fd7f887c5485001dbb8f6b2919db06ae8e686e2 to 8f09d5198e060add5dea75ed240739f6485ba8ce

I just made a small clean-up and checked that doc builds and look nice.


New commits:

8fba50fMerge with 6.4.beta4
8f09d51trac #13304 put raise statement into py3 shape, plus minor cleanup

comment:16 Changed 6 years ago by mmezzarobba

Frédéric, did you review the commits prior to yours?

Last edited 6 years ago by mmezzarobba (previous) (diff)

comment:17 follow-up: Changed 6 years ago by vdelecroix

  • 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: Changed 6 years ago by 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 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)

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: Changed 6 years ago by vdelecroix

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

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 mmezzarobba

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: Changed 6 years ago by vdelecroix

  • Cc jdemeyer added

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?

comment:22 in reply to: ↑ 21 Changed 6 years ago by vdelecroix

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 vdelecroix

  • Status changed from needs_work to positive_review

comment:24 Changed 6 years ago by jdemeyer

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: Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work
  • Work issues set to add doctest

Actually, #17585 fixes

sage: V = ZZ['x']^50000
sage: V([0]*50000)

but not

sage: vector([0]*50000)/1

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

comment:26 in reply to: ↑ 25 Changed 6 years ago by vdelecroix

Replying to jdemeyer:

Actually, #17585 fixes

sage: V = ZZ['x']^50000
sage: V([0]*50000)

but not

sage: vector([0]*50000)/1

Since 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 jdemeyer

  • 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 vbraun

  • Branch changed from public/ticket/13304 to 8f09d5198e060add5dea75ed240739f6485ba8ce
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.