linux x64 c ++为链表分配过多的内存;为什么？ [英] linux x64 c++ allocates way too much memory for a linked list; why?

问题描述

我的c ++编写的progam（x64）包含这个链接的列表代码：

我将使用stackoverflow上的链接列表示例代码来说明这个问题。 p>

旧代码段已删除;对不起，如果评论没有意义了。

添加了完整的工作代码，以显示我的问题是什么。
compile：g ++ linkedlist.cpp -o linked-list

  #include< cstdlib> 
 #include< iostream> 
 
 using namespace std; 
 
 
结构节点
 {
 public：
 unsigned int part1; // 4 bytes 
 unsigned int part2; // 4 bytes 
 node * next; //指针，64位系统上的8个字节
 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 
 {
 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; //索引列表，430m，。 
 //将在堆上创建
 LinkedList * list = NULL; 
 
 
 
 
 
 int main（int argc，char * argv []）
 
 {
 LinkedList list_instance; 
 
 cout<< 1 LinkedList instance take [<< sizeof（list_instance）<< ] bytes in memory！< endl; 
 
 node node_instance; 
 
 cout<< 1个节点实例采用[< sizeof（node_instance）<<] in memory！< endl; 
 
 
 try {
 list = new LinkedList [index_size]; 
} 
 
 catch（std :: bad_alloc）{
 cout< 分配存储器错误< endl; 
 return 0; 
 //重新启动代码
} 
 
 unsigned int some_data [] = {00，01}; 
 unsigned int index; 
 
 LinkedList * list_instance2 = NULL; 
 
 
 
 cout<< Allocating ...< endl; 
 
 for（int i = 0; 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<< 这个过程*应该*周围消耗< sk  
 cout<< 分配完成，*检查过程大小*并按任意数字键+ ENTER退出...<< endl; 
 
 int u = 0; 
 cin>> u; 
 
 
 return 0; 
} 
  

编译它，运行它，看看你的进程大小是否远程匹配。
如果不是 - 在哪里是问题？

哦，我运行它64位slackware 13.37与未修改的默认内核。 $ b

解决方案

在我的方块上，使用稍作修改的来源（见下面的注释）

• 使用标准库堆例程使用1243 MiB而不是预期785 MiB


• 在使用Boost对象池分配节点时（使用标准库堆），它使用840 MiB时，它会使用791 MiB。或 tcmalloc）

这些开销在执行堆例程时非常清楚。

下面是代码：

• 注意使用 new（nothrow） code>


• 此外，开始时的基线测量（我使用 pmap $（pgrep test）| tail on linux）



• 注意插入中的选择：

    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 c>到到 #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 b $ b {
 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; //索引列表
 //将在堆上创建
 LinkedList * list = NULL; 
 
 int main（int argc，char * argv []）
 {
 LinkedList list_instance; 
 cout<< 1 LinkedList instance take [<< sizeof（list_instance）<< ] bytes in memory！< endl; 
 node node_instance; 
 cout<< 1个节点实例采用[< sizeof（node_instance）<<] in memory！< endl; 
 cout<< 在动态分配之前：*检查基线过程大小*并按ENTER开始分配...< endl; 
 std :: string s; 
 std :: getline（std :: cin，s）; 
 list = new（nothrow）LinkedList [index_size]; 
 if（！list）
 {
 cout<< 分配存储器错误< endl; 
 return 1; 
} 
 unsigned int some_data [] = {00，01}; 
 cout<< 分配节点...< endl; 
 for（unsigned int i = 0; 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<< 这个过程*应该*周围消耗< sk  cout<< Allocating done，* check the process size * and press ENTER to exit ...<< endl; 
 std :: getline（std :: cin，s）; 
 return 0; 
} 
  

i will be using linked list example code seen here on stackoverflow to illustrate the problem.

my c++ written progam (x64) contains this linked list code :

old code snippets deleted; im sorry if comments doesnot make sense anymore.

added fully working code to show what my problem is. compile : g++ linkedlist.cpp -o linked-list

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

compile it, run it and see if your process size even remotely matches whats expected. if not - where is the problem ?

oh, and i run it on 64 bit slackware 13.37 with a unmodified default kernel.

解决方案

On my box, with slightly modified source (see below with notes)

• it uses 1243 MiB rather than the 'expected' 785 MiB using the standard library heap routines
• it uses 791 MiB when using Google's tcmalloc
• it uses 840 MiB when using Boost Object Pool to allocate nodes (with standard library heap or tcmalloc)

The overhead is very clearly in the implementation of the heap routines.

Here's the code:

• Note the use of new (nothrow) there.
• Also, the baseline measurement at the start (I used pmap $(pgrep test) | tail on linux)

• Note the choice in 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
  }
  

  Change #if 1 to #if 0 to use the Boost Object Pool

• There was a strangeness in the node allocation loop

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

  I changed it to what you probably intended:

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

这篇关于linux x64 c ++为链表分配过多的内存;为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！