c++ - 用户定义的堆栈和内置堆栈在内存使用方面有什么区别？

Question

我想为具有大量递归调用的程序使用用户定义的堆栈？定义用户定义的堆栈是否有用？

Answer 1

有几种方法可以做到这一点。

主要是两个:

(1) 使用CPU/处理器堆栈。有一些变体，每个都有自己的局限性。

(2) 或者，重新编码您的函数以使用模拟“堆栈”的“堆栈框架”结构。实际函数不再是递归的。这实际上可以是无限的，直到堆允许的范围内

---

对于 (1) ...

(A) 如果您的系统允许，您可以发出 系统调用 来扩展进程的堆栈大小。您可以执行此操作的数量可能会受到限制，并且会与共享库地址发生冲突。

(B) 您可以malloc 大面积。使用一些[有些] 复杂的内联 asm 技巧，您可以将此区域交换为堆栈 [并再次返回] 并使用此 malloc 区域作为堆栈调用您的函数。可行，但不适合胆小的人......

(C) 一个更简单的方法是malloc 一个大的区域。将此区域传递给 pthread_attr_setstack。然后，使用 pthread_create 将递归函数作为线程运行。请注意，您并不真正关心多线程，这只是避免“困惑”的 asm 欺骗的一种简单方法。

对于 (A)，假设堆栈扩展系统调用允许，限制可以是堆栈允许的所有可用内存[达到某些系统范围或 RLIMIT_* 参数]。

对于 (B) 和 (C)，您必须在开始之前“猜测”并使 malloc 足够大。完成后，大小固定，不能进一步扩展。

事实上，这并不完全正确。 [需要时] 重复使用 asm 技巧，您可以模拟接近无限的堆栈。但是，IMO，跟踪这些大型 malloc 区域的开销足够高，我会选择下面的 (2)。

---

对于 (2) ...

这可以根据需要实际扩展/收缩。优点之一是您无需事先猜测需要多少内存。 [伪] 堆栈可以根据需要不断增长 [直到 malloc 返回 NULL :-)]。

这是一个示例递归函数[粗略地视为伪代码]:

int
myfunc(int a,int b,int c,int d)
{
    int ret;

    // do some stuff ...

    if (must_recurse)
        ret = myfunc(a + 5,b + 7,c - 6,d + 8);
    else
        ret = 0;

    return ret;
}

这里是函数更改为使用 struct 作为堆栈框架 [再次，松散的伪代码]:

typedef struct stack_frame frame_t;
struct stack_frame {
    frame_t *prev;
    int a;
    int b;
    int c;
    int d;
};

stack_t *free_pool;
#define GROWCOUNT   1000

frame_t *
frame_push(frame_t *prev)
{
    frame_t *cur;

    // NOTE: we can maintain a free pool ...
    while (1) {
        cur = free_pool;

        if (cur != NULL) {
            free_pool = cur->prev;
            break;
        }

        // refill free pool from heap ...
        free_pool = calloc(GROWCOUNT,sizeof(stack_t));
        if (free_pool == NULL) {
            printf("frame_push: no memory\n");
            exit(1);
        }

        cur = free_pool;
        for (int count = GROWCOUNT;  count > 0;  --count, ++cur)
            cur->prev = cur + 1;
        cur->prev = NULL;
    }

    if (prev != NULL) {
        *cur = *prev;
        cur->prev = prev;

        cur->a += 5;
        cur->b += 7;
        cur->c += 6;
        cur->d += 8;
    }
    else
        memset(cur,0,sizeof(frame_t));

    return cur;
}

frame_t *
frame_pop(frame_t *cur)
{
    frame_t *prev;

    prev = cur->prev;

    cur->prev = free_pool;
    free_pool = cur;

    return prev;
}

int
myfunc(void)
{
    int ret;
    stack_t *cur;

    cur = frame_push(NULL);

    // set initial conditions in cur...

    while (1) {
        // do stuff ...

        if (must_recurse) {
            cur = frame_push(cur);
            must_recurse = 0;
            continue;
        }

        // pop stack
        cur = frame_pop(cur);
        if (cur == NULL)
            break;
    }

    return ret;
}