1

問題を説明するために、stackoverflowでここに表示されているリンクリストのサンプルコードを使用します。

私のc++で書かれたプログラム（x64）には、次のリンクリストコードが含まれています。

古いコードスニペットが削除されました。コメントが意味をなさなくなったらごめんなさい。

私の問題が何であるかを示すために完全に機能するコードを追加しました。コンパイル：g ++linkedlist.cpp -olinked-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;
}

それをコンパイルして実行し、プロセスサイズが予想とリモートで一致するかどうかを確認します。そうでない場合-問題はどこにありますか？

ああ、私はそれを変更されていないデフォルトのカーネルを使用して64ビットのSlackware13.37で実行します。

4

1 に答える 1

1

私の箱では、ソースが少し変更されています（以下のメモを参照）

  • 標準ライブラリヒープルーチンを使用する「予想される」785MiBではなく1243MiBを使用します
  • Googleのtcmallocを使用する場合は791MiBを使用します
  • Boost Object Poolを使用してノードを割り当てる場合（標準ライブラリヒープまたはtcmallocを使用） 、840MiBを使用します

オーバーヘッドは、ヒープルーチンの実装に非常に明確にあります。

コードは次のとおりです。

  • そこでの使用に注意してくださいnew (nothrow)。
  • また、開始時のベースライン測定（pmap $(pgrep test) | tailLinuxで使用）

  • の選択に注意してください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
}

    BoostObjectPool#if 1を#if 0使用するように変更します

  • ノード割り当てループに奇妙さがありました

    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 に答える