Opened 7 years ago

Closed 7 years ago

Last modified 6 years ago

#3150 closed defect (fixed)

[with patch, positive review] Memory leak in combinat/matrices/dancing_links.pyx

Reported by: carlohamalainen Owned by: carlohamalainen
Priority: major Milestone: sage-3.0.2
Component: combinatorics Keywords:
Cc: sage-combinat Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

The wrapper for the C++ class dancing_links in dancing_links.pyx does not deallocate all memory resulting in a leak.

Running valgrind on dlxcpp.py:

==23234== LEAK SUMMARY:
==23234==    definitely lost: 64 bytes in 2 blocks.
==23234==    indirectly lost: 368 bytes in 12 blocks.
==23234==      possibly lost: 201,979 bytes in 708 blocks.
==23234==    still reachable: 28,370,716 bytes in 19,122 blocks.
==23234==         suppressed: 0 bytes in 0 blocks.

After applying the patch:

==26826== LEAK SUMMARY:
==26826==    definitely lost: 0 bytes in 0 blocks.
==26826==      possibly lost: 202,323 bytes in 709 blocks.
==26826==    still reachable: 28,370,372 bytes in 19,121 blocks.
==26826==         suppressed: 0 bytes in 0 blocks.

As another test I ran the following Sage program and watched the memory usage in top. Before the memory usage of the python process would grow rapidly, with the patch it seems to stabilise quickly (about 10% memory on my 2Gb laptop).

from sage.combinat.matrices.dancing_links import dlx_solver

rows = [[0,1,2]]
rows+= [[0,2]]
rows+= [[1]]
rows+= [[3]]

for _ in range(10000000):
    x = sage.combinat.matrices.dancing_links.dlx_solver(rows) 
    x.search()

Attachments (1)

dlxmem.patch (3.1 KB) - added by carlohamalainen 7 years ago.

Download all attachments as: .zip

Change History (6)

Changed 7 years ago by carlohamalainen

comment:1 Changed 7 years ago by mabshoff

  • Summary changed from Memory leak in combinat/matrices/dancing_links.pyx to [with patch, needs review] Memory leak in combinat/matrices/dancing_links.pyx

comment:2 Changed 7 years ago by rlm

  • Summary changed from [with patch, needs review] Memory leak in combinat/matrices/dancing_links.pyx to [with patch, positive review pending] Memory leak in combinat/matrices/dancing_links.pyx

I haven't done doctests with this patch, but I'm familiar with this file, and it looks right. Tom Boothby should probably confirm.

comment:3 Changed 7 years ago by mabshoff

  • Summary changed from [with patch, positive review pending] Memory leak in combinat/matrices/dancing_links.pyx to [with patch, positive review] Memory leak in combinat/matrices/dancing_links.pyx

The patch is good and valgrinds clean to me. I am doctesting with only that patch applied to make sure everything still works, so if nothing pops up it will be merged :)

Cheers,

Michael

comment:4 Changed 7 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged in Sage 3.0.2.alpha0

comment:5 Changed 6 years ago by nthiery

  • Cc sage-combinat added
Note: See TracTickets for help on using tickets.