If I were to implement three sorting algorithms in c++ and then wanted to examine their space complexity/amount of RAM they take up. How could I do this? Are there any standard or third party libraries that I can use?
4
-
1look at valgrind for the overall usage of the heap ( I do not know if you are also interested by the stack usage). But your question is strange, is only about the sort ? not the space used by the tree itself ?bruno– bruno2019-05-25 13:02:20 +00:00Commented May 25, 2019 at 13:02
-
Without downloading any third party tools or dependencies one easy and simple way is to just run it with say 10^6 numbers, check the amount of ram it takes from your task manager etc, and then run it with 2*10^6 numbers and see how much your ram usage increases.ruohola– ruohola2019-05-25 13:03:38 +00:00Commented May 25, 2019 at 13:03
-
If you are implementing the algorithm, then it is very easy to determine the space complexity from the code itself.Phil1970– Phil19702019-05-25 14:38:49 +00:00Commented May 25, 2019 at 14:38
-
You generally determine time and space complexity by analyzing the algorithm, not your implementation's actual memory use.user9254539– user92545392019-05-25 17:09:50 +00:00Commented May 25, 2019 at 17:09
Add a comment
|
2 Answers
Is this under Unix/Linux ? If so, you could compute the difference between the values returned by sbrk(0) at the beginning and the end of your program. That would give the total amount of heap memory during the run.
See manual page at sbrk(2). "Calling sbrk() with an increment of 0 can be used to find the current location of the program break."
(addendum) Using a toy C++ program that just allocates one large vector,it turns out that the GNU C++ runtime tends to allocate very large objects using mmap() rather than sbrk().
Using strace:
$ strace ./vec1.x |& grep map
...
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f4ac2b42000
mmap(NULL, 800002048, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f4a93051000
...
$
You can also grep with brk instead of map.
Using Valgrind:
$ valgrind ./sbrk1.x
...
==22223== total heap usage: 3 allocs, 3 frees, 800,073,728 bytes allocated
....
$
Hope it helps !
4 Comments
mrfr
Nice! I think this is what im looking for, will check! Thanks
mrfr
I cant get it to work with sbrk. sbrk(0) returns a pointer and not a value. How can I calculate the difference then? Im also trying to dereference that pointer, but then I only get an address (I think). Do you have any code examples on how to use it?
jpmarinier
@ Felix Rosén - you do not want to dereference the pointers returned by sbrk(), as they point into an as yet unallocated vacuum. The idea is to have two pointers returned by sbrk(0), say sbrk1 and sbrk2, taken before and after creating your data structures. Then you cast these two values to char* and substract them. That gives you the number of allocated bytes. Like: size_t diff = static_cast<char*>(sbrk2) - static_cast<char*>(sbrk1);
mrfr
Thanks! I did as you said, but the difference is unfortunately
0If you want to examine their complexity - as an asymptotic function - you would not really be able to do that empirically, e.g. by hooking allocations and de-allocations. You would need to derive asymptotic bounds on the maximum amount of allocated space by carefully analyzing your code. It is theoretically impossible to automate this task in the general case, as your program might be arbitrarily complex.
In practice, what I suggest you do is try to organize your allocations and de-allocations so that they don't happen spontaneously all over the place. That should help you bound the maximum allocated amount.
To the extent that you're asking for a software tool to measure the allocated amount during a run - that is off-topic for StackOverflow, and you should ask on softwarerecs.stackexchange.com .
