5

i have a quite weird question which probably has no practical use but the answers bothers me a lot. I tried to mess around today a little bit with arrays and how they are allocated in memory using this code: (Compiler Xcode 4 btw, 4 byte integer)

int ***c;
int size_x = 0;
int size_y = 0;
int size_z = 0;

cout << "Enter x: " << endl;
cin >> size_x;
cout << "Enter y: " << endl;
cin >> size_y;
cout << "Enter z: " << endl;
cin >> size_z;

c = new int**[size_x];
for (int i = 0; i < size_x; ++i) {
    *(c+i) = new int*[size_y];
    for (int j = 0; j < size_y; ++j) {
        *(*(c+i)+j) = new int[size_z];
    }
}

for (int i = 0; i < size_x; ++i) {
    for (int j = 0; j < size_y; ++j) {
        for (int k = 0; k < size_z; ++k) {
            cout << (*(*(c+i)+j)+k) << endl;
            //cout << &c[i][j][k] << endl;
        }
    }
}

delete [] c;

When i enter now: 3, 2 and 4 i get the following output in the console:

0x100100a60 0x100100a64 0x100100a68 0x100100a6c 0x100100a70 0x100100a74 0x100100a78 0x100100a7c 0x100100a90 0x100100a94 0x100100a98 0x100100a9c 0x100100aa0 0x100100aa4 0x100100aa8 0x100100aac 0x100100ac0 0x100100ac4 0x100100ac8 0x100100acc 0x100100ad0 0x100100ad4 0x100100ad8 0x100100adc

What my question is now, if we look at the output, than we see that mostly, the memory is aligned every 4 bytes but sometimes we see a bigger step like from 0x100100a7c to 0x100100a90 .

Is this normal and how can i prevent this? Why is this? Is there a possibility to force c to align my memory as a constant line? (I'm not native english so sorry for that but i don't know how to say it better)

Its just for general understanding :-)

Thank u!

P.S. is it enough to use delete [] once btw or do i have to go through each of the 3 memory blocks and delete [] there the whole array? EDIT:

I delete memory now like this and it works pretty good:

cout << "Free Memory" << endl;

for (int i = 0; i < m_sx; ++i) {
    for (int j = 0; j < m_sy; ++j) {
        delete [] m_array[i][j];
        //delete [] (*(*(m_array)+j)+k);
    }
    delete [] m_array[i];
}

delete [] m_array, m_array = NULL;
Improve this question
4
  • 2
    I added a C++ tag. Should I also remove the C tag, or do you really want to have a C answer, too? Mondern C and C++ are quite different on how you can implement multidimensionnal arrays. Commented Nov 6, 2011 at 15:28
  • This has a practical use actually, by removing indirection and helping cache. Commented Nov 6, 2011 at 15:29
  • By the way, instead of using new[] and delete[] to allocate an array you would be better off directly using a vector ;) Commented Nov 6, 2011 at 15:31
  • Every new[] needs a delete[]. Commented Nov 6, 2011 at 15:33

5 Answers 5

Reset to default
7

Yes, this is normal. The memory is aligned, btw., it's just not contiguous because subsequent calls to new do not make this guarantee. And yes, you can allocate the entire 3-d array in a single, contiguous buffer:

int *A = new int[size_x * size_y * size_z];

or, safer

std::vector<int> A(size_x * size_y * size_z);

and then index it with

int element = A[i * size_z * size_y + j * size_z + k]

to get the element at (i,j,k).

This is, in fact, very useful, as it gives you multidimensional arrays with little overhead, preserving locality of reference and preventing indirection. Also, the error handling for this allocation scheme is much simpler so you run less of a risk of memory leaks. Any good matrix library will be implemented this way. For C++, that includes Boost.MultiArray.

As for deallocation: yes, you need multiple calls to delete[] in your present scheme.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

is the first one also faster? i can image because the system doesn't have to jump around so much right?
@MarkusPfundstein: for many operations, yes. That's what I mean by locality of reference.
4

Heres a routine which allocates the 3D array of dimension N1 x N2 x N3 in contiguous memory space while allowing you the a[i][j][k] syntax for operator access. The array is dynamic but continuous so it's a huge plus over the vector<> approach and loops of new[] calls.

template <class T> T ***Create3D(int N1, int N2, int N3)
{
    T *** array = new T ** [N1];

    array[0] = new T * [N1*N2];

    array[0][0] = new T [N1*N2*N3];

    int i,j,k;

    for( i = 0; i < N1; i++) {

        if (i < N1 -1 ) {

            array[0][(i+1)*N2] = &(array[0][0][(i+1)*N3*N2]);

            array[i+1] = &(array[0][(i+1)*N2]);

        }

        for( j = 0; j < N2; j++) {     
            if (j > 0) array[i][j] = array[i][j-1] + N3;
        }

    }

    cout << endl;
    return array;
};

template <class T> void Delete3D(T ***array) {
    delete[] array[0][0]; 
    delete[] array[0];
    delete[] array;
};

And later in your implementation routine...

int *** array3d;
int N1=4, N2=3, N3=2;

int elementNumber = 0;

array3d = Create3D<int>(N1,N2,N3);

cout << "{" << endl;
for (i=0; i<N1; i++) {
    cout << "{";
    for (j=0; j<N2; j++) {
        cout << "{";
        for (k=0; k<N3; k++) {
            array3d[i][j][k] = elementNumber++;
            cout << setw(4) << array3d[i][j][k] << " ";
        }
        cout << "}";
    }
    cout << "}";
    cout << endl ;
}
cout << "}" << endl;

Delete3D(array3d);

Gives the output:

{
{{   0    1 }{   2    3 }{   4    5 }}
{{   6    7 }{   8    9 }{  10   11 }}
{{  12   13 }{  14   15 }{  16   17 }}
{{  18   19 }{  20   21 }{  22   23 }}
}
Improve this answer

1 Comment

This is also equivalent to larsman's answer above, where the array is allocated as int * A = new int[N1*N2*N3] and accessed as val = A[i*N2*N3 + j*N3 + k]. But here bc of all the pointers-to-pointers you can use val = array3d[i][j][k]. To obtain the equivalent int * type reference to the array, one would do int * A = array3d[0][0].
3

Since this is tagged C, here is also a C answer. Since C99 multidimensional arrays can be handled quite efficiently, even if the sizes are dynamic:

double c[size_x][size_y][size_z];

This allocates the matrix contiguously on the stack. Matrix elements are accessed by c[i][j][k] and the compiler does all the indexing arithmetic for you. If you fear that this could lead to SO, you can easily call malloc with it:

double (*c)[size_y][size_z] = malloc(sizeof(double[size_x][size_y][size_z]));
Improve this answer

Comments

2

The issue is not that your memory isn't aligned ... the requirement by the C++ specification for a call to new and new[] is that it passes back a pointer pointing to contiguous memory that is properly aligned for the platform and the size of the object requested.

Your problem is that you are not allocating the entire buffer for the array with a single call to new[], but rather with multiple calls to new[]. Therefore while each call to new will return aligned and contiguous memory, the multiple calls to new[] are not required to return memory buffers that themselves are contiguously allocated. For example, each call to new[] returns aligned memory, but as you noted, there can be "gaps" in the start of each memory array that new returns. The reason for these "gaps" can have multiple reasons, and really depends on how the underlying OS is allocating memory for your program.

If you do not want to have any "gaps" in each array, then you will need to allocate the entire buffer with a single call to new.

Finally, to answer your question about delete[], yes, because you did not allocate the entire memory buffer with a single call to new[], you cannot delete your array with a single call to delete[]. Every call to new[] must be paired with a call to delete[] since those were separate memory allocations.

Improve this answer

2 Comments

thanks a lot for your answer. Makes a lot of sense and clears things out for me.. I wrote now above how I delete the memory.It seems to work fine. When i allocate memory right after it the same space gets used.
BTW, don't do delete [] m_array, m_array = NULL; in your last line ... the comma does not create a "sequence point" per the C++ spec, therefore depending on how the compiler decides to order the operations, you could end up with a huge memory leak as the compiler decides to reverse the operations and assign NULL to m_array and then call delete [] on the now NULL pointer. You will want to make those two separate statements by separating them with a semi-colon.
1

Yes this is normal. You allocate data row by row; The only thing you can be sure is that data will be contiguous on each row.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.