使用大量内存的堆实现 - C语言

Question

使用大量内存的堆实现 - C语言

4

我正在编写一份 C 语言实现的最小堆作为 Dijkstra 算法的一部分。我已经明确了所有细节，我的测试程序通过了 valgrind 测试，但在过程中它分配了荒谬的大量内存。最后一个测试是在一个由 INT_MAX 乘以 INT_MAX 的网格上进行的（坐标只是整数），当我进行测试时会收到 SIGXCPU 错误。即使我只是向队列中插入 16k 个位置然后删除所有内容，它仍然需要很长时间并分配超过 8MB 的内存。当我在巨大的网格测试用例上运行它时，它可以达到 500MB，在我手动退出之前。可能出了什么问题？这是我的代码的一部分:

struct position {
    int x;
    int y
};

typedef struct elt {
    int priority;
    int distance;
    struct position p;
} *Elt;

typedef struct heap {
    int size;
    int capacity;
    Elt *elts;
} *Heap;

void heap_insert(Heap h, Elt e, int *counter) {
    if(h->capacity < (h->size + 2)) {
        h->elts = realloc(h->elts, h->capacity * sizeof(Elt) * 2);
        h->capacity *= 2;
    }
    h->elts[h->size] = malloc(sizeof(*Elt));
    elt_assign(h->elts[h->size], e);
    h->size++;
    heapify(h->size, h->elts);
    *counter = *counter + 1;
}

我所有的其他函数都只在函数内一次性进行内存管理，或者根本不进行内存管理。在这种情况下，初始大小为64，但是我尝试过从1024开始也得到了同样的效果。我还尝试限制队列的大小，但没有用。我很确定不是我的堆化代码有问题，但为了保险起见，我放在这里：

static void floatDown(int n, Elt *a, int pos) {
    Elt x = malloc(sizeof(struct elt));
    elt_assign(x, a[pos]);
    for(;;) {
        if(Child(pos, 1) < n && a[Child(pos, 1)]->priority < a[Child(pos, 0)]->priority) {
            if(a[Child(pos, 1)]->priority < x->priority) {
                elt_assign(a[pos], a[Child(pos, 1)]);
                pos = Child(pos, 1);
            } else {
                break;
            }
        } else if(Child(pos, 0) < n && a[Child(pos, 0)]->priority < x->priority) {
            elt_assign(a[pos], a[Child(pos, 0)]);
            pos = Child(pos, 0);
        } else {
            break;
        }
    }
    elt_assign(a[pos], x);
    free(x);
}

static void heapify(int n, Elt *a) {
    for(int i = n - 1; i >= 0; i--) {
        floatDown(n, a, i);
    }
}

非常感谢您的帮助。

- jclancy

1

我觉得 elt_assign 方法在这里也会很有用。 - Makoto

我同意Makoto的观点，就你发布的代码而言，没有明显的泄漏。 - alk

你说“它在过程中分配了荒谬的大量内存”。它分配了多少？从打印malloc和realloc返回的值可以得到一些见解。（我会制作包装函数myMalloc和myRealloc）。可能是由于floatdown中的Elt x = malloc...导致内存碎片化，因此我想知道heap_insert中的每个realloc是否以某种低效的方式分配了全新的内存块。还要计算每个malloc和realloc的时间，并打印出时间，也许显示指数级减速。将Elt x = malloc替换为typedef struct elt e = a[pos];。 - gbulmer

我省略了elt_assign函数，因为问题中已经有大量代码，但它只是e->p.x = temp->p.x等。谢谢gbulmer，我会尝试这两种方法。我相当有信心，在10≤x≤16的范围内运行2^x个插入操作会导致指数级减速。在16时，速度非常慢。我并不是说每个alloc分配的内存都超出了合理范围，而是如果我将8000个Elts插入堆中，valgrind将报告我分配了800万字节的内存，超过了50万次分配（全部释放，但仍然太多）。另外，在您的最后一个建议中，为什么要有typedef呢？ - jclancy

@jclancy - 抱歉，我复制+粘贴错误了; typedef struct elt e = a[pos]; 应该是 struct elt e = a[pos];。在 floatDown 中将 Elt x = malloc... 更改为 struct elt e = a[pos]; 可能会显著减少 malloc 和 free 的空间量；如果 floatdown 被调用 (N.log N) 次，那么这是相当多的 malloc+free 调用。 - gbulmer

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gbulmer · Accepted Answer

这是我的工作理论。我愿意发现自己的错误，但没有其余的代码，我无法对其进行仪器测试。

当typedef struct elt {...} *Elt;时，... struct heap { ... Elt *elts; } ...的间接性通过复制1个指针而不是4个整数来节省成本，但复制速度很快，并且仅发生log2(N)次。

相反，每个struct elt都是单独分配的malloc。如果不深入挖掘找到malloc块的实际大小，我们可以估计平均浪费N/2 sizeof(struct elt)（实际上，我认为在我的机器上更糟糕）。

它还可能创建不连续的内存块（通过在大块之间放置小块），因此realloc必须始终分配更大的块，因此很难重用以前的块。在这种特定情况下，我认为这并不像由于内部碎片而造成的浪费或大量调用malloc那样重要。

它也可能创建“高速缓存破坏者”。实际值被分散在整个内存中，由于malloc'd struct elt块的内部碎片，缓存行相对稀疏。

所以替换为：

typedef struct elt {
    int priority;
    int distance;
    struct position p;
} *Elt;

typedef struct heap {
    int size;
    int capacity;
    Elt *elts;
} *Heap;

使用

typedef struct elt {
    int priority;
    int distance;
    struct position p;
} Elt;    // no longer a pointer

typedef struct heap {
    int size;
    int capacity;
    Elt *elts;
} *Heap;

并进行更改：

void heap_insert(Heap h, Elt e, int *counter) {
    if(h->capacity < (h->size + 2)) {
        h->elts = realloc(h->elts, h->capacity * sizeof(Elt) * 2);
        h->capacity *= 2;
    }
    h->elts[h->size] = malloc(sizeof(*Elt));
    elt_assign(h->elts[h->size], e);
    h->size++;
    heapify(h->size, h->elts);
    *counter = *counter + 1;
}

为了

void heap_insert(Heap h, Elt e, int *counter) {
    if(h->capacity < (h->size + 2)) {
        h->elts = realloc(h->elts, h->capacity * sizeof(Elt) * 2);
        h->capacity *= 2;
    }
    h->elts[h->size] = e;  // no longer need to malloc
    h->size++;
    heapify(h->size, h->elts);
    *counter = *counter + 1;
}

所以为了存储堆而malloc/realloc的内存量应该大约是2 * N * sizeof(struct elt)。函数/宏elt_assign可能需要更改来隐藏其他更改。

然后通过更改以下内容进一步减少malloc的数量：

static void floatDown(int n, Elt *a, int pos) {
    Elt x = malloc(sizeof(struct elt));
    elt_assign(x, a[pos]);
...
    elt_assign(a[pos], x);
    free(x);
}

to

static void floatDown(int n, Elt *a, int pos) {
    Elt x = a[pos];
...
    a[pos] = x;
}

这应该进一步减少了malloc和free的内存量。

基本上，realloc只需要（大约）log2（N）次调用。realloc也可能更有可能仅扩展现有块而不是复制。

编辑：

heap_insert中存在比内存分配更大的问题：

void heap_insert(Heap h, Elt e, int *counter) {
    ...
    heapify(h->size, h->elts);
    ...
}

heapify会在每次向堆中插入元素时被调用，也就是说，heapify会被调用N次。它的作用是:

static void heapify(int n, Elt *a) {
    for(int i = n - 1; i >= 0; i--) {
        floatDown(n, a, i);
    }
}

该代码对于已经插入的每个元素都在堆上调用了floatdown，因此heap_insert的运行时间大约为(N^2)/2 (即O(N^2))。

我认为heap_insert应该对添加到堆中的每个元素使用floatDown，而不是heapify。