1

I'm trying to find out how much memory (in Bytes) a list of lists is using.

The Problem is illustrated here:

enter image description here

It Shows a Container List storing pointers to other lists (the Storage Lists) each storing uniformly size elements (let's say 10 Bytes each). So the first Storage List is storing 4 Elements, next 30, then the next one 12 and 10 and the last one 5 Elements. All the Elements are of the same C++ Type (which is just a struct of plain old data).

My Aim: The Container List above should have current size variable, which keeps track of the number of bytes the lists he is pointing to (with all tracked space for *prev and *next pointers).

So far, what I tried, is using allocators to track the number of bytes allocated by the lists (through a static class variable). Although that leads to a problem with std::list::splice, when moving elements from list see here: The elements which are spliced to another Container List are not tracked. It should even be able to track the bytes transfered to add that bytes-Count to the current size of another Container List.

  • Do I have to avoid using the STD allocators for memory tracking and instead use boost's intrusive lists somehow for tracking memory like that?

  • What kind of C++ feature does possibly support me by solving my
    problem?

Robert
  • 127
  • 1
  • 10
  • 1
    IMHO `std::allocator` is the choice. Where do you see the problem with your implementation? – Kaveh Vahedipour Sep 13 '17 at 11:29
  • This might be better suited for [Computer Science](https://cs.stackexchange.com/). – Ron Sep 13 '17 at 11:30
  • 1
    @KavehVahedipour The problem of std::allocator in my solution lies in being just able to track the total amount of memory used by all the Container Lists. If I would use two different allocators to separate the tracked memory counters, I'm not able to use std::list::splice because that requires the same allocator to be used. Even if that would be possible, a transfer does not track the bytes because just the pointers are rearranged (no allocate of the std::allocator is called). – Robert Sep 13 '17 at 11:34
  • 3
    This sounds like the original C++98 problem - a list cannot have both an O(1) size and an O(1) splice. You have to choose, because someone has to do the counting. Can you not count the bytes when you need the value? – Bo Persson Sep 13 '17 at 12:14
  • @BoPersson Nice mentioning about list::size() method. In C++11 Splice is O(1) and the call to size() is calculating that size by iterating over the elements instead of storing it as a member, so O(n). Memory Tracking here is kinda like that too. Unfortunately I cannot count the bytes by traversing through the Storage Lists, because I don't really have a byte count associated with these std::lists. It would be good to have a byte count instead of a size count on std::lists. The Allocator I implemented just stores the bytes in a variable but added for all the Storage Lists. – Robert Sep 13 '17 at 13:01
  • 1
    "I don't really have a byte count associated with these std::lists" You don't need the byte count stored anywhere, you can calculate it from the size. You should know how many bytes an empty list and a list of 1 element take. It should scale linearly. These sizes are pretty much constant for a given element type, so you can discover them by running a small test program with a custom allocator. – n. m. could be an AI Sep 13 '17 at 14:04

1 Answers1

0

I found out that you can use EASTL allocators, because they are bound on each list object.

So on EASTL::CustomAllocator::allocate and EASTL::CustomAllocator::deallocate you can notify the main list that the allocated bytes of the sub-list (here: Storage List) has changed their weight (here: size in number of bytes allocated by Storage List).

This way the main list (here: Container List) always get a updated weight, which is cached and bound to the main list.

For the CustomAllocator which should notify the main list see my answer on:

How to track memory usage using EASTL?

Robert
  • 127
  • 1
  • 10