使用的内存:std :: list vs std :: forward_list

Question

因为list还有一个指针(前一个指针)而不是forward_list,所以如果它们都拥有相同数量的元素,即1 << 30,则list将使用几乎1/3的内存.对？

然后,如果我重复调用越来越大的调整大小,则forward_list必须能够调整大于列表的大小.

测试代码:

#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;
}

令我惊讶的是,当这个过程被杀死时,它们的大小几乎相同......有人可以解释它吗？

Answer 1

你应该发现,通过更好的记忆嗅探,你的初始假设,即std::list<T>消耗三倍的能量是正确的.在我的Windows机器上,我使用GetProcessMemoryInfo编写了一个快速内存使用程序

这是我的计划的核心:

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;
}

在发布版本下运行时的结果:

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

这是cplusplus.com的一句话,它甚至说两个容器之间应该有明显的内存差异.

forward_list容器和列表容器之间的主要设计区别在于,第一个容器内部仅保留指向下一个元素的链接,而后者每个元素保留两个链接:一个指向下一个元素,一个指向前一个元素,从而有效在两个方向上迭代,但每个元素消耗额外的存储空间,并且插入和移除元素的时间略微增加.因此,forward_list对象比列表对象更有效,尽管它们只能向前迭代.

使用列表中的调整大小功能,就像在发布的代码中一样,内存差异甚至更加明显,std::list<T>消耗的内存是其四倍.

Answer 2

我知道问题是4岁,但接受的答案没有意义(正如贾斯汀雷蒙德指出的那样).

尼克巴布科克的方法是不精确的,因为元素的数量太少; 堆上总会有一些开销,你也会测量.

为了表明这一点,我使用了更大的数据类型和更多元素(4096):On g++ 6.2.1和linux x64 sizeof(void*) = 8and sizeof (bigDataType_t) = 800(bigData_tis long[100]).

那么我们期待什么呢？每种类型的列表都必须将实际数据存储在堆上; std::list每个链接存储2个指针(向后和向前),std::forward_list只有一个(向前).

预期记忆std::list: 4096 x 800 + 2 x 8 x 4096 = 3,342,336 bytes

实际内存std::list:3,415,040 bytes

预期记忆std::forward_list: 4096 x 800 + 1 x 8 x 4096 = 3,309,568 bytes

实际内存std::forward_list:3,382,272 bytes

我使用Massif来获取程序的堆使用情况.

我们可以看到,数字非常合适.使用大数据类型时,额外指针的内存没有太大区别!

当使用charas as datatype(作为OP)时,预期和实际的内存占用量不太合适,很可能是因为一些开销.但是,内存消耗没有因素3.

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

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

我的代码:

#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;
}