Compiling C++ code makes the system hang

Question

When I try to compile this file by issuing the command, "g++ qr.cpp -o qr" The system hangs. I haven't seen this kind of an error anywhere else.

#include<iostream>

using namespace std;

bool win[1000000001];
bool know[1000000001];

int sixes[] = {6, 36, 216, 1296, 7776, 46656, 279936, 1679616, 10077696, 60466176, 362797056};

bool check(int n){
   cout << n << endl;
   if(!know[n]){
      bool b = check(n-1);
      for(int i=0; i<11; i++){
         if(n > sixes[i]){
            b = b & check(n-sixes[i]);
         }
      }
      win[n] = !b;
   }
   return win[n];
}

int main(){
   win[1] = know[1] = true;
   for(int j=0; j<11; j++){
      win[sixes[j]] = know[sixes[j]] = true;
   }
   int n = 1; 
   cin >> n;
   int i = 0;
   while(n != 0){
      i++;
      win[n] = check(n);
      cout << i << (win[n]?"-Heckle":"-Jeckle");
      cin >> n;
      if(n!=0) cout << endl;
   }
   return 0;
}

My compiler version information is given below.

yasith@vostro:~/Dropbox/Shared$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.6.1/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.6.1-9ubuntu3' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++,go --prefix=/usr --program-suffix=-4.6 --enable-shared --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-plugin --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.6.1 (Ubuntu/Linaro 4.6.1-9ubuntu3) 

Answer 1

Do you realize how big these are?

bool win[1000000001];
bool know[1000000001];

Those are at least 1GB each!!! You're gonna want to allocate them dynamically...

Answer 2

It compiles fine with g++ 4.6.1 on my Debian system, which only has 1GB of memory.

I tried looking at the memory used by the various passes of the compiler and the linker when changing the size of the arrays, and the memory use didn't change much, indicating the compiler wasn't trying to allocate any data-structures proportional to the array size.

However, I have the new GNU linker "gold" installed.

I then tried it again, using the older ("BFD-based") GNU linker, which is still the default on many systems, for the link step—and then my system started thrashing like crazy (I had to kill the linker process)!

So it seems that the new gold linker is smarter about big arrays than the older linker.

On Debian, gold can be installed as the system linker by just installing the "binutils-gold" package. [I don't know if Ubuntu has the same package, but as Ubuntu is based on Debian, it seems likely.]