Sorting large array of pairs

Question

I need an algorithm which sorts an array of pairs according to the first element of each pair. The following code works fine for v_size<~2^19, however, at sizes of close to 2^19 it crashes due to a segmentation fault. What is the reason? A size of ~524000 is not huge. (I'm using gcc (Debian 4.7.2-5) 4.7.2)

#include <iostream>
#include <algorithm>
#include <iterator>
#include <time.h>

using namespace std;


int main( int argc, char ** argv )
{
    srand(time(NULL));

    int v_size=524000;
    std::pair<double, int> AB_large[v_size];

    for( int i = 0; i<v_size; ++i)
    {
      AB_large[i].first  = static_cast <double> (rand()) / static_cast <double> (RAND_MAX);
      AB_large[i].second = i;
    }

    std::sort(AB_large, AB_large+v_size);
    return 0;
}

Answer 1

It looks like a stack overflow.

Try not to use automatic variables for such large objects:

std::vector< std::pair<double, int> >AB_large(v_size);

// ...

std::sort(AB_large.begin(), AB_large.end());

Answer 2

Your array is a local variable, so it is created on the stack. There is usually a limit on stack size. On Linux, it can usually be viewed and modified by ulimit command. (On Windows, a stack limit for a C++ executable is determined at compile time, and it can be altered by compiler options or pragmas.)

One instance of your pair is 8+4=12 bytes in size. The default stack limit is usually 8 mebibytes. Perhaps 12 bytes are padded to 16 bytes due to alignment settings of your compiler. So, 2¹⁹ * 16 = 2²³ bytes, which is the very same 8 mebibytes.