Opened 9 years ago

Closed 6 years ago

#10262 closed enhancement (duplicate)

memory leak in scalar*vector multiplication

Reported by: dimpase Owned by: jason, was
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: linear algebra Keywords: linear algebra, memory leak
Cc: mderickx Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13304 Stopgaps:

Description

Here is an example

sage: for i in range(1,8):
    A=(1/2)*vector([x/2 for x in range(i*1000)])
    get_memory_usage()
....:     
921.53125
1287.4765625
2111.984375
3577.546875
5867.19140625
9164.109375
... (killed, due to running out of memory)

The printed numbers in Mb. Needless to say:

sage: for i in range(1,8):
....:     A=vector([x/2 for x in range(i*1000)])
....:     get_memory_usage()
....:     
828.91015625
829.4453125
829.73046875
830.0
830.55859375
830.75
831.0078125

works as expected. (This is with Sage 4.6 on x64, but is not limited to this particular platform: see https://groups.google.com/group/sage-devel/browse_thread/thread/e86f13c78b92a8bb?hl=en. Sage 4.5.3 shows the same behaviour.)

Attachments (1)

10548-coerce-traceback-doctest.patch (1.0 KB) - added by mderickx 9 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 9 years ago by dimpase

  • Summary changed from memory leak in scalar*vector mutiplication to memory leak in scalar*vector multiplication

comment:2 Changed 9 years ago by drkirkby

FWIW, I've found when building on Solaris with a special library for memory allocation, which allows leaks to be detected, before I got to the

sage: 

there was already memory leaked. I think it was only 14 bytes, but once I did a few calculations, more showed up. I think there are quite a few in Sage. Of course, some are more serious than others, but whatever the amount of memory leaked, it shows there's a coding error.

Dave

comment:3 follow-up: Changed 9 years ago by jason

As I mentioned on the thread, I tracked this down to a call from the coercion system to create an element of the parent. The coercion system did this when it was trying to figure out the action of the number on the vector:

The problem seems to stem from the lines

     cdef Element x = X.an_element()
     cdef Element y = Y.an_element()

inside of the detect_element_action function in coerce_actions.pyx. Notice:

sage: v=vector(range(10000))
sage: get_memory_usage()
206.84765625
sage: w=v.parent().an_element()
sage: get_memory_usage()
3321.14453125 

comment:4 in reply to: ↑ 3 ; follow-up: Changed 9 years ago by dimpase

Replying to jason:

As I mentioned on the thread, I tracked this down to a call from the coercion system to create an element of the parent.

So w is a 10000 long vector over "ambient_pid_with_category". I'd call this alone a bug, for this is horribly inefficient. Coercion for module operation could be much better...

My guess is that "an_element()" gets memoised, and retained instead of being destroyed at each for-loop. Indeed:

sage: for i in [1,2,3,4,1,2,3,4]:
....:     
....:     A=(1/2)*vector([x/2 for x in range(i*1000)])
....:     get_memory_usage()
....:     
261.58984375
513.59765625
1073.109375
2057.37890625
2057.37890625
2057.37890625
2057.37890625
2057.62890625
sage: for i in [1,3,5,1,3,5]:
    A=(1/2)*vector([x/2 for x in range(i*1000)])
    get_memory_usage()
....:     
2057.62890625
2057.62890625
3614.55078125
3614.55078125
3614.80078125
3615.05078125

So we get these huge vectors clogging up the memory, in hope that someone might want to compute in the free modules (over ambient_pid_with_category) of these dimensions again...

Should one just turn the memoisation for modules off completely? This would not cure the coercion inefficiency completely, but at least would prevent this leak...

comment:5 follow-up: Changed 9 years ago by jdemeyer

  • Priority changed from blocker to major

Why is this a blocker?

comment:6 in reply to: ↑ 5 Changed 9 years ago by dimpase

  • Type changed from defect to enhancement

Replying to jdemeyer:

Why is this a blocker?

it is not, indeed. After investigating what happens, I forgot to change it to major, sorry.

comment:7 Changed 9 years ago by mderickx

This might also be related to #10570 since that ticket shows that there are call stack frames in the coerce_actions framework which stay alive for some reason.

comment:8 Changed 9 years ago by mderickx

  • Cc mderickx added

Changed 9 years ago by mderickx

comment:9 Changed 9 years ago by mderickx

sorry uploaded a patch to the wrong ticket

comment:10 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:11 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:12 in reply to: ↑ 4 Changed 6 years ago by mmezzarobba

Replying to dimpase:

My guess is that "an_element()" gets memoised, and retained instead of being destroyed at each for-loop.

At least with #14711, the parent and its cached elements appear to be correctly destroyed after each loop turn. However, calling an_element() triggers the computation of a basis, and the whole basis is cached!

sage: for i in [4, 3, 2, 1, 4, 3, 2, 1]:
    del A; gc.collect(); A=(1/2)*vector([x/2 for x in range(i*1000)]); get_memory_usage()
....:     
4029
2483.984375
4030
1842.5390625
3030
1831.33203125
2030
1831.33203125
1030
2483.984375
4030
1842.54296875
3030
1831.33203125
2030
1831.33203125

Possible quick fix, with some code duplication:

  • src/sage/modules/free_module.py

    diff --git a/src/sage/modules/free_module.py b/src/sage/modules/free_module.py
    index a61b433..81a626c 100644
    a b class FreeModule_ambient(FreeModule_generic): 
    44094409        """
    44104410        return self
    44114411
     4412    def gen(self, i):
     4413        if i < 0 or i >= self.rank():
     4414            raise ValueError, "Generator %s not defined."%i
     4415        v = self.zero().__copy__()
     4416        v[i] = self.base_ring()(1)
     4417        v.set_immutable()
     4418        return v
     4419
    44124420    def basis(self):
    44134421        """
    44144422        Return a basis for this ambient free module.

But I am not convinced it is such a good idea in general to cache the basis of a FreeModule_ambient...

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

comment:13 Changed 6 years ago by mmezzarobba

Turns out there is already a more polished version of the fix I was suggesting at #13304.

comment:14 Changed 6 years ago by mmezzarobba

  • Milestone changed from sage-6.2 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

comment:15 follow-up: Changed 6 years ago by dimpase

  • Dependencies set to 13304
  • Status changed from needs_review to needs_info

perhaps this ticket should at least provide a doctest that this issue is fixed by #13304?

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

comment:16 Changed 6 years ago by dimpase

  • Dependencies changed from 13304 to #13304

comment:17 in reply to: ↑ 15 Changed 6 years ago by mmezzarobba

Replying to dimpase:

perhaps this ticket should at least provide a doctest that this issue is fixed by #13304?

The patches on the other ticket already test that coercion works on a vector of length 50000...

comment:18 Changed 6 years ago by dimpase

  • Status changed from needs_info to positive_review

comment:19 Changed 6 years ago by vbraun

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.