CODEWITHSUNDEEP
c++memory-managementdata-structureslinked-list
Andrew Gaspar
Andrew Gaspar

Reputation: 548

Fast allocation of linked list and slow deallocation

I'm a C++ novice and I've run into a frustrating problem -

I have this templated LinkedList implementation:

template <typename U>
class LinkedList : std::iterator<std::input_iterator_tag, U> {
public:
    struct Node {
    friend LinkedList;
        U content;
        Node* getNext() { return next; };
    private:
        Node* next;
        Node* prev;
    };

    LinkedList() : head(NULL), tail(NULL) { };
    ~LinkedList() {
        Node * current = tail;
        while(current != NULL) {
            Node* temp = current;
            current = current->prev;
            delete temp;
        }
    };
    Node* getHead() { return head; }
    Node* getTail() { return tail; }
    bool append(U content) {
        Node* node = new Node();
        if(node == NULL) return false;

        node->content = content;
        if(tail == NULL) {
            tail = head = node;
        } else {
            tail->next = node;
            node->prev = tail;
            tail = node;
        }

        return true;
    };

bool remove(U* cont) {
    if(tail == NULL) return false;

    if(cont != NULL) *cont = tail->content;

    Node *temp = tail;
    if(tail == head) {
        tail = NULL;
        head = NULL;
    } else tail = temp->prev;
    delete temp;
    return true;
};
private:
    Node *head, *tail;
};

I run the following code against it:

char c1, c2;
cout << "start allocation" << endl;

LinkedList<int>* list = new LinkedList<int>();

for(ULONGLONG i = 0; i < 1e5; i++) {
    list->append(0);
}

cout << "allocation complete" << endl;

cin >> c1;

cout << "start deleting" << endl;

delete list;

cout << "done deleting" << endl;

cin >> c2;

cout << c2 << endl; // don't optimize read key away

So it allocates 100,000 int nodes and then it deletes them all. Allocating the space for all of the nodes is almost instantaneous while deleting them takes ~10 seconds. Am I doing something obviously wrong?

Upvotes: 1

Views: 335

Answers (2)

StilesCrisis
StilesCrisis

Reputation: 16290

Try running in Release mode instead of Debug.

In Debug mode, when freeing a block, the runtime will do lots of sanity checks to make sure you didn't overwrite memory you didn't own, and it also scrubs the freed memory contents. In Release, all of that overhead goes away.

(Note that I'm assuming here that you are using Dev Studio. Other platforms have different rules for enabling memory checks, but your issue sounds very similar to my experiences with Dev Studio in Debug mode.)

Upvotes: 0

jmucchiello
jmucchiello

Reputation: 18984

This is probably an artifact of how the run time library deallocates memory. During allocation, finding a block for each node item is probably just a few operations to take the main pool, and split it into two parts and return the smaller part for your program's use. Freeing that block might include walking a free list to see if these small allocations can be combined into larger free blocks.

Upvotes: 3

Related Questions