メモリを使用しているユーザ定義スタックと組み込みスタックの違いは何ですか？

Question

再帰呼び出しの数が多い私のプログラムにユーザー定義のスタックを使用したいですか？ユーザー定義のスタックを定義すると便利でしょうか？

Answer 1

すべての関数、オブジェクト、変数、およびユーザー定義の構造体は、OSとコンパイラによって制御されるメモリ空間を使用します。つまり、定義されたスタックは、OSのプロセススタックに指定されている一般的なメモリ空間で動作します。その結果、大きな違いはありませんが、効率の良い最適化された構造を定義して、この一般的なスタックをはるかに優れたものにすることができます。

Answer 2

これを行うにはいくつかの方法があります。主

、：

（1）CPU /プロセッサスタックを使用。いくつかのバリアントがあり、それぞれに独自の制限があります。

（2）または、スタックをシミュレートする「スタックフレーム」構造体を使用するように関数をコード化します。実際の関数は再帰的でなくなります。これは、ヒープは、あなたのシステムが許すならば、あなたは、プロセスのスタックサイズを拡張するためにsyscallを発行することができます（1）...

（A）については

---

を可能にするものは何でもまで実質的に無限することができます。どれくらいのことができるか、共有ライブラリのアドレスとの衝突には限界があります。

（B）malloc大きな領域です。いくらか複雑なインラインasmトリッキーでは、この領域をスタックのために入れ替えて（そしてもう一度）、このmalloc領域をスタックとして呼び出すことができます。喜んではいますが、心のかすかではありません。

（C）簡単な方法は、mallocです。この領域をpthread_attr_setstackに渡します。次に、再帰関数をpthread_createを使ってスレッドとして実行します。注意してください。実際には複数のスレッドを気にする必要はありませんが、それは「面倒な」asmトリッキーを避けるための簡単な方法です。

（A）、とし、とすると、スタックの拡張が許可されているため、システム全体またはRLIMIT_ *パラメータまでスタックに使用可能なすべてのメモリを使用できます。

（B）と（C）を使用すると、開始する前に十分に大きな数字を「推測」してmallocにする必要があります。完了後、サイズは固定されており、ではなく、をさらに延長することができます。

実際、そうではありません。 asmトリッキーを使用して[必要なときに]繰り返し、無限に近いスタックをシミュレートすることができます。しかし、IMOは、これらの大きなmalloc領域を追跡するオーバーヘッドが十分に高いので、私は（2）を選択します。 （2）...

これは文字通り展開することができますについては

---

/必要に応じて契約。利点の1つは、必要なメモリ量を事前に推測する必要がないことです。 [pseudo]スタックは、[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; 
}