[Nauty] Memory leaks
Matthias Walter
matthias at matthiaswalter.org
Mon Aug 13 16:43:52 AEST 2018
Hi Brendan,
thank you for the (quick!) clarification. Good to hear that there is no
real leak. Your explanation sounds like one could in principle add a
method to clean-up all these helper structures such as free lists, etc.,
right?
Best,
Matthias
On 12.08.2018 14:38, Brendan McKay wrote:
>
> Hi Matthias,
>
> What you see is not a memory leak even though valgrind is suspicious
> of it.
>
> I'm appending mail I sent to Marco a short time ago which explains it.
>
> To check there is really no leak, I compiled nautyex3.c exactly as
> distributed except for disabling the output to stdout, (i.e. without
> the DYNFREE insertions that you made), and I ran it like this:
>
> %%% (for n in `seq 1 1000000` ; do echo 1000 ; done) | nautyex3
>
> After about 15 minutes the memory usage is still exactly the same as
> it was after the first few seconds, according to both 'top' and
> /proc/PID/statm . So the program is reusing the allocated memory as
> intended, and never losing any of it.
>
> Hope that helps.
> Brendan.
>
> --------------------------------------------------
>
> The thing about those allocations is that if you call the same
> functions again, the same memory will be reused. So they aren't
> strictly leaks, though they are problematic.
>
> The problem being addressed is that for very simple functions with
> dynamic allocation, the time will be dominated by the cost of
> allocation and freeing. Also, in practice the same functions tend to
> be called multiple times with the same graph size. So a long time
> (decades) ago I got the idea of doing the allocation once and keeping
> the memory for future calls. When I first implemented this, some
> things got much faster.
>
> Today with multi-thread programming being normal, this method is not
> so great. I have detailed plans for a new scheme which uses the stack
> for small arrays and malloc/free for large arrays, but I didn't have
> time to implement it yet.
>
> Of course, if you find a case where the memory in use keeps growing
> without limit, that's an error and I'd appreciate knowing about it.
>
>
> On 12/8/18 9:43 pm, Matthias Walter wrote:
>> Dear developers,
>>
>> we are using nauty (27b11) for a project and observed several memory
>> leaks occuring in the densenauty() call. Is there a way to free this
>> memory? To reproduce this bug we considered the nautyex3.c example
>> and added
>>
>> DYNFREE(g,g_sz);
>> DYNFREE(lab,lab_sz);
>> DYNFREE(ptn,ptn_sz);
>> DYNFREE(orbits,orbits_sz);
>>
>> after the allgroup() call to free the memory that we allocated
>> explicitly. Using valgrind, we observe the following leaks after
>> running it with n=1 and aborting with n=-1 afterwards.
>>
>> Best,
>> Matthias
>>
>> ==26840==
>> ==26840== HEAP SUMMARY:
>> ==26840== in use at exit: 1,124 bytes in 19 blocks
>> ==26840== total heap usage: 25 allocs, 6 frees, 3,192 bytes allocated
>> ==26840==
>> ==26840== 4 bytes in 1 blocks are still reachable in loss record 1 of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x402B17: nauty (nauty.c:358)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 4 bytes in 1 blocks are still reachable in loss record 2 of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x402B65: nauty (nauty.c:359)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 4 bytes in 1 blocks are still reachable in loss record 3 of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x402BB3: nauty (nauty.c:360)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 4 bytes in 1 blocks are still reachable in loss record 4 of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x404216: doref (nautil.c:492)
>> ==26840== by 0x401C74: firstpathnode0 (nauty.c:591)
>> ==26840== by 0x4031D5: nauty (nauty.c:498)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 4 bytes in 1 blocks are still reachable in loss record 5 of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x4055A2: refine1 (naugraph.c:352)
>> ==26840== by 0x40428C: doref (nautil.c:497)
>> ==26840== by 0x401C74: firstpathnode0 (nauty.c:591)
>> ==26840== by 0x4031D5: nauty (nauty.c:498)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 4 bytes in 1 blocks are still reachable in loss record 6 of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x408773: makecosetreps (naugroup.c:222)
>> ==26840== by 0x400C98: main (nautyex3.c:71)
>> ==26840==
>> ==26840== 4 bytes in 1 blocks are still reachable in loss record 7 of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x4087BA: makecosetreps (naugroup.c:223)
>> ==26840== by 0x400C98: main (nautyex3.c:71)
>> ==26840==
>> ==26840== 4 bytes in 1 blocks are still reachable in loss record 8 of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x408C69: allgroup (naugroup.c:376)
>> ==26840== by 0x400CA5: main (nautyex3.c:76)
>> ==26840==
>> ==26840== 6 bytes in 1 blocks are still reachable in loss record 9 of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x402C03: nauty (nauty.c:361)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 6 bytes in 1 blocks are still reachable in loss record 10
>> of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x402C53: nauty (nauty.c:362)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 8 bytes in 1 blocks are still reachable in loss record 11
>> of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x402A7B: nauty (nauty.c:356)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 8 bytes in 1 blocks are still reachable in loss record 12
>> of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x402AC9: nauty (nauty.c:357)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 8 bytes in 1 blocks are still reachable in loss record 13
>> of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x401BC2: firstpathnode0 (nauty.c:578)
>> ==26840== by 0x4031D5: nauty (nauty.c:498)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 12 bytes in 1 blocks are still reachable in loss record 14
>> of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x402CA7: nauty (nauty.c:363)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 12 bytes in 1 blocks are still reachable in loss record 15
>> of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x4055F6: refine1 (naugraph.c:353)
>> ==26840== by 0x40428C: doref (nautil.c:497)
>> ==26840== by 0x401C74: firstpathnode0 (nauty.c:591)
>> ==26840== by 0x4031D5: nauty (nauty.c:498)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 16 bytes in 1 blocks are still reachable in loss record 16
>> of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x402A2D: nauty (nauty.c:355)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 16 bytes in 1 blocks are still reachable in loss record 17
>> of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x401BA5: firstpathnode0 (nauty.c:576)
>> ==26840== by 0x4031D5: nauty (nauty.c:498)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 40 bytes in 1 blocks are still reachable in loss record 18
>> of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x408667: grouplevelproc (naugroup.c:181)
>> ==26840== by 0x401EC2: firstpathnode0 (nauty.c:625)
>> ==26840== by 0x4031D5: nauty (nauty.c:498)
>> ==26840== by 0x405CD2: densenauty (naugraph.c:657)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== 960 bytes in 1 blocks are still reachable in loss record 19
>> of 19
>> ==26840== at 0x4C2DB8F: malloc (in
>> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>> ==26840== by 0x405C89: densenauty (naugraph.c:654)
>> ==26840== by 0x400C7F: main (nautyex3.c:57)
>> ==26840==
>> ==26840== LEAK SUMMARY:
>> ==26840== definitely lost: 0 bytes in 0 blocks
>> ==26840== indirectly lost: 0 bytes in 0 blocks
>> ==26840== possibly lost: 0 bytes in 0 blocks
>> ==26840== still reachable: 1,124 bytes in 19 blocks
>> ==26840== suppressed: 0 bytes in 0 blocks
>> ==26840==
>> ==26840== For counts of detected and suppressed errors, rerun with: -v
>> ==26840== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
>>
>> _______________________________________________
>> Nauty mailing list
>> Nauty at anu.edu.au
>> http://mailman.anu.edu.au/mailman/listinfo/nauty
More information about the Nauty
mailing list