Why are variable length arrays in C++ overlapping on some sizes?

Question

After providing an answer to a question here, I was testing this code that I edited and noticed some strange behavior:

#include <iostream>
#define MAX 100
using namespace std;

int main()
{
    int size = 0;
    int array[MAX];
    int i, j;
    int input;

    cout << "Array: ";
    for(i = 0; i < MAX; i++)
    {
        cin >> input;

        if(input == -1)
            break;
        else
        {
            array[i] = input;
            size++;
        }
    }

    cout << "Size: " << size << "\n\n";


    int left[size / 2];
    int right[size / 2];

    for(i = 0; i < size / 2; i++)
        left[i] = array[i];
    for(i = size / 2, j = 0; i < size; i++, j++)
        right[j] = array[i];

    cout << "Left: ";
    for(i = 0; i < size / 2; i++)
        cout << left[i] << ' ';
    cout << '\n';

    cout << "Right: ";
    for(i = 0; i < size - size / 2; i++)
        cout << right[i] << ' ';
    cout << '\n';

    return 0;
}

This code is supposed to split the array into two separate arrays. Somehow the output is wrong when these are the input:

1 2 3 4 5 6 7 8 9 -1

Left: 9  2  3  4
Right: 5  6  7  8  9

After debugging If the elements of left were printed like this:

for(i = size / 2, j = 0; i < size; i++, j++)
{
    right[j] = array[i];
    cout << left[0] << ' ';
}
cout << '\n';

It says that the value of left[0] is modified after the 5th iteration:

1 1 1 1 9
Left: 9 2 3 4
Right: 5 6 7 8 9

This only happens when the array size is 9. I haven't tested beyond 16 yet. I could fix the code so that it would have the correct size

int right[size - size / 2];

or use malloc() to adhere to the C++ Standard,

int *left = (int *) malloc(sizeof(*left) * n / 2);
int *right = (int *) malloc(sizeof(*left) * n / 2);

so that left wouldn't be affected, but that's not what I'm asking. Why does it only happen when splitting an array size of 9? Why was left[0] overwritten? Is this is a bug in g++ that should be reported or is the problem something else?

Answer 1

It says that the value of left[0] is modified after the 5th iteration:

That is your answer. The problem occurs in the fifth iteration over an array with four elements.

When size is odd, the calculation of size/2 rounds down. So the sum size/2 + size/2 is strictly less than size, yet your loops ensure that all size elements from the original array are assigned somewhere. Something has to be assigned to an unexpected location. We call this "undefined behavior", and whatever the compiler does at that point is correct according to the C++ standard. (Whatever happens, the compiler gets to blame your code for it.) It just happens that when size is 9, the compiler used left[0] as the location for right[4].

Behind the scenes, the left and right arrays are probably more-or-less adjacent in memory. The layout would have right[0] through right[size/2], then possibly some unused space (also known as "padding"), then left[0] through left[size/2]. When you access one-past the last element of right, you end up either in the unused space or in left[0]. When you overwrite the unused space, you see no symptoms since that space is otherwise unused. However, when you overwrite left[0] you definitely see a symptom.

Your compiler apparently uses padding to make sure the arrays are aligned to 4*sizeof(int). (Must be faster that way, as compilers rarely introduce waste without a reason. Still, I am surprised it's not 2*sizeof(int) instead.) That is, there is no padding when size/2 is a multiple of 4. If this guesswork is accurate, you should see this behavior when size is odd and size/2 is a multiple of 4; that is when size is one more than a multiple of 8, as in 9, 17, 25, 33, etc.