Opened 10 years ago

Closed 5 years ago

#8905 closed defect (fixed)

Memory leak in echelon over QQ

Reported by: SimonKing Owned by: tbd
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: memleak Keywords: memleak echelonize
Cc: mderickx Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Apparently there is a memory leak in Sage-4.4 when one echelonizes a matrix over QQ:

sage: MS = MatrixSpace(QQ,8)
sage: M = MS.random_element()
sage: N = copy(M)
sage: N.echelonize()
sage: N==M
False
sage: mem = get_memory_usage()
sage: n = 0
sage: while(1):
....:     n+=1
....:     if get_memory_usage()>mem:
....:         mem = get_memory_usage()
....:         print mem,n
....:     N = copy(M)
....:     N.echelonize()
....:
797.95703125 1
798.0859375 32
798.21484375 71
798.34375 110
798.47265625 155
798.6015625 199
798.8515625 202
798.98046875 243
799.109375 292
799.23828125 329
799.37109375 371
799.5 406
799.79296875 426
799.921875 471
800.05078125 530
800.1796875 582
800.30859375 634
800.61328125 666
...

Here I show that the critical step really is the echelon form:

sage: MS = MatrixSpace(QQ,8)
sage: M = MS.random_element()
sage: N = copy(M)
sage: mem = get_memory_usage()
sage: n = 0
sage: while(1):
....:     n+=1
....:     if get_memory_usage()>mem:
....:         mem = get_memory_usage()
....:         print mem,n
....:     N = copy(M)
....:
797.92578125 1

The memory consumption is stable at that point. So, copying M is no problem, but computing the echelon form is!

Change History (15)

comment:1 Changed 10 years ago by SimonKing

  • Milestone set to sage-4.4.2

comment:2 Changed 10 years ago by SimonKing

Similarly, one gets

sage: MS = MatrixSpace(QQ,8)
sage: M = MS.random_element()
sage: M = M.stack(M)
sage: v = copy(M).left_kernel()
sage: n = 0
sage: mem = get_memory_usage()
sage: while(1):
....:     n+=1
....:     if get_memory_usage()>mem:
....:         mem = get_memory_usage()
....:         print mem,n
....:     v = copy(M).left_kernel()
....:
800.3828125 27
800.51171875 62
800.640625 94
800.76953125 151
801.05078125 168
801.1796875 187
801.30859375 221
801.4375 256
801.56640625 278
801.71484375 314
802.08984375 375
802.21875 423
802.34765625 460
802.4765625 497
802.60546875 521
802.8984375 610
803.02734375 635
803.15625 690

I guess the two are related.

comment:3 Changed 9 years ago by mderickx

I guess #10262 might explain both of these leaks. I wouldn't find it strange that somewhere in both algorithms scalar*vector multiplication happens.

comment:4 Changed 9 years ago by mderickx

  • Cc mderickx added

comment:5 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:9 Changed 5 years ago by mmezzarobba

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

Seems to be fixed indeed.

┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.6.rc2, Release Date: 2015-04-02                 │
[...]
sage: MS = MatrixSpace(QQ,8)
sage: M = MS.random_element()
sage: N = copy(M)
sage: N.echelonize()
sage: N==M
False
sage: mem = get_memory_usage()
sage: n = 0
sage: while(1):
....:     n+=1
....:     if get_memory_usage()>mem:
....:         mem = get_memory_usage()
....:         print mem,n
....:     N = copy(M)
....:     N.echelonize()
....:
1006.625 2302
1006.875 19154
1007.0078125 27590
1007.2578125 36321

comment:10 follow-up: Changed 5 years ago by SimonKing

  • Status changed from needs_review to needs_info

Marco, the numbers you are giving indicate that the memory leak is smaller than before. But why do you think it is fixed?

comment:11 in reply to: ↑ 10 ; follow-up: Changed 5 years ago by mmezzarobba

  • Milestone changed from sage-duplicate/invalid/wontfix to sage-6.6
  • Status changed from needs_info to needs_work

Replying to SimonKing:

Marco, the numbers you are giving indicate that the memory leak is smaller than before. But why do you think it is fixed?

No, you are right, I misread the results. It looks like we are still leaking about 16 bytes per call.

comment:12 in reply to: ↑ 11 Changed 5 years ago by nbruin

Replying to mmezzarobba:

No, you are right, I misread the results. It looks like we are still leaking about 16 bytes per call.

I wouldn't be so quick to conclude linear behaviour from so few data points. I'm getting:

1130.9375 1
1131.1875 5107
1131.4375 22580
1131.6875 39743

and no further increase up to n=738068 (after which I gave up). Echelonization over QQ likely leads to very complicated memory use (lots of allocation/deallocation), so together with non-deterministic gc (because parents only clear on triggered GC) you expect that the memory layout shows a lot of short-term fluctuations: fragmentation will lead to slowly increasing memory footprint; hopefully stabilizing over long periods. The numbers above are quite consistent with that. Certainly gc.objects() is not showing any significant object accumulation, so any leak would have to be outside python.

I see no indication of a memory leak here anymore, but I guess you could valgrind it to be certain.

comment:13 Changed 5 years ago by mmezzarobba

Yes, I came to the same conclusion after letting it run for a bit longer:

1005.9921875 376
1006.2421875 2015
1006.4921875 19150
1006.4921875 20000
1006.640625 30356
1006.890625 36624
1006.890625 40000
1006.890625 60000
1006.890625 80000
1007.140625 95959
1007.140625 100000
1007.140625 6000000

comment:14 Changed 5 years ago by mmezzarobba

  • Milestone changed from sage-6.6 to sage-duplicate/invalid/wontfix
  • Status changed from needs_work to positive_review

Setting the ticket to duplicate/positive_review as we agree that the problem is fixed and there is no obvious regression test to add.

comment:15 Changed 5 years ago by vbraun

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