关于c++内存回收（delete）对程序整体运行时间影响的疑问

Author Avatar
MorphLing 11月 16, 2020

起因是这样的，最近算法课在上红黑树，写红黑树的时候肯定涉及一些内存管理的问题，主要是在插入结点的时候要用new分配一个新的结点，并在清空红黑树的时候把这些结点delete释放掉。

算法导论书上只提供了插入和删除操作的代码，但是因为要测试多组数据的运行时间，需要自己实现一个清空(destroy)操作。本着避免一切可能造成的内存泄漏的原则，一开始我写了完整的清空函数，也就是从根节点开始递归，回收每个结点的内存空间，其中我的结点和树定义如下。

enum RBTColor{RED, BLACK};

class RBTNode {
public:
    RBTColor color;
    int key;
    RBTNode *lson;
    RBTNode *rson;
    RBTNode *parent;
    RBTNode(RBTColor c, int k) {
        color = c;
        key = k;
        lson = rson = parent = NULL;
    }
};
class RBTree {
public:
    RBTree() {
        root = NULL;
    }
    void destroy() {
        destroy(root);
    }
private:
    void destroy(RBTNode *&root) {
        if (root == NULL) return ;
        if (root->lson) destroy(root->lson);
        if (root->rson) destroy(root->rson);
        delete root;
        root = NULL;
    }
}rb_tree;

然而运行时感觉运行时间很奇怪，于是修改测试数据，测了5组规模一样的数据，发现只有第一次的运行时间是正常的，后面四次的时间明显大很多。进一步记录了一下destroy函数所占用的时间，结果如下。

destroy time : 0 ms SIZE : 100000 RUNTIME : 71 ms
destroy time : 46 ms SIZE : 100000 RUNTIME : 3308 ms
destroy time : 38 ms SIZE : 100000 RUNTIME : 2442 ms
destroy time : 38 ms SIZE : 100000 RUNTIME : 3415 ms
destroy time : 39 ms SIZE : 100000 RUNTIME : 2267 ms
destroy time : 38 ms

意识到可能是destroy的过程中的某些操作产生了这样的结果，采取控制变量法，尝试去掉了内存回收的部分之后运行时间时间恢复正常。修改后的destroy和测试结果如下，但很明显，这样写又会有内存泄漏的问题，即没有在清空红黑树前回收每个结点的内存

void destroy() {
    // clock_t rec = clock();
    // destroy(root);
    // cout << "destroy time : " << clock() - rec << " ms ";
    root = NULL;
}

SIZE : 100000 RUNTIME : 61 ms
SIZE : 100000 RUNTIME : 64 ms
SIZE : 100000 RUNTIME : 71 ms
SIZE : 100000 RUNTIME : 67 ms
SIZE : 100000 RUNTIME : 65 ms

可以确定是清空操作(destroy)造成了这一现象。此时我陷入了疑惑：RUNTIME所记录的仅仅是执行红黑树“插入”操作所消耗的时间，并没有记录清空操作的时间，与清空操作唯一的联系是对于内存的操作。但清空操作完成后，此时红黑树的根结点指针指向空结点，整个程序的执行状态和程序刚开始时几乎完全相同，但实际运行时间却差了40-50倍。

一个猜想是清空时的delete操作影响到了程序所能够使用的内存空间，但delete是起到回收内存的作用的，理论上来说意味着可供使用的内存空间更大了，为什么会比不回收内存空间的写法耗时更久呢？这一猜想完全不能解释这种现象。

以上就是我目前遇到的最主要的问题，对此我还做了以下尝试：

  1. 修改测试数据规模大小，测试了10^6的情况，仍有这个问题

    destroy time : 0 ms SIZE : 1000000 RUNTIME : 669 ms
destroy time : 470 ms SIZE : 1000000 RUNTIME : 7070 ms
destroy time : 462 ms SIZE : 1000000 RUNTIME : 7294 ms
destroy time : 473 ms SIZE : 1000000 RUNTIME : 7754 ms
destroy time : 471 ms SIZE : 1000000 RUNTIME : 6117 ms
destroy time : 468 ms

  2. 把释放内存的部分写到了RBTNode的析构函数中，并修改对应的destroy：

    class RBTNode {
public:
    RBTColor color;
    int key;
    RBTNode *lson;
    RBTNode *rson;
    RBTNode *parent;
    RBTNode(RBTColor c, int k) {
        color = c;
        key = k;
        lson = rson = parent = NULL;
    }
    ~RBTNode() {
        if (lson) delete(lson); lson = NULL;
        if (rson) delete(rson); rson = NULL;
    }
};
void destroy() {
    clock_t rec = clock();
    delete(root);
    root = NULL;
    cout << "destroy time : " << clock() - rec << " ms ";
}

    从结果来说，和原来的没有任何区别

  3. 写了一个简化版的测试程序，通过最简单的数据结构（链表）进行测试，问题仍然存在，可见不是红黑树操作的问题

    #include <bits/stdc++.h>

using namespace std;

int cnt;

class Node {
public:
    Node(int x) {
        key = x;
        nxt = NULL;
    }
    int key;
    Node *nxt;
};

class chain {
public:
    chain() {
        head = NULL;
    }
    void destroy() {
        clock_t rec = clock();
        Node *now = head, *pre;
        while(now !=NULL && now->nxt != NULL) {
            pre = now;
            now = now->nxt;
            delete pre;
            pre = NULL;
            cnt++;
        }
        if (now) delete now;
        head = NULL;
        cout << "destroy time : " << clock() - rec << " ms" << endl;
    }
    void insert(int x) {
        Node *node = new Node(x);
        insert(head, node);
    }
    void print() {
        print(head);
        cout << endl;
    }
private:
    Node *head;
    void destroy(Node *&now) {
        if (!now) return;
        cnt++;
        destroy(now->nxt);
        delete now;
        now = NULL;
    }
    void insert(Node *&now, Node *&node) {
        if (now == NULL) {
            now = node;
            return;
        }
        insert(now->nxt, node);
    }
    void print(Node *now) {
        if (!now) return;
        cout << now->key << " ";
        print(now->nxt);
    }
}L;

int main() {
    clock_t rec;
    L.destroy();
    for (int j = 1; j <= 5; j++) {
        rec = clock();
        for (int i = 1; i <= 10000; i++) L.insert(i);
        cout << "time : " << clock() - rec << " ms " ;
        L.destroy();
    }
    return 0;
}

    运行结果如下：

    destroy time : 0 ms
time : 120 ms destroy time : 383 ms
time : 506 ms destroy time : 378 ms
time : 499 ms destroy time : 375 ms
time : 498 ms destroy time : 375 ms
time : 507 ms destroy time : 375 ms

    仍然是只有第一次运行时时间正常，后面几次时间都长很多。

    且去掉delete之后时间恢复正常。再次确定是delete造成的问题。

  4. 抄了一个网上的红黑树代码，加上delete之后自己跑了一下，还是有这个问题

  5. 建了两颗红黑树，先对第一棵树做一遍插入和清空操作，再对第二棵树做插入操作，发现第二个树的插入时间也变慢了（进一步确定了问题与内存管理的关系）

重新简述下问题：在清空数据结构时，如果用delete回收了内存，那么会对下一次使用同样数据结构的运行时间产生非常大的影响。但原因未知，希望能找到对于这一现象的解释。

加了delete之后变慢的时间：

SIZE :100 RUNTIME : 2 ms
SIZE :1000 RUNTIME : 2 ms
SIZE :10000 RUNTIME : 13 ms
SIZE :100000 RUNTIME : 1049 ms
SIZE :1000000 RUNTIME : 4881 ms

不加delete正常的运行时间：

SIZE :100 RUNTIME : 9 ms
SIZE :1000 RUNTIME : 2 ms
SIZE :10000 RUNTIME : 8 ms
SIZE :100000 RUNTIME : 126 ms
SIZE :1000000 RUNTIME : 1341 ms

（搞了好几天了没搞懂为什么，救救孩子

附红黑树代码（只有插入操作）

#include <iostream>
#include <ctime>
#include <string.h>
#include <algorithm>

using namespace std;

const int MAXN = 1e6 + 5;

int data[MAXN], height;

enum RBTColor{RED, BLACK};

class RBTNode {
public:
    RBTColor color;
    int key;
    RBTNode *lson;
    RBTNode *rson;
    RBTNode *parent;
    RBTNode(RBTColor c, int k) {
        color = c;
        key = k;
        lson = rson = parent = NULL;
    }
    ~RBTNode() {
        if (lson) delete(lson); lson = NULL;
        if (rson) delete(rson); rson = NULL;
    }
};

class RBTree {
public:
    RBTree() {
        root = NULL;
    }
    ~RBTree() {
        destroy();
    }
    void insert(int key) {
        RBTNode *node = new RBTNode(RED, key);
        insert(root, node);
        //cout << "finish" << endl;
    }
    void inOrder() {
        cout << "root : " << root->key << endl;
        inOrder(root);
    }
    void check() {
        check(root, 1);
    }
    void destroy() {
        clock_t rec = clock();
        delete(root);
        root = NULL;
        cout << "destroy time : " << clock() - rec << " ms ";
        // root = NULL;
    }
private:
    RBTNode *root;
    void check(RBTNode *&x, int h) {
        h += x->color;
        if (x->lson) check(x->lson, h);
        if (x->rson) check(x->rson, h);
        if (x->color == 0) {
            if (x->lson && x->lson->color == 0 || x->rson && x->rson->color == 0)
                cout << "COLOR ERROR!" << endl;
        }
        if (!x->lson && !x->rson) {
            if (height == 0) height = h;
            else {
                if (height != h)
                    cout << "HEIGHT ERROR!" << endl;
            }
        }
    }
    void inOrder(RBTNode *&x) {
        if (x->lson) inOrder(x->lson);
        cout << "color : " << (x->color ? "BLACK" : "RED  ");
        cout << " key : " << x->key << endl;
        if (x->rson) inOrder(x->rson);
    }
    void insert(RBTNode *&root, RBTNode *&node) {
        if (root == NULL) {
            root = node; 
            insertFixup(root, root);
            return;
        }
        RBTNode *x = root, *y;
        while(x != NULL) {
            y = x;
            if (node->key < x->key) x = x->lson;
            else x = x->rson;
        }
        x = node;
        x->parent = y;
        if (node->key < y->key) y->lson = node;
        else y->rson = node;
        insertFixup(root, node);
    }
    void leftRotate(RBTNode *&root, RBTNode *&x) {
        RBTNode *y = x->rson, *z = x->parent;
        if (z == NULL) root = y;
        else 
            if (z->lson == x) z->lson = y;
            else z->rson = y;
        y->parent = x->parent;
        x->parent = y;
        x->rson = y->lson;
        if (x->rson) {
            x->rson->parent = x;
        }
        y->lson = x;
    }
    void rightRotate(RBTNode *&root, RBTNode *&x) {
        RBTNode *y = x->lson, *z = x->parent;
        if (z == NULL) root = y;
        else
            if (z->lson == x) z->lson = y;
            else z->rson = y;
        y->parent = x->parent;
        x->parent = y;
        x->lson = y->rson;
        if (x->lson) {
            x->lson->parent = x;
        }
        y->rson = x;
    }
    void insertFixup(RBTNode *&root, RBTNode *&x) {
        if (root == x) {
            x->color = BLACK;
            return;
        }
        RBTNode *y = x->parent;
        if (y->color == RED) {
            RBTNode *gparent = y->parent;
            if (gparent->lson == y) {
                RBTNode *uncle = gparent->rson;
                if (uncle && uncle->color == RED) {
                    uncle->color = y->color = BLACK;
                    gparent->color = RED;
                    insertFixup(root, gparent);    
                } else {
                    if (y->rson == x) {
                        leftRotate(root, y);
                        swap(x, y);
                    }
                    gparent->color = RED;
                    y->color = BLACK;
                    rightRotate(root, gparent);
                }
            } else {
                RBTNode *uncle = gparent->lson;
                if (uncle && uncle->color == RED) {
                    uncle->color = y->color = BLACK;
                    gparent->color = RED;
                    insertFixup(root, gparent);
                } else {
                    if (y->lson == x) {
                        rightRotate(root, y);
                        swap(x, y);
                    }
                    gparent->color = RED;
                    y->color = BLACK;
                    leftRotate(root, gparent);
                }
            }
        }    
    }
    void destroy(RBTNode *&root) {
        if (root == NULL) return ;
        if (root->lson) destroy(root->lson);
        if (root->rson) destroy(root->rson);
        delete root;
        root = NULL;
    }
}rb_tree;

class randInt {
public:
    randInt(int n, int s, int t):_n(n), _s(s), _t(t) {
        _r = _t - _s + 1;
        get = 0;
        exi = new bool[_r];
        number = new int[n];
        memset(exi, 0, sizeof(bool) * _r);
        memset(number, 0, sizeof(int) * _n);
    }
    ~randInt() {
        delete[] exi;
        delete[] number;
    }
    void generate_no_duplicate() {
        for (int i = 0; i < _n; i++) {
            int res = rand() * rand() % _r + _s;
            while(exi[res - _s]) res = rand() * rand() % _r + _s;
            exi[res - _s] = 1;
            number[i] = res;
        }
    }
    int getNum() {
        return number[get++];
    }
private:
    int _n, _s, _t, _r, get;
    bool *exi;
    int *number;
};

void calc_time(int SIZE, int s, int t) {
    rb_tree.destroy();
    clock_t rec = clock();
    for (int i = 0; i < SIZE; i++) {
        rb_tree.insert(data[i]);
    }
    cout << "SIZE : " << SIZE << " RUNTIME : " << clock() - rec << " ms" << endl;
}

int main() {
    srand(time(NULL));
    int n, s, t; 
    for (int i = 0; i < MAXN; i++) data[i] = i;
    random_shuffle(data, data + MAXN);
    for (int i = 1; i <= 5; i++) {
        calc_time(1000000, s, t);
    }
    return 0;
}