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

Question

我正在用 C 编写一个 min-heap 的实现，作为 Dijkstra 算法的一部分。我已经了解了所有细节，并且我的测试程序通过了 valgrind 测试，但它在此过程中分配了荒谬的内存量。最终测试是在 INT_MAX 的 INT_MAX 网格上(坐标只是整数)，我在测试时出现了 SIGXCPU 错误。即使我只是将 16k 位置插入队列然后删除所有内容，它仍然需要很长时间并分配超过 8 MB。当我在巨大的网格测试用例上运行它时，在我手动退出之前它可以达到 500 MB。可能发生了什么？这是我的部分代码:

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

如有任何帮助，我们将不胜感激。

Answer 1

这是我的工作理论。我愿意发现我错了，但没有其余代码，我无法检测、运行和测试它。

的间接... struct heap { ... Elt *elts; } ... 当 typedef struct elt {...} *Elt; 节省了复制 4 个整数并将其替换为复制 1 个指针的成本，但复制速度很快，而且它只发生 log2(N) 次。

相反，每个 struct elt 都是单独 malloc 的。不用四处寻找 malloc block 的实际大小，我们可以估计平均会浪费 N/2 sizeof(struct elt)(实际上，我认为在我的机器上更糟)。

它也可能创建不连续的内存块(通过将小块放在大块之间)，因此 realloc 必须总是分配一个更大的 block ，因此重用以前的 block 会更难。在这种特定情况下，我认为这与内部碎片造成的浪费或 malloc 的大量调用无关紧要。

它也可能会创建一个“缓存破坏者”。实际值分布在整个内存中，并且由于 malloc'd struct elt block 的内部碎片，缓存行相对稀疏。

所以替换:

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'd/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);
}

到

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

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

本质上，应该只有(大约)log2(N) 次 realloc 调用。 realloc 更有可能只是扩展现有 block 而不是复制。

---

编辑:

heap_insert 中有一个比内存分配更大的问题:

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

heapify 为插入堆中的每个 元素调用，即 heapify 被调用 N 次。 heapify 是:

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。