Segmentation Fault chkstk_ms C++

Question

I need help with this following counting sort implementation. Is it because value of x can be too big? I am getting segmentation fault. This is what gdb says:

Program received signal SIGSEGV, Segmentation fault.
___chkstk_ms () at /usr/src/debug/gcc-5.4.0- 1/libgcc/config/i386/cygwin.S:146
146     /usr/src/debug/gcc-5.4.0-1/libgcc/config/i386/cygwin.S: No such file or directory.

And here is the code snippet,

void radix_sort::sort_array(int array[], int n)
{
    int arrayB[n];

    auto k = *std::max_element(&array[0], &array[n - 1]);
    auto m = *std::min_element(&array[0], &array[n - 1]);

    long int x = k - m + 1;
    int arrayC[x];

    for (auto i = 0; i < n; i++)
        arrayC[array[i] - m]++;

    for (long int i = 1; i < x; i++)
        arrayC[i] = arrayC[i] + arrayC[i - 1];

    for (auto i = n - 1; i >= 0; i--)
    {
        arrayB[arrayC[array[i] - m] - 1] = array[i];
        arrayC[array[i] - m]--;
    }

    for (int i = 0; i < n; i++)
        array[i] = arrayB[i];
}

Sufferable

int arrayB[n]; is non-standard C++ and in the GCC 4 and 5 implementation can easily result in a stack overflow if n is sufficiently large. Probably not your problem, but worth keeping an eye on. same again for int arrayC[x];. Search keyword: "Variable Length Array" for more info. – Enhanced

The job of __chkstk_ms is to intentionally generate a segfault when the array cannot fit on the stack. So yes, n is too large. If you can't limit its value then you must use the new[] and delete[] operators instead. – Toboggan

I tried using new[] and delete[] operators. It is not segfaulting anymore. gdb now says the problem is with this line int arrayC[x]; I know x can be very big. Consider if k = 2 billion and m = -2 billion, then x = 4 billion. What should I use to make sure it works with this range? – Sufferable

Answer 1

In

arrayC[array[i] - m]++;

at this point in the code no elements of arrayC have been assigned, so an unknown number is incremented. This may blow up

arrayB[arrayC[array[i] - m] - 1] = array[i];

a few lines later because arrayC[array[i] - m] could be negative or a few billion and out of range for all we know.

Enhanced

How do you suggest to fix it? – Sufferable

My go-to would be to replace the variable length arrays with std::vector. std::vector<int> arrayC(x); would make arrayC standard-compliant and auto initialize all elements to 0. If std::vector is off the table (and variable length arrays aren't for some reason), int arrayC[n] = {0};. Otherwise std::fill or similar. – Enhanced

I am still getting the same seg fault using int arrayC[x] = {0}; I have another version with vector which does not give any output here: https://mcmap.net/q/1919393/-counting-sort-c-11 – Sufferable

Answer 2

These declarations of arrays

int arrayB[n];
int arrayC[x];

declares variable length arrays. Variables length arrays are not a standard C++ feature. Instead of declaring variable length arrays you need to allocate memory dynamically.

These calls of standard algorithms

auto k = *std::max_element(&array[0], &array[n - 1]);
auto m = *std::min_element(&array[0], &array[n - 1]);

ignore the last element of the array array. Instead you need to write

auto k = *std::max_element( array, array + n );
auto m = *std::min_element( array, array + n );

The array arrayC is not initialized.

int arrayC[x];

So this statement

arrayC[array[i] - m]++;

invokes undefined behavior.

Pay attention to that within the function you need to check that n is greater than 0.

The function can be declared and defined the following way.

void radix_sort::sort_array( int a[], size_t n )
{
    if (n)
    {
        auto minmax = std::minmax_element( a, a + n );
        auto min = *minmax.first, max = *minmax.second;

        size_t k = max - min + 1;

        auto p = std::make_unique<int[]>( k );

        for (size_t i = 0; i < n; i++)
        {
            ++p[a[i] - min];
        }

        std::partial_sum( p.get(), p.get() + k, p.get() );

        auto b = std::make_unique<int[]>( n );

        for (size_t i = n; i-- != 0; )
        {
            b[--p[a[i] - min]] = a[i];
        }

        std::copy( b.get(), b.get() + n, a );
    }
}

Phanotron