1

我将使用在 stackoverflow 上看到的链表示例代码来说明问题。

我的 c++ 编写的程序（x64）包含这个链表代码：

旧代码片段已删除；如果评论不再有意义，我很抱歉。

添加了完整的工作代码来显示我的问题是什么。编译：g++linkedlist.cpp -o 链表

#include <cstdlib>
#include <iostream>

using namespace std;


 struct node
{
    public :
          unsigned int part1; // 4 bytes
          unsigned int part2; // 4 bytes
          node *next;         //pointer, 8 bytes on 64 bit system
      unsigned int read_part1();
 };


struct LinkedList
 {
     public:
     LinkedList();
          void insert(unsigned int data[], unsigned int data1);
          bool isEmpty() const;
          node* head;
 };

unsigned int node::read_part1() {
return part1;
}
 LinkedList::LinkedList():
 head(NULL)
{
}

bool LinkedList::isEmpty() const
{
  return (head == NULL);
}

  void LinkedList::insert(unsigned int data[], unsigned int data1)
 {



    node* oldHead = head;
    node* newHead = new node();
    newHead->part1 = data[0];
    newHead->part2 = data1;
    newHead->next = oldHead;
    head = newHead;

  }

unsigned int allocations = 300000000;
unsigned int index_size = 430000000;//index of lists, 430m,.
                    //will be creatad on heap
    LinkedList *list = NULL;





int main(int argc, char *argv[])

{
LinkedList list_instance;

cout << "1 LinkedList instance takes [" << sizeof(list_instance) << "] bytes in memory!"<< endl;

node node_instance;

cout << "1 node instance takes [" << sizeof(node_instance) <<"] bytes in memory !"<< endl;


    try{
    list = new LinkedList[index_size];
    }

     catch(std::bad_alloc) {
    cout << "Error allocating memory" << endl;
     return 0;
    //reboot code
    }

unsigned int some_data[] = {00, 01};
unsigned int index;

LinkedList *list_instance2 = NULL;



cout << "Allocating ..." << endl;

for (int i=0; i<allocations; i++)
{

index = rand();
unsigned short inde = (unsigned short)index;
list_instance2 = &list[inde];

list_instance2->insert(some_data, some_data[1]);


}

unsigned long sk = ((allocations * sizeof(node_instance) + index_size*sizeof(list_instance))) / (1024*1024*1024);

cout << "This process *should* consume around " << sk <<" GBytes of memory, but does it ?"<< endl;

cout << "Allocating done, *check the process size* and press any number key + ENTER to exit ..." << endl;

int u=0;
cin >> u;


return 0;
}

编译它，运行它，看看你的进程大小是否与预期的一致。如果不是 - 问题出在哪里？

哦，我在 64 位 slackware 13.37 上使用未修改的默认内核运行它。

4

1 回答 1

1

在我的盒子上，稍微修改了源代码（见下文附注）

  • 它使用 1243 MiB 而不是使用标准库堆例程的“预期”785 MiB
  • 使用 Google 的 tcmalloc 时它使用 791 MiB
  • 使用 Boost Object Pool 分配节点时使用 840 MiB（使用标准库堆或tcmalloc）

在堆例程的实现中开销非常明显。

这是代码：

  • 注意new (nothrow)那里的使用。
  • 另外，开始时的基线测量（我pmap $(pgrep test) | tail在 linux 上使用过）

  • 注意 中的选择insert：

    void LinkedList::insert(unsigned int data[], unsigned int data1)
{
#if 1
    head = new node { data[0], data1, head };
#else
    static boost::object_pool<node> node_pool;

    node* add = node_pool.malloc();
    *add = node { data[0], data1, head };
    head = add;
#endif
}

    更改#if 1为#if 0使用 Boost 对象池

  • 节点分配循环出现异常

    index = rand();
unsigned short inde = (unsigned short)index;
list_instance2 = &list[inde];
list_instance2->insert(some_data, some_data[1]);

    我将其更改为您可能想要的：

    list[rand() % index_size].insert(some_data, some_data[1]);



#include <stdlib.h>
#include <iostream>
#include <boost/pool/object_pool.hpp>

using namespace std;

struct node
{
    unsigned int part1; // 4 bytes
    unsigned int part2; // 4 bytes
    node *next;         //pointer, 8 bytes on 64 bit system
};

struct LinkedList
{
public:
    LinkedList();
    void insert(unsigned int data[], unsigned int data1);
    bool isEmpty() const;
    node* head;
};

LinkedList::LinkedList():
    head(NULL)
{
}

bool LinkedList::isEmpty() const
{
    return (head == NULL);
}

void LinkedList::insert(unsigned int data[], unsigned int data1)
{
#if 1
    head = new node { data[0], data1, head };
#else
    static boost::object_pool<node> node_pool;

    node* add = node_pool.malloc();
    *add = node { data[0], data1, head };
    head = add;
#endif
}

const unsigned int allocations = 30000000;
const unsigned int index_size = 43000000;//index of lists
//will be creatad on heap
LinkedList *list = NULL;

int main(int argc, char *argv[])
{
    LinkedList list_instance;
    cout << "1 LinkedList instance takes [" << sizeof(list_instance) << "] bytes in memory!"<< endl;
    node node_instance;
    cout << "1 node instance takes [" << sizeof(node_instance) <<"] bytes in memory !"<< endl;
    cout << "Before dynamic allocations: *check the baseline process size* and press ENTER to start allocating ..." << endl;
    std::string s;
    std::getline(std::cin, s);
    list = new (nothrow) LinkedList[index_size];
    if (!list)
    {
        cout << "Error allocating memory" << endl;
        return 1;
    }
    unsigned int some_data[] = {00, 01};
    cout << "Allocating nodes ..." << endl;
    for (unsigned int i=0; i<allocations; i++)
    {
        list[rand() % index_size].insert(some_data, some_data[1]);
    }
    unsigned long sk = ((allocations * sizeof(node_instance) + index_size*sizeof(list_instance))) >> 20;
    cout << "This process *should* consume around " << sk <<" MiB of memory, but does it ?"<< endl;
    cout << "Allocating done, *check the process size* and press ENTER to exit ..." << endl;
    std::getline(std::cin, s);
    return 0;
}
于 2012-10-14T23:02:47.410 回答