search

digraphs / Digraphs

The GAP package Digraphs
https://digraphs.github.io/Digraphs
Other
29 stars 42 forks source link

Reduce Memory Usage #626

Closed DanielPointon closed 1 week ago

DanielPointon commented 3 months ago

Contains the following:

Dynamic memory allocation and deallocation for Homomorphism Dynamic memory allocation and deallocation for Cliques Subtle bug fix for Bliss Graphs when N > 512/3 (see the old allocation of BLISS_GRAPH[i] vs the new in homos.c) Support for Digraph homomorphism with N>512 Support for Bitarray operations with N > 512 Support for flexible bitarray lookup sizes

Logic for memory allocation is as follows:

Logic for bitarrays:

DanielPointon commented 3 months ago

MAXVERTS > 512 now supported!! :)

And I got some test results

On my branch: 824MB of memory 
On main branch: 2.4GB of memory
DanielPointon commented 3 months ago

@james-d-mitchell is there any chance you're able to link me to the configuration for the "coverage" check run on azure? It's failing with a weird error that I can't reproduce locally, and I'd like to know exactly what config the system is using so I can debug

https://dev.azure.com/jdm3/jdm3/_build/results?buildId=3162&view=logs&j=1117f030-3e3a-5822-cfd7-97e776c1f4cb

I had a look in the .github/workflows folder but couldn't see any thing useful

james-d-mitchell commented 3 months ago

It's here:

https://github.com/digraphs/Digraphs/blob/main/azure-pipelines.yml

@DanielPointon

james-d-mitchell commented 3 months ago

Also rebased this onto main and force pushed, this should fix the ci.

DanielPointon commented 3 months ago

Also rebased this onto main and force pushed, this should fix the ci.

It did, thanks! Ignoring the coverage test this looks good to go

james-d-mitchell commented 3 months ago

Thanks @DanielPointon I think we can ignore the code coverage, unless you can see some places to add tests that test some lines that aren't tested, if you can, them please do, if not, then forget about it

james-d-mitchell commented 3 months ago

@DanielPointon I started reviewing this but realised that there are a few issues, and so I fixed compile warnings in digraphs in general in #633, and hoped you could rebase your PR on top of those.

DanielPointon commented 3 months ago

@DanielPointon I started reviewing this but realised that there are a few issues, and so I fixed compile warnings in digraphs in general in #633, and hoped you could rebase your PR on top of those.

Lol, 17 merge conflicts. I've rebased :) Will look at fixing compile warnings now

DanielPointon commented 3 months ago

@DanielPointon I started reviewing this but realised that there are a few issues, and so I fixed compile warnings in digraphs in general in #633, and hoped you could rebase your PR on top of those.

Lol, 17 merge conflicts. I've rebased :) Will look at fixing compile warnings now

@james-d-mitchell I think I've fixed all the compile warnings I caused, apologies if there's anything egregious I missed, the VIP is my first time writing C :)

james-d-mitchell commented 2 months ago

Unfortunately, the changes in this PR appear to leak memory, here's the output of valgrind:

mem_leak.txt

Thanks to @Joseph-Edwards for running valgrind.

I will fix this.

DanielPointon commented 2 months ago

Unfortunately, the changes in this PR appear to leak memory, here's the output of valgrind:

mem_leak.txt

Thanks to @Joseph-Edwards for running valgrind.

I will fix this.

Ah, sorry! I've made a quick push to fix a few of the errors: https://github.com/DanielPointon/Digraphs/commit/45c928adc886719f643f2c9cb40f6a3fa52e76d2

I can revert if it gets in the way of your debugging

Joseph-Edwards commented 2 months ago

This is the valgrind output with those changes:

mem_leak_2.txt

DanielPointon commented 2 months ago

@Joseph-Edwards thanks! @james-d-mitchell if you're okay to hold off until Monday I think I can fix this up over the weekend and save you some time.

DanielPointon commented 2 months ago 
...
==4226== LEAK SUMMARY:
==4226==    definitely lost: 0 bytes in 0 blocks
==4226==    indirectly lost: 0 bytes in 0 blocks
==4226==      possibly lost: 0 bytes in 0 blocks
==4226==    still reachable: 294,718 bytes in 239 blocks
==4226==         suppressed: 0 bytes in 0 blocks

@james-d-mitchell all memory leaks now fixed, essentially the issue was that some structures have a 'size' parameter associated with them which is continuously updated, but the size of underlying structures doesn't always match this, which the free functions assumed. I've also rebased on main and added the functions to manually free cliques and homomorphism data.

james-d-mitchell commented 2 months ago

Awesome thanks @DanielPointon and @Joseph-Edwards !

Joseph-Edwards commented 2 months ago

Unfortunately, it seems like there are still memory leaks when testing standard/grahom.tst: mem_leak_3.txt

DanielPointon commented 2 months ago

@Joseph-Edwards 

==3459== LEAK SUMMARY:
==3459==    definitely lost: 0 bytes in 0 blocks
==3459==    indirectly lost: 0 bytes in 0 blocks
==3459==      possibly lost: 0 bytes in 0 blocks

Fixed! Sorry about that. C is hard.

Joseph-Edwards commented 2 months ago

@DanielPointon no need to apologise! I took the liberty of Valgrinding tst/teststandard.g and that seems to be leak free too. Nice job!

james-d-mitchell commented 1 month ago

I just rebased this (and squashed it) on to the current main branch, this was more or less difficult, and so might contain some mistakes!

james-d-mitchell commented 1 week ago

With the changes in this PR, I'm seeing an approx. 27% 9% loss in performance in the test file tst/extreme/grahom.tst with this branch:

gap> Test("~/digraphs/tst/extreme/grahom.tst");
Digraphs package: extreme/grahom.tst
msecs: 73179
true
gap> Test("~/digraphs/tst/extreme/grahom.tst");
Digraphs package: extreme/grahom.tst
msecs: 74211
true

This was tested after I commented out the lines:

 # Wipe internal structures for homos and cliques
   DIGRAPHS_FREE_HOMOS_DATA();
   DIGRAPHS_FREE_CLIQUES_DATA();

in DIGRAPHS_StopTest. So, it seems that the loss of performance is not related to the actual de/allocation of memory.

With the main branch` I get:

gap> DigraphsTestInstall();
Digraphs package: testinstall.tst
msecs: 53
true
gap> Test("~/digraphs/tst/extreme/grahom.tst");
Digraphs package: extreme/grahom.tst
msecs: 66923
true
gap> Test("~/digraphs/tst/extreme/grahom.tst");
Digraphs package: extreme/grahom.tst
msecs: 66778
true

I'll need to investigate a bit further to see why this might be the case. I'm more or less happy to accept a small loss of performance with these changes, ~~but I'm not sure that I'd class ~27% as small. ~~

UPDATE: I added an addition test at the end of extereme/grahom.tst which accounted for most of the change in performance, I think I can live with a 9% decrease in perf!

james-d-mitchell commented 1 week ago

@Joseph-Edwards any chance you can run this through valgrind again? I think I might have inadvertently force pushed and deleted some of Daniel's fixes :(

Joseph-Edwards commented 1 week ago

@james-d-mitchell will the new Valgrind action suffice? If no, I'll happily run it again.

I also think I have a local copy of the old branch. If that'd be helpful to see, I can push it to my fork

james-d-mitchell commented 1 week ago

Thanks @Joseph-Edwards, if you could push the old branch to your fork that'd be awesome!

Also the new valgrind action would be just fine, where is that exactly?

Joseph-Edwards commented 1 week ago

Pushed to https://github.com/Joseph-Edwards/Digraphs

And hopefully you should be able to see the Valgrind action in the actions tab. It should be callable somehow, but I'm not sure how off the top of my head.

james-d-mitchell commented 1 week ago

Thanks @Joseph-Edwards I figured out how to call the valgrind job, and thanks for the push too!