malloc 内存分配的替代方案作为堆栈

Question

我正在寻找 malloc 的 c 替代方案，它只会用作堆栈。更像是 alloca 但不受堆栈大小限制 space 。它用于编写数学算法。

我将使用大量内存（算法中间可能使用数百兆字节）
内存以类似堆栈的顺序访问。我的意思是下一个要释放的内存总是最近分配的内存。
希望能够运行各种系统（Windows 和类 Unix）
~~作为额外的，~~可以与线程一起使用的东西，其中类似堆栈的分配和释放顺序仅适用于单个线程。（即理想情况下每个线程都有自己的 "pool" 用于内存分配）

我的问题是，是否有类似的东西，或者这是否易于实施？

Answer 1

我在旧的 FORTRAN 程序中看到了一种策略，它可能正是您正在寻找的。该策略涉及使用从 main.

向下传递到每个函数的全局数组

char global_buffer[SOME_LARGE_SIZE];

void foo1(char* buffer, ...);
void foo2(char* buffer, ...);
void foo3(char* buffer, ...);

int main()
{
   foo1(global_buffer, ....);
}

void foo1(char* buffer, ...)
{
   // This function needs to use SIZE1 characters of buffer.
   // It can let the functions that it calls use buffer+SIZE1

   foo2(buffer+SIZE1, ...);

   // When foo2 returns, everything from buffer+SIZE1 is assumed
   // to be free for re-use.
}

void foo2(char* buffer, ...)
{
   // This function needs to use SIZE2 characters of buffer.
   // It can let the functions that it calls use buffer+SIZE2

   foo3(buffer+SIZE2, ...);
}

void foo3(char* buffer, ...)
{
   // This function needs to use SIZE3 characters of buffer.
   // It can let the functions that it calls use buffer+SIZE3

   bar1(buffer+SIZE3, ...);
}

Answer 2

正如您已经发现的那样，只要它与 malloc 一起工作，您就应该使用它，并且只有在需要发挥最后一点性能时才回来。

一个适合这种情况的想法：您可以使用一个块列表，在需要时分配。使用列表可以在您达到虚拟内存限制时最终换出数据。

struct block {
  size_t size;
  void * memory;
  struct block * next;
};
struct stacklike {
  struct block * top;
  void * last_alloc;
};
void * allocate (struct stacklike * a, size_t s) {
  // add null check for top
  if (a->top->size - (a->next_alloc - a->top->memory) < s + sizeof(size_t)) {
    // not enough memory left in top block, allocate new one
    struct block * nb = malloc(sizeof(*nb));
    nb->next = a->top;
    a->top = nb;
    nb->memory = malloc(/* some size large enough to hold multiple data entities */);
    // also set nb size to that size
    a->next_alloc = nb->memory;
  }
  void * place = a->next_alloc;
  a->next_alloc += s;
  *((size_t *) a->next_alloc) = s; // store size to be able to free
  a->next_alloc += sizeof (size_t);
  return place;
}

我希望这能说明总体思路，对于实际实施，还有很多需要考虑的地方。

要换出内容，请将其更改为双向链表并跟踪分配的总字节数。如果达到限制，请将结尾写入某个文件。

Answer 3

这听起来像是 Obstack 的完美用法。

我自己从来没有用过它，因为 API 真的很混乱，我现在找不到例子。但是它支持你想要的所有操作，另外还支持流式创建"current"对象。

编辑：举了一个简单的例子。 Obstack API 显示出岁月痕迹，但原则至少是合理的。

您可能需要研究调整 align/block 设置，如果您喜欢种植，可能会使用 obstack_next_free 和 obstack_object_size。

#include <obstack.h>
#include <stdio.h>
#include <stdlib.h>

void *xmalloc(size_t size)
{
    void *rv = malloc(size);
    if (rv == NULL)
        abort();
    return rv;
}

#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free

const char *cat(struct obstack *obstack_ptr, const char *dir, const char *file)
{
    obstack_grow(obstack_ptr, dir, strlen(dir));
    obstack_1grow(obstack_ptr, '/');
    obstack_grow0(obstack_ptr, file, strlen(file));
    return obstack_finish(obstack_ptr);
}

int main()
{
    struct obstack main_stack;
    obstack_init(&main_stack);
    const char *cat1 = cat(&main_stack, "dir1", "file1");
    const char *cat2 = cat(&main_stack, "dir1", "file2");
    const char *cat3 = cat(&main_stack, "dir2", "file3");
    puts(cat1);
    puts(cat2);
    puts(cat3);
    obstack_free(&main_stack, cat2);
    // cat2 and cat3 both freed, cat1 still valid
}

malloc 内存分配的替代方案作为堆栈

malloc alternative for memory allocation as a stack

c

memory

malloc

multithreading

dynamic-memory-allocation