TopCoderのスタックサイズの増やし方

TopCoder

なるほど……。試してみよう。

#include <string>
#include <vector>
#include <utility>
#include <set>
#include <cstdlib>
using namespace std;

set<pair<int,int> > S;

void f1(int a, int b, int x, int y)
{
    if (a==0 || b==0)
    {
        S.insert(make_pair(x,y));
        return;
    }

    S.insert(make_pair(a,b));
    if (a<b)
        f1(a, b-a, x, y);
    else
        f1(a-b, b, x, y);
}

int f2(int c, int d)
{
    if (c==0 || d==0)
        return -1;

    if (S.count(make_pair(c,d)) > 0)
        return c+d;

    return c<d ? f2(c, d-c) : f2(c-d, d);
}

class PairGame{public:
int maxSum( int a, int b, int c, int d )
{
    f1(a, b, 1234567, 1234567);
    return f2(c, d);
}};

このプログラムは、TopCoder SRM 620 Div1 Easy PairGameを再帰で書いたもの。f1の引数のx,yを消せば通るけど、引数が増えるとスタックの消費量も増えてスタックオーバーフローで落ちる。単に引数を追加するだけだと最適化で消えてしまったので、最後に意味もなくSに追加している。

int a, b, c, d, r;
long long esp_org, esp_new;

class PairGame{public:
int maxSum( int a, int b, int c, int d )
{
    //  新しいスタック領域を確保する
    const int size = 128*1024*1024;
    void *p = malloc(size);
    esp_new = (long long)p + size - 1;

    //  スタック上の変数を待避
    ::a = a, ::b = b, ::c = c, ::d = d;

    //  スタックを置き換える
    __asm__("mov %rsp, esp_org");
    __asm__("mov esp_new, %rsp");
    
    //  メインの処理
    f1(::a, ::b, 1234567, 1234567);
    r = f2(::c, ::d);

    //  スタックを元に戻す
    __asm__("mov esp_org, %rsp");

    return r;
}};

このように書き換えたら通った。簡単(･∀･)　次のところでハマった。

  • 64ビットなので、espではなくrspを使い、C++側の変数も64ビットにする必要がある
  • rspは確保した領域の先頭ではなく、末尾を指すようにする必要がある（スタックは上位から下位に使っていくので）

再帰が深くなりすぎる場合、再帰を使わないように書いていたけれど、ここまで簡単にできるならばスタックサイズを増やすのはありかもしれない。