Used memory: std :: list vs std :: forward_list

Question

Because the list has one more pointer (previous pointer) than forward_list, so if both of them contain the same number of elements, i.e. 1 <30, the list will use almost 1/3 more memory. Correctly?

Then, if I repeat that resizing is larger and larger, forward_list should be able to resize much larger than the list.

Test code:

#include<forward_list> #include<list> #include<iostream> int main(){ using namespace std; typedef list<char> list_t; //typedef forward_list<char> list_t; list_t l; list_t::size_type i = 0; try{ while(1){ l.resize(i += (1<<20)); cerr<<i<<" "; } } catch(...){ cerr<<endl; } return 0; } 

To my surprise, when the process is killed, they are almost the same size ... Can anyone interpret this?

Answer 1

You should find that with improved memory, your initial hypothesis that std::list<T> will consume three times as much energy is correct. On my Windows machine, I hacked a memory fast program using GetProcessMemoryInfo

Here is the core of my program:

 int main() { size_t initMemory = MemoryUsage(); std::list<unsigned char> linkedList; for (int i = 0; i < ITERATIONS; i++) linkedList.push_back(i % 256); size_t linkedListMemoryUsage = MemoryUsage() - initMemory; std::forward_list<unsigned char> forwardList; for (int i = 0; i < ITERATIONS; i++) forwardList.push_front(i % 256); size_t forwardListMemoryUsage = MemoryUsage() - linkedListMemoryUsage - initMemory; std::cout << "Bytes used by Linked List: " << linkedListMemoryUsage << std::endl; std::cout << "Bytes used by Forward List: " << forwardListMemoryUsage << std::endl; return 0; } 

Results when run in release build:

 #define ITERATIONS 128 Bytes used by Linked List: 24576 Bytes used by Forward List: 8192 8192 * 3 = 24576 

Here is a quote from cplusplus.com , which even says that there should be a noticeable difference in memory between the two containers.

The main difference in design between the forward_list container and the container list is that the former stores only a link to the next element inside, and the latter stores two links to the element: one points to the next element and one to the previous one, which allows iteration in both directions but consuming additional storage per item and with a slightly higher overhead time for inserting and removing items. Thus, forward_list objects are more efficient than a list of objects, although they can only be repeated forward.

Using the resize function in lists, as in the published code, the memory difference was even more pronounced if std::list<T> consumes four times as much memory.

Answer 2

I know that the question is 4 years old, but the accepted answer does not make sense (as Justin Raymond pointed out).

Nick Babcock's approach is fuzzy, because the number of elements is too low; there is always some overhead on the heap that you will also measure.

To show this, I used a larger data type and other elements (4096): On g++ 6.2.1 and linux x64 sizeof(void*) = 8 and sizeof (bigDataType_t) = 800 ( bigData_t is long[100] ).

So what do we expect? Each type of list must store the actual data on the heap; std::list stores 2 pointers to a link (back and forth), std::forward_list only one (forward).

Expected memory for std::list : 4096 x 800 + 2 x 8 x 4096 = 3,342,336 bytes

Actual memory for std::list : 3,415,040 bytes

Expected memory for std::forward_list : 4096 x 800 + 1 x 8 x 4096 = 3,309,568 bytes

Actual memory for std::forward_list : 3,382,272 bytes

I used Massif to get use of a bunch of programs.

As we can see, the numbers fit pretty well. When using large data types, the memory for the extra pointer does not matter much!

When using char as a data type (like OP), the expected and actual amount of memory does not fit too well, most likely due to some overhead. However, there is no factor 3 for memory consumption.

std::list: Expected 69,632 bytes, actual: 171,008 bytes

std::forward_list: Expected 36,864 bytes, actual: 138,240 bytes

My code is:

 #include <list> #include <forward_list> struct bigData_t { long foo[100]; }; typedef bigData_t myType_t; // typedef char myType_t; int main() { #ifdef USE_FORWARD_LIST std::forward_list<myType_t> linkedList; #else std::list<myType_t> linkedList; #endif for (int i = 0; i < 4096; i++) { myType_t bigData; linkedList.push_front(bigData); } return 0; }