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;
}

It's not huge compared to the amount of address space. But compared to the amount of *stack* space... — Jon, May 06 '14 at 13:27
You do know that it will be at least 6288000 bytes? Well over 5 gigabytes of memory. That's probably more than you have for stack space. — Some programmer dude, May 06 '14 at 13:28
@JohnDibling: You mean when there are two elements with the same value? — pawel_winzig, May 06 '14 at 13:45
BTW, I would use a map instead of an array you have to sort. — John Dibling, May 06 '14 at 13:50
@JohnDibling: Degeneracies in the first argument do not matter (for me here) as long as the int index is unique. What would be the benefit of map in this case? — pawel_winzig, May 06 '14 at 14:02
@pawel_winzig: A map is a natural fit for what you're trying to do. It also doesn't reallocate when you push on to it and it is automatically sorted on insertion. Honestly, I don't see why you would use a `vector` here. — John Dibling, May 06 '14 at 14:07
@JohnDibling: It wouldn't be a problem that I sort a list of elements which are not unique? Could you post your suggestion? — pawel_winzig, May 06 '14 at 14:13
More like megabytes. Actually not a lot, but apparently still more than the stack size — Niklas B., May 06 '14 at 16:18

score 3 · Accepted Answer · answered May 06 '14 at 13:28

3

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());

answered May 06 '14 at 13:28

rodrigo

94,151
12
143
190

score 3 · Answer 2 · edited May 23 '17 at 11:58

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.

Sorting large array of pairs

2 Answers2