[Networkit] Graph.shrinkToFit()

Marvin Ritter marvin.ritter at student.kit.edu
Tue May 13 01:13:51 CEST 2014


Wow, a lot of discussion about a little idea ... and sorry for starting it
in German.

*Benefit in memory usage*
So in worst case every vector Graph class has 2^x + 1 elements and hence
has allocated space for 2^(x+1) elements taking up nearly double the space
needed. I don't see it getting worse, because Florian argument about the
capacity not decreasing is generally right, but Graph never uses the clear
or any element remove method. So the size is not decreasing.
When nodes or edges are removed they are marked as not existing, but are
left in the vector. This has it pros and cons and is some different topic.
So in best case scenario shrink_to_fit() would free 50% of the memory, in
practice it will be much less, but 10-20% sounds realistic to me. I will
put up some test cases tomorrow.

*When to call it*
I like the idea to call it once at the end of the graph readers/generators.
Feels right as long as the performance is not a problem.

*Performance*
shrink_to_fit() can take up to linear time in the number of elements in the
vector. So something like O(n) + O(m)
But as far as I can remember several graph generators perform worse,
checking each possible edge, resulting in O(n^2)
Also copying all elements of a vector should be relatively cheap (btw. this
is done during the graph generation anyway, when the vector dynamically
increases its size) and we can parallelize the shrink_to_fit() call over
all vectors easily.
I might create some benchmark for this as well.

*Implementation*
I already have a prototype:
https://algohub.iti.kit.edu/parco/NetworKit/NetworKit-DirectedGraph/files/5956ab4780d38174a8e92c0ae843abb5b41343fa/src/cpp/graph/Graph.cpp
So if the test go well I will create a pull request for it.

Best regards
Marvin


On Tue, May 13, 2014 at 12:02 AM, Christian Staudt <christian.staudt at kit.edu
> wrote:

>
> Am 12.05.2014 um 23:36 schrieb Florian Weber <uagws at student.kit.edu>:
>
> >>
> >> So this could be an important improvement. I say
> >> "could" because there is one thing that needs to be checked, namely
> whether
> >> shrinking significantly increases construction time.
> >
> > construction time of what? Copy-Ctors don't care for the capacity of the
> > object they copy.
>
> I mean construction as in the time from when the graph object is initially
> created to when it is passed to the user to work with.
>
> >>
> >> If it does we need to see
> >> if we want to make the tradeoff.
> >
> > I would recommend implementing this with a shrinkToFit-method that is to
> > be called by the user (basically exactly the same that std::vector
> > does), so that there really wouldn't be a tradeoff.
>
> Yes, I can only imagine this as a method. But if the method exists, then
> any code which constructs a graph that is meant to be static should call it
> before returning the graph. This includes file readers and static graph
> generators. So in practice, both the memory used and the time I have to
> wait for the finished graph matters. Therefore we need to see how long
> calling std::vector::shrinkToFit 100 million times takes.
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140513/26321819/attachment.html>


More information about the NetworKit mailing list