[Networkit] Graph.shrinkToFit()

Marvin Ritter marvin.ritter at student.kit.edu
Tue May 13 10:12:20 CEST 2014

*Measure memory*
While creating a test case I ran into a little problem. There is no way to
measure the memory used by the process or an object in C++ - at least not
without using OS X specific methods. Therefor I added another method and
said that the memory used by the vectors mainly depends on their capacity
and the elements, so for "std::vector<int> v" it should be "sizeof(int) *
v.capacity()" (ignoring some bytes for the object itself). Does anyone has
a better idea?

Doing so the results look very good. I created 4 graphs and on each on the
allocated memory was decreased by 17% (or more). Way below the possible
50%, but still a lot. And measuring the runtime you get this for very
little extra time.

[ RUN      ] GraphMemoryBenchmark.shrinkToFitForErdosRenyi
G(n = 1000, m = 4982), generation took 117 ms, memory used before shrink:
140968, memory used after shrink: 111912, relative saving: 0.206118,
shrinking took 335 us
G(n = 5000, m = 125250), generation took 2732 ms, memory used before
shrink: 2778560, memory used after shrink: 2164704, relative saving:
0.220926, shrinking took 2964 us
G(n = 10000, m = 499492), generation took 10884 ms, memory used before
shrink: 10588976, memory used after shrink: 8313200, relative saving:
0.214919, shrinking took 8481 us
[       OK ] GraphMemoryBenchmark.shrinkToFitForErdosRenyi (13750 ms)
[ RUN      ] GraphMemoryBenchmark.shrinkToFitForGraphReader
G(n = 192244, m = 609066), reading took 894 ms, memory used before shrink:
19168984, memory used after shrink: 15920968, relative saving: 0.169441,
shrinking took 47071 us
[       OK ] GraphMemoryBenchmark.shrinkToFitForGraphReader (988 ms)

1) Note that the graph generation is in milliseconds while I had to measure
the shrinking in microseconds.
2) Interestingly the shrinking worked much better for Erdös Renyi graph
than for some random graph from the input directory.

Link to file with test

Does anyone has an overview how many algorithms in NetworKit change the

Best Regards
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140513/7e9a1c78/attachment.html>

More information about the NetworKit mailing list