今天考试考了一道需要递归$10^5$层的题目。。。

然后我就发现我爆栈了

然后我就手写模拟栈递归浪费了很多时间

虽然其实评测的时候带了编译开栈命令,但是那个命令是Windows底下的,所以我Ubuntu就没辙了。

然后去网上搜手动开栈,但都是很久以前的代码,目前的G++编译器已经不能编译了QvQ

最后找到一段报错还算比较少的代码,改了改就能用了。

Windows10 64位版本和Ubuntu 16.04 LTS 64位版本下编译测试通过。

G++版本:

g++ --version
g++ (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

首先我们上一段会爆栈的代码

#include <bits/stdc++.h>

using namespace std;

void main2()
{
    int arr[10000000];
    puts("QvQ"), exit(0);
}

int main(int argc, char const* argv[])
{
    main2();
    return 0;
}

很显然不会输出”QvQ”这三个字,而会直接爆栈Segment Fault,因为在函数main2()内开了个38MB的数组,而Ubuntu下栈空间默认是8MB。

我们再上一段扩栈后的代码

#include <bits/stdc++.h>

using namespace std;

extern void main2(void) __asm__ ("main2"); 

void main2()
{
    int arr[10000000];
    puts("QvQ"), exit(0);
}

int main(int argc, char const* argv[])
{
    int size = 128 << 20; // 128 MB
    char* p = new char[size] + size;
    __asm__ __volatile__(  
        "movq %0, %%rsp\n"
        "pushq $exit\n"
        "jmp main2\n"
        :: "r"(p));
    main2();
    return 0;
}

于是我们就愉♂快地发现它没有爆栈,而是输出了可爱的“QvQ”

这是因为我们先申请了128MB的内存,并用指针p表示这段内存。

然后我们把main2()所申请的栈空间放在了p里面

实际上如果在main2()里调用函数,比如这样:

#include <bits/stdc++.h>

using namespace std;

extern void main2(void) __asm__ ("main2"); 

void boom()
{
    int arr[10000000];
}

void main2()
{
    boom();
    puts("QvQ"), exit(0);
}

int main(int argc, char const* argv[])
{
    int size = 128 << 20; // 128 MB
    char* p = new char[size] + size;
    __asm__ __volatile__(  
        "movq %0, %%rsp\n"
        "pushq $exit\n"
        "jmp main2\n"
        :: "r"(p));
    main2();
    return 0;
}

是依然能输出可爱的”QvQ”的!

因为boom()函数也是在main2()内调用的!

所以栈空间也会存到p内

这就意味着我们可以用这个扩栈来防止递归爆栈。。。

真是有趣QvQ

不过好像BZOJ上会CE,估计是它的编译器实在是版本太老了

别的OJ没试过QvQ

另外32位机也没试过,要是有同学试了32位机的请在底下留言告诉我情况吧哈哈= ̄ω ̄=

Update

有同学反馈代码在32位机上运行正常

(^-^)V

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

8 条评论

foreverpiano · 2018年3月2日 11:48 下午

#pragma comment(linker, "/STACK:102400000,102400000")

如果可以开编译选项的话这样也可以的吧

    konnyakuxzy · 2018年3月3日 8:34 上午

    Ubuntu 16.04 LTS 64位下测试您那个命令并没有用
    并不知道为什么

juruo-oier · 2018年3月2日 8:01 下午

大佬 32位可以

Cai · 2018年3月2日 7:42 下午

为什么不直接修改Lemon的代码文件?

为什么不直接修改Ubuntu里面关于ulimit(limit)的配置文件?

    konnyakuxzy · 2018年3月2日 8:56 下午

    OrzCai
    很显然这样的话可以强行开栈啊
    就算评测的人没开我们也不怕是不是
    至于修改ulimit…
    这样我觉得不是很好吧。。。
    比如会不会出现出题人故意让您爆栈呢?

      Cai · 2018年3月2日 9:12 下午

      然而您内嵌汇编可是直接GG啊

      (好像CC并不查这东西

        konnyakuxzy · 2018年3月2日 9:41 下午

        Orz
        也许吧
        我太弱了不清楚
        其实一般不需要手动开栈的

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *